Рассмотрим алгоритм решения задач симплексным методом[17].
1. Математическая модель задачи должна бать канонической. Если она неканоническая, то ее надо привести к каноническому виду.
2. Находим исходное опорное решение и проверяем его на оптимальность. Для этого заполняем симплекс-таблицу. Все строки таблицы 1-го шага, за исключением строки Dj (индексная строка), заполняем по данным системы ограничений и целевой функции.
Симплексная таблица имеет следующий вид:
| сi | Базисная переменная (БП) | с1 | с2 | ¼ | сm | сm+1 | ¼ | сn | f (` X) |
| x1 | x2 | ¼ | xm | xm+1 | ¼ | xn | b1 | ||
| c1 | x1 | ¼ | h1, m+1 | ¼ | h1n | l1 | |||
| c2 | x2 | ¼ | h2, m+1 | ¼ | h2n | l2 | |||
| ¼ | ¼ | ¼ | ¼ | ¼ | ¼ | ¼ | ¼ | ¼ | ¼ |
| cm | xm | ¼ | hm, m+1 | ¼ | hmn | lm | |||
| D j | ¼ | D m+1 | ¼ | D n | f (` X1) |
Индексная строка (D j) для переменных находится по формуле
и для свободного члена по формуле
.
При этом возможны следующие случаи решения задачи на максимум:
- если все оценки D j ³ 0, то найденное решение оптимальное;
- если хотя бы одна оценка D j £ 0, но при соответствующей переменной нет ни одного положительного коэффициента, решение задачи прекращают, так как f (X) ® ¥, т.е. целевая функция не ограничена в области допустимых решений;
- если хотя бы одна оценка отрицательная, а при соответствующей переменной есть хотя бы один положительный коэффициент, то нужно перейти к другому опорному решению;
- если отрицательных оценок в индексной строке несколько, то в столбец базисной переменной (БП) вводят ту переменную, которой соответствует наибольшая по абсолютной величине отрицательная оценка.
Пусть одна оценка D k £ 0 или наибольшая по абсолютной величине D k £ 0, тогда k -й столбец принимают за ключевой (разрешающий). За ключевую (разрешающую) строку принимают ту, которой соответствует минимальное отношение свободных членов (bi) к положительным коэффициентам k -го столбца. Элемент, находящийся на пересечении ключевых строки и столбца, называют ключевым (разрешающим) элементом.
3. Заполнение симплексной таблицы 2-го шага:
- переписывается ключевая строка, разделив ее элементы на ключевой элемент;
- заполняют базисные столбцы;
- остальные коэффициенты таблицы находят по правилу «прямоугольника». Оценки можно считать по приведенным выше формулам или по правилу «прямоугольника». Получается новое опорное решение, которое проверяется на оптимальность и т.д.
Примечание. Если целевая функция f (X) требует нахождения минимального значения, то критерием оптимальности задачи является неположительность оценок D j при всех 
.
Правило «прямоугольника» состоит в следующем. Пусть ключевым элементом 1-го шага является элемент 1-й строки (m +1)-го столбца h1, m+1. Тогда элемент i -й строки (m+2)-го столбца 2-го шага, который обозначим 
, по правилу «прямоугольника» определяется по формуле
,
где h1, m+1, hi, m+1, hi, m+2 – элементы 1-го шага.
