Алгоритм симплекс-метода

1. Записываем данную задачу в исходную симплекс-таблицу.

2. Если все элементы оценочной строки симплексной таблицы неотрицательны, то исходный план является оптимальным.

3. Если в оценочной строке содержится отрицательный элемент, над которым в таблице нет положительных элементов, то целевая функция не ограничена сверху и задача не имеет решения.

4. Если над каждым отрицательным элементом оценочной строки в соответствующем столбце есть хотя бы один положительный элемент, то можно перейти к лучшему плану.

С этой целью:

а) выбираем в исходной таблице разрешающий столбец. Это столбец, соответствующий наименьшей отрицательной оценке. Пусть это столбец, соответствующий переменной ;

б) выбираем разрешающую (q-тую) строку из условия

в) элемент – разрешающий;

г) элементы разрешающей строки делим на разрешающий элемент;

д) элементы остальных строк вычисляем по правилу «прямоугольника»;

е) элементы оценочной строки также вычисляются по правилу нахождения оценок. Эту формулу можно использовать в качестве контроля вычислений.