Несиметричні задачі

max F = CX AX = B X  0	min Z = BY A^TY  C Y
min F = CX AX = B X  0	max Z = BY A^TY  C Y

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

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

Лема 3.1 (основна нерівність теорії двоїстості). Якщо та — допустимі розв’язки відповідно прямої та двоїстої задач, то виконується нерівність

або . (3.7)

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

Маємо:

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

. (3.8)

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

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

(3.9)

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

.

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

Лема 3.2 (достатня умова оптимальності). Якщо та — допустимі розв’язки відповідно прямої та двоїстої задач, для яких виконується рівність

(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 матрицю, що утворена з компонент векторів А₁, А₂,…, А_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).

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

.

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

Доведена теорема дає змогу в процесі розв’язування однієї задачі водночас знаходити план другої.

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