8.Поняття двоїстості. Основні теореми двоїстості та їх економічний смисл на прикладі задачі раціонального використання ресурсів.

Теорія двоїстості – центральна частина лінійного програмування. Дослідження двоїстості дало можливість отримати важливі теоретичні (розробити ефективні методи розв’язування ЗЛП, проаналізувати та оцінити чутливість моделей лінійного програмування) і практичні (дати економічне тлумачення отриманого розв’язку, розкрити нові закономірності та співвідношення, властиві досліджуваній проблемі) результати.

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

Для виробництва п видів продукції витрачається т видів ресурсів. Відомо:

a_ij - норма витрати і-го виду ресурсів на одиницю продукції j-го виду (і =  ); (j = ).

b_i - запас ресурсу і-го виду на запланований період (і =  );

с_j - прибуток від реалізації одиниці продукції j-го виду (j = )..

Скласти план виробництва, що забезпечує максимальний прибуток.

Уведемо позначення: х_j - запланований випуск продукції j-го виду; Z - прибуток від реалізації всієї виробленої продукції.

Математична модель задачі. Знайти такі х_j, які забезпечують максимум функції

Z = c₁х₁ + с₂х₂ + … + с_nx_n (max)

і задовільняють обмеження

.

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

Складемо математичну модель і дамо економічну інтерпретацію двоїстої задачі відносно задачі (2.60)-(2.62).

Нехай у_і - ціна одиниці ресурсу і-го виду (і =  ), тоді вартість усіх ресурсів

f = b₁y₁ + b₂y₂ + ... + b_my_m.

Прибуток від продажу ресурсів, потрібних для випуску одиниці j-го виробу, має бути не меншим за прибуток від реалізації готового виробу:

a_1jy₁ + a_2jy₂ + … +a_mjy_m ³ c_j.

Отже, двоїсту задачу можна сформулювати так. Знаючи у₁, у₂, ..., у_т, які надають мінімуму функції

f = b₁y₁ + b₂y₂ + ... + b_my_m (min)

і задовольняють обмеження

.

Економічна інтерпретація двоїстої задачі: якими мають бути ціни одиниці ресурсів, щоб при заданих обсягах ресурсів (b_i) і прибутку від реалізації одиниці продукції (с_j) мінімізувати загальну вартість ресурсів; у_і називаються оцінками, або обліковими, неявними цінами. Ці оцінки (ціни) - відносні, оскільки одні й ті самі ресурси для різних підприємств мають різну цінність, а оцінки ресурсів для того самого підприємства також змінюються зі зміною обсягів ресурсів. Відносність оцінок обумовлена ще й тим, що вони виражаються в одиницях вартості продукції, що випускається.

Розрізняють симетричні та несиметричні пари двоїстих задач. Якщо системи основних обмежень як у вихідній, так і в двоїстій задачі мають вигляд нерівностей, то такі пари двоїстих задач називатимемо симетричними. При цьому на змінні двоїстої задачі також накладається умова невід’ємності.

Можна виділити два види математичних моделей симетричної пари двоїстих задач.

1. Вихідна задача

Z = C×X (max); A×X £ B;; X ³ 0

Двоїіста f = y×B (min); Y×A ³ С Y ³ 0.

2. Вихідна задача

Z = C×X (min); A×X ³ B; X ³ 0.

Двоїста задача f = y×B (max); Y×A £ С; Y ³ 0.

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

Несиметричні двоїсті пари задач також бувають двох видів.

3. Вихідна задача

Z = C×X (max); A×X = B; X ³ 0

Двоїста задача f = y×B (min); Y×A ³ С.4. Вихідна задача

Z = C×X (min); A×X = B; X ³ 0.

Двоїста задача f = y×B (max); Y×A £ С.

У разі побудови несиметричної пари змінюється третій етап. Оскільки у вихідній ЗЛП обмеження – рівняння, знаки нерівностей у двоїстій задачі визначаються видом екстремуму. Якщо f ® max, то обмеження „£”, якщо f ® min, то „³".