Шаг 1. Составляем симплекс-таблицу и рассчитываем симплекс-разности 
по формуле (2.8).
Шаг 2. Определяем знак симплекс-разностей:
· если все 
, 
, то получен оптимальный план;
· если существуют 
, , то переходим к шагу 2.
Шаг 3. Определяем ключевой столбец. Ключевым или разрешающим столбцом называется столбец соответствующий максимальной по модулю 
среди отрицательных симплекс-разностей.
Шаг 4. Определяем знак элементов ключевого столбца:
· если все 
, 
то 
неограничена (
);
· если 
, то переходим к шагу 5.
Шаг 5. Определяем ключевую строку. Ключевой строкой называется строка, в которой отношение 
минимально при условии, что . Пусть минимум достигается при 
, строка с номером 
называется ключевой (разрешающей), а элемент 
– ключевой элемент.
Шаг 6. Переходим к новой симплекс-таблице и новому базису, выводя из него неизвестный 
, заменяя его на известный 
. Изменение базиса означает переход к новому плану. Элементы новой симплекс-таблицы вычисляются следующим образом:
, 
.
Переходим к шагу 1.
Замечание:
1. Если 
выполняется в нескольких точках, то в качестве ключевого элемента можно выбрать любой из них.
2. Если исходная задача линейного программирования является вырожденной, то есть среди ее всевозможных базисных решений есть вырожденные, то в ходе ее решения симплекс-методом могут появиться и вырожденные базисные решения. При этом возможны холостые шаги симплекс-метода, т.е. итерации, на которых не изменяется. Возможно также и зацикливание, т.е. бесконечная последовательность холостых шагов. Для его предотвращения разработаны специальные алгоритмы-антициклины.
Однако в подавляющем большинстве случаев холостые шаги сменяются шагами с убыванием целевой функции и процесс решения завершается в результате конечного числа итераций.
Метод искусственного базиса
Если задача линейного программирования в каноническом виде не содержит базиса, то для ее решения применяют метод искусственного базиса.
Пусть исходная задача (2.1)-(2.3) не имеет базиса. Запишем для исходной задачи расширенную задачу в следующем виде:
; (2.9)
, 
; (2.10)
, 
. (2.11)
где 
– произвольное большое число, 
.
Опорный план задачи (2.9)-(2.11) будет иметь вид:
.
Вектора 
, 
, …, 
образуют искусственный базис задачи линейного программирования.
Теорема 6. Если найдено решение расширенной задачи, и при этом все искусственные переменные равны нулю, то найденное решение будет оптимальным для исходной задачи линейного программирования.
Теорема 7. Если оптимальное решение расширенной задачи содержит хотя бы одну отличную от нуля искусственную переменную, то исходная задача не имеет решения в силу несовместимости системы ограничений.
Теорема 8. Если расширенная задача не имеет решения, то и исходная задача также не имеет решения либо в силу несовместимости системы ограничений либо в силу неограниченности целевой функции.
Пример практической части второй главы