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

Пара двойственных задач линейного программирования рассматривается в асимметричной форме.

Задача А. При заданных вещественных числах в_i , c_j , a_ij , i I={1, 2, …, m}, j J={1, 2, …, n} максимизировать функцию

μ(х) = c_j x_j

на множестве n-мерных векторов

x = ( x₁, x₂,…, x_n ),

удовлетворяющих условиям:

х _j 0, j J,

a_ij x_j + b_i 0 , i  I .

Задача А*. При исходных данных задачи А минимизировать функцию

ν(y)= b_i y_i

на множестве векторов

y= (y₁, y₂,…, y_m),

удовлетворяющих условиям

a_ij y_i + c_j 0, j J.

Введем m-мерные векторы

β = (b₁, b₂, …, b_m),

α ^j=(a_1j, a_2j, …, a_mj), j J,

и перепишем задачи А и А* в следующем виде.

Задача А_м. Максимизировать линейную функцию

μ (x)= с_j x_j (1)

на множестве n-мерных векторов

x=(x₁, x₂, …, x_n), (2)

удовлетворяющих условиям

x_j 0, j J, (3)

x_j α ^j+ β=0. (4)

Задача А_м*. Минимизировать линейную функцию

ν(y)=( β, y) (5)

на множестве m-мерных векторов

y= (y₁, y₂,…y_m), (6)

удовлетворяющих системе линейных неравенств

(α ^j, y)+ c_j 0, jJ. (7)

В методе последовательного улучшения важную роль выполняют m-элементные подмножества К множества J. Множества К называются базисными (б.м), если соответствующие векторы { α ^k} kK образуют базис в R^m. Очевидно, что для б.м. К имеют единственное решение системы уравнений

x_k α ^k+β=0, (8)

(α^k,y) + c_k =0, kK. (9)

Обозначим через x(K) решение системы (8), дополненное до n-мерного вектора. x(K) – допустимый вектор, если его компоненты не отрицательные, множество К – допустимое базисное множество, д. б. м. К.

Обозначим y(K) – решение системы (9) и

Z_j=( ^j,y(K))+c_j, j  J (10)

y(K) – двойственно допустимый вектор, если

z_j 0, jJ (11)

множество К в этом случае является двойственно допустимым базисным множеством , д. д. б. м. К.

Метод последовательного улучшения основан на следующем утверждении.

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

μ(х(К)) = ν(у(К)) (12)