Шаги симплекс-метода принято выполнять с помощью т.н. симплекс таблиц. Рассмотрим их на следующем примере:
x1 -x4 - 2x6 = 5
x2 + 2x4 - 3х5 + x6 = 3
x3 + 2x4 - 5х5 + 6x6 = 5
F = x1 + x2 + x3 +1→ min
В таблицу вносятся коэффициенты при переменных в ограничениях и свободные члены. Коэффициенты целевой функции вносятся (с противоположными знаками) в последнюю строку. Первый столбец содержит обозначения текущих базисных переменных. В правую нижнюю ячейку вносится свободный член целевой функции (со своим знаком!).
Пояснение. Целевая функция записывается также как динейное ограничение на переменные F, x1,…, x6: F - x1 - x2 - x3=1. В этой полной СЛУ F является базисной переменной, но при всех переходах от базиса к базису соответствующий ей столбец не меняется, переменная F остается базисной и потому в таблице не записывается, остается «за кадром».
В исходной форме примера целевая функция содержит базисные переменные. Следует исключить их и выразить функцию только через свободные переменные. Добавим к последней строчке таблицы последовательно первую, вторую и третью (в общем случае умножив предварительно на «подходящее число). Получим: F + 3x4-8x5 + 5x6.= 14.
x1 x2 x3 x4 x5 x6 b
x1 1 0 0 -1 0 -2 5
3/1 x2 0 1 0 2 -3 1 3
5/6 x3 0 0 1 2 -5 6 5
-1 -1 -1 0 0 0 1 (исходная строка для целевой функции)
0 0 0 3 -8 5 14 (б.п. исключены)
В нашем примере система ограничений-равенств уже приведена к базису.
В общем случае единичные базисные столбцы формируются из исходной таблицы методом Гаусса. Однако при этом может получиться недопустимое базисное решение (некоторые базисные переменные могут получить отрицательные значения). Получение исходного допустимого базиса – отдельная задача, обсудим позже.
Для перехода от исходного допустимого базиса к очередному лопустимому и «лучшему» базису необходимо выбрать некоторую «новую» переменную xj, такую, что знак коэффициента при ней в последней строке таблицы положителен (то есть в целевой функции отрицателен). Назовем ее и соответствующий ей столбец разрешающими. Кроме того, необходимо соблюдение двух правил, обеспечивающих допустимость очередного базиса:
1. Разрешающий столбец Aj (вводимый в базис) должен содержать хотя бы один положительный элемент aij > 0.
2. Для всех положительных элементов этого столбца Aj надо подсчитать отношение bi/ aij и выбрать строку i, для которой оно минимально – ведущую строку.
Повторение предыдущей таблицы (для обозримости)
x1 x2 x3 x4 x5 x6 b Базисное решение:
x1 1 0 0 -1 0 -2 5 x1=(5,3,5,0,0,0), F(x1)=14
5/1 x2 0 1 0 2 -3 1 3
5/6 x3 0 0 1 2 -5 6 5
0 0 0 3 -8 5 14
Введем в базис переменную х6. Правила 1 и 2 будут соблюдены, если в качестве ведущей выбрать третью строку. При этом из базиса уйдет переменная x3.
x1 x2 x3 x4 x5 x6 b Базисное решение:
x1 1 0 1/3 -1/3 10/6 0 20/3 x2=(20/3,13/6,0,0,5/6), F(x2)=59/6<14
13/10 x2 0 1 -1/6 5/3 -13/6 0 13/6
2 ½ x6 0 0 1/6 1/3 -5/6 1 5/6
0 0 5/6 4/3 -23/6 0 59/6
На следующей итерации вводим в базис x4, выводя из него переменную x2.
Получим следующую таблицу:
x1 x2 x3 x4 x5 x6 b
x1 1 1/5 3/10 0 -21/10 0 71/10
x4 0 1/5 -1/10 1 23/5 0 13/10
x6 0 -4/5 1/5 0 -2/5 1 2/5
0 -4/5 -11/18 0 -17/18 0 81/10
В этой таблице все коэффициенты последней строки неположительны. Следовательно, дальнейшее улучшение целевой функции невозможно. Итак,
x3=x* = (71/10, 0, 0, 13/10, 0, 2/5) – оптимальное базисное решение, F*=F(x*) = 81/10.
Все коэффициенты в последней строке отрицательны (то есть в целевой функции положительны), полученное базисное решение есть минимум.
Упражнение: Выпишите СЛУ, соответствующую полученному базису.
Замечание 1. Если условие 1 не выполнено (т. е. все коэффициенты при переменной xj, входящей в целевую функцию с положительным коэффициентом, неположительны), то задача ЛП неограничена, решения нет.
Замечание 2. Если минимальное из отношений bi/aij равно нулю, новая базисная переменная в очередном базисном решении равна 0, улучшения функции на данном шаге не происходит. Но происходит переход к новому базису. В принципе возможен эффект зацикливания, когда после нескольких таких шагов (без улучшения значения функции) происходит возврат к уже пройденному базисному решению. В линейном программировании, к счастью, разработаны процедуры (антициклины) предотвращающие такой эффект, и они заложены в программные реализации симплекс-метода.