СИМПЛЕКСНЫЙ МЕТОД
Симплексный метод (метод последовательного улучшения плана) решения задачи линейного программирования основан на переходе от одного опорного плана к другому, при котором значение целевой функции возрастает (убывает) для задачи на max (на min) при условии, что данная задача имеет оптимальный план и каждый ее опорный план является невырожденным. Указанный переход возможен, если известен какой-нибудь исходный опорный план. Рассмотрим задачу, для которой этот план можно непосредственно записать. Пусть векторная форма данной задачи имеет следующий вид:
(10.24)
при условиях
(10.25)
(10.26)
где
;
– единичные векторы, образующие базис m-мерного пространства.
Пусть . Допустим, что
Теорема 10.5 (условие оптимальности). Опорный план задачи (10.24) – (10.26) является оптимальным, если для любого j, .
Теорема 10.6. Если опорный план Х0 задачи (10.24) – (10.26) невырожден и , но среди чисел есть положительные (не все ), то существует такой опорный план , что .
Теорема 10.7. Если для некоторого j = k и среди чисел нет положительных , то целевая функция (10.24) задачи (10.24) – (10.26) не ограничена на множестве ее планов.
Сформулированные теоремы позволяют проверить, является ли найденный опорный план оптимальным, и выявить целесообразность перехода к новому опорному плану. Нахождение оптимального плана симплексным методом включает следующие этапы.
1. Находят опорный план.
2. Составляют симплекс-таблицу (см. табл. 10.3 ).
Базисные переменные … … … …
… … … …
1 0 … 0 … 0 … …
0 1 … 0 … 0 … …
… … … … … … … … … … … … … …
0 0 … 1 … 0 … …
… … … … … … … … … … … … … …
0 0 … 0 … 1 … …
0 0 … 0 … 0 … …
Таблица 10.3
3. Выясняют, имеется ли хотя бы одно отрицательное число . Если нет, то найденный опорный план оптимален. Если же среди чисел имеются отрицательные, то либо устанавливают неразрешимость задачи, либо переходят к новому опорному плану.
4. Находят направляющие столбец и строку. Направляющий столбец определяется из условия , где максимум берется по тем j, для которых , а , а направляющая строка – минимальным из отношений компонент столбца вектора к положительным компонентам направляющего столбца.
5. По формулам
определяют положительные компоненты нового опорного плана, коэффициенты разложения векторов по векторам нового базиса и числа . Все эти числа записываются в новой симплекс таблице (табл. 10.4).
6. Проверяют найденный опорный план на оптимальность. Если он не является оптимальным и необходимо перейти к новому опорному плану, то возвращаются к этапу 4, а в случае получения оптимального плана или установления неразрешимости процесс решения задачи завершают.
Таблица 10.4
Базисные переменные … … … …
… … … …
1 0 … … 0 … 0 …
0 1 … … 0 … 0 …
… … … … … … … … … … … … … …
0 0 … … 0 … 1 …
… … … … … … … … … … … … … …
0 0 … … 1 … 0 …
0 0 … … 0 … 0 …