Третя теорема двоїстості. Економічне тлумачення.
Теорема (третя теорема двоїстості). Компоненти оптимального плану двоїстої задачі Неможливо розібрати вираз (невідома помилка): y_i^*
Неможливо розібрати вираз (невідома помилка): (i=1,n) дорівнюють значенням частинних похідних від цільової функції Неможливо розібрати вираз (невідома помилка): F(b_1,b_2...,b_m) за відповідними аргументами Неможливо розібрати вираз (невідома помилка): b_i
,Неможливо розібрати вираз (невідома помилка): (i=1,n)
або
Неможливо розібрати вираз (невідома помилка): dF/db_i=y_i^*
,Неможливо розібрати вираз (невідома помилка): i=1,2,...,m
19:19, 3 травня 2012 (EEST)Sergkyl(3.28)</math></center>
Доведення. Розглянемо задачу лінійного програмування, подану в канонічній формі:
Неможливо розібрати вираз (невідома помилка): maxF=c_1x_1+c_2x_2+...+c_nx_n
19:17, 3 травня 2012 (EEST)Sergkyl (3.29)
Неможливо розібрати вираз (невідома помилка): x_j\ge 0
,Неможливо розібрати вираз (невідома помилка): j=1,n
19:17, 3 травня 2012 (EEST)Sergkyl (3.31)
Двоїсту задачу до задачі (3.29)-(3.31) сформулюємо так: знайти оптимальний план Неможливо розібрати вираз (невідома помилка): Y^*=(y_1^*,y_2^*,...,y_m^*)
,за якого мінімізується значення
Неможливо розібрати вираз (невідома помилка): Z=b_1y_1+b_2y_2+...+b_my_m (3.32) за умов:причому умова невід’ємності змінних Неможливо розібрати вираз (невідома помилка): y_i^*
Неможливо розібрати вираз (невідома помилка): (i=\overline{1,n})
відсутня.
Позначимо Неможливо розібрати вираз (невідома помилка): Y^*=(y_1^*,y_2^*,...,y_m^*)
— оптимальний план двоїстої задачі,Неможливо розібрати вираз (невідома помилка): X^*=(x_1^*,x_2^*,...,x_m^*) — оптимальний план задачі Неможливо розібрати вираз (невідома помилка): (3.29)
-Неможливо розібрати вираз (невідома помилка): (3.31) . За першою теоремою двоїстості відомо, що:Неможливо розібрати вираз (невідома помилка): maxF=c_1x_1+c_2x_2+...+c_nx_n=minZ=b_1y_1^*+b_2y_2^*+...+b_my_m^*
або Неможливо розібрати вираз (невідома помилка): F=b_1y_1^*+b_2y_2^*+...+b_my_m^*
19:17, 3 травня 2012 (EEST)Sergkyl(3.34)
Оскільки досліджується питання впливу зміни значень Неможливо розібрати вираз (невідома помилка): b_i
,Неможливо розібрати вираз (невідома помилка): (i=1,n)
на Неможливо розібрати вираз (невідома помилка): F , то лінійну функцію (3.34) можна розглядати як функцію від аргументів Неможливо розібрати вираз (невідома помилка): b_i
,Неможливо розібрати вираз (невідома помилка): (i=1,n) .Тоді частинні похідні за змінними Неможливо розібрати вираз (невідома помилка): b_i ,Неможливо розібрати вираз (невідома помилка): (i=1,n)
будуть дорівнювати компонентам оптимального плану двоїстої задачі Неможливо розібрати вираз (невідома помилка): y_i^* :Неможливо розібрати вираз (невідома помилка): dF/db_i=y_i^* ,Неможливо розібрати вираз (невідома помилка): i=1,2,...,m
19:17, 3 травня 2012 (EEST)Sergkyl(3.35)
Однак дане твердження справедливе лише у тому разі, коли компоненти оптимального плану Неможливо розібрати вираз (невідома помилка): Y^*=(y_1^*,y_2^*,...,y_m^*)
залишаються постійними, а оскільки за першою теоремою двоїстості Неможливо розібрати вираз (невідома помилка): Y^*=C^*D^{-1}
, то значення двоїстих оцінок будуть незмінними лише за умови постійної структури оптимального плану початкової задачі.
Отже, рівності (3.35) справджуються лише за незначних змін Неможливо розібрати вираз (невідома помилка): b_i ,інакше суттєва зміна умов початкової задачі (правих частин системи обмежень (3.30) та цільової функції (3.32) приведе до зміни базису в оптимальному плані прямої задачі, а значить, і до іншого розв’язку двоїстої Неможливо розібрати вираз (невідома помилка): Y^{~}\ne Y^* .
Економічний зміст третьої теореми двоїстості. Двоїсті оцінки є унікальним інструментом, який дає змогу зіставляти непорівнянні речі. Очевидно, що неможливим є просте зіставлення величин, які мають різні одиниці вимірювання. Якщо взяти як приклад виробничу задачу, то цікавим є питання: як змінюватиметься значення цільової функції (може вимірюватися в грошових одиницях) за зміни обсягів різних ресурсів (можуть вимірюватися в тоннах, Неможливо розібрати вираз (невідома помилка): M^2
, люд./год, га тощо).Використовуючи третю теорему двоїстості, можна легко визначити вплив на зміну значення цільової функції збільшення чи зменшення обсягів окремих ресурсів: числові значення двоїстих оцінок показують, на яку величину змінюється цільова функція за зміни обсягу відповідного даній оцінці ресурсу
