Двоїсті (спряжені) задачі лінійного програмування

Модель пари двоїстих задач у загальній формі. В загальному випадку для кожної задачі ЛП у загальній формі запису можна поставити у відповідність двоїсту (спряжену) для неї задачу (табл.2.6, 2.7).

Таблиця 2.6

Вихідна задача ЛП	Спряжена задача ЛП

Таблиця 2.7

Моделі спряжених задач
Симетричні моделі	Несиметричні моделі
Вихідна	Спряжена	Вихідна	Спряжена

Правила формування двоїстих задач формулюються таким чином.

1. Одна з двох спряжених задач є задачею пошуку максимуму лінійної форми, а друга – мінімуму лінійної форми.

2. Матрицю обмежень спряженої задачі визначають шляхом тран­спонування матриці вихідної задачі.

3. Коефіцієнти лінійної форми спряженої задачі є вільними членами системи обмежень вихідної задачі.

4. Вільні члени системи обмежень спряженої задачі є коефіцієнтами лінійної форми вихідної задачі.

5. Кожній змінній прямої задачі відповідає одне обмеження спряженої задачі, причому якщо j -а змінна невід’ємна, то j -им обмеженням спряженої задачі буде нерівність із знаком ³ (не менше) і навпаки; змінним, які не мають обмеження на знак, відповідають обмеження рівності.

6. Кожному обмеженню прямої задачі відповідає одна змінна спря­женої задачі, причому якщо і -е обмеження нерівністю типу £ (не більше), то і - а змінна спряженої задачі – невід’ємна; обмеженням у вигляді рівностей відповідають змінні без обмеження на знак.

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

Основні теореми двоїстості. Властивості основної теореми двоїстості можна описати у вигляді таблиці (табл. 2.8).

Таблиця 2.8

Двоїста задача	Пряма задача
Має плани	Немає планів
Має плани	max F(x)=min G(l)	min G(l)® - ¥
Немає планів	Max F(x) ® ¥	Можливо

Друга теорема двоїстості надає властивості оптимальних планів парі спряжених задач (умови доповняльної нежорсткості):

Розв’язавши одну з пари симетричних задач, можна за значеннями в (m+1)-му рядку кінцевої симплекс-таблиці визначити значення змінних оптимального плану другої задачі. Оптимальні значення змінних двоїстої задачі знаходять із співвідношень:

Наприклад, у задачі:

розв’язок якої наведено у таблиці нижче, з останньої таблиці знаходимо, що . Аналогічно з індексного рядка кінцевої таблиці, що відповідає оптимальному плану двоїстої задачі, маємо, щоx_j^* = - D _m+j^под, j=1,n.

Якщо розглядати несиметричні задачі, то співвідношення для визначення змінних оптимального плану двоїстої задачі набуде вигляду де A^-1_x – матриця, обернена до матриці векторів остан­нього базису. Коли ж ви­хідна задача зведена до одиничного базису, обчислення оберненої матриці не потрібне, бо A^-1_x містить колонки кінцевої таблиці на місці колонок одиничних векторів початкової таблиці.

I	Б	C	X
Р 1	Р 2	Р 3	Р 4
	Р 3				-1
	Р 4
m +1			-3	-2
I	Б	C	X
	Р 3				-1
	Р 4					-2
m +1				-5
I	Б	C	X
Р 1	Р 2	Р 3	Р 4
	Р 3		8/3				1/3
	Р 4		2/3			-2/3	1/3
m +1					-1/3	5/3
I	Б	C	X
Р 1	Р 2	Р 3	Р 4
	Р 3
	Р 4
m +1

Приклад 2.8. Сформулюємо задачу, двоїсту до такої задачі:

Перепишемо систему обмежень у вигляді

Тоді двоїста задача набуде вигляду:

Приклад 2.9. Розв’язати ЗЛП за допомогою геометричної інтерпретації двоїстої задачі:

Двоїста до неї задачамає вигляд:

а її геометрична інтерпретація зображена на рисунку нижче.

Пряма рівняння G(l) досягає найменшого значення в точці А, де l^*₁=7/2, l^*₂=5/2. Тоді G(l^*)=23 унаслідок основної теореми F(X^*)=23.

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

З оптимального плану спряженої задачі маємо, що в другому та третьому співвідношеннях виконується рівність, тоді x₂ ¹0, x₃ ¹0, у той час як x₁= 0, x₄=0 оскільки в першомута четвертому співвідно­шенняхрівність не виконується.