Враховуючи, що

(y⁰, A x⁰) = y⁰_i (a_ij x⁰_j) = x⁰_j (y⁰_i a_ij ) = (x⁰, A^Ty⁰ ),

отримуємо F(x⁰) ³ Q(y⁰), що і завершує доведення.

Наслідок 9.1. Якщо значення цільової функції F на деякому допустимому розв’язку x⁰ прямої задачі співпадає із значенням цільової функції Q на деякому допустимому розв’язку y⁰ двоїстої задачі, то ці допустимі розв’язки x⁰ і y⁰ оптимальні.

Наслідок 9.2. Якщо цільова функція прямої задачі необмежена, то двоїста задача недопустима, тобто її допустима область пуста.

Теорема 9.3 (Про зв’язок між оптимальними розв’язками прямої та двоїстої задач) Якщо пряма задача має розв’язок, то розв’язок має і двоїста задача, і розв’язок двоїстої задачі утворюється координатами вектору симплекс-множників оптимальної симплекс таблиці прямої задачі з протилежними знаками.

Доведення. Розглянемо пряму задачу після приведення її до канонічної форми. Непрямі обмеження мають вигляд

a₁₁ x₁ + a₁₂ x₂ +…+ a_1n x_n - x_n+1 = b₁,

a₂₁ x₁ + a₂₂ x₂ +…+ a_2n x_n - x_n+2 = b₂,

a_m1 x₁ + a_m2 x₂ +…+ a_mn x_n - x_n+m = b_m.

Індексному рядку оптимальної симплекс-таблиці відповідає рівняння

-F + (c₁ + a_i1 p_i) x₁ +(c₂ + a_i2 p_i) x₂ +…+ (c_n + a_in p_i) x_n - p_i x_n+i = b_i p_i, (9.9)

де p_i – симплекс-множники.

Кожний коефіцієнт (показаний у дужках) індексного рядку оптимальної симплекс-таблиці при пошуку мінімуму повинен бути невід’ємним. Тому маємо систему нерівностей

c_j + a_ij p_i ³ 0, j = 1, n. (9.10)

Коефіцієнти при додаткових змінних також повинні бути невід’ємні.

-p_i ³ 0, і = 1, m. (9.11)

З систем (9.10) і (9.11) прямує, що симплекс-множники, взяті з протилежним знаком, задовольняють обмеженням двоїстої задачі.

a_ij (-p_i) £ c_j, j = 1, n;

-p_i ³ 0, і = 1, m.

Оскільки у рівнянні (9.9) після підстановки оптимального опорного плану x⁰ = (x⁰₁, x⁰₂, …, x⁰_n) усі доданки, які містять змінні прямої задачі, дорівнюють нулю (коефіцієнти індексного рядка при базисних змінних дорівнюють нулю, а небазисні змінні самі дорівнюють нулю), можна записати:

F (x⁰) = b_i (-p_i ) = Q (-p),

де p = (p₁, p₂, …, p_m) – вектор симплекс-множників.

З наслідку 9.1 прямує, що значення цільової функції Q (-p) є оптимальним, що і завершує доведення.

Принцип комплементарності

Для симплекс-множників, відповідаючих оптимальному опорному плану прямої задачі, виконується система рівнянь

p_i x⁰_n+і = 0, і = 1, m. (9.12)

Аналогічно, для двоїстої задачі, симплекс-множники оптимального опорного плану y⁰ = (y⁰₁, y⁰₂, …, y⁰ _m) якої позначимо q_j, маємо

q _j y⁰_m+j = 0, j = 1, n. (9.13)

Дата добавления: 2014-01-13