Контрольная работа: Двоїста задача лінійного програмування: економічна інтерпретація знаходження оптимальних планів

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

(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	…	« 1 2 3 4 5 6 7 8 9 10 » К-во Просмотров: 375 Бесплатно скачать Контрольная работа: Двоїста задача лінійного програмування: економічна інтерпретація знаходження оптимальних планів >>> Скачать <<< Меню Поиск