Перша теорема подвійності

У прямій і подвійною завданнях є оптимальні рішення, при цьому значення цільових функцій збігаються: f(х)= g(y).

Економічний сенс 1-ої теореми подвійності наступний. План виробництва x і набір оцінок ресурсів у виявляються оптимальними тоді і тільки тоді, коли загальна вартість продукції, визначена при відомих заздалегідь цінах продукції, дорівнює витратам на ресурси по «внутрішніх» (визначуваним тільки з рішення задачі) цінах ресурсів у. Для всіх же інших планів x і у обох завдань прибуток від продукції завжди менше (або рівна) вартості витрачених ресурсів: f(x)< g(y), тобто цінність всієї випущеної продукції не перевершує сумарної оцінки наявних ресурсів. Значить, величина g(y)- f(x) характеризує виробничі втрати залежно від даної виробничої програми і вибраних оцінок ресурсів.

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

Друга теорема подвійності

Хай - допустиме рішення прямої задачі, а - допустиме рішення подвійної задачі. Для того, щоб вони стали оптимальними рішеннями необхідно і достатньо, щоб виконувалися наступні співвідношення:

Дані умови дозволяють, знаючи оптимальне вирішення одного з взаємно подвійних завдань, знайти оптимальне рішення іншої задачі.

З 2-ої теореми подвійності виходять такі вимоги на оптимальну виробничу програму і оптимальний вектор оцінок :

якщо те

якщо те

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

якщо те

якщо те .

З даних умов виходить, що якщо j-й вид продукції увійшов до оптимального плану, то він в оптимальних оцінках не збитковий, якщо ж j-й вид продукції збитковий, то він не увійде до плану, тобто не випускатиметься. Теорема про оцінки

Значення змінних у, в оптимальному рішенні подвійної задачі є оцінками впливу вільних членів bi системи обмежень-нерівностей прямого завдання на величину Дf(x)=Дb_iy_i.

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

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

y1- подвійна оцінка ресурсу праця, або «ціна» праці;

y2 - подвійна оцінка ресурсу сировина, або «ціна» сировини;

y3 - подвійна оцінка ресурсу устаткування, або «ціна» устаткування.

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

Необхідно знайти такі «ціни» на ресурси yi, щоб загальна вартість використовуваних ресурсів була мінімальною.

Обмеження. Число обмежень в системі подвійного завдання дорівнює числу змінних в початковому завданні. У початковому завданні чотири змінних, отже, в подвійному завданні чотири обмеження. Правими частинами в обмеженнях подвійного завдання є коефіцієнти при невідомих в цільовій функції початкового завдання. Ліва частина обмеження визначає вартість ресурсів, витрачених на виробництво одиниці продукції. Кожне обмеження відповідає певному виду продукції.

,

,

,

,

Рішення подвійної задачі можна знайти в звіті Пошуку рішень - звіті по стійкості. Тіньові ціни ресурсів праця, сировина і устаткування відповідно дорівнюють 4/3, 0, 1/3 або в десяткових дробах: 1,3333; 0; 0,3333.

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

1. Аналіз використання ресурсів в оптимальному плані виконується за допомогою співвідношень 2-ої теореми подвійності:

якщо те

якщо те

Ресурси працю і устаткування мають відмінні від нуля оцінки 4/3 і 1/3 - ці ресурси повністю використовуються в оптимальному плані, є дефіцитними, стримуючими зростання цільової функції. Праві частини цих обмежень дорівнюють лівим частинам:

,

,

,

Ресурс «сировина» використовується не повністю (280 < 480), тому має нульову подвійну оцінку

,

.

Цей ресурс не впливає на план випуску продукції.

Загальна вартість використовуваних ресурсів при випуску 30 килимів другого вигляду і 10 килимів третього вигляду складе 150 тис. крб.

