Вычислительный алгоритм симплекс-метода применяется для решения задачи линейного программирования (ЛП) с односторонним ограничением и требованием неотрицательности переменных:
(1)
Алгоритм симплекс-метода включает пять этапов, которые рассмотрим на примере решения следующей задачи ЛП:
(2)
Этап 1. Представить исходные данные в виде симплекс-таблицы.
Вводим дополнительные (базисные) переменные y в ограничения и записываем задачу в стандартной форме (предварительно записываем систему таким образом, чтобы в ограничениях были знаки «», и вводим дополнительные переменные):
(3)
Значения свободного члена c0 и коэффициентов cj, при свободных переменных x в уравнении целевой функции, свободных членов bi и коэффициентов аij при свободных переменных в уравнениях ограничений записываем в симплекс-таблицу (таблица 1).
Таблица 1
Свободный член
x1
x2
x3
E
-2
y1
-1
-1
y2
-5
-2
-1
y3
y4
Этап 2. Проверить совместимость ограничений (наличие ОДР).
Признак 1. Ограничения совместимы, если на каждой итерации (результате повторения математической операции) в каждой строке, имеющей отрицательный свободный член, есть хотя бы один отрицательный элемент.
Из таблицы 1 видно, что признак 1 выполняется.
Этап 3. Найти допустимое решение (координаты любой вершины ОДР).
Признак 2. Решение является допустимым, если в строках базисных переменных симплекс-таблицы все свободные члены неотрицательные.
Из таблицы 1 видно, что признак 2 не выполняется.
Если это требование не выполняется, производится обмен переменных. На каждой итерации такого обмена одна переменная из свободных переводится в базисные, а одна базисная – в свободные.
Алгоритм перехода при обмене переменных состоит из пяти шагов.
1 Числа, содержащиеся в исходной симплекс-таблице, записать в верхних левых частях ячеек новой симплекс-таблицы.
2 Выбрать разрешающий элемент.
В строке, содержащей отрицательный свободный член, выбрать отрицательный элемент. Столбец, в котором находится выбранный элемент, принять в качестве разрешающего.
От выбора разрешающего столбца зависит число итераций, в результате которых находится допустимое решение. Для выбора разрешающего столбца проводится сложный анализ. На оптимальное решение выбор столбца не влияет.
В качестве разрешающего столбца могут быть приняты столбцы x1 и x3. Разрешающим принят столбец x1.
В разрешающем столбце для всех элементов аij, имеющих одинаковый знак со свободным членом bi, определить отношение bi/аij. Значение может быть равно нулю. Строку с минимальным значением bi/аij выбрать в качестве разрешающей.
Для рассматриваемого примера и в качестве разрешающей принимаем строку y3.
Разрешающим элементом принимается элемент, принадлежащий разрешающим столбцу и строке.
3 Заполнить нижние правые части ячеек симплекс-таблицы по следующим правилам:
1) ячейку разрешающего элемента заполнить , где –разрешающий элемент;
2) ячейки разрешающей строки заполнить элементами, стоящими в этих ячейках, умноженными на ;
3) ячейки разрешающего столбца заполнить элементами, стоящими в этих ячейках, умноженными на минус ;
4) выделить в разрешающей строке все верхние числа, а в разрешающем столбце – все нижние числа;
5) все остальные ячейки заполнить произведением выделенных чисел, находящихся в той же строке и в том же столбце, в которых расположена данная ячейка.
Таблица 1 преобразована в таблицу 2.
Таблица 2
x1
y3
Свободныйчлен
x1
x2
x3
E
-2
y1
-1
-1
y2
-5
-2
-1
y3
y4
4 Перейти к следующей симплекс-таблице.
В новой симплекс-таблице:
1) поменять местами обмениваемые переменные;
2) в разрешающих строке и столбце записать в верхней левой части каждой ячейки число, стоящее в нижней правой части данной ячейки;
3) в остальных ячейках записать в верхней левой части сумму двух чисел, стоящих в каждой ячейке.
Новая симплекс-таблица представлена в таблице 3 (левые верхние части ячеек).
Таблица 3
x3
y2
Свободныйчлен
y3
x2
x3
E
-1
y1
-1
y2
-1
-2
-2
-1
-1
x1
y4
-1
5 Проверить признаки.
Если признак 2 выполняется, полученное решение является допустимым. В противном случае проверяется признак 1. Если признак 1 выполняется, то обмен переменных повторяется ещё раз. В противном случае допустимое решение получено быть не может.
Из таблицы 3 видно, что признак 2 не выполняется, а признак 1 выполняется.
Повторяем обмен переменных.
Результаты повторного обмена переменных представлены в таблице 4. Признак 2 выполняется и значения в таблице 4 являются допустимым решением рассматриваемого примера.
Таблица 4
Свободный член
y3
x2
y2
E
y1
x3
-2
-2
-1
x1
y4
Из таблицы 4 следует, что x1=2; x3=1; y1=2; y4=1; y3=x2=y2=0; E=3 (см. столбец свободного члена).
Этап 4. Проверить наличие оптимального решения, то есть ограниченность целевой функции.
Признак 3а. Целевая функция имеет минимальное значение (ограничена снизу), если на каждой итерации в каждом столбце, в строке целевой функции которого находится положительный элемент, есть хотя бы один положительный элемент.
Признак выполняется для таблиц 2; 3; 4.
Признак 3б. Целевая функция имеет максимальное значение (ограничена сверху), если на каждой итерации в каждом столбце, в строке целевой функции которого находится отрицательный элемент, есть хотя бы один положительный элемент.
Этап 5. Найти оптимальное решение.
Признак 4а. Целевая функция имеет максимальное значение в том случае, когда в строке целевой функции все элементы, кроме свободного члена, который не рассматривается, положительные.
Признак 4б. Целевая функция имеет минимальное значение в том случае, когда в строке целевой функции все элементы, кроме свободного члена, который не рассматривается, отрицательные.
Признак 4в. Если в строке целевой функция все элементы, кроме свободного члена, который не рассматривается, одного знака и при этом есть хотя бы один нулевой элемент, то полученное нулевое решение является альтернативным.
Последнее означает, что есть и другой набор значений переменных, при которых целевая функция имеет такое же оптимальное значение.
Признак 4б для симплекс-таблицы 4 не выполняется. В этом случае продолжается обмен переменных так же, как при поиске допустимого решения, за исключением: разрешающим принимается столбец, в строке целевой функции которого находится элемент, не соответствующий по знаку проверяемому признаку.
Очередные симплекс-таблицы для рассматриваемого примера представлены в таблицах 5-7.
В таблице 7 признак 4б выполняется и полученное решение является оптимальным (в смысле минимума целевой функции). При x1=3/2; x3=2; y1=1/2; y3=1/2; x2=y4=y2=0; min E=1.
(1)
(2)
», и вводим дополнительные переменные):
(3)
может быть равно нулю. Строку с минимальным значением bi/аij выбрать в качестве разрешающей.
и в качестве разрешающей принимаем строку y3.
, где 
–разрешающий элемент;
;
Таблица 2
Таблица 3
Таблица 5
Таблица 6