Симплекс-метод: пошаговый алгоритм решения ЗЛП с примером

В прошлом уроке задача про столы и тумбы решилась на чертеже. А теперь усложним: третий продукт, четвёртый станок, двадцать сортов сырья. Рисовать полуплоскости в двадцатимерном пространстве не выйдет — нужен метод, который живёт в любой размерности. Такой метод есть: симплекс-метод, придуманный Джорджем Данцигом в 1947 году для военной логистики. Он не рисует ничего. Он ходит по вершинам многогранника допустимых планов с помощью одной таблицы и двух правил выбора.

Почему вершинный перебор работает без чертежей#

Из графического урока остался один факт: если область допустимых решений ограничена, оптимум линейной функции сидит в вершине. Вершины — их конечное число. Значит, теоретически можно перебрать их все. Симплекс-метод делает это умнее: из текущей вершины он переходит не куда угодно, а в соседнюю — ту, где целевая функция больше. Значение $F$ растёт с каждой итерацией, и процесс останавливается, когда лучше уже не бывает.

Соседние вершины отличаются ровно одной образующей прямой: одна граница отошла, другая прижалась. Алгебраический след — обмен ролями между переменными: одна покидает базис, одна занимает её место. Вот и вся механика. Название метод не обязано объяснять: «симплекс» достался ему от ранней геометрической интерпретации Данцига и прижился, хотя ничего простого, кроме таблицы, в методе нет.

Каноническая форма: базисные и свободные переменные#

Переводим задачу про цех в каноническую форму — добавляем балансовые переменные $x_3$ и $x_4$, недогрузки станков:

Переменных четыре, уравнений два. Делим их на две группы. Свободные переменные — те, что приравниваем нулю: на старте это $x_1$ и $x_2$, выпуск пуст. Базисные переменные — те, что выражаются из уравнений: $x_3=8$, $x_4=6$. Набор $(0,0,8,6)$ — базисное решение, и оно в точности соответствует вершине $(0,0)$ чертежа: нулевой выпуск, станки простаивают.

Каждая вершина ОДР отвечает своему базису, и переход в соседнюю вершину — это обмен: одна переменная входит в базис, другая выходит. Симплекс-метод — формальная процедура такого обмена, в которой ничего не рисуют и ничего не угадывают.

Симплекс-таблица: что где записано#

Таблица устроена так: строки — базисные переменные с их ценами $c_B$; столбцы — все переменные задачи; в правом столбце $b$ — правые части, то есть значения базисных переменных. Внизу — строка оценок ${\Delta }_j=z_j-c_j$, где $z_j$ — произведение столбца $j$ на вектор цен $c_B$, а $c_j$ — цена самой переменной. В клетке пересечения строки оценок со столбцом $b$ живёт текущее значение $F=c_B\cdot b$.

Начальная таблица задачи о цехе:

Оценки здесь — просто минусы цен свободных переменных: ${\Delta }_1=-2$, ${\Delta }_2=-3$, потому что базисные переменные ничего не стоят. Отрицательные оценки и есть сигнал: текущий план можно улучшить.

Алгоритм за пять шагов#

1. 1
   Привести задачу к канонической форме и записать начальную таблицу: базис — балансовые переменные.
2. 2
   Посмотреть на строку оценок: все ${\Delta }_j\ge 0$? План оптимален — стоп.
3. 3
   Выбрать разрешающий столбец: ${\Delta }_j<0$, обычно наибольшую по модулю отрицательную оценку.
4. 4
   Выбрать разрешающую строку: для положительных элементов столбца посчитать симплекс-отношения ${\theta }_i=b_i/a_{ij}$ и взять строку с минимумом. Элемент $a_{ij}$ на пересечении — разрешающий.
5. 5
   Пересчитать таблицу методом Жордана–Гаусса: разрешающую строку поделить на разрешающий элемент, из остальных строк вычесть её с подходящими множителями. Вернуться к шагу 2.

Почему минимум $\theta$ работает именно так? Разрешающий элемент — ось вращения: вводимая переменная растёт от нуля, базисные в ответ меняются. Первая базисная переменная, упавшая до нуля, и есть граница роста; шагнуть дальше — план выйдет из ОДР, и это обнаружится в столбце $b$ отрицательными числами. Минимальное симплекс-отношение останавливает переменную ровно на границе: новая вершина достигнута, план остался допустимым.

