Основні властивості та теореми двоїстості

Властивості допустимих розв’язків двоїстих задач сформулюємо як теореми двоїстості.

 

Властивість 1. (Основна нерівність теорії двоїстості) Якщо і – допустимі розв’язки прямої (2.8) – (2.10) і двоїстої (2.11) – (2.13) задач, то .

Доведення. Помножимо обмеження (2.9) на відповідні двоїсті невідомі , дістанемо

, . (2.19)

Знак нерівності не змінюється, оскільки всі . Додамо ліві і праві частини нерівностей (2.19):

(2.20)

Аналогічні операції проведемо з обмеженнями(2.12):

(2.21)

Подвійні суми в нерівностях (2.20) і (2.21) являють собою різні форми запису одного й того самого виразу

,

отже, ці нерівності можна об’єднати

.

Остаточно основна нерівність теорії двоїстості для значень цільових функцій на допустимих розв’язках матиме вигляд

. (2.22)

Властивість 2. Якщо і – допустимі розв’язки взаємно двоїстих задач (2.8) – (2.10) та (2.11) – (2.13) і , то – оптимальні розв’язки цих задач.

Доведення. Будемо доводити властивість від супротивного. Припустимо існує оптимальний розв’язок прямої задачі , для якого . Але тоді повинна справджуватися нерівність , що суперечить основній нерівності теорії двоїстості (2.22). Отже вихідне припущення – хибне, тобто для будь-якого допустимого, в тому числі й опорного розв’язку задачі (2.8) – (2.10) справедливо , а це і означає, що є оптимальним розв’язком прямої задачі. Аналогічно можна довести, що – оптимальний план двоїстої задачі (2.11) – (2.13).

Теорема 1. (Перша теорема двоїстості – теорема про мінімакс). Якщоодна з двоїстих задач має розв’язок, то інша також має розв’язок, і оптимальні значення цільових функцій на розв’язках цих задач однакові, тобто

(2.23)

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

Наслідок. Для того щоб обидві взаємно двоїсті задачі мали розв’язок необхідно і достатньо, щоб кожна з них мала принаймні по одному допустимому розв’язку.

Теорема 2. (Друга теорема двоїстості – двоїстий критерій оптимальності). Допустимі розв’язки і двоїстих задач відповідно (2.14) – (2.16) та (2.17) – (2.18) тоді і тільки тоді є оптимальними розв’язками цих задач, коли виконуються рівності

(2.24)

Якщо розглядається пара симетричних двоїстих задач (2.8) – (2.10) та (2.11) – (2.13), то повинні виконуватися ще і рівності

(2.25)

Рівності (2.24), (2.25) називають умовами доповняльної нежорсткості. Із цих рівностей випливає, що коли деяке обмеження задачі на оптимальному розв’язку не перетворюється на точну рівність, то відповідна невідома оптимального розв’язку двоїстої задачі обов’язково дорівнює нулю.

Далі буде показано, як за допомогою наведених рівностей на основі відомого розв’язку задачі лінійного програмування можна знайти оптимальний розв’язок двоїстої задачі.