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

7.1. Метод последовательного уточнения оценок позволяет построить конечную последовательность псевдопланов

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

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

7.2. Более точно, нам понадобится так называемая лексикографическая модификация метода последовательного уточнения оценок (лексикографический двойственный симплекс-метод), позволяющая вместо исходной задачи (1.9) — (1.11) решать ее лексикографический вариант. Найти лексикографический максимум расширенного плана

при условиях

Задачу лексикографической максимизации расширенного плана на многограннике (1.10) — (1.11) будем обозначать через и будем для краткости называть ее изадачей.

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

7.3. Общая итерация. Имеется -псевдоплан и соответствующие ему Столбцы обозначаем через Проверяем, является ли таблица допустимой (т. е. выполнено ли условие Если является, то -оптимальный план. Если не является, то ищем переменную выводимую из базиса, по правилу

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

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

7.4. Способы построения исходного -псевдоплана указаны в книге [45]. Укажем здесь лишь один прием для нахождения Пусть построена симплексная таблица соответствующая задаче (1.9) — (1.11) и не являющаяся -нормальной. Ей соответствуют множества индексов Пусть функция 2 ограничена на множестве

Тогда (например, с помощью метода последовательного улучшения плана, а часто и непосредственно) можно найти такое число что

Введем новую переменную

Припишем строку (7.6) снизу к таблице и выберем переменную выводимую из базиса, по правилу

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

Произведем пересчет по формулам § 5 и получим -нормальную таблицу и соответствующие ей Здесь