Відмінності між версіями «Третя теорема двоїстості. Економічне тлумачення.»

Матеріал з Вікі ЦДУ
Перейти до: навігація, пошук
Рядок 2: Рядок 2:
 
Компоненти оптимального плану двоїстої задачі <math>y_{i}^{*}</math> <math>i=\overline{1,n}</math> дорівнюють значенням частинних похідних від цільової функції <math>F(b_{1},b_{2}...,b_{m})</math> за відповідними аргументами <math>b_{i}</math> ,<math>i=\overline{1,n}</math>  
 
Компоненти оптимального плану двоїстої задачі <math>y_{i}^{*}</math> <math>i=\overline{1,n}</math> дорівнюють значенням частинних похідних від цільової функції <math>F(b_{1},b_{2}...,b_{m})</math> за відповідними аргументами <math>b_{i}</math> ,<math>i=\overline{1,n}</math>  
 
або <br>  
 
або <br>  
<math>dF/db_i=y_{i}^{*}</math> , <math>(i=1,2,...,m)</math> (3.28) <br>
+
<math>dF/db_i=y_{i}^{*}</math> , <math>(i=1,2,...,m)~~~~~~~~(1)</math> <br>
 
'''Доведення.''' Розглянемо задачу лінійного програмування, подану в канонічній формі:
 
'''Доведення.''' Розглянемо задачу лінійного програмування, подану в канонічній формі:
<math>max F=c_{1}x_{1}+c_{2}x_{2}+...+c_{n}x_{n}</math> (3.29) <br>
+
<math>max F=c_{1}x_{1}+c_{2}x_{2}+...+c_{n}x_{n}~~~~~~~~(2)</math>   <br>
 
