3. Основні теореми двоїстості та їх економічний зміст

Зв’язок між оптимальними розв’язками прямої та двоїстої задач встановлюють леми та теореми двоїстості. Розглянемо задачі (3.1) – (3.3) та (3.4) – (3.6) з економічною інтерпретацією.

Якщо та – допустимі розв’язки відповідно прямої та двоїстої задач, то виконується нерівність

або . (3.7)

Доведення. Помножимо кожне рівняння системи (3.2) на відповідну змінну двоїстої задачі:

Підсумувавши праві і ліві частини нерівностей, отримаємо:

. (3.8)

Аналогічно перетворимо систему обмежень (3.5) двоїстої задачі:

Підсумувавши після множення тут також ліві та праві частини, отримаємо нерівність:

(3.9)

Ліві частини нерівностей (3.8) та (3.9) збігаються, отже:

.

Нерівність (3.7) доведено.

Якщо та – допустимі розв’язки відповідно прямої та двоїстої задач, для яких виконується рівність

(3.10)

то X*, Y* – оптимальні розв’язки відповідних задач.

Доведення. Нехай – допустимий план прямої задачі (3.1) – (3.3). Тоді на підставі нерівності (3.7) маємо: . За умовою задачі , отже

(3.11)

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

В аналогічний спосіб доводиться, що – оптимальний план двоїстої задачі.

3.1 Перша теорема двоїстості

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

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

Доведення. Допустимо, що початкова задача (3.1) – (3.3) має оптимальний план, який отриманий симплексним методом. Не порушуючи загальності, можна вважати, що останній базис складається з першихm векторів . Остання симплексна таблиця має вигляд:

Таблиця 3.1

і	Базис	Сб	План	с1	с2	…	сm	cm + 1	…	cn
				x1	x2	…	xm	xm + 1	…	xn
1	x1			1	0	…	0		…
2	x2			0	1	…	0		…
m	xm			0	0	…	1		…
m + 1			F0	0	0	…	0		…

Позначимо через D матрицю, що утворена з компонент векторів А1, А2,…, Аm останнього базису в першій симплексній таблиці.

Для оптимального плану отримаємо:

(3.12)

де , В-вектор, що складається з вільних членів системи обмежень.

Звідси:

(3.13)

Симплексна таблиця 3.1 містить коефіцієнти розкладу векторів початкової системи обмежень задачі за векторами базису, тобто кожному вектору з системи обмежень задачі (3.1) – (3.3) Аj відповідає в симплексній таблиці вектор , такий що

(3.14)

Позначимо через матрицю, що складається з коефіцієнтів розкладу векторів . Тоді буде справджуватися рівність:

, звідки

. (3.15)

Враховуючи (3.13), значення оптимального плану даної задачі знаходиться у вигляді:

де , причому

,

тобто всі компоненти вектора є оцінками оптимального плану задачі (3.1) – (3.3), а тому

. (3.16)

Оскільки оптимальний план початкової задачі подано у вигляді , то за правилами побудови двоїстої задачі можна допустити, що її оптимальний план матиме вигляд:

. (3.17)

Доведемо, що дійсно є оптимальним планом двоїстої задачі.

Система обмежень двоїстої задачі у векторно-матричній формі матиме вигляд: .

Підставимо в цю нерівність значення . Тоді, враховуючи (3.15), (3.16) та (3.17), отримаємо: .

Звідки: . Отже, задовольняє систему обмежень (3.5) двоїстої задачі, тому є допустимим планом задачі (3.4) – (3.6).

Для даного плану значення функціонала дорівнюватиме:

, (3.18)

де . Підставимо в (3.18) значення з (3.17) та, враховуючи (3.13), матимемо:

. (3.19)

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

Отже, за лемою 3.2 (достатня умова оптимальності плану задачі лінійного програмування) план є оптимальним планом двоїстої задачі (3.4) – (3.6).

Аналогічно доводиться, що коли двоїста задача має розв’язок, то початкова також має розв’язок і виконується рівність: .

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

Економічний зміст першої теореми двоїстості. Максимальний прибуток (Fmax) підприємство отримує за умови виробництва продукції згідно з оптимальним планом , однак таку саму суму грошей ( ) воно може мати, реалізувавши ресурси за оптимальними цінами . За умов використання інших планів на підставі основної нерівності теорії двоїстості можна стверджувати, що прибутки від реалізації продукції завжди менші, ніж витрати на її виробництво.