Відмінності між версіями «Найпростіша постановка двохетапної задачі СП.»

де

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

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