5.3. Співвідношення двоїстості.

Між прямою та двоїстою задачами існує тісний взаємозв'язок.  Оптимальний розв’язок однієї з пари сполучених задач можна одержати безпосередньо із сиплекс-таблиці з оптимальним розвязком задачі, що є двоїстою по відношенню до вихідної.

Згадані співвідношення між значеннями змінних сполучених задач називаються співвідношеннями двоїстості і полягають в наступному: коефіцієнт при початковій базисній змінній в оптимальному z-рівнянні прямої задачі дорівнює різниці між лівою та правою частинами обмеження двоїстої задачі, асоційованого з даною початковою змінною.

Розглянемо наступний приклад.

Приклад  4.3.

Задача лінійного програмування задана такою моделлю:

Z=5x1+12x2+4x3max 

 

 

У результаті зведення задачі до стандартної форми, введення штучних змінних та запису цільової функції у вигляді з невід’ємною правою частиною отримаємо:

Пряма задача: 

Z+(-5-2M)x1+(-12+2M)x2+(-4-3M)x3=-10M 

 

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

W=10y1+8y2min

Звівши модель двоїстої задачі до стандартної форми та ввівши штуні зміннні, матимемо: 

W+(-10+4M) y1+(-8+4 M)  + (8-4 M)  -My3-My4-My5=21M

У результаті незалежного розв’язання пари сполучених задач були отримані дві сиплекс-таблиці з відповідними оптимальними розв’язками:

 

 

Із таблиці 4.2 очевидно, що оптимальні значення двоїстих змінних складають: y1=29/5,  y2=y2 - y2 =0-2/5=-2/5. Той самий результат можна отримати із симплексної таблиці з оптимальним розв’язком прямої задачі (див. Табл. 4.1), скориставшись співвідношенням двоїстості. Покажемо це.

 

Початковимибазиснимизміннимипрямої задачіє x4 та R. Змінна x4 прямої задачі асоціюється з обмеженням  y10 двоїстої задачі. Різниця між лівою та правою частинами цього обмеження, згідно співвідношення двоїстості, має дорівнювати z-коефіцієнту при змінній x4 в таблиці 4.1, тобто: y1-0=29/5. Звідси y1=29/5. Аналогічно знайдемо оптимальне значення двоїстої змінної y2 з рівняння: y2+М= -2/5+M, звідки y2=-2/5. Підставивши оптимальні значення змінних у рівняння цільової функції, отримаємо: wmin=10y1+8y2=1029/5+8(-2/5)=54 4/5.

Порівняння результатів, отриманих при розв’язанні прямої та двоїстої задач дозволяють зробити два цікавих висновки:

1. На ітерації, яка приводить до оптимуму, z max=wmin=54 4/5.

2. У задачі максимізації цільова функція послідовно зростає від початкового значення z=-8М до оптимального z=54 4/5. У задачі мінімізації цільова функція послідовно зменшується від початкового значення w=21М до оптимальаного w=54 4/5.

З порівняння таблиць 4.1 та 4.2 видно, що значення цільових функцій в оптимальних розв’язках прямої та двоїстої задач збігаються. В задачі максимізації значення цільової функції поступово збільшується від початкового значення z=-8M  до z opt=54 4/5. В задачі мінімізації - поступово зменшується від w=21M  до wopt=54 4/5. Звідси випливає, що процеси максимізації та мінімізації збігаються в деякій "точці рівноваги", що досягається при рівності цільових функцій двох сполучених задач. Такий результат є наслідком першої теореми двоїстості. Цей висновок ілюструє рис. 4.1. Наведена схема показує, що значення цільової функції в будь-якому допустимому розв’язку задачі мінімізації завжди є верхньою границею значень цільової функції в будь-якому допустимому розв’язку задачі максимізації. Отже, процеси максимізації та мінімізації збігаються в деякій “точці рівноваги”, після досягнення якої цільові функції задач покращити неможливо. Така точка досягається при рівності цільових функцій обох задач і відповідає їх оптимальним розв’язкам.

           

 

 

 

 

 

 

 

 

 

 

 

Рис. 4.1.

 

По відношенню до будь-якої пари спряжених задач отримані результати можна узагальнити наступним чином.

1.  Для будь-якої пари допустимих розв’язків прямої та двоїстої задач значення цільової функції в задачі максимізації ніколи не перевищує значення цільової функції в задачі мінімізації.

2.  У точці, що відповідає оптимальним розв’язкам прямої та двоїстої задач, значення цільових функцій цих задач співпадають.

Зазначимо таку важливу обставину: отримані результати не залежать від того, як із задач є прямою, а яка – двоїстою. Єдине, що слід брати до уваги, - це напрямок оптимізації (максимізація або мінімізація). При цьому пряма задача може бути задачею мінімізації, а двоїста – задачею максимізації.