Лекция 8
Метод последовательного уточнения оценок

Иногда это метод называют еще двойственным симплекс-методом. Ранее говорилось, что одновременно с решением прямой задачи, решается и двойственная задача. Если проследить за получающимися преобразованиями двойственной таблицы и переменных u_i и x_j, записав таблицу для двойственной задачи в обычном виде, то получим описание нового метода: метода последовательного уточнения оценок.

Пусть дана задача:

Симплексая таблица, построенная для данной задачи, будет иметь вид:

В методе последовательного уточнения оценок сначала избавляются от отрицательности в W-строке (получают псевдоплан), а затем, перебирая псевдопланы, ищут оптимальный план (первый найденный опорный).

Правило выбора разрешающего элемента

Если все коэффициенты W-строки неотрицательны, то 0 является оценкой снизу для целевой функции W и можно переходить к отысканию оптимального решения. Иначе выбираем некоторый b_r < 0 рассматриваем r-й столбец.

Находим в r-м столбце какой-нибудь из отрицательных элементов, например, a_rs. Тогда строку с номером s, содержащую a_rs, выбираем в качестве разрешающей строки. Если все коэффициенты r-го столбца неотрицательны, то либо W неограничена снизу (), либо система ограничений противоречива. (Из противоречивости двойственной не следует неограниченность прямой задачи).

Находим неотрицательное отношение коэффициента W-строки к коэффициентам разрешающей (s-й) строки. В качестве разрешающего берем тот элемент разрешающей s-й строки, для которого это отношение положительно и минимально, т.е. выбираем некоторый коэффициент a_sk, для которого .

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

Если все q₁, ..., q_n - неотрицательны, то таблица соответствует оптимальному решению и q₀ = min W, иначе, q₀ - оценка снизу для W.

Правило выбора разрешающего элемента при поиске оптимального решения.

В качестве разрешающей строки берем строку, содержащую отрицательный коэффициент, например, q_s < 0, и строка с номером s будет разрешающей.

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

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

После выбора разрешающего элемента делаем шаг обыкновенного жорданова исключения.

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

Замечание

Если в симплекс-методе мы приближаемся к оптимальному решению при поиске минимума сверху, передвигаясь по опорным планам, то в методе последовательного уточнения оценок при поиске минимума к оптимальному решению снизу, причем промежуточные планы (псевдопланы) не являются опорными (лежат вне многогранника решений). Первое же допустимое решение (опорный план) будет оптимальным.