Линейное программирование, решение задач симплексным методом (стр. 6 из 8)
Сведение задачи минимизации к задаче максимизации линейной функции
Мы рассматривали решение симплекс-методом задачи отыскания максимума линейной функции
W = c1x1 + c2x2 + … + cnxn.
Однако во многих экономических задачах требуется найти минимум линейной функции. Для этого достаточно положить
W = -Z = -c1x1 – c2x2 - … - cnxn
и решать задачу максимизации полученной функции W при соответствующих ограничениях. Так как ясно, что
min Z = -max W.
Минимизировать линейную функциюZ = -2X1 + 5X2
при выполнении ограничений
7X1 + 2X2 ≥ 14,
5X1 + 6X2 ≤ 30,
3X1 + 8X2 ≥ 24,
X1 ≥ 0, X2 ≥ 0.
Геометрическое решение задачи на (рис. 5) и ему отвечает оптимальное решение в точке
С (48/11, 15/11) и при этом Zmin = -21/11.
Рис 5. Геометрическое решение задачи
Вводя выравнивающие переменные Yi ≥ 0 и функцию W = -Z = 2X1 - 5X2 → max, задачу запишем в виде.
Y1 = 7X1 + 2X2 - 14,
Y2 = -5X1 - 6X2 + 30,
Y3 = 3X1 + 8X2 - 24,
W = 2X1 - 5X2.
Записываем эту систему в виде таблицы.
| |
| -X1 | -X2 | 1 | |
| Y1 | -7 | -2 | -14 |
| Y2 | 5 | 6 | 30 |
| Y3 | -3 | -8 | -24 |
| W | 2 | 5 | 0 |
Так как имеются отрицательные свободные члены, то от них избавляемся. Выбираем наименьший отрицательный член в Y3 – строке и в этой строке берем отрицательный элемент “-8”, который соответствует разрешающему столбцу. Свободные члены делим на соответствующие элементы разрешающего столбца и выбираем наименьшее положительное отношение, тогда Y3 – строка разрешающая. Производя ШМЖИ с разрешающим элементом “-8”, получаем таблицу.
| -X1 | -Y3 | 1 | |
| Y1 | -50/8 | -2/8 | -8 |
| Y2 | 22/8 | 6/8 | 12 |
| X2 | 3/8 | -1/8 | 3 |
| W | -31/8 | 5/8 | -15 |
Избавляемся от отрицательного свободного члена в Y1 – строке, совершая ШМЖИ с разрешающим элементом “-50/8”, получаем таблицу.
| -Y1 | -Y3 | 1 | |
| X1 | -8/50 | 2/50 | 64/50 |
| Y2 | 22/50 | 32/50 | 424/50 |
| X2 | 3/50 | -7/50 | 126/50 |
| W | -31/50 | 39/50 | -502/50 |
Так как все свободные члены в 1 – столбце неотрицательные, то выбираем разрешающий элемент как в МЖИ для задачи на max. Совершаем ШМЖИ с разрешающим элементом “22/50”, получаем таблицу.
 | -Y2 | -Y3 | 1 |
| X1 | 4/11 | 3/11 | 48/11 |
| Y1 | 25/11 | 16/11 | 212/11 |
| X2 | -3/22 | -5/22 | 15/11 |
| W | 31/22 | 37/22 | 21/11 |
Так как в W – строке и в 1 – столбце нет отрицательных элементов, то получили оптимальное решение X1 = 48/11, X2 = 15/11, Wmax – 21/11 или Zmin = –Wmax = -21/11,
Практическая часть
1.
Решить задачу симплекс методом.X1 + 3X2 ≤ 300 F = 2X1 + 3X2 → max
X1 + X2 ≤ 150
X1 ≥ 0
X2 ≥ 0
Решение
X1 + 3X2 + X3 = 300 F - 2X1 - 3X2 = 0
X1 + X2 + X4 = 150
| Б | С.Ч | X1 | X2 | X3 | X4 |
| X3 | 300 | 1 | 3 | 1 | 0 |
| X4 | 150 | 1 | 1 | 0 | 1 |
| F | 0 | -2 | -3 | 0 | 0 |
| Б | С.Ч | X1 | X2 | X3 | X4 |
| X2 | 100 | 1/3 | 1 | 1/3 | 0 |
| X4 | 50 | 2/3 | 0 | 1/3 | 1 |
| F | 300 | -1 | 0 | 1 | 0 |
(-1) (3)
| Б | С.Ч | X1 | X2 | X3 | X4 |
| X2 | 75 | 0 | 1 | 1/2 | -1/2 |
| X1 | 75 | 1 | 0 | -1/2 | 3/2 |
| F | 375 | 0 | 0 | 1/2 | 3/2 |
(-1/3) (1)
Ответ: X1 = 75; X2 = 75; X3 = 0; X4 = 0.
Задача №1.
Предприятие выпускает продукцию двух видов. Виды сырья, его запасы, нормы расхода сырья на у.е. каждого вида продукции, прибыль производства от реализации продукции даны в таблице.
Как следует спланировать выпуск продукции, чтобы прибыль предприятия была наибольшей?
Решение
X1 + 3X2 ≤ 20 F = 2X1 + X2 → max
2X1 + X2 ≤ 102X1 + 2X2 ≤ 17
X1 + 3X2 + X3 = 20 F - 2X1 - X2 = 0
2X1 + X2 + X4 = 10
2X1 + 2X2 + X5 =17
| Б | С.Ч | X1 | X2 | X3 | X4 | X5 |
| X3 | 20 | 1 | 3 | 1 | 0 | 0 |
| X4 | 10 | 2 | 1 | 0 | 1 | 0 |
| X5 | 17 | 2 | 2 | 0 | 0 | 1 |
| F | 0 | -2 | -1 | 0 | 0 | 0 |
| Б | С.Ч | X1 | X2 | X3 | X4 | X5 |
| X3 | 15 | 0 | 5/2 | 1 | -1/2 | 0 |
| X1 | 5 | 1 | 1/2 | 0 | 1/2 | 0 |
| X5 | 7 | 0 | 1 | 0 | -1 | 1 |
| F | 10 | 0 | 0 | 0 | 1 | 0 |
(-1)(-2)(2)