Відмінності між версіями «Найпростіша постановка двохетапної задачі СП.»
| Рядок 96: | Рядок 96: | ||
<math> Ax=k</math>, <math>(Ax)_{i} = k_{i}, </math> | <math> Ax=k</math>, <math>(Ax)_{i} = k_{i}, </math> | ||
| − | <math> Q(k) = Q(x) = M {\sum\limits_{i=1}^m \Q_{i}(x,b_{i})}={\sum\limits_{i=1}^m \ | + | <math> Q(k) = Q(x) = M {\sum\limits_{i=1}^m \Q_{i}(x,b_{i})}={\sum\limits_{i=1}^m \M\Q_{i}(k_{i},b_{i})}= {\sum\limits_{i=1}^m \Q_{i}(k_{i})}. </math> |
Версія за 16:22, 8 квітня 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^{-}
і Неможливо розібрати вираз (невідома помилка): 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}-<] 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).
Розглянемо кілька інших форм запису еквівалентної детермінованої задачі для найпростішої постановки двохетапної задачі. При різних умовах різні форми запису можуть виявитися більш зручними для аналізу.
Введемо вектори
Неможливо розібрати вираз (невідома помилка): \tilde {q} = \frac{1}{2} (q^{+} + q^{-}), \tilde {c} = c - 1/2 (q^{+} - q^{-}) A.
Маємо
Неможливо розібрати вираз (невідома помилка): \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^{-}).
(11)
На планах двохетапної задачі
Неможливо розібрати вираз (невідома помилка): (y^{+} - y^{-}) = b - Ax.
Виключаючи тривіальний практично нецікавий випадок, можна вважати що Неможливо розібрати вираз (невідома помилка): q^{+}>0, q^{-}>0.
Тому на оптимальному плані Неможливо розібрати вираз (невідома помилка): y^{+} y^{-} = 0
і Неможливо розібрати вираз (невідома помилка): y^{+} + y^{-} = |b - Ax|.
Із (11) видно, що при цьому розв'язанні задачі задовольняє рівнянню
Неможливо розібрати вираз (невідома помилка): \tilde {c} x + \tilde {q} M |b - Ax| + \frac{1}{2} (q^{+} - q^{-}) Mb = cx + M(q^{+} y^{+} + q^{-} y^{-}).
Тому еквівалентна детермінована задача дя двохетапної задачі в найпростішій постановці може бути переписана у вигляді
Неможливо розібрати вираз (невідома помилка): \tilde {c}x+\tilde {q}M|b - Ax|\to min,
(12)
Неможливо розібрати вираз (невідома помилка): A^{(1)}x=b^{(1)},
(13)
Неможливо розібрати вираз (невідома помилка): x\ge0.
(14)
Наведемо ще одну форму записи цієї ж завдання. Введемо позначення
Неможливо розібрати вираз (невідома помилка): Ax=k , Неможливо розібрати вираз (невідома помилка): (Ax)_{i} = k_{i},
Неможливо розібрати вираз (невідома помилка): Q(k) = Q(x) = M {\sum\limits_{i=1}^m \Q_{i}(x,b_{i})}={\sum\limits_{i=1}^m \M\Q_{i}(k_{i},b_{i})}= {\sum\limits_{i=1}^m \Q_{i}(k_{i})}.
Список використаних джерел
1. Юдин Д. Б. Математические методы управления в условиях неполной информации. / Юдин Д. Б. М: «Сов. радио», 1974. – 400 с.