<center><math>\left\{ {\begin{array}{l}
 
<center><math>\left\{ {\begin{array}{l}
 
  a_{11}x_{1}+a_{12}x_{2}+a_{1n}x_{n}=b_{1} \\  
 
  a_{11}x_{1}+a_{12}x_{2}+a_{1n}x_{n}=b_{1} \\  
  a_{21}x_{1}+a_{22}x_{2}+a_{2n}x_{n}=b_{2} \\ ~~~~~~~~(3.30)           
+
  a_{21}x_{1}+a_{22}x_{2}+a_{2n}x_{n}=b_{2} \\            
 
................................ \\  
 
................................ \\  
 
  a_{m1}x_{1}+a_{m2}x_{2}+a_{mn}x_{n}=b_{m} \\  
 
  a_{m1}x_{1}+a_{m2}x_{2}+a_{mn}x_{n}=b_{m} \\  
\end{array}} \right.</math></center>   
+
\end{array}} \right.~~~~~~~~(3)</math></center>   
 
<math>x_j\ge 0</math> ,<math>j=\overline{1,n}</math>    (3.31) <br>
 
<math>x_j\ge 0</math> ,<math>j=\overline{1,n}</math>    (3.31) <br>
  

Версія за 10:41, 4 травня 2012

Теорема (третя теорема двоїстості). Компоненти оптимального плану двоїстої задачі Неможливо розібрати вираз (невідома помилка): y_{i}^{*}

Неможливо розібрати вираз (невідома помилка): i=\overline{1,n}
дорівнюють значенням частинних похідних від цільової функції Неможливо розібрати вираз (невідома помилка): F(b_{1},b_{2}...,b_{m})
за відповідними аргументами Неможливо розібрати вираз (невідома помилка): b_{i}
,Неможливо розібрати вираз (невідома помилка): i=\overline{1,n}

або
Неможливо розібрати вираз (невідома помилка): dF/db_i=y_{i}^{*}

, Неможливо розібрати вираз (невідома помилка): (i=1,2,...,m)~~~~~~~~(1)
 

Доведення. Розглянемо задачу лінійного програмування, подану в канонічній формі: Неможливо розібрати вираз (невідома помилка): max F=c_{1}x_{1}+c_{2}x_{2}+...+c_{n}x_{n}~~~~~~~~(2)

  
Неможливо розібрати вираз (невідома помилка): \left\{ {\begin{array}{l} a_{11}x_{1}+a_{12}x_{2}+a_{1n}x_{n}=b_{1} \\ a_{21}x_{1}+a_{22}x_{2}+a_{2n}x_{n}=b_{2} \\ ................................ \\ a_{m1}x_{1}+a_{m2}x_{2}+a_{mn}x_{n}=b_{m} \\ \end{array}} \right.~~~~~~~~(3)

Неможливо розібрати вираз (невідома помилка): x_j\ge 0

,Неможливо розібрати вираз (невідома помилка): j=\overline{1,n}
   (3.31) 

Двоїсту задачу до задачі (3.29)-(3.31) сформулюємо так: знайти оптимальний план Неможливо розібрати вираз (невідома помилка): Y^*=(y_{1}^{*},y_{2}^{*},...,y_{m}^{*})

,за якого мінімізується значення Неможливо розібрати вираз (невідома помилка):  Z=b_{1}y_{1}+b_{2}y_2{}+...+b_{m}y_{m}
 (3.32) 

за умов:

Неможливо розібрати вираз (невідома помилка): \left\{ {\begin{array}{l} a_{11}y_{1}+a_{12}y_{2}+a_{1n}y_{n} \ge c_{1} \\ a_{21}y_{1}+a_{22}y_{2}+a_{2n}y_{n} \ge c_{2} \\ ................................ \\ a_{m1}y_{1}+a_{m2}y_{2}+a_{mn}y_{n} \ge c_{m} \\ \end{array}} \right.

причому умова невід’ємності змінних Неможливо розібрати вираз (невідома помилка): y_i^*

Неможливо розібрати вираз (невідома помилка): (i=\overline{1,n})
відсутня. 

Позначимо Неможливо розібрати вираз (невідома помилка): Y^*=(y_{1}^{*},y_{2}^{*},...,y_{m}^{*})

— оптимальний план двоїстої задачі,Неможливо розібрати вираз (невідома помилка): X^*=(x_{1}^{*},x_{2}^{*},...,x_{m}^{*})
 — оптимальний план задачі (3.29)-(3.31). За першою теоремою двоїстості відомо, що:Неможливо розібрати вираз (невідома помилка): max\ F=c_{1}x_{1}+c_{2}x_{2}+...+c_{n}x_{n}=min\ Z=b_{1}y_{1}^{*}+b_{2}y_{2}^{*}+...+b_{m}y_{m}^{*}

або Неможливо розібрати вираз (невідома помилка): F=b_{1}y_{1}^{*}+b_{2}y_{2}^{*}+...+b_{m}y_{m}^{*} (3.34)
Оскільки досліджується питання впливу зміни значень Неможливо розібрати вираз (невідома помилка): b_{i} ,Неможливо розібрати вираз (невідома помилка): (i=\overline{1,n})

на Неможливо розібрати вираз (невідома помилка): F
, то лінійну функцію (3.34) можна розглядати як функцію від аргументів Неможливо розібрати вираз (невідома помилка): b_{i}

,Неможливо розібрати вираз (невідома помилка): (i=\overline{1,n}) .Тоді частинні похідні за змінними Неможливо розібрати вираз (невідома помилка): b_{i} ,Неможливо розібрати вираз (невідома помилка): (i=\overline{1,n})

будуть дорівнювати компонентам оптимального плану двоїстої задачі Неможливо розібрати вираз (невідома помилка): y_{i}^{*}
:Неможливо розібрати вираз (невідома помилка): dF/db_{i}=y_{i}^{*}
,Неможливо розібрати вираз (невідома помилка): i=1,2,...,m

(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

, люд./год, га тощо).Використовуючи третю теорему двоїстості, можна легко визначити вплив на зміну значення цільової функції збільшення чи зменшення обсягів окремих ресурсів: числові значення двоїстих оцінок показують, на яку величину змінюється цільова функція за зміни обсягу відповідного даній оцінці ресурсу Неможливо розібрати вираз (невідома помилка): y_{i}^{*}=F /\bigtriangleup{b_{i}}

.Отже, за умови незначних змін Неможливо розібрати вираз (невідома помилка): b_{i}

замість задачі (3.29)—(3.31) маємо нову задачу, де Неможливо розібрати вираз (невідома помилка): b_{i}
замінено на Неможливо розібрати вираз (невідома помилка): b_{i}^{'}=b_{i}+\bigtriangleup{b_{i}}

.Позначимо через Неможливо розібрати вираз (невідома помилка): X^{'}

оптимальний план нової задачі.Для визначення Неможливо розібрати вираз (невідома помилка): F(X^{'})
не потрібно розв’язувати нову задачу лінійного програмування, а достатньо скористатися формулою Неможливо розібрати вираз (невідома помилка): F(X^{'})-F(X^{*})=y_{i}^{*}b_{i}

, де Неможливо розібрати вираз (невідома помилка): X^*

— оптимальний план задачі (3.29)—(3.31).