§ 6. Метод последовательного улучшения плана (прямой симплекс-метод)

6.1. Метод последовательного улучшения плана позволяет построить конечную последовательность опорных планов

последний из которых является оптимальным планом задачи Целевая функция возрастает (точнее, не убывает) с ростом В геометрической интерпретации это соседние вершины многогранника планов. Каждому из опорных планов соответствуют: симплексная таблица и множества (индексов, нумерующих соответственно базисные и небазисные переменные).

Процесс решения состоит из начальной итерации (построение исходного опорного плана и последовательности общих итераций.

6.2. Общая итерация. Имеется опорный план и соответствующие ему

Проверяем, является ли таблица нормальной (т. е. выполнено ли условие для всех ). Если

является, то план оптимальный. Если не является, то ищем переменную вводимую в базис, по правилу

Затем ищем переменную выводимую из базиса, по правилу

Если среди чисел нет положительных, то задача неразрешима.

Если такие числа есть, то производим пересчет по формулам § 5. Получаем Здесь

6.3. Чтобы найти исходный опорный план преобразуем исходную задачу (1.9) -(1.11) таким образом, чтобы правые части всех уравнений были неотрицательными Для этого следует те из уравнений (1.10), для которых переписать в виде

где

Рассмотрим вспомогательную задачу: Максимизировать

при условиях

Опорный план этой задачи

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