Перегляд вихідного коду сторінки Найпростіша постановка двохетапної задачі СП.

<font size=3>Розглянемо, двоетапну задачу, в якій випадковим є тільки вектор обмежень, а матриця компенсації ''В'' 
(після відповідної перестановки рядків і стовпців) може бути представлена у вигляді ''В = (Е, -Е)'', де ''Е'' - одинична матриця розміру ''mxm''. Розіб'ємо вектори ''у'' і ''q'' на дві частини, відповідні підматриці ''Е, -Е'' матриці ''B''. Задача  в цьому випадку приймає вид 

<font size=3><math>Q(x)=cx+MP(x,b)\to min,</math>  (1)<font>

<font size=3><math>A^{(1)}x=b^{(1)},</math>   (2) <font>

<font size=3><math>x\ge0,</math>   (3) <font>

де

<math>P(x,b)=\{min(q^{+}y^{+}+q^{-}y^{-}|y^{+}-y^{-}=b(\omega)-Ax;y^{+}\ge0, y^{-}\ge0\}.</math>  (4)

Тут <math>q^{+},q^{-},y^{+},y^{-}</math>- m-мірні вектори.
 
Будемо називати модель (1)-(3) ''найпростішою постановкою 
двохетапної задачі лінійного стохастичного програмування''. 
Очевидно, що завдання (4) другого етапу має плани при 
довільної реалізації <math>(\omega)</math> і будь-якому вибраному попередньому плані х.

Тобто <math>K_{2}=R^{n}</math> і <math> K=K_{1}=\{x|A^{(1)}x=b^{(1)}, x\ge0\}</math>.

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

<math>\{z|zB\le q\}\neq\varnothing </math>.

У розглянутому випадку

<math>\{z|zB\le q\}=\{z|z(E, -E)\le q\}=\{z|-q^{-}\le z\le q^{+}\} \neq\varnothing</math>.

Таким чином, для розв'язання задачі другого етапу в 
найпростішій постановці двохетапної задачі необхідно і достатньо, щоб <math>-q^{-}\le q^{+}</math> тобто

<math>q^{+}+q^{-}\ge 0.</math>  (5)

У практичних задачах умова (5) завжди виконується, 
оскільки штрафи <math>-q^{-}</math> і  <math>q^{+}</math>, як правило, невід'ємні. 

Задача, двоїста до задачі (4) другого етапу, має вигляд

<math>Q(x,b)=\{max z(b-Ax)|-q^{-}\le z\le q^{+} \}</math>.  (6)

Задача (6) легко вирішується. Розв'язок цієї задачі записується формулою

<math>Q(x,b)={\sum\limits_{i=1}^m \Q_{i}(x,b_{i})},</math>

де

<math> \Q_i(x,b_{i})=\begin{cases}
[b_{i}-(Ax)_{i}] q^{+}_{i}, b_{i}-(Ax)_{i}\geqslant 0 \\
-[b_{i}-(Ax)_{i}] q^{-}_{i},
b_{i}-(Ax)_{i}\le 0 
\end{cases}</math>.   (7)

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

<math>cx+M{\sum\limits_{i=1}^m \Q_{i}(x,b_{i})\to min},</math>  (8)

<math>A^{(1)}x=b^{(1)},</math>   (9)

<math>x\ge0,</math>   (10)

де <math>Q_{i}(x,b_{i})</math> визначаються з співвідношень (7).

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

Введемо вектори

<math> \tilde {q} = \frac{1}{2} (q^{+} + q^{-}),   \tilde {c} = c - \frac{1}{2} (q^{+} - q^{-}) A. </math>

Маємо

<math> \tilde {c} x + \tilde {q} M (q^{+} + q^{-}) + \frac{1}{2} (q^{+} - q^{-}) Mb = cx + \frac{1}{2} (q^{+} - q^{-}) M [(b - Ax) - (y^{+} - y^{-})] + M (q^{+} y^{+} - q^{-} y^{-}). </math>     (11)

На планах двохетапної задачі

<math> (y^{+} - y^{-}) = b - Ax. </math>     

Виключаючи тривіальний практично нецікавий випадок, можна вважати що <math>  q^{+}>0,  q^{-}>0. </math> Тому на оптимальному плані <math> y^{+} y^{-} = 0 </math> і <math> y^{+} + y^{-} = |b - Ax|.  </math> Із (11) видно, що при цьому розв'язанні задачі задовольняє рівнянню 

<math> \tilde {c} x + \tilde {q} M |b - Ax| + \frac{1}{2} (q^{+} - q^{-}) Mb = cx + M(q^{+} y^{+} + q^{-} y^{-}). </math>

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

<font size=3><math>\tilde {c}x+\tilde {q}M|b - Ax|\to min,</math>  (12)<font>

<font size=3><math>A^{(1)}x=b^{(1)},</math>   (13) <font>

<font size=3><math>x\ge0.</math>   (14) <font>

Наведемо ще одну форму записи цієї ж завдання. Введемо позначення

<math> Ax=\varkappa</math>,  <math>(Ax)_{i} = \varkappa_{i}, </math>

<math> Q(\varkappa) = Q(x) = M {\sum\limits_{i=1}^m \Q_{i}(x,b_{i})}={\sum\limits_{i=1}^m M \Q_{i}(\varkappa_{i},b_{i})}= {\sum\limits_{i=1}^m \Q_{i}(\varkappa_{i})}. </math>

Функції <math> Q_{i}(\varkappa_{i},b_{i}), </math> так як і <math> Q_{i}(\varkappa_{i}), </math> - опуклі функції по <math> \varkappa_{i}. </math>

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

<font size=3><math> cx+{\sum\limits_{i=1}^m \Q_{i}(\varkappa_{i})}\to min,</math>  (15)<font>

<font size=3><math>A^{(1)}x=b^{(1)},</math>   (16) <font>

<font size=3><math>Ax=\varkappa,</math>   (17) <font>

<font size=3><math>x\ge0.</math>   (18) <font>

Вивчимо функції <math> Q_{i}(\varkappa_{i}). </math>

Позначимо через <math>\delta_{i} </math> і <math>\gamma_{i} </math> відповідно точну верхню і точну нижню грані випадкової величини <math> b_{i}(\omega), </math> через <math> \overline{b}=(\overline{b}_{1},...,\overline{b}_{m})=Mb </math> - математичне сподівання вектора обмежене і через <math> F_{i} b_{i} </math> - функцію розподілу компонентів <math> b_{i}(\omega). </math>

Розділимо множину значень <math> \varkappa_{i} </math> на три області:  <math> (-\infty, \gamma_{i}), [\gamma_{i}, \delta_{i}], (\delta_{i}, \infty). </math> Якщо <math> b_{i}(\omega) </math> не має нижньої (відповідно верхньої) грані, покладем <math> \gamma_{i}=-\infty </math> (відповідно <math> \delta_{i}=\infty). </math>

Обчислимо значення <math> Q_{i}(\varkappa_{i}) </math> в кожній із цих областей. Маємо


<math> Q_{i}(\varkappa_{i})= MQ_{i}(\varkappa_{i}, b_{i})=-q^{-}_{i}\int \limits_{b_{i}\leqslant\varkappa_{i}} (b_{i}-\varkappa_{i})dF_{i}(b_{i})+q^{+}_{i}\int \limits_{b_{i}>\varkappa_{i}} (b_{i}-\varkappa_{i})dF_{i}(b_{i})=q^{+}_{i}\int \limits_{\Omega}[b_{i}(\omega)-\varkappa_{i}]dp-(q^{+}_{i}+q^{-}_{i})\int \limits_{b_{i}\leqslant\varkappa_{i}} (b_{i}-\varkappa_{i})dF_{i}(b_{i}), </math>

або

<math> Q_{i}(\varkappa_{i})=q^{+}_{i}\overline{b}_{i}-q^{+}_{i}\varkappa_{i}-(q^{+}_{i}+q^{-}_{i})\int \limits_{b_{i}\leqslant\varkappa_{i}} (b_{i}-\varkappa_{i})dF_{i}(b_{i}). </math>   (19)

Розглянемо три випадки.

1. Нехай <math> \varkappa_{i}<\gamma_{i}. </math> В цьому випадку

<math> \{b_{i}|b_{i}\leqslant\varkappa_{i}\}\neq\varnothing. </math>

Із (19) отримаємо

<math> Q_{i}(\varkappa_{i})=q^{+}_{i}\overline{b}_{i}-q^{+}_{i}\varkappa_{i}. </math>

Тобто функція <math> Q_{i}(\varkappa_{i}) </math> лінійна на проміжку <math> (-\infty, \gamma_{i}). </math>

2. <math> \varkappa_{i}\in [\gamma_{i},\delta_{i}].</math> В цьому випадку

<math> \{b_{i}|b_{i}\leqslant\varkappa_{i}\}=\{b_{i}|\gamma_{i}\leqslant b_{i} \leqslant \varkappa_{i}\}. </math>

Функція <math> Q_{i}(\varkappa_{i}) </math> на цьому відрізку виражається співвідношенням

<math> Q_{i}(\varkappa_{i})=q^{+}_{i}\overline{b}_{i}-q^{+}_{i}\varkappa_{i}-(q^{+}_{i}+q^{-}_{i})\int \limits^{\varkappa_{i}}_{\gamma_{i}}(b_{i}-\varkappa_{i})dF_{i}(b_{i}). </math>

Конкретний вид опуклої функції <math> Q_{i}(\varkappa_{i}) </math> залежить від функції розподілу <math> F_{i}(b_{i}). </math>

3. <math> \varkappa_{i}>\delta_{i}. </math> В цьому випадку множина <math> \{b_{i}|b_{i}\leqslant\varkappa_{i}\} </math> збігається з усією областю змінної <math> b_{i}(\omega) </math> і 

<math> \int \limits_{b_{i}\leqslant\varkappa_{i}} [b_{i}(\omega)-\varkappa_{i}]dF_{i}(b_{i})=\int \limits_{\Omega}[b_{i}(\omega)-\varkappa_{i}]dp=\overline{b}_{i}-\varkappa_{i}. </math>   

Отже, функція <math> Q_{i}(\varkappa_{i}) </math> на проміжку <math> (\delta_{i}, \infty) </math> лінійна 

<math> Q_{i}(\varkappa_{i})=-q^{-}_{i}\overline{b}_{i}+q^{-}_{i}\varkappa_{i}. </math>

Опукла функція <math> Q_{i}(\varkappa_{i}) </math> неперервна на всій числовій прямій.

Характер функції <math> Q_{i}(\varkappa_{i}) </math> дозволяє спростити запис задачі (15)-(18) і зробити її більш зручною для якісного і кількісного аналізу.

Введемо змінні <math> \varkappa^{(1)}_{i}, \varkappa^{(2)}_{i}, \varkappa^{(3)}_{i}, </math> задовольняють умовам

<math> \begin{cases}
[b_{i}-(Ax)_{i}] q^{+}_{i},b_{i}-(Ax)_{i}\geqslant 0 \\
-[b_{i}-(Ax)_{i}] q^{-}_{i}, 
b_{i}-(Ax)_{i}\le 0 
\end{cases}</math>. 



==Список використаних джерел==
1.	Юдин Д. Б. Математические методы управления в условиях неполной информации. / Юдин Д. Б. М: «Сов. радио», 1974. – 400 с.