Відмінності між версіями «Умови оптимальності плану першого етапу задачі стохастичного програмування.»
| Рядок 1: | Рядок 1: | ||
| − | Сформулюємо необхідні умови оптимальності попереднього плану x двохетапної задачі. | + | <font size=3> Сформулюємо необхідні умови оптимальності попереднього плану x двохетапної задачі. </font> |
| − | Введемо вектор | + | <font size=3> Введемо вектор </font> |
<math>~c_x=M[c-z^*(A,b,x)A]</math> | <math>~c_x=M[c-z^*(A,b,x)A]</math> | ||
| − | та лінійну форму <math>L_{x_1}=(c_1,x)=M[c-z^*(A,b,x_1)A]x</math> | + | <font size=3> та лінійну форму <math>L_{x_1}=(c_1,x)=M[c-z^*(A,b,x_1)A]x</math> </font> |
| − | '''Теорема 1 (необхідна умова оптимальності плану двохетапної задачі):''' | + | <font size=3> '''Теорема 1 (необхідна умова оптимальності плану двохетапної задачі):''' </font> |
| − | Якщо x* - розв’язок двохетапної задачі, то для будь-якого <math>x \in K</math> | + | <font size=3> Якщо x* - розв’язок двохетапної задачі, то для будь-якого <math>x \in K</math> </font> |
<math>L_x(x^*)\leq{L_x(x)}</math> (1) | <math>L_x(x^*)\leq{L_x(x)}</math> (1) | ||
| − | '''Доведення:''' | + | <font size=3> '''Доведення:''' </font> |
| − | Оскільки x* - оптимальний план, а x – план двохетапної задачі, то <math>Q(x^*)\leq{Q(x)}</math>, тобто | + | <font size=3> Оскільки x* - оптимальний план, а x – план двохетапної задачі, то <math>Q(x^*)\leq{Q(x)}</math>, тобто |
| − | <math>M\{cx^*+z^*(A,b,x^*)(b-Ax^*)\}\leq{M\{cx+z^*(A,b,x)(b-Ax)\}}</math> (2) | + | <math>M\{cx^*+z^*(A,b,x^*)(b-Ax^*)\}\leq{M\{cx+z^*(A,b,x)(b-Ax)\}}</math> (2) </font> |
| − | Крім того | + | <font size=3> Крім того </font> |
<math>M\{z^*(A,b,x^*)(b-Ax^*)\}\geq{M\{z^*(A,b,x)(b-Ax)\}}</math> (3) | <math>M\{z^*(A,b,x^*)(b-Ax^*)\}\geq{M\{z^*(A,b,x)(b-Ax)\}}</math> (3) | ||
| − | так як z*(A,b,x*) - оптимальний план задачі, двоїстої до задачі другого етапу при x=x*. | + | <font size=3> так як z*(A,b,x*) - оптимальний план задачі, двоїстої до задачі другого етапу при x=x*. </font> |
| − | Віднімаючи від (2) (3) приходимо до твердження (1): | + | <font size=3> Віднімаючи від (2) (3) приходимо до твердження (1): </font> |
<math>M(cx^*)+M(z^*(A,b,x^*)b)-M(z^*(A,b,x^*)Ax^*)-M(z^*(A,b,x)Ax^*)+M(z^*(A,b,x)b)\leq{M(cx)+M(z^*(A,b,x)b)-M(z^*(A,b,x)Ax)-M(z^*(A,b,x^*)Ax^*)+M(z^*(A,b,x^*)b)}</math> | <math>M(cx^*)+M(z^*(A,b,x^*)b)-M(z^*(A,b,x^*)Ax^*)-M(z^*(A,b,x)Ax^*)+M(z^*(A,b,x)b)\leq{M(cx)+M(z^*(A,b,x)b)-M(z^*(A,b,x)Ax)-M(z^*(A,b,x^*)Ax^*)+M(z^*(A,b,x^*)b)}</math> | ||
| Рядок 32: | Рядок 32: | ||
<math>L_x(x^*)\leq{L_x(x)}</math> | <math>L_x(x^*)\leq{L_x(x)}</math> | ||
| − | '''Теорема доведена.''' | + | <font size=3> '''Теорема доведена.''' </font> |
| − | Теорема 1 містить ідею аналізу двохетапної задачі. Теорема стверджує, що розв’язок x* двохетапної задачі надає лінійній формі <math>L_{x_1}(x)=M[c-z^*(A,b,x_1)A]x</math> значення, що не перевищує значення форми в точці <math>x_1 \in K</math>. | + | <font size=3> Теорема 1 містить ідею аналізу двохетапної задачі. Теорема стверджує, що розв’язок x* двохетапної задачі надає лінійній формі <math>L_{x_1}(x)=M[c-z^*(A,b,x_1)A]x</math> значення, що не перевищує значення форми в точці <math>x_1 \in K</math>. </font> |
| − | Звідси випливає наступний метод аналізу двохетапної задачі. | + | <font size=3> Звідси випливає наступний метод аналізу двохетапної задачі. </font> |
| − | Вибираємо деяку кількість точок <math>x_1 \in K</math> і обчислюємо для них розв’язки <math>~z^*(A,b,x_1)</math> задачі лінійного програмування (3.8)-(3.9), двоїстої до задачі другого етапу. | + | <font size=3> Вибираємо деяку кількість точок <math>x_1 \in K</math> і обчислюємо для них розв’язки <math>~z^*(A,b,x_1)</math> задачі лінійного програмування (3.8)-(3.9), двоїстої до задачі другого етапу. </font> |
| − | Для кожного вибраного <math>~x_1</math> будуємо нерівність типу (1): <math>L_{x_1}(x)\leq{L_{x_1}(x_1)}</math> | + | <font size=3> Для кожного вибраного <math>~x_1</math> будуємо нерівність типу (1): <math>L_{x_1}(x)\leq{L_{x_1}(x_1)}</math> |
| − | Отримана таким чином послідовність нерівностей представляє собою систему обмежень, що звужують множину, в якій міститься оптимум, і, відповідно, тих, що скорочують діапазон зміни показника якості розв’язку двохетапної задачі. | + | <font size=3> Отримана таким чином послідовність нерівностей представляє собою систему обмежень, що звужують множину, в якій міститься оптимум, і, відповідно, тих, що скорочують діапазон зміни показника якості розв’язку двохетапної задачі. </font> |
| − | Наведемо економічну інтерпретацію умови (1). | + | <font size=3> '''Наведемо економічну інтерпретацію умови''' (1). </font> |
| − | Вектор z*(A,b,x) – розв’язок задачі, двоїстої до задачі другого етапу, представляє собою вектор оцінок продуктів. що виявилися дефіцитними або надлишковими при інтенсивностях x технологічних способів після того, як були реалізовані технологічна матриця A та вектор попиту b. Ці оцінки визначають вплив величини нев’язки на витрати, пов’язані з найбільш економною ліквідацією нев’язок. Величина | + | <font size=3> Вектор z*(A,b,x) – розв’язок задачі, двоїстої до задачі другого етапу, представляє собою вектор оцінок продуктів. що виявилися дефіцитними або надлишковими при інтенсивностях x технологічних способів після того, як були реалізовані технологічна матриця A та вектор попиту b. Ці оцінки визначають вплив величини нев’язки на витрати, пов’язані з найбільш економною ліквідацією нев’язок. Величина </font> |
<math>\sum^{m}_{i=1}{a_{ij}z^{*}_i(A,b,x)}-c_j</math> | <math>\sum^{m}_{i=1}{a_{ij}z^{*}_i(A,b,x)}-c_j</math> | ||
| − | вказує на прибутковість експлуатації j-ого технологічного способу з одиничною інтенсивністю у припущенні, що параметри умов задачі реалізувалися як елементи матриці A та складові векторів b, c, а оцінки продуктів пораховані для випадку, коли експлуатація технологічних способів відбувається з інтенсивністю x. | + | <font size=3> вказує на прибутковість експлуатації j-ого технологічного способу з одиничною інтенсивністю у припущенні, що параметри умов задачі реалізувалися як елементи матриці A та складові векторів b, c, а оцінки продуктів пораховані для випадку, коли експлуатація технологічних способів відбувається з інтенсивністю x. |
| − | Якщо вектор x* визначає оптимальний попередній план двохетапної задачі, то сумарний середній прибуток при інтенсивностях x* використання технологічних способів виробництва, підрахована в оптимальних оцінках (ті, що відповідають x*), не менше сумарного середнього прибутку, порахованого в оптимальних оцінках для будь-якого іншого допустимого плану x. | + | Якщо вектор x* визначає оптимальний попередній план двохетапної задачі, то сумарний середній прибуток при інтенсивностях x* використання технологічних способів виробництва, підрахована в оптимальних оцінках (ті, що відповідають x*), не менше сумарного середнього прибутку, порахованого в оптимальних оцінках для будь-якого іншого допустимого плану x. </font> |
| − | '''Теорема 2 (необхідна і достатня умова оптимальності плану двохетапної задачі):''' | + | <font size=3> '''Теорема 2 (необхідна і достатня умова оптимальності плану двохетапної задачі):''' </font> |
| − | Нехай x* - внутрішня точка множини K, а цільова функція Q(x) детермінованої задачі, еквівалентної двохетапній задачі, диференційована в околі x*. Тоді задача, двоїста до задачі другого етапу, має розв’язок z*(A,b,x*) такий, що | + | <font size=3> Нехай x* - внутрішня точка множини K, а цільова функція Q(x) детермінованої задачі, еквівалентної двохетапній задачі, диференційована в околі x*. Тоді задача, двоїста до задачі другого етапу, має розв’язок z*(A,b,x*) такий, що </font> |
<math>c_{x^*}=M[c-z^*(A,b,x^*)A]=0</math> (4) | <math>c_{x^*}=M[c-z^*(A,b,x^*)A]=0</math> (4) | ||
| − | тоді і тільки тоді, коли x* - розв’язок двохетапної задачі. | + | <font size=3> тоді і тільки тоді, коли x* - розв’язок двохетапної задачі. </font> |
| − | '''Доведення:''' | + | <font size=3> '''Доведення:''' </font> |
| − | Згідно з теоремою, що визначає опорний функціонал до Q(x), стверджуємо, що гіперплощина | + | <font size=3> Згідно з теоремою, що визначає опорний функціонал до Q(x), стверджуємо, що гіперплощина </font> |
<math>~u=M[c-z^*(A,b,x_0)A]x+Mz^*(A,b,x_0)b</math> | <math>~u=M[c-z^*(A,b,x_0)A]x+Mz^*(A,b,x_0)b</math> | ||
| − | є опорною гіперплощиною до множини <math>u\geq{Q(x)}</math>в точці <math>~x=x_0</math>. | + | <font size=3> є опорною гіперплощиною до множини <math>u\geq{Q(x)}</math>в точці <math>~x=x_0</math>. |
| − | За умовою опукла функція Q(x) диференційована в точці x=x*. Відповідно опорна гіперплощина | + | <font size=3> За умовою опукла функція Q(x) диференційована в точці x=x*. Відповідно опорна гіперплощина </font> |
<math>~u=M[c-z^*(A,b,x^*)A]x+Mz^*(A,b,x^*)b</math> | <math>~u=M[c-z^*(A,b,x^*)A]x+Mz^*(A,b,x^*)b</math> | ||
| − | дотикається до гіперповерхні u=Q(x) в точці x=x*. | + | <font size=3> дотикається до гіперповерхні u=Q(x) в точці x=x*. </font> |
| − | Враховуючи, що x* - внутрішня точка множини K отримаємо, що рівність | + | <font size=3> Враховуючи, що x* - внутрішня точка множини K отримаємо, що рівність </font> |
<math>\frac{\partial Q}{\partial x}=\frac{\partial u}{\partial x}=M[c-z^*(A,b,x^*)A]=0</math> | <math>\frac{\partial Q}{\partial x}=\frac{\partial u}{\partial x}=M[c-z^*(A,b,x^*)A]=0</math> | ||
| − | є необхідною умовою оптимальності вектора x*. | + | <font size=3> є необхідною умовою оптимальності вектора x*. </font> |
| − | Рівність (4) є також і достатньою умовою, оскільки функція Q(x) опукла вниз. | + | <font size=3> Рівність (4) є також і достатньою умовою, оскільки функція Q(x) опукла вниз. </font> |
| − | '''Теорема доведена.''' | + | <font size=3> '''Теорема доведена.''' </font> |
Версія за 21:21, 22 березня 2014
Сформулюємо необхідні умови оптимальності попереднього плану x двохетапної задачі.
Введемо вектор Неможливо розібрати вираз (невідома помилка): ~c_x=M[c-z^*(A,b,x)A]
та лінійну форму Неможливо розібрати вираз (невідома помилка): L_{x_1}=(c_1,x)=M[c-z^*(A,b,x_1)A]x
Теорема 1 (необхідна умова оптимальності плану двохетапної задачі):
Якщо x* - розв’язок двохетапної задачі, то для будь-якого Неможливо розібрати вираз (невідома помилка): x \in K
Неможливо розібрати вираз (невідома помилка): L_x(x^*)\leq{L_x(x)}
(1)
Доведення:
Оскільки x* - оптимальний план, а x – план двохетапної задачі, то Неможливо розібрати вираз (невідома помилка): Q(x^*)\leq{Q(x)} , тобто Неможливо розібрати вираз (невідома помилка): M\{cx^*+z^*(A,b,x^*)(b-Ax^*)\}\leq{M\{cx+z^*(A,b,x)(b-Ax)\}}
(2)
Крім того
Неможливо розібрати вираз (невідома помилка): M\{z^*(A,b,x^*)(b-Ax^*)\}\geq{M\{z^*(A,b,x)(b-Ax)\}}
(3)
так як z*(A,b,x*) - оптимальний план задачі, двоїстої до задачі другого етапу при x=x*.
Віднімаючи від (2) (3) приходимо до твердження (1):
Неможливо розібрати вираз (невідома помилка): M(cx^*)+M(z^*(A,b,x^*)b)-M(z^*(A,b,x^*)Ax^*)-M(z^*(A,b,x)Ax^*)+M(z^*(A,b,x)b)\leq{M(cx)+M(z^*(A,b,x)b)-M(z^*(A,b,x)Ax)-M(z^*(A,b,x^*)Ax^*)+M(z^*(A,b,x^*)b)}
Неможливо розібрати вираз (невідома помилка): M(cx^*)-M(z^*(A,b,x)Ax^*)\leq{M(cx)-M(z^*(A,b,x)Ax)}
Неможливо розібрати вираз (невідома помилка): M[c-z^*(A,b,x)A]x^*\leq{M[c-z^*(A,b,x)A]x}
Неможливо розібрати вираз (невідома помилка): L_x(x^*)\leq{L_x(x)}
Теорема доведена.
Теорема 1 містить ідею аналізу двохетапної задачі. Теорема стверджує, що розв’язок x* двохетапної задачі надає лінійній формі Неможливо розібрати вираз (невідома помилка): L_{x_1}(x)=M[c-z^*(A,b,x_1)A]x
значення, що не перевищує значення форми в точці Неможливо розібрати вираз (невідома помилка): x_1 \in K
.
Звідси випливає наступний метод аналізу двохетапної задачі.
Вибираємо деяку кількість точок Неможливо розібрати вираз (невідома помилка): x_1 \in K
і обчислюємо для них розв’язки Неможливо розібрати вираз (невідома помилка): ~z^*(A,b,x_1) задачі лінійного програмування (3.8)-(3.9), двоїстої до задачі другого етапу.
Для кожного вибраного Неможливо розібрати вираз (невідома помилка): ~x_1
будуємо нерівність типу (1): Неможливо розібрати вираз (невідома помилка): L_{x_1}(x)\leq{L_{x_1}(x_1)}
Отримана таким чином послідовність нерівностей представляє собою систему обмежень, що звужують множину, в якій міститься оптимум, і, відповідно, тих, що скорочують діапазон зміни показника якості розв’язку двохетапної задачі.
Наведемо економічну інтерпретацію умови (1).
Вектор z*(A,b,x) – розв’язок задачі, двоїстої до задачі другого етапу, представляє собою вектор оцінок продуктів. що виявилися дефіцитними або надлишковими при інтенсивностях x технологічних способів після того, як були реалізовані технологічна матриця A та вектор попиту b. Ці оцінки визначають вплив величини нев’язки на витрати, пов’язані з найбільш економною ліквідацією нев’язок. Величина
Неможливо розібрати вираз (невідома помилка): \sum^{m}_{i=1}{a_{ij}z^{*}_i(A,b,x)}-c_j
вказує на прибутковість експлуатації j-ого технологічного способу з одиничною інтенсивністю у припущенні, що параметри умов задачі реалізувалися як елементи матриці A та складові векторів b, c, а оцінки продуктів пораховані для випадку, коли експлуатація технологічних способів відбувається з інтенсивністю x.
Якщо вектор x* визначає оптимальний попередній план двохетапної задачі, то сумарний середній прибуток при інтенсивностях x* використання технологічних способів виробництва, підрахована в оптимальних оцінках (ті, що відповідають x*), не менше сумарного середнього прибутку, порахованого в оптимальних оцінках для будь-якого іншого допустимого плану x.
Теорема 2 (необхідна і достатня умова оптимальності плану двохетапної задачі):
Нехай x* - внутрішня точка множини K, а цільова функція Q(x) детермінованої задачі, еквівалентної двохетапній задачі, диференційована в околі x*. Тоді задача, двоїста до задачі другого етапу, має розв’язок z*(A,b,x*) такий, що
Неможливо розібрати вираз (невідома помилка): c_{x^*}=M[c-z^*(A,b,x^*)A]=0
(4)
тоді і тільки тоді, коли x* - розв’язок двохетапної задачі.
Доведення:
Згідно з теоремою, що визначає опорний функціонал до Q(x), стверджуємо, що гіперплощина
Неможливо розібрати вираз (невідома помилка): ~u=M[c-z^*(A,b,x_0)A]x+Mz^*(A,b,x_0)b
є опорною гіперплощиною до множини Неможливо розібрати вираз (невідома помилка): u\geq{Q(x)}
в точці Неможливо розібрати вираз (невідома помилка): ~x=x_0
.
За умовою опукла функція Q(x) диференційована в точці x=x*. Відповідно опорна гіперплощина
Неможливо розібрати вираз (невідома помилка): ~u=M[c-z^*(A,b,x^*)A]x+Mz^*(A,b,x^*)b
дотикається до гіперповерхні u=Q(x) в точці x=x*.
Враховуючи, що x* - внутрішня точка множини K отримаємо, що рівність
Неможливо розібрати вираз (невідома помилка): \frac{\partial Q}{\partial x}=\frac{\partial u}{\partial x}=M[c-z^*(A,b,x^*)A]=0
є необхідною умовою оптимальності вектора x*.
Рівність (4) є також і достатньою умовою, оскільки функція Q(x) опукла вниз.
Теорема доведена.
