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

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

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

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

Приклад 5.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

 

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

Таблиця 5.1. Симплекс-таблиця оптимального розв’язку прямої задачі

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

Початковими базисними змінними прямої задачі є x4 та R. Змінна x4 прямої задачі асоціюється з обмеженням  y1³0 двоїстої задачі. Різниця між лівою та правою частинами цього обмеження, згідно співвідношення двоїстості, має дорівнювати z-коефіцієнту при змінній x4 в таблиці 5.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.

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

 

Рис. 5.1. Схема пошуку оптимального розв’язку пари сполучених задач

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

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

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

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

5.4. Економічна інтерпретація двоїстості

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

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

2. На будь-якій ітерації процесу розв’язання прямої задачі коефіцієнт z-рівняння при змінній xj дорівнює різниці між лівою і правою частинами відповідного обмеження двоїстої задачі.

Ці відношення дозволяють дати економічну інтерпретацію двоїстості. Для цього розглянемо пряму задачу як задачу розподілу обмежених ресурсів з цільовою функцією, що підлягає максимізації. Нехай кожен коефіцієнт cj цільової функції прямої задачі являє собою прибуток на одиницю продукції j-го виду виробничої діяльності. Витрати ресурсу і, запаси якого обмежені величиною bі, на одиницю продукції j-го виду виробничої діяльності дорівнює aij одиницям цього ресурсу.

Дамо економічну інтерпретацію обом результатам, які були сформульовані на початку даного розділу.

5.4.1. Економічна інтерпретаія змінних двоїстої задачі

 Запишемо умову рівності цільових функцій у вигляді:

zopt=wopt=  .

Проаналізуємо цю формулу з точки зору розмірностей величин, які вона містить. Оскільки z являє собою розмір прибутку, що вимірюється в грошових одиницях; а bi - кількість i-го ресурсу в прийнятих одиницях виміру, то величина yi повинна виражатись у грошових одиницях на одиницю i-го ресурсу.

Таким чином, кожна змінна двоїстої задачі являє собою цінність i-го ресурсу. Тому іноді двоїсті змінні називають тіньовими цінами.

5.4.2. Економічна інтерпретаія обмежень двоїстої задачі

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

(Z-коефіцієнт при xj )=  (5.1)

Проаналізуємо цей вираз щодо величин, які він містить. Оскільки Cj являє собою прибуток на одиницю j-го виду виробничої діяльності, то ця величина має вимірюватись у грошових одиницях (г.о./од. продукції). Із умови узгодженості розмірностей витікає, що величина  також повинна мати розмірність г.о./од. При цьому  має відповідати деяким питомим витратам (або “вартості”). Величина aij – це кількість і-го ресурсу, що використовується для випуску одиниці продукції j-го виду виробничої діяльності, тому змінна yi має являти собою “внутрішню” (тіньову) ціну одиниці і-го ресурсу, і член  можна розглядати як сумарну оцінку всіх ресурсів, які використовуються при виробництві одиниці продукції j-го виду виробничої діяльності. Така інтерпретація призводить до такого запису рівняння (5.1) у відповідних одиницях виміру:

[г.о. (прибуток або витрати)/од.]= [г.о. (витрати)/од.]-[г.о. (прибуток / од.]

Умова оптимальності (в задачі максимізації), що використовується в симплекс-методі, полягає в тому, що вид виробничої діяльності, відсутній у поточному розв’язку (і якому відповідає небазисна змінна xj =0) має вводитись у наступний розв’язок з додатнім рівнем використання (xj >0) тільки в тому випадку, коли z-коефіцієнт при данній змінній є від’ємним. У протилежному випадку збільшення використання даного виду виробничої діяльності не призведе до покращання значення цільової функції. Дамо економічну інтерпретацію цій умові, використавши результати аналізу розмірностей. Невикористаний вид виробничої діяльності j має бути представлений у розв’язку тільки в тому випадку, коли:

 <0, тобто коли:

 .

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

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

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