Умови оптимальності плану першого етапу задачі стохастичного програмування.

Сформулюємо необхідні умови оптимальності попереднього плану 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*. </font> <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)}

Неможливо розібрати вираз (невідома помилка): 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 </math> та вектор попиту b </math>. Ці оцінки визначають вплив величини нев’язки на витрати, пов’язані з найбільш економною ліквідацією нев’язок. Величина  

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

опукла вниз.  

Теорема доведена.