тис. крб. Не використаний повністю в оптимальному плані ресурс отримує нульову оцінку. Нульова оцінка ресурсу свідчить про його недефіцитність. Ресурс недефіцитний не із-за його необмежених запасів (вони обмежені величиною bi), а із-за неможливості його повного використання в оптимальному плані. Оскільки сумарна витрата недефіцитного ресурсу менше його загальної кількості, то план виробництва їм не лімітується. Даний ресурс не перешкоджає і далі максимізувати цільову функцію f(x).

2. Аналіз ефективності окремих варіантів плану виконується на основі співвідношень з 2-ої теореми подвійності:

якщо те

якщо те .

Якщо виріб увійшов до оптимального плану (xj > 0), то в подвійних оцінках воно не збиткове, тобто вартість ресурсів, витрачених на виробництво одиниці виробу, дорівнює його ціні. Такі вироби ефективні, вигідні з погляду прийнятого критерію оптимальності. У нашому завданні це килими другого і третього видів. Якщо вартість ресурсів, витрачених на виробництво одного виробу, більше його ціни, то цей виріб не увійде до оптимального плану із-за його збитковості. У нашому завданні до плану випуску не увійшли килими першого і четвертого видів, тому, що витрати по ним перевищують ціну на 7 (10-3) тис. крб. і 9.666 (10,666 - 1) тис. крб. відповідно. Це можна підтвердити, підставивши в обмеження подвійного завдання оптимальні значення вектора у.

,

,

,

.

Різницю між правими і лівими частинами обмежень подвійного завдання можна знайти в Звіті по стійкості в стовпці «Нормована вартість».

3. Аналіз впливу зміни правих частин обмежень на значення цільової функції (чутливість вирішення до зміни запасів сировини) виконується за допомогою теореми про оцінки.

Припустимо, що запас сировини ресурсу «праця» змінилася на 12 ед., тобто складає 80 + 12 = 92 ед. З теореми про оцінки відомо, що коливання величини bi приводить до збільшення або зменшення f(x). Воно визначається величиною уi у разі, коли при зміні величин bi значення змінних уi в оптимальному плані відповідного подвійного завдання залишаються незмінними. У нашому завданні збільшення запасів ресурсу «праця» приведе до збільшення значення цільової функції на 16 тис. крб. . Для подвійних оцінок оптимального плану вельми істотне значення має їх граничний характер. Точною мірою впливу обмежень на функціонал оцінки є лише при малому прирості обмеження. Відомо, що оцінки не міняють своєї величини, якщо не міняється набір векторів, що входять в базис оптимального плану, тоді як інтенсивності цих векторів (значення невідомі) в плані можуть мінятися. Тому необхідно знати такі інтервали зміни кожного з вільних членів системи обмежень початкової ЗЛП, або інтервали стійкості подвійних оцінок, в яких оптимальний план подвійного завдання б не мінявся. Цю інформацію можна отримати із Звіту по стійкості. У нашому завданні в нижчеприведеному фрагменті звіту видно, що запаси дефіцитних ресурсів «праця» і «устаткування » можуть бути як зменшені, так і збільшені, збільшення запасу ресурсу «сировина» не вплине на план випуску продукції.

После увеличения запаса ресурса «труд» до 92 чел./ч было получено новое решение задачи. Изменение запасов ресурсов в пределах интервалов устойчивости двойственных оценок привело не только к изменению значения целевой функции на 16 тыс. руб., но и к изменению плана выпуска. При этом структура плана не изменилась - изделия, которые были убыточны, не вошли и в новый план выпуска, так как цены на ресурсы не изменились. Новый план выпуска составляет 28 ковров второго вида и 18 ковров третьего вида. Изменение общей стоимости продукции на 16 тыс. руб. (24 - 8 = 16) получено за счет уменьшения на 2 ед. ковров второго вида по цене 4 тыс руб. (4 тыс. руб. x (28 - 30) = -8 тыс. руб.) и увеличения на 8 ед. ковров третьего вида по цене 3 тыс. руб. (3 тыс. руб. х (18-10) = 24 тыс. руб.).

4. Чутливість вирішення до зміни коефіцієнтів цільової функції початкового завдання.

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