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

Версія за 22:27, 26 березня 2014

Розглянемо, двоетапну задачу, в якій випадковим є тільки вектор обмежень, а матриця компенсації В (після відповідної перестановки рядків і стовпців) може бути представлена ​​у вигляді В = (Е, -Е), де Е - одинична матриця розміру 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^{-}\le 0

 (5)

У практичних задачах умова (5) завжди виконується, оскільки штрафи Неможливо розібрати вираз (невідома помилка): -q^{-}\le 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).