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

Пусть рассматриваемая ЗЛП решается на нахождение максимума целевой функции.

Алгоритм симплекс-метода состоит в выполнении следующих шагов.

1. Составить первую симплекс-таблицу, исходя из условий задачи.

2. Проверить критерий оптимальности. Если он выполняется, то опорный план является оптимальным, т.е. он имеет значение = (0, 0, …, 0, b₁, b₂, …, b_m). Соответствующее значение целевой функции определяется соотношением z = z₀.

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

3. Определить переменную, которую необходимо ввести в базис. Для этого в оценочной строке определить наибольший по абсолютной величине отрицательный элемент. Столбец, содержащий наибольшую по абсолютной величине отрицательную оценку, помечается стрелкой и называется разрешающим столбцом (s-й столбец). Он помечается вертикальной стрелкой.

4. Вычислить симплексные отношения, разделив свободные члены на соответствующие коэффициенты выделенного столбца . При этом учитываются только неотрицательные отношения. Записать их в соответствующий столбец таблицы.

5. Определить переменную, которую необходимо вывести из базиса. Для этого определяется строка, содержащая наименьшее симплексное отношение. Она помечается стрелкой. Эта строка является разрешающей (r-я строка).

6. Выделить разрешающий элемент, стоящий на пересечении разрешающей строки и разрешающего столбца.

7. Перейти к новой симплексной таблице, в которой переменные x_r и x_s меняются местами.

8. Заполнить клетки новой симплексной таблицы следующим образом.

· В клетке, соответствующей разрешающему элементу старой таблицы, записать обратную величину .

· Все остальные элементы r-й строки вычислить делением соответствующих элементов старой таблицы на разрешающий элемент:

· Все остальные элементы s-го столбца вычислить делением соответствующих элементов старой таблицы на разрешающий элемент с изменением знака частного на противоположный:

· Остальные элементы новой симплексной таблицы вычислить по правилу прямоугольника:

· Столбец симплексных отношений остается незаполненным. Он заполняется при необходимости перехода к новой симплексной таблице.

9. Перейти к пункту 2.