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

Матеріал з Вікі ЦДУ
Перейти до: навігація, пошук
 
(не показано одну проміжну версію цього учасника)
Рядок 1: Рядок 1:
−
'''Теорема (третя теорема двоїстості)'''.<br> Компоненти оптимального плану двоїстої задачі <math>y_i^*</math> <math>(i=1,n)</math> дорівнюють значенням частинних похідних від цільової функції <math>F(b_1,b_2...,b_m)</math> за відповідними аргументами <math>b_i</math>,<math>(i=1,n)</math> або
+
== '''Третя теорема двоїстості.Економічний зміст третьої теореми двоїстості.''' ==
−
<math>dF/db_i=y_i^*</math> ,<math>i=1,2,...,m</math>                (3.28) <br>
+
−
Доведення. Розглянемо задачу лінійного програмування, подану в канонічній формі:
+
−
<math>maxF=c_1x_1+c_2x_2+...+c_nx_n</math>                          (3.29) <br>
+
−
<math>x_j\ge 0</math> ,<math>j=1,n</math>                          (3.31) <br>
+
  
−
Двоїсту задачу до задачі (3.29)-(3.31) сформулюємо так: знайти оптимальний план <math>Y^*=(y_1^*,y_2^*,...,y_m^*)</math> ,за якого мінімізується значення <br> <math>Z=b_1y_1+b_2y_2+...+b_my_m</math>   (3.32) за умов:причому умова невід’ємності змінних <math>y_i^*</math><math>(i=1,n)</math> відсутня. <br>
+
==='''Теорема (третя теорема двоїстості).''' ===
−
Позначимо <math>Y^*=(y_1^*,y_2^*,...,y_m^*)</math> — оптимальний план двоїстої задачі,<math>X^*=(x_1^*,x_2^*,...,x_m^*)</math>  — оптимальний план задачі (3.29)—(3.31). За першою теоремою двоїстості відомо, що:
+
Компоненти [http://wiki.kspu.kr.ua/index.php/%D0%A1%D0%B8%D0%BC%D0%BF%D0%BB%D0%B5%D0%BA%D1%81-%D0%BC%D0%B5%D1%82%D0%BE%D0%B4_%D1%80%D0%BE%D0%B7%D0%B2%E2%80%99%D1%8F%D0%B7%D1%83%D0%B2%D0%B0%D0%BD%D0%BD%D1%8F_%D0%B7%D0%B0%D0%B4%D0%B0%D1%87_%D0%9B%D0%9F._%D0%9E%D0%BF%D1%82%D0%B8%D0%BC%D0%B0%D0%BB%D1%8C%D0%BD%D0%B8%D0%B9_%D1%80%D0%BE%D0%B7%D0%B2%E2%80%99%D1%8F%D0%B7%D0%BE%D0%BA._%D0%9A%D1%80%D0%B8%D1%82%D0%B5%D1%80%D1%96%D0%B9_%D0%BE%D0%BF%D1%82%D0%B8%D0%BC%D0%B0%D0%BB%D1%8C%D0%BD%D0%BE%D1%81%D1%82%D1%96_%D0%BF%D0%BB%D0%B0%D0%BD%D1%83 оптимального плану] двоїстої задачі <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>
 +
<center><math>dF/db_i=y_{i}^{*}~</math> , <math>(i=1,2,...,m)~~~~~~~~(1)</math></center>  <br>
 +
 
 +
=== '''Доведення.''' ===
 +
Розглянемо [http://wiki.kspu.kr.ua/index.php/%D0%A0%D0%BE%D0%B7%D0%B2%E2%80%99%D1%8F%D0%B7%D1%83%D0%B2%D0%B0%D0%BD%D0%BD%D1%8F_%D0%B7%D0%B0%D0%B4%D0%B0%D1%87%D1%96_%D0%BB%D1%96%D0%BD%D1%96%D0%B9%D0%BD%D0%BE%D0%B3%D0%BE_%D0%BF%D1%80%D0%BE%D0%B3%D1%80%D0%B0%D0%BC%D1%83%D0%B2%D0%B0%D0%BD%D0%BD%D1%8F_%D1%81%D0%B8%D0%BC%D0%BF%D0%BB%D0%B5%D0%BA%D1%81%D0%BD%D0%B8%D0%BC_%D0%BC%D0%B5%D1%82%D0%BE%D0%B4%D0%BE%D0%BC._%D0%93%D0%B5%D0%BE%D0%BC%D0%B5%D1%82%D1%80%D0%B8%D1%87%D0%BD%D0%B0_%D1%96%D0%BD%D1%82%D0%B5%D1%80%D0%BF%D1%80%D0%B5%D1%82%D0%B0%D1%86%D1%96%D1%8F_%D1%81%D0%B8%D0%BC%D0%BF%D0%BB%D0%B5%D0%BA%D1%81%D0%BD%D0%BE%D0%B3%D0%BE_%D0%BC%D0%B5%D1%82%D0%BE%D0%B4%D1%83 задачу лінійного програмування], подану в канонічній формі:
 +
<math>max F=c_{1}x_{1}+c_{2}x_{2}+...+c_{n}x_{n}~~~~~~~~(2)</math>  <br>
 +
<center><math>\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)</math></center> 
 +
<center><math>x_j\ge 0~</math> ,<math>j=\overline{1,n}~~~~~~~~(4)</math></center>    <br>
 +
 
 +
[http://wiki.kspu.kr.ua/index.php/%D0%95%D0%BA%D0%BE%D0%BD%D0%BE%D0%BC%D1%96%D1%87%D0%BD%D0%B0_%D1%96%D0%BD%D1%82%D0%B5%D1%80%D0%BF%D1%80%D0%B5%D1%82%D0%B0%D1%86%D1%96%D1%8F_%D0%BF%D1%80%D1%8F%D0%BC%D0%BE%D1%97_%D1%82%D0%B0_%D0%B4%D0%B2%D0%BE%D1%97%D1%81%D1%82%D0%BE%D1%97_%D0%B7%D0%B0%D0%B4%D0%B0%D1%87_%D0%9B%D0%9F._%D0%9F%D1%80%D0%B0%D0%B2%D0%B8%D0%BB%D0%B0_%D0%BF%D0%BE%D0%B1%D1%83%D0%B4%D0%BE%D0%B2%D0%B8_%D0%B4%D0%B2%D0%BE%D1%97%D1%81%D1%82%D0%B8%D1%85_%D0%B7%D0%B0%D0%B4%D0%B0%D1%87 Двоїсту задачу] до задачі (2)-(4) сформулюємо так: знайти оптимальний план <math>Y^*=(y_{1}^{*},y_{2}^{*},...,y_{m}^{*})~</math> ,за якого мінімізується значення <center><math> Z=b_{1}y_{1}+b_{2}y_2{}+...+b_{m}y_{m}~~~~~~~~~~~(5)</math></center> 
 +
за умов: <br>
 +
<center><math>\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.~~~~~~~~~~(6)</math></center>
 +
причому умова невід’ємності змінних <math>y_i^*</math> <math>(i=\overline{1,n})~</math> відсутня. <br>
 +
Позначимо <math>Y^*=(y_{1}^{*},y_{2}^{*},...,y_{m}^{*})~</math> — оптимальний план двоїстої задачі,<math>X^*=(x_{1}^{*},x_{2}^{*},...,x_{m}^{*})~</math>  — оптимальний план задачі (2)-(4). За [http://wiki.kspu.kr.ua/index.php/%D0%9F%D0%B5%D1%80%D1%88%D0%B0_%D1%82%D0%B5%D0%BE%D1%80%D0%B5%D0%BC%D0%B0_%D0%B4%D0%B2%D0%BE%D1%97%D1%81%D1%82%D0%BE%D1%81%D1%82%D1%96._%D0%95%D0%BA%D0%BE%D0%BD%D0%BE%D0%BC%D1%96%D1%87%D0%BD%D0%B5_%D1%82%D0%BB%D1%83%D0%BC%D0%B0%D1%87%D0%B5%D0%BD%D0%BD%D1%8F першою теоремою двоїстості] відомо, що:<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}^{*}~~~~~~~~(7)</math> <br>
 +
Оскільки досліджується питання впливу зміни значень <math>b_{i}~</math>,<math>(i=\overline{1,n})~</math> на <math>F~</math> , то лінійну функцію (7) можна розглядати як функцію від аргументів <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~~~~~~~~~(8)</math> <br>
 +
 
 +
Однак дане твердження справедливе лише у тому разі, коли компоненти оптимального плану <math>Y^*=(y_1^*,y_2^*,...,y_m^*)~</math> залишаються постійними, а оскільки за [http://wiki.kspu.kr.ua/index.php/%D0%9F%D0%B5%D1%80%D1%88%D0%B0_%D1%82%D0%B5%D0%BE%D1%80%D0%B5%D0%BC%D0%B0_%D0%B4%D0%B2%D0%BE%D1%97%D1%81%D1%82%D0%BE%D1%81%D1%82%D1%96._%D0%95%D0%BA%D0%BE%D0%BD%D0%BE%D0%BC%D1%96%D1%87%D0%BD%D0%B5_%D1%82%D0%BB%D1%83%D0%BC%D0%B0%D1%87%D0%B5%D0%BD%D0%BD%D1%8F першою теоремою двоїстості] <math>Y^*=C^*D^{-1}~</math>, то значення двоїстих оцінок будуть незмінними лише за умови постійної структури оптимального плану початкової задачі.
 +
 
 +
Отже, рівності (8)  справджуються лише за незначних змін <math>b_i~</math>,інакше суттєва зміна умов початкової задачі (правих частин системи обмежень (3)  та цільової функції (5) приведе до зміни базису в оптимальному плані прямої задачі, а значить, і до іншого розв’язку двоїстої <math>Y^{~}\ne Y^*~</math>.
 +
 
 +
==='''Економічний зміст третьої теореми двоїстості.''' ===
 +
Двоїсті оцінки є унікальним інструментом, який дає змогу зіставляти непорівнянні речі. Очевидно, що неможливим є просте зіставлення величин, які мають різні одиниці вимірювання. Якщо взяти як приклад виробничу задачу, то цікавим є питання: як змінюватиметься значення цільової функції (може вимірюватися в грошових одиницях) за зміни обсягів різних ресурсів (можуть вимірюватися в тоннах, <math>M^2</math> , люд./год, га тощо).Використовуючи третю теорему двоїстості, можна легко визначити вплив на зміну значення цільової функції збільшення чи зменшення обсягів окремих ресурсів: числові значення двоїстих оцінок показують, на яку величину змінюється цільова функція за зміни обсягу відповідного даній оцінці ресурсу <math>y_{i}^{*}=F /\bigtriangleup{b_{i}}~</math>.Отже, за умови незначних змін <math>b_{i}~</math> замість задачі (2)—(4) маємо нову задачу, де <math>b_{i}~</math> замінено на <math>b_{i}^{'}=b_{i}+\bigtriangleup{b_{i}}~</math>.Позначимо через <math>X^{'}~</math> оптимальний план нової задачі.Для визначення <math>F(X^{'})~</math> не потрібно розв’язувати нову [http://wiki.kspu.kr.ua/index.php/%D0%A0%D0%BE%D0%B7%D0%B2%E2%80%99%D1%8F%D0%B7%D1%83%D0%B2%D0%B0%D0%BD%D0%BD%D1%8F_%D0%B7%D0%B0%D0%B4%D0%B0%D1%87%D1%96_%D0%BB%D1%96%D0%BD%D1%96%D0%B9%D0%BD%D0%BE%D0%B3%D0%BE_%D0%BF%D1%80%D0%BE%D0%B3%D1%80%D0%B0%D0%BC%D1%83%D0%B2%D0%B0%D0%BD%D0%BD%D1%8F_%D1%81%D0%B8%D0%BC%D0%BF%D0%BB%D0%B5%D0%BA%D1%81%D0%BD%D0%B8%D0%BC_%D0%BC%D0%B5%D1%82%D0%BE%D0%B4%D0%BE%D0%BC._%D0%93%D0%B5%D0%BE%D0%BC%D0%B5%D1%82%D1%80%D0%B8%D1%87%D0%BD%D0%B0_%D1%96%D0%BD%D1%82%D0%B5%D1%80%D0%BF%D1%80%D0%B5%D1%82%D0%B0%D1%86%D1%96%D1%8F_%D1%81%D0%B8%D0%BC%D0%BF%D0%BB%D0%B5%D0%BA%D1%81%D0%BD%D0%BE%D0%B3%D0%BE_%D0%BC%D0%B5%D1%82%D0%BE%D0%B4%D1%83 задачу лінійного програмування], а достатньо скористатися формулою <math>F(X^{'})-F(X^{*})=y_{i}^{*}b_{i}~</math>, де <math>X^*~</math> — оптимальний план задачі (2)—(4).
 +
 +
== '''Література'''  ==
 +
 
 +
[http://fingal.com.ua/content/view/454/76/1/2/ Математичне програмування -Третя теорема двоїстості.Економічний зміст третьої теореми двоїстості.- Наконечний С.І.]

Поточна версія на 17:07, 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}~~~~~~~~(4)

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

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

за умов:

Неможливо розібрати вираз (невідома помилка): \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.~~~~~~~~~~(6)

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

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

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

— оптимальний план двоїстої задачі,Неможливо розібрати вираз (невідома помилка): X^*=(x_{1}^{*},x_{2}^{*},...,x_{m}^{*})~
 — оптимальний план задачі (2)-(4). За першою теоремою двоїстості відомо, що:Неможливо розібрати вираз (невідома помилка): 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}^{*}~~~~~~~~(7)

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

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

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

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

Однак дане твердження справедливе лише у тому разі, коли компоненти оптимального плану Неможливо розібрати вираз (невідома помилка): Y^*=(y_1^*,y_2^*,...,y_m^*)~ 

залишаються постійними, а оскільки за першою теоремою двоїстості Неможливо розібрати вираз (невідома помилка): Y^*=C^*D^{-1}~

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

Отже, рівності (8) справджуються лише за незначних змін Неможливо розібрати вираз (невідома помилка): b_i~ ,інакше суттєва зміна умов початкової задачі (правих частин системи обмежень (3) та цільової функції (5) приведе до зміни базису в оптимальному плані прямої задачі, а значить, і до іншого розв’язку двоїстої Неможливо розібрати вираз (невідома помилка): Y^{~}\ne Y^*~ .

Економічний зміст третьої теореми двоїстості.

Двоїсті оцінки є унікальним інструментом, який дає змогу зіставляти непорівнянні речі. Очевидно, що неможливим є просте зіставлення величин, які мають різні одиниці вимірювання. Якщо взяти як приклад виробничу задачу, то цікавим є питання: як змінюватиметься значення цільової функції (може вимірюватися в грошових одиницях) за зміни обсягів різних ресурсів (можуть вимірюватися в тоннах, Неможливо розібрати вираз (невідома помилка): M^2 

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

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

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

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

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

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

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

Література

Математичне програмування -Третя теорема двоїстості.Економічний зміст третьої теореми двоїстості.- Наконечний С.І.

Отримано з https://wiki.cusu.edu.ua/index.php?title=Третя_теорема_двоїстості._Економічне_тлумачення.&oldid=66795