Метод последовательного улучшения допустимого вектора (МПУ)

Метод последовательного улучшения допустимого вектора (МПУ)

Метод последовательного улучшения допустимого вектора (МПУ)

МПУ состоит в последователь­ном выполнении идентичных шагов (опишем вычислительные процедуры одного шага). К началу очередного шага пусть имеются некоторое ДБМ К и отвечающий ему допустимый вектор х(K) = (х₁, х₂, . . ., х_п). Над этими исходными данными выполняются следующие процедуры:

I. Определение вектора y(К).

Зная базисные векторы и допустимый базисный вектор =( х₁, х₂, . . ., х_m, 0,…,0), решаем систему линейных уравнений:

Эта система имеет единственное решение , т.к. К – это базисное множество.

II. Проверка двойственной допустимости ДБМ К.Для найденного вектора у(К) вычисляются величины и проверяются неравенства , .

1. Находим величины

При этом возможны два случая:

а) . Это означает, что базисное множество К является одновременно допустимым и двойственно допустимым базисным множеством. Тогда (потеореме: если базисное множество К является одновременно допустимым и двойственно допустимым базисным множеством, то отвечающие ему векторы и оптимальные соответственно в задачах А и А*) векторы х(К) и у (К) оптимальны для соответствующих задач и . На этом процесс заканчивается с выдачей искомых оптимальных векторов.

б) условие а) нарушается, т.е. К не является двойственно допустимым и вектор не допустимый в задаче А*. Надо найти и перейти к выполнению следующей процедуры.

III. Вычисление коэффициентов разложения вектора по базисным векторам.

Для этого решаем систему уравнений . Матрица этой системы совпадает с транспонированной матрицей системы, решаемой на процедуре 1, поэтому она также имеет единственное решение. В результате определяем

IV. Определение .Проверяем выполнение неравенств , . При этом возможны два случая.

(а) Все коэффициенты g_k неположительные. Тогда на основании следствия 1 векторы , опреде­ляемые в лемме 3, являются допустимыми в задаче А при всех , а линейная функ­ция на множестве таких векторов не ограничена сверху. Процесс на этом заканчи­вается с выдачей вектора х(К) и коэффициентов g_k.