Математические методы в решении экономических задач
Х2 = 120 - Х1 - Х5
Х3 = 510 - Х1 + Х5
[Х4 = 207 - Х1 + Х5]
F = 30Х₁ +49(120 - Х1 - Х5) = 5880 + 23 Х1 - 7 Х5
При Х1 = Х5 = 0 имеем F = 5880. Это уже лучше, чем на I шаге, но не искомый максимум. Дальнейшее увеличение функции F возможно за счет введения переменной Х1 в число базисных; так как эта переменная входит в выражение F с положительным коэффициентом, поэтому ее увеличение приводит к увеличению линейной формы и ее невыгодно считать свободной, т. е. равной нулю.
Для ответа на вопрос, какую переменную вывести из базисных в свободные, примем:
Х1 = min ; = min{840; 108,2; 63} = 63,
далее Х1 переведём в базисные вместо Х4.
III шаг. Базисные переменные: Х1, Х2, Х3; свободные переменные: Х4, Х5. Выразим основные переменные и линейную форму через свободные. Из последнего уравнения системы (1.3) имеем:
Х1 = 207 + Х5 – Х4 => Х1 = 63 + Х5 - Х4
Подставляя это выражение в остальные уравнения и в линейную форму, получим:
Х1 = 63 + Х5 - Х4
Х2 = 120 - (63 + Х5 - Х4) - Х5 = 111 - Х5 - Х4
Х3 = 510 - (63 + Х5 - Х4) + Х5 = 213 - Х5 + Х4
Х1 = 63 + Х5 - Х4
Х2 = 111 - Х5 - Х4
Х3 = 213 - Х5 + Х4
F = 5880 + 23(63 + Х5 - Х4) - 7 Х5 = 7329 - 2 Х5 - 7 Х4
Так как в выражение линейной формы переменные Х4 и Х5 входят с отрицательным коэффициентами, то никакое увеличение F за счет этих переменных невозможно.
Следовательно, на III шаге критерий оптимальности достигнут и задача решена. Оптимальным служит решение (63;111;213;207;0), при котором Fmаx= 7329.
Таким образом, для получения наибольшей прибыли, равной 7329 ден. ед., из данных запасов сырья предприятие должно изготовить 63 вида изделий А1 и 111изделий вида А2.
Ответ: Х1* = 63; Х2* = 111. Fmаx= 7329.
Решить задачу табличным симплексным методом
Рассмотренный симплексный метод решения ЗЛП в предыдущем пункте можно свести к записи однотипно заполняемых таблиц. Осуществить это возможно, придерживаясь следующего алгоритма:
Привести задачу линейного программирования к каноническому виду.
Найти начальное опорное решение с базисом из единичных векторов и коэффициенты разложений векторов условий по базису опорного решения. Если опорное решение отсутствует, то задача не имеет решения в силу несовместности системы ограничений.
Вычислить оценки разложений векторов условий по базису опорного решения и заполнить симплексную таблицу.
Если выполняется признак единственности оптимального решения (для любого вектора условий, не входящего в базис, оценка отлична от нуля), то решение задачи заканчивается.
Если выполняется условие существования множества оптимальных решений (оценка хотя бы одного вектора условий, не входящего в базис, равна нулю), то путем простого перебора находят все оптимальные решения.
Если выполняются условия отсутствия оптимального решения вследствие неограниченности целевой функции (не имеет решения, если для какого-либо из векторов условий с оценкой, противоречащей признаку оптимальности, среди коэффициентов разложения по базису опорного решения нет положительного), то задача не имеет решения ввиду неограниченности целевой функции.
Если пункты 4-6 алгоритма не выполняются, находят новое опорное решение с использованием условий нахождения оптимального решения.
Составим математическую модель задачи. Искомый выпуск продукции А1 обозначим через Х1, продукции А2 – Х2. Поскольку имеются ограничения на выделенный предприятию фонд сырья каждого вида, переменные Х1, Х2 должны удовлетворять следующей системе неравенств:
5Х1+2Х2 ≤ 750
4Х1+5 Х2 ≤ 807
Х1+7Х2 ≤ 840
Х1≥0, Х2≥0
Общая стоимость произведенной предприятием продукции при условии выпуска Х1изделий А1 и Х2 изделий А2 составляет F = 30Х₁ +49Х₂
По своему экономическому содержанию переменные Х1 и Х2 могут принимать только лишь неотрицательные значения: Х1, Х2 ≥0.
Таким образом, приходим к следующей математической задаче: среди всех неотрицательных решений системы неравенств (1.1) требуется найти такое, при котором функция F = 30Х₁ +49Х₂ принимает максимальное значение.
Запишем эту задачу в форме основной задачи линейного программирования. Для этого перейдем от ограничений-неравенств к ограничениям-равенствам. Введем три дополнительные переменные, в результате чего ограничения запишутся в виде системы уравнений:
5Х1+2Х2+Х3 = 750
4Х1+5 Х2+ Х4 = 807
Х1+7Х2+Х5 = 840
Хi≥0, i=1….5
Эти дополнительные переменные по экономическому смыслу означают не используемое при данном плане производства количество сырья того или иного вида. Например, Х3 — это неиспользуемое количество сырья 1-ого вида и т.д.
Для решения задачи табличным симплексным методом прежде всего нужно найти любое базисное решение. В данном случае это легко сделать. Для этого достаточно взять в качестве базисных добавочные переменные Х3, Х4, Х5.,а в качестве свободных переменные Х1 и Х2 равными нулю, получим базисное решение (0; 0; 750; 807; 840), которое к тому же оказалось допустимым. F = 30Х₁ +49Х₂ => F - 30Х₁ - 49Х₂ = 0
Переходим к поискам оптимального решения.
Составим симплексную таблицу:
Как видно из таблицы (2.1), значения всех переменных отвечают такому «плану», при котором ничего не производится, сырье не используется и значение целевой функции равно нулю (т. е. стоимость произведенной продукции отсутствует). Этот план, конечно, не является оптимальным.
Это видно и из 4-й строки таблицы (2.1), так как в ней имеется два отрицательных числа: (- 30; - 49;0;0;0). Отрицательные числа не только свидетельствуют о возможности увеличения общей стоимости производимой продукции, но и показывают, на сколько увеличится эта сумма при введении в план единицы того или другого вида продукции.
Даже с экономической точки зрения наиболее целесообразным является включение в план производства изделий А2. Это же необходимо сделать и на основании формального признака симплексного метода, поскольку максимальное по абсолютной величине отрицательное число -49, стоит в 4-й строке 2-го столбца => этот столбец является разрешающим.Определяем вектор, подлежащий исключению из базиса и выбираем разрешающую строку. Для этого находим:
Х2 = min ; ; = 120.
Найдя число = 120, => 3-я строка (Х5) является разрешающей. Следовательно, в базис введем Х2 вместо Х5. Тем самым мы, с экономической точки зрения определили, какое количество изделий А2 предприятие может изготовлять с учетом норм расхода и имеющихся объемов сырья каждого вида.
Таблица (2.1)
Базисные переменные | Свободные переменные | 1 | 2 | 3 | 4 | 5 | |
Х1 | Х2 | Х3 | Х4 | Х5 | |||
1 | Х3 | 750 | 5 | 2 | 1 | 0 | 0 |
2 | Х4 | 807 | 4 | 5 | 0 | 1 | 0 |
3 | Х5 | 840 | 1 | 7 | 0 | 0 | 1 |
4 | F | 0 | -30 | -49 | 0 | 0 | 0 |
На пересечении разрешающего столбца и строки находится разрешающий элемент - это число 7. Производим пересчет всех коэффициентов таблицы, таким образом , чтоб на месте разрешающего элемента получить 1, а в разрешающем столбце все элементы = 0.
Для этого: 1) Третью строку разделим на 7, в результате получим на месте разрешающего элемента 1.
2) Третью строку умножим на 2 и из первой строки вычтем то, что получилось при умножении. Результат записываем в первую строку.
3) Третью строку домножим на 5 и из второй строки вычтем то, что получилось при умножении. Результат записываем во вторую строку.
4) Третью строку умножим на 49 и прибавим к строке F.
При пересчете у нас в столбике F, таблицы (2.2), опять оказалось отрицательное число, а это говорит о том что решение нужно продолжать.
Далее, разрешающим столбцом у нас будет Х1,т.к отрицательное число -23 находится в нем.
Определяем вектор, подлежащий исключению из базиса и выбираем разрешающую строку. Для этого находим:
Х1 = min ; ; = 63.
Найдя число = 63, => 2-я строка (Х4) является разрешающей. Следовательно, в базис введем Х1 вместо Х4.
Запишем все расчёты в таблицу
Таблица (2.2)
Базисные переменные | Свободные переменные | 1 | 2 | 3 | 4 | 5 | |
Х1 | Х2 | Х3 | Х4 | Х5 | |||
1 | Х3 | 510 | 33/7 | 0 | 1 | 0 | -2/7 |
2 | Х4 | 207 | 23/7 | 0 | 0 | 1 | -5/7 |
3 | Х2 | 120 | 1/7 | 1 | 0 | 0 | 1/7 |
4 | F | 5880 | -23 | 0 | 0 | 0 | 7 |
На пересечении разрешающего столбца и строки находится разрешающий элемент - это число 23/7. Производим пересчет всех коэффициентов таблицы, таким образом , чтоб на месте разрешающего элемента получить 1, а в разрешающем столбце все элементы = 0.
Для этого: 1) Третью строку разделим на и запишем получившееся в эту же строку.
2) Из первой строки вычтем вторую, умноженную на и записываем в первую строку.
3) Из третьей строки вычтем вторую умноженную на , результат запишем в третью строку.
4) К строке F прибавим вторую строку умноженную на 23 и запишем в строку F.
Таблица (2.3)
Базисные переменные | Свободные переменные | 1 | 2 | 3 | 4 | 5 | |
Х1 | Х2 | Х3 | Х4 | Х5 | |||
1 | Х3 | 213 | 0 | 0 | 1 | -33/23 | 119/161 |
2 | Х1 | 63 | 1 | 0 | 0 | 7/23 | -5/23 |
3 | Х2 | 111 | 0 | 1 | 0 | -1/23 | 28/161 |
4 | F | 7329 | 0 | 0 | 0 | 7 | 2 |
Ответ: из изложенного выше экономического содержания данных таблицы (2.3) следует, что на втором шаге план задачи является оптимальным. Х1* = 63; Х2* = 111. Fmаx= 7329, это значит, что общая стоимость всей произведенной продукции, а она равна 7329 рублей, является максимальной
Решение задачи двойственным методом
Под двойственной задачей понимается вспомогательная задача линейного программирования, формулируемая с помощью определённых правил непосредственно из условий прямой задачи. Заинтересованность в определении оптимального решения прямой задачи путём решения двойственной к ней задачи обусловлена тем, что вычисления при решении ДЗ могут оказаться менее сложными. Трудоёмкость вычислений при решении ЗЛП в большей степени зависит от числа ограничений, а не от количества переменных.
Каждой задаче линейного программирования можно определенным образом сопоставить некоторую другую задачу линейного программирования, называемую двойственной или сопряженной по отношению к исходной или прямой.
5Х1+2Х2 ≤ 750 Y1
4Х1+5 Х2 ≤ 807 Y2
Х1+7Х2 ≤ 840 Y3
F = 30Х₁ +49Х₂ => max
Целевая функция исходной задачи задаётся на максимум, а целевая функция двойственной – на минимум.
Составим матрицу для исходной задачи:
А =
Чтобы составить матрицу для двойственной задачи нужно применить транспонирование (т.е. замена строк – столбцами, а столбцов – стоками)
АТ =
Число переменных в двойственной задаче равно числу соотношений в системе (1.1) исходной задачи, т.е. равно трем.
Коэффициентами в целевой функции двойственной задачи являются свободные члены системы уравнений, т .е 750,807,840.
Целевая функция исходной задачи исследуется на максимум, а система условий содержит только уравнения. Поэтому в двойственной задаче целевая функция исследуется на минимум, а её переменные могут принимать любые значения (в том числе и отрицательные). Следовательно, для исходной задачи двойственная задача такова: умножим правые части ограничений на соответствующие переменные двойственной задачи и сложим их, получим целевую функции
Z(Y) = 750Y1 + 807Y2 + 840Y3 => min.
5Y1 + 4Y2 + Y3 ≥ 30
2Y1 + 5Y2 + 7Y3 ≥ 49
Y1 = 0
Y2 = 7
Y3 = 2
Z(Y) = 750·0 + 807·7+ 840·2 = 7329
Ответ: Z(Y) = F(Х) = 7329, Y1* = 0, Y2* = 7, Y3* = 2.
Транспортная задача линейного программирования
Под названием «транспортная задача» объединяется широкий круг задач с единой математической моделью. Данные задачи относятся к задачам линейного программирования и могут быть решены симплексным методом. Однако матрица системы ограничений транспортной задачи настолько своеобразна, что для ее решения разработаны специальные методы. Эти методы, как и симплексный метод, позволяют найти начальное опорное решение, а затем, улучшая его, получить оптимальное решение.
Задача №2
Формулировка транспортной задачи
На три базы: А₁, А₂, А₃ поступил однородный груз в количествах: а₁, а₂, а₃, соответственно. Груз требуется перевезти в пять пунктов: b₁ в пункт В₁, b₂ в пункт В₂, b₃ в пункт В₃, b₄ в пункт В₄, b₅ в пункт В₅.
Спланировать перевозки так, чтобы общая их стоимость была минимальной. Матрица тарифов сij перевозок между пунктами отправления и пунктами назначения, а также запасы и потребности представлены ниже:
Пункт отправления | В₁ | В₂ | В₃ | В₄ | В₅ | Запасы, аi |
А₁ | 2 | 4 | 5 | 11 | 3 | 400 |
А₂ | 12 | 8 | 6 | 14 | 11 | 370 |
А₃ | 10 | 15 | 7 | 9 | 18 | 380 |
Потребности, bj | 250 | 200 | 290 | 260 | 150 | 1150 |
Исходные данные транспортной задачи обычно записываются в таблице:
Для разрешимости транспортной задачи необходимо и достаточно, чтобы запасы груза в пунктах отправления были равны потребностям в грузе в пунктах назначения. Проверяем выполнение необходимого и достаточного условия разрешимости задачи. Находим суммарные запасы поставщиков и запросы потребителей: 400 + 370 + 380 = 1150,