Відмінності між версіями «Третя теорема двоїстості. Економічне тлумачення.»
Матеріал з Вікі ЦДУ
Sergkyl (обговорення • внесок) |
Sergkyl (обговорення • внесок) |
||
| Рядок 1: | Рядок 1: | ||
'''Теорема (третя теорема двоїстості).''' | '''Теорема (третя теорема двоїстості).''' | ||
| − | Компоненти оптимального плану двоїстої задачі <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)~~~~~~~~(1)</math> <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}~~~~~~~~(2)</math> <br> | <math>max F=c_{1}x_{1}+c_{2}x_{2}+...+c_{n}x_{n}~~~~~~~~(2)</math> <br> | ||
| Рядок 11: | Рядок 11: | ||
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.~~~~~~~~(3)</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> |
| − | Двоїсту задачу до задачі (3.29)-(3.31) сформулюємо так: знайти оптимальний план <math>Y^*=(y_{1}^{*},y_{2}^{*},...,y_{m}^{*})</math> ,за якого мінімізується значення <math> Z=b_{1}y_{1}+b_{2}y_2{}+...+b_{m}y_{m}</math> (3.32) | + | Двоїсту задачу до задачі (3.29)-(3.31) сформулюємо так: знайти оптимальний план <math>Y^*=(y_{1}^{*},y_{2}^{*},...,y_{m}^{*})~</math> ,за якого мінімізується значення <math> Z=b_{1}y_{1}+b_{2}y_2{}+...+b_{m}y_{m}~</math> (3.32) |
за умов: | за умов: | ||
<center><math>\left\{ {\begin{array}{l} | <center><math>\left\{ {\begin{array}{l} | ||
| Рядок 21: | Рядок 21: | ||
a_{m1}y_{1}+a_{m2}y_{2}+a_{mn}y_{n} \ge c_{m} \\ | a_{m1}y_{1}+a_{m2}y_{2}+a_{mn}y_{n} \ge c_{m} \\ | ||
\end{array}} \right.</math></center> | \end{array}} \right.</math></center> | ||
| − | причому умова невід’ємності змінних <math>y_i^*</math> <math>(i=\overline{1,n})</math> відсутня. <br> | + | причому умова невід’ємності змінних <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> — оптимальний план задачі (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>, то значення двоїстих оцінок будуть незмінними лише за умови постійної структури оптимального плану початкової задачі. |
| − | Отже, рівності (3.35) справджуються лише за незначних змін <math>b_i</math>,інакше суттєва зміна умов початкової задачі (правих частин системи обмежень (3.30) та цільової функції (3.32) приведе до зміни базису в оптимальному плані прямої задачі, а значить, і до іншого розв’язку двоїстої <math>Y^{~}\ne Y^*</math>. | + | Отже, рівності (3.35) справджуються лише за незначних змін <math>b_i~</math>,інакше суттєва зміна умов початкової задачі (правих частин системи обмежень (3.30) та цільової функції (3.32) приведе до зміни базису в оптимальному плані прямої задачі, а значить, і до іншого розв’язку двоїстої <math>Y^{~}\ne Y^*~</math>. |
'''Економічний зміст третьої теореми двоїстості.''' | '''Економічний зміст третьої теореми двоїстості.''' | ||
| − | Двоїсті оцінки є унікальним інструментом, який дає змогу зіставляти непорівнянні речі. Очевидно, що неможливим є просте зіставлення величин, які мають різні одиниці вимірювання. Якщо взяти як приклад виробничу задачу, то цікавим є питання: як змінюватиметься значення цільової функції (може вимірюватися в грошових одиницях) за зміни обсягів різних ресурсів (можуть вимірюватися в тоннах, <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). |
Версія за 11:03, 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)
Неможливо розібрати вираз (невідома помилка): 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)
за умов:
причому умова невід’ємності змінних Неможливо розібрати вираз (невідома помилка): 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).
