Решение задач линейного программирования 3 (стр. 4 из 6)
Двухфазный симплекс-метод.
Если после приведения математической модели к канонической форме не все ограничения находятся в предпочтительном виде, то для решения задачи требуется применить двухфазный симплекс-метод.
Целевая функция вспомогательной задачи представляет собой сумму фиктивных переменных, которую необходимо минимизировать.
Начальный базис вспомогательной задачи составляют переменные:
1. в ограничениях, которые находятся в предпочтительном виде, -те переменные, которые обеспечили предпочтительность этих ограничений.
2. в ограничениях, которые не находятся в предпочтительном виде,- фиктивные переменные
Целевую функцию вспомогательной задачи выражаем через небазисные переменные и решаем систему обычным симплекс-методом(описан выше).
Если все искусственные переменные покинули базис и исключены из таблицы, а строка вспомогательной функции содержит одни нули, то это означает, что решение вспомогательной задачи окончено.
Т.к. как все фиктивные переменные покинули задачу, то система основных ограничений вспомогательной задачи совпадает с исходной системой основных ограничений. Искуственнная целевая функция с исчезновением фиктивных переменных трансформировалась в нулевую. Поэтому для перехода ко второй фазе симплекс-метода необходимо вернуться к исходной целевой функции. Поскольку исходная целевая функция содержит базисные переменные, их необходимо исключить, выразив через небазисные переменные. Далее система решается обычным симплекс-методом, описанным раннее.
4. Решение задачи оптимизации
Для решения задачи необходимо привести её математическую модель(2.4) к канонической форме(введём свободные переменные).
Т.к. не все ограничения находятся в предпочтительном виде, значит будем применять при решении задачи двухфазный симплекс-метод.
Введём фиктивные переменные х16, х17, х18 и решим задачу относительно их:
Будем решать задачу табличным симплекс-методом, как описывалось ранее.
| min | b | x1 | x2 | x3 | x4 | x5 | x6 | x7 | x8 | x9 | x10 | x11 | x12 |
| L | 11700 | -8 | -6 | -12 | -14 | -15 | -12 | -11 | -13 | -4 | 1 | 1 | 1 |
| x16 | 3000 | -8 | -6 | -12 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 |
| x17 | 5400 | 0 | 0 | 0 | -14 | -15 | -12 | 0 | 0 | 0 | 0 | 1 | 0 |
| x18 | 3300 | -1 | 0 | 0 | -1 | 0 | 0 | -1 | 0 | 0 | 0 | 0 | 0 |
| x13 | 300 | -1 | 0 | 0 | -1 | 0 | 0 | -1 | 0 | 0 | 0 | 0 | 0 |
| x14 | 300 | 0 | -1 | 0 | 0 | -1 | 0 | 0 | -1 | 0 | 0 | 0 | 0 |
| x15 | 300 | 0 | 0 | -1 | 0 | 0 | -1 | 0 | 0 | -1 | 0 | 0 | 0 |
Этой симплексной таблице соответствует начальный базисный план х(0) = (0,0,0,0,0,0,0,0,0,0,0,0,300,300,300,3000,5400,3300). L (x(0)) = 11700. Этот план не оптимален, так как целевая функция вспомогательной задачи на минимум содержит отрицательные коэффициенты.
Выбираем базисный столбец и разрешающую строку:
| min | b | x1 | x2 | x3 | x4 | x5 | x6 | x7 | x8 | x9 | x10 | x11 | x12 | θ |
| L | 11700 | -8 | -6 | -12 | -14 | -15 | -12 | -11 | -13 | -4 | 1 | 1 | 1 | |
| x16 | 3000 | -8 | -6 | -12 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | ∞ |
| x17 | 5400 | 0 | 0 | 0 | -14 | -15 | -12 | 0 | 0 | 0 | 0 | 1 | 0 | 360 |
| x18 | 3300 | -1 | 0 | 0 | -1 | 0 | 0 | -1 | 0 | 0 | 0 | 0 | 0 | ∞ |
| x13 | 300 | -1 | 0 | 0 | -1 | 0 | 0 | -1 | 0 | 0 | 0 | 0 | 0 | ∞ |
| x14 | 300 | 0 | -1 | 0 | 0 | -1 | 0 | 0 | -1 | 0 | 0 | 0 | 0 | 300 |
| x15 | 300 | 0 | 0 | -1 | 0 | 0 | -1 | 0 | 0 | -1 | 0 | 0 | 0 | ∞ |
Пересчёт симплексной таблицы происходит по правилам, описанным в разделе 3.
Произведём пересчёт симплексной таблицы и если план получится не оптимальным, то снова выберем ведущий столбец и разрешающую строку.
| min | b | x1 | x2 | x3 | x4 | x14 | x6 | x7 | x8 | x9 | x10 | x11 | x12 | θ |
| L | 7200 | -8 | -6 | -12 | -14 | 15 | -12 | - 11 | 2 | -4 | 1 | 1 | 1 | |
| x16 | 3000 | -8 | -6 | -12 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | ∞ |
| x17 | 900 | 0 | 15 | 0 | -14 | 15 | -12 | 0 | 15 | 0 | 0 | 1 | 0 | 64.286 |
| x18 | 3300 | 0 | 0 | 0 | 0 | 0 | 0 | -11 | -13 | -4 | 0 | 0 | 1 | ∞ |
| x13 | 300 | -1 | 0 | 0 | -1 | 0 | 0 | -1 | 0 | 0 | 0 | 0 | 0 | ∞ |
| x5 | 300 | 0 | -1 | 0 | 0 | -1 | 0 | 0 | -1 | 0 | 0 | 0 | 0 | 300 |
| x15 | 300 | 0 | 0 | -1 | 0 | 0 | -1 | 0 | 0 | -1 | 0 | 0 | 0 | ∞ |
Произведём пересчёт симплексной таблицы и если план получится не оптимальным, то снова выберем ведущий столбец и разрешающую строку.
| min | b | x1 | x2 | x3 | x14 | x6 | x7 | x8 | x9 | x10 | x11 | x12 | θ |
| L | 6300 | -8 | -6 | -12 | 0 | 0 | - 11 | -13 | -4 | 1 | 0 | 1 | |
| x16 | 3000 | -8 | -6 | -12 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | ∞ |
| x4 | 64.286 | 0 | 1.071 | 0 | 1.071 | -0.857 | 0 | 1.071 | 0 | 0 | 0.071 | 0 | ∞ |
| x18 | 3300 | 0 | 0 | 0 | 0 | 0 | -11 | -13 | -4 | 0 | 0 | 1 | 253.846 |
| x13 | 235.174 | -1 | 0 | 0 | -1.071 | 0.857 | -1 | -1.071 | 0 | 0 | -0.071 | 0 | 220 |
| x5 | 300 | 0 | -1 | 0 | -1 | 0 | 0 | -1 | 0 | 0 | 0 | 0 | 300 |
| x15 | 300 | 0 | 0 | -1 | 0 | -1 | 0 | 0 | -1 | 0 | 0 | 0 | ∞ |
Произведём пересчёт симплексной таблицы и если план получится не оптимальным, то снова выберем ведущий столбец и разрешающую строку.
| min | b | x1 | x2 | x3 | x14 | x6 | x7 | x13 | x9 | x10 | x11 | x12 | θ |
| L | 3440 | 4.133 | 7 | -12 | 13 | -10.4 | 1.133 | 12.133 | -4 | 1 | 0.867 | 1 | |
| x16 | 3000 | -8 | -6 | -12 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 250 |
| x4 | 300 | -1 | 0 | 0 | 0 | 0 | -1 | -1 | 0 | 0 | 0 | 0 | ∞ |
| x18 | 440 | 12.133 | 13 | 0 | 13 | -10.4 | 1.133 | 12.133 | -4 | 0 | 0.867 | 1 | ∞ |
| x8 | 220 | -0.933 | -1 | 0 | -1 | 0.8 | -0.933 | -.933 | 0 | 0 | -0.067 | 0 | ∞ |
| x5 | 80 | 0.933 | 0 | 0 | 0 | -0.8 | 0.933 | 0.933 | 0 | 0 | 0.067 | 0 | ∞ |
| x15 | 300 | 0 | 0 | -1 | 0 | -1 | 0 | 0 | -1 | 0 | 0 | 0 | 300 |
Произведём пересчёт симплексной таблицы и если план получится не оптимальным, то снова выберем ведущий столбец и разрешающую строку.
| min | b | x1 | x2 | x14 | x6 | x7 | x13 | x9 | x10 | x11 | x12 | θ |
| L | 440 | 12.133 | 13 | 13 | -10.4 | 1.133 | 12.133 | -4 | 0 | 0.867 | 1 | |
| x3 | 250 | -0.667 | -0.5 | 0 | 0 | 0 | 0 | 0 | 0.083 | 0 | 0 | ∞ |
| x4 | 300 | -1 | 0 | 0 | 0 | -1 | -1 | 0 | 0 | 0 | 0 | ∞ |
| x18 | 440 | 12.133 | 13 | 13 | -10.4 | 1.133 | 12.133 | -4 | 0 | 0.867 | 1 | 42.308 |
| x8 | 220 | -0.933 | -1 | -1 | 0.8 | -0.933 | 0.933 | 0 | 0 | -0.067 | 0 | ∞ |
| x5 | 80 | 0.933 | 0 | 0 | -0.8 | 0.933 | 0.933 | 0 | 0 | 0.067 | 0 | 100 |
| x15 | 50 | 0.667 | 0.5 | 0 | -1 | 0 | 0 | -1 | -0.083 | 0 | 0 | 50 |
Произведём пересчёт симплексной таблицы