Відмінності між версіями «Найпростіша постановка двохетапної задачі СП.»
| Рядок 10: | Рядок 10: | ||
де | де | ||
| − | <math>P(x,b)=\{min(q^{+}y^{+}+q^{-}y^{-}|y^{+}-y^{-}=b(\omega)-Ax;y^{+}\ge0, y^{-}\ge0\}</math> (4) | + | <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-мірні вектори. | Тут <math>q^{+},q^{-},y^{+},y^{-}</math>- m-мірні вектори. | ||
| Рядок 19: | Рядок 19: | ||
довільної реалізації <math>(\omega)</math> і будь-якому вибраному попередньому плані х. | довільної реалізації <math>(\omega)</math> і будь-якому вибраному попередньому плані х. | ||
| − | Тобто <math>K_{2}=R^{n}</math> і <math> K=K_{1}=\{x|A^{(1)}x=b^{(1)}, x\ge0\}</math> | + | Тобто <math>K_{2}=R^{n}</math> і <math> K=K_{1}=\{x|A^{(1)}x=b^{(1)}, x\ge0\}</math>. |
Необхідна і достатня умова існування кінцевого | Необхідна і достатня умова існування кінцевого | ||
| Рядок 25: | Рядок 25: | ||
задачі набуває досить простий вигляд. У загальному випадку ця умова має вигляд | задачі набуває досить простий вигляд. У загальному випадку ця умова має вигляд | ||
| − | <math>\{z|zB\le q\}\neq\varnothing </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>\{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^{-}\le q^{+}</math> тобто | ||
| − | <math>q^{+}+q^{-}\ge 0</math> (5) | + | <math>q^{+}+q^{-}\ge 0</math>. (5) |
У практичних задачах умова (5) завжди виконується, | У практичних задачах умова (5) завжди виконується, | ||
| − | оскільки штрафи <math>-q^{-}\le q^{+}</math>, як правило, невід' | + | оскільки штрафи <math>-q^{-}\le q^{+}</math>, як правило, невід'ємні. |
Задача, двоїста до задачі (4) другого етапу, має вигляд | Задача, двоїста до задачі (4) другого етапу, має вигляд | ||
| − | <math>Q(x,b)=\{max z(b-Ax)|-q^{-}\le z\le q^{+} \}</math> (6) | + | <math>Q(x,b)=\{max z(b-Ax)|-q^{-}\le z\le q^{+} \}</math>. (6) |
| − | Задача (6) легко вирішується. | + | Задача (6) легко вирішується. Розв'язок цієї задачі записується формулою |
<math>Q(x,b)={\sum\limits_{i=1}^m \Q_{i}(x,b_{i})},</math> | <math>Q(x,b)={\sum\limits_{i=1}^m \Q_{i}(x,b_{i})},</math> | ||
| Рядок 53: | Рядок 53: | ||
-[b_{i}-(Ax)_{i}] q^{-}_{i}, | -[b_{i}-(Ax)_{i}] q^{-}_{i}, | ||
b_{i}-(Ax)_{i}\le 0 | b_{i}-(Ax)_{i}\le 0 | ||
| − | \end{cases}</math> (7) | + | \end{cases}</math>. (7) |
Тому еквівалентна опукла задача для двоетапної | Тому еквівалентна опукла задача для двоетапної | ||
Версія за 13:00, 26 березня 2019
Розглянемо, двоетапну задачу, в якій випадковим є тільки вектор обмежень, а матриця компенсації В (після відповідної перестановки рядків і стовпців) може бути представлена у вигляді В = (Е, -Е), де Е - одинична матриця розміру 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^{-}\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).
