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

Матеріал з Вікі ЦДПУ
Перейти до: навігація, пошук
Рядок 24: Рядок 24:
 
Позначимо <math>Y^*=(y_{1}^{*},y_{2}^{*},...,y_{m}^{*})~</math> — оптимальний план двоїстої задачі,<math>X^*=(x_{1}^{*},x_{2}^{*},...,x_{m}^{*})~</math>  — оптимальний план задачі (3.29)-(3.31). За першою теоремою двоїстості відомо, що:<math>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}^{*}~</math> <br>
 
Позначимо <math>Y^*=(y_{1}^{*},y_{2}^{*},...,y_{m}^{*})~</math> — оптимальний план двоїстої задачі,<math>X^*=(x_{1}^{*},x_{2}^{*},...,x_{m}^{*})~</math>  — оптимальний план задачі (3.29)-(3.31). За першою теоремою двоїстості відомо, що:<math>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}^{*}~</math> <br>
 
або <math>F=b_{1}y_{1}^{*}+b_{2}y_{2}^{*}+...+b_{m}y_{m}^{*}~</math>(3.34) <br>
 
або <math>F=b_{1}y_{1}^{*}+b_{2}y_{2}^{*}+...+b_{m}y_{m}^{*}~</math>(3.34) <br>
Оскільки досліджується питання впливу зміни значень <math>b_{i}</math>,<math>(i=\overline{1,n})</math> на <math>F</math> , то лінійну функцію (3.34) можна розглядати як функцію від аргументів <math>b_{i}</math>,<math>(i=\overline{1,n})~</math>.Тоді частинні похідні за змінними <math>b_{i}~</math>,<math>(i=\overline{1,n})~</math> будуть дорівнювати компонентам оптимального плану двоїстої задачі <math>y_{i}^{*}~</math> :<math>dF/db_{i}=y_{i}^{*}~</math> ,<math>i=1,2,...,m~</math>(3.35) <br>
+
Оскільки досліджується питання впливу зміни значень <math>b_{i}~</math>,<math>(i=\overline{1,n})~</math> на <math>F~</math> , то лінійну функцію (3.34) можна розглядати як функцію від аргументів <math>b_{i}~</math>,<math>(i=\overline{1,n})~</math>.Тоді частинні похідні за змінними <math>b_{i}~</math>,<math>(i=\overline{1,n})~</math> будуть дорівнювати компонентам оптимального плану двоїстої задачі <math>y_{i}^{*}~</math> :<math>dF/db_{i}=y_{i}^{*}~</math> ,<math>i=1,2,...,m~</math>(3.35) <br>
  
 
Однак дане твердження справедливе лише у тому разі, коли компоненти оптимального плану <math>Y^*=(y_1^*,y_2^*,...,y_m^*)~</math> залишаються постійними, а оскільки за першою теоремою двоїстості <math>Y^*=C^*D^{-1}~</math>, то значення двоїстих оцінок будуть незмінними лише за умови постійної структури оптимального плану початкової задачі.  
 
Однак дане твердження справедливе лише у тому разі, коли компоненти оптимального плану <math>Y^*=(y_1^*,y_2^*,...,y_m^*)~</math> залишаються постійними, а оскільки за першою теоремою двоїстості <math>Y^*=C^*D^{-1}~</math>, то значення двоїстих оцінок будуть незмінними лише за умови постійної структури оптимального плану початкової задачі.  
Рядок 32: Рядок 32:
 
'''Економічний зміст третьої теореми двоїстості.'''  
 
'''Економічний зміст третьої теореми двоїстості.'''  
 
Двоїсті оцінки є унікальним інструментом, який дає змогу зіставляти непорівнянні речі. Очевидно, що неможливим є просте зіставлення величин, які мають різні одиниці вимірювання. Якщо взяти як приклад виробничу задачу, то цікавим є питання: як змінюватиметься значення цільової функції (може вимірюватися в грошових одиницях) за зміни обсягів різних ресурсів (можуть вимірюватися в тоннах, <math>M^2</math> , люд./год, га тощо).Використовуючи третю теорему двоїстості, можна легко визначити вплив на зміну значення цільової функції збільшення чи зменшення обсягів окремих ресурсів: числові значення двоїстих оцінок показують, на яку величину змінюється цільова функція за зміни обсягу відповідного даній оцінці ресурсу <math>y_{i}^{*}=F /\bigtriangleup{b_{i}}~</math>.Отже, за умови незначних змін <math>b_{i}~</math> замість задачі (3.29)—(3.31) маємо нову задачу, де <math>b_{i}~</math> замінено на <math>b_{i}^{'}=b_{i}+\bigtriangleup{b_{i}}~</math>.Позначимо через <math>X^{'}~</math> оптимальний план нової задачі.Для визначення <math>F(X^{'})~</math> не потрібно розв’язувати нову задачу лінійного програмування, а достатньо скористатися формулою <math>F(X^{'})-F(X^{*})=y_{i}^{*}b_{i}~</math>, де <math>X^*~</math> — оптимальний план задачі (3.29)—(3.31).
 
Двоїсті оцінки є унікальним інструментом, який дає змогу зіставляти непорівнянні речі. Очевидно, що неможливим є просте зіставлення величин, які мають різні одиниці вимірювання. Якщо взяти як приклад виробничу задачу, то цікавим є питання: як змінюватиметься значення цільової функції (може вимірюватися в грошових одиницях) за зміни обсягів різних ресурсів (можуть вимірюватися в тоннах, <math>M^2</math> , люд./год, га тощо).Використовуючи третю теорему двоїстості, можна легко визначити вплив на зміну значення цільової функції збільшення чи зменшення обсягів окремих ресурсів: числові значення двоїстих оцінок показують, на яку величину змінюється цільова функція за зміни обсягу відповідного даній оцінці ресурсу <math>y_{i}^{*}=F /\bigtriangleup{b_{i}}~</math>.Отже, за умови незначних змін <math>b_{i}~</math> замість задачі (3.29)—(3.31) маємо нову задачу, де <math>b_{i}~</math> замінено на <math>b_{i}^{'}=b_{i}+\bigtriangleup{b_{i}}~</math>.Позначимо через <math>X^{'}~</math> оптимальний план нової задачі.Для визначення <math>F(X^{'})~</math> не потрібно розв’язувати нову задачу лінійного програмування, а достатньо скористатися формулою <math>F(X^{'})-F(X^{*})=y_{i}^{*}b_{i}~</math>, де <math>X^*~</math> — оптимальний план задачі (3.29)—(3.31).
 +
==Література==
 +
[http://fingal.com.ua/content/view/454/76/1/2/ Посилання на використану літературу]

Версія за 11:09, 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).

Література

Посилання на використану літературу