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

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

Неможливо розібрати вираз (невідома помилка): Q(x)=cx+MP(x,b)\to min,

 (1)

Неможливо розібрати вираз (невідома помилка): A^{(1)}x=b^{(1)},

  (2) 

Неможливо розібрати вираз (невідома помилка): x\ge0,

  (3) 

де

Неможливо розібрати вираз (невідома помилка): P(x,b)=\{min(q^{+}y^{+}+q^{-}y^{-}|y^{+}-y^{-}=b(\omega)-Ax;y^{+}\ge0, y^{-}\ge0\}.

 (4)

Тут Неможливо розібрати вираз (невідома помилка): q^{+},q^{-},y^{+},y^{-} - m-мірні вектори.

Будемо називати модель (1)-(3) найпростішою постановкою двохетапної задачі лінійного стохастичного програмування. Очевидно, що завдання (4) другого етапу має плани при довільної реалізації Неможливо розібрати вираз (невідома помилка): (\omega)

і будь-якому вибраному попередньому плані х.

Тобто Неможливо розібрати вираз (невідома помилка): K_{2}=R^{n}

і Неможливо розібрати вираз (невідома помилка):  K=K_{1}=\{x|A^{(1)}x=b^{(1)}, x\ge0\}

.

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

Неможливо розібрати вираз (невідома помилка): \{z|zB\le q\}\neq\varnothing .

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

Неможливо розібрати вираз (невідома помилка): \{z|zB\le q\}=\{z|z(E, -E)\le q\}=\{z|-q^{-}\le z\le q^{+}\} \neq\varnothing .

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

тобто

Неможливо розібрати вираз (невідома помилка): q^{+}+q^{-}\ge 0.

 (5)

У практичних задачах умова (5) завжди виконується, оскільки штрафи Неможливо розібрати вираз (невідома помилка): -q^{-}

і  Неможливо розібрати вираз (невідома помилка): q^{+}

, як правило, невід'ємні.

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

Неможливо розібрати вираз (невідома помилка): Q(x,b)=\{max z(b-Ax)|-q^{-}\le z\le q^{+} \} . (6)

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

Неможливо розібрати вираз (невідома помилка): Q(x,b)={\sum\limits_{i=1}^m \Q_{i}(x,b_{i})},

де

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

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

Неможливо розібрати вираз (невідома помилка): cx+M{\sum\limits_{i=1}^m \Q_{i}(x,b_{i})\to min},

 (8)

Неможливо розібрати вираз (невідома помилка): A^{(1)}x=b^{(1)},

  (9)

Неможливо розібрати вираз (невідома помилка): x\ge0,

  (10)

де Неможливо розібрати вираз (невідома помилка): Q_{i}(x,b_{i})

визначаються з співвідношень (7).

Список використаних джерел

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