Полный пример: две итерации до оптимума#

Идём по таблице. Разрешающий столбец — $x_2$: оценка $-3$ самая отрицательная. Симплекс-отношения: $8/2=4$ и $6/1=6$; минимум у строки $x_3$. Разрешающий элемент — двойка на пересечении. Тумбы входят в план, простой станка А уходит из базиса.

Пересчёт. Первую строку делим на 2 — она становится строкой базисной $x_2$: $(1/2,1,1/2,0\mid 4)$. Из строки $x_4$ вычитаем её: $(1/2,0,-1/2,1\mid 2)$. Оценки пересчитываем по ценам $c_B=(3,0)$: для столбца $x_1$ выходит $z_1=3\cdot 1/2+0\cdot 1/2=3/2$, значит ${\Delta }_1=3/2-2=-1/2$; для столбца $x_3$ выходит ${\Delta }_3=3/2-0=3/2$. Значение $F=3\cdot 4+0\cdot 2=12$ — в точности вершина $(0,4)$ чертежа из графического урока.

Отрицательная оценка осталась одна — столбец $x_1$. Отношения: $4:(1/2)=8$ и $2:(1/2)=4$ — уходит простой станка Б, столы входят в план. Разрешающий элемент $1/2$. Делим строку $x_4$ на него: получается строка $x_1$: $(1,0,-1,2\mid 4)$. Из строки $x_2$ вычитаем половину новой: $(0,1,1,-1\mid 2)$. Столбец $b$ читает ответ: $x_2=2$, $x_1=4$.

Строка оценок стала неотрицательной: ${\Delta }_3=3\cdot 1+2\cdot (-1)=1$, ${\Delta }_4=3\cdot (-1)+2\cdot 2=1$. Все ${\Delta }_j\ge 0$ — план оптимален. Ответ: $x_1=4$, $x_2=2$, $F=14$ — ровно то, что дал чертёж. Балансовые переменные обнулились: оба станка загружены до упора, свободного часа нет.

Три сигнала таблицы: оптимум, бесконечность, вырожденность#

• Все оценки неотрицательны — план оптимален. Если при этом нулевая оценка стоит у свободной переменной, оптимум не единственный: есть целая грань равноценных планов.
• В разрешающем столбце нет положительных элементов — целевая функция не ограничена: улучшать можно бесконечно, симплекс-отношения считать не из чего.
• Минимальное симплекс-отношение равно нулю — вырожденность: из базиса уйдёт переменная с нулевым значением, а $F$ за шаг не изменится.

Вырожденность — не ошибка, а состояние: у многогранника вершина, где сходится больше ограничений, чем нужно для базиса. Метод продолжает работать, просто один шаг оказывается бесплатным. Теоретически возможен цикл — возврат к старому базису; на практике его обрывают правилом выбора строки, например правилом Блэнда: брать строку с наименьшим номером уходящей переменной.

Геометрически алгоритм выглядит скромно: старт в вершине $(0,0)$, шаг к $(0,4)$, шаг к $(4,2)$. Две итерации — потому что задачу из немногих переменных метод проходит за считанные ходы. В промышленных задачах с тысячами ограничений вершин триллионы, но симплекс всё равно приходит к ответу за десятки шагов: он не блуждает, а всегда лезет вверх по склону $F$.

Откуда метод берётся и куда идёт#

Пересчёт таблицы — элементарные преобразования строк, те же, что в методе Гаусса: делим строку, вычитаем из других, обнуляем столбец. Разница только в маршруте: гаусс приводит систему к ступенчатому виду раз и навсегда, симплекс после каждого пересчёта заново решает, какой столбец ввести в базис. Термин закреплён в словарной статье про метод Гаусса, а потренировать сами преобразования строк можно в тренажёре СЛАУ.

Финальная таблица щедрее, чем кажется: оценки при балансовых переменных — это готовые теневые цены ресурсов. В нашем примере ${\Delta }_3=1$ и ${\Delta }_4=1$ означают: лишний час любого станка стоит тысячу. Откуда это берётся и как читать — двойственность в ЛП.