Найпростіша постановка двохетапної задачі СП.
Розглянемо, двоетапну задачу, в якій випадковим є тільки вектор обмежень, а матриця компенсації В (після відповідної перестановки рядків і стовпців) може бути представлена у вигляді В = (Е, -Е), де Е - одинична матриця розміру 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).
Розглянемо кілька інших форм запису еквівалентної детермінованої задачі для найпростішої постановки двохетапної задачі. При різних умовах різні форми запису можуть виявитися більш зручними для аналізу.
Введемо вектори
Неможливо розібрати вираз (невідома помилка): \tilde {q} = \frac{1}{2} (q^{+} + q^{-}), \tilde {c} = c - \frac{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=\varkappa , Неможливо розібрати вираз (невідома помилка): (Ax)_{i} = \varkappa_{i},
Неможливо розібрати вираз (невідома помилка): Q(\varkappa) = Q(x) = M {\sum\limits_{i=1}^m \Q_{i}(x,b_{i})}={\sum\limits_{i=1}^m M \Q_{i}(\varkappa_{i},b_{i})}= {\sum\limits_{i=1}^m \Q_{i}(\varkappa_{i})}.
Функції Неможливо розібрати вираз (невідома помилка): Q_{i}(\varkappa_{i},b_{i}),
так як і Неможливо розібрати вираз (невідома помилка): Q_{i}(\varkappa_{i}),
- опуклі функції по Неможливо розібрати вираз (невідома помилка): \varkappa_{i}.
Двохетапна стохастична задача в найпростішій постановці зведена, таким чином, до наступної задачі опуклого сепарабельного програмування:
Неможливо розібрати вираз (невідома помилка): cx+{\sum\limits_{i=1}^m \Q_{i}(\varkappa_{i})}\to min,
(15)
Неможливо розібрати вираз (невідома помилка): A^{(1)}x=b^{(1)},
(16)
Неможливо розібрати вираз (невідома помилка): Ax=\varkappa,
(17)
Неможливо розібрати вираз (невідома помилка): x\ge0.
(18)
Вивчимо функції Неможливо розібрати вираз (невідома помилка): Q_{i}(\varkappa_{i}).
Позначимо через Неможливо розібрати вираз (невідома помилка): \delta_{i}
і Неможливо розібрати вираз (невідома помилка): \gamma_{i}
відповідно точну верхню і точну нижню грані випадкової величини Неможливо розібрати вираз (невідома помилка): b_{i}(\omega),
через Неможливо розібрати вираз (невідома помилка): \overline{b}=(\overline{b}_{1},...,\overline{b}_{m})=Mb
- математичне сподівання вектора обмежене і через Неможливо розібрати вираз (невідома помилка): F_{i} b_{i}
- функцію розподілу компонентів Неможливо розібрати вираз (невідома помилка): b_{i}(\omega).
Розділимо множину значень Неможливо розібрати вираз (невідома помилка): \varkappa_{i}
на три області: Неможливо розібрати вираз (невідома помилка): (-\infty, \gamma_{i}), [\gamma_{i}, \delta_{i}], (\delta_{i}, \infty).
Якщо Неможливо розібрати вираз (невідома помилка): b_{i}(\omega)
не має нижньої (відповідно верхньої) грані, покладем Неможливо розібрати вираз (невідома помилка): \gamma_{i}=-\infty
(відповідно Неможливо розібрати вираз (невідома помилка): \delta_{i}=\infty).
Обчислимо значення Неможливо розібрати вираз (невідома помилка): Q_{i}(\varkappa_{i})
в кожній із цих областей. Маємо
Неможливо розібрати вираз (невідома помилка): Q_{i}(\varkappa_{i})= MQ_{i}(\varkappa_{i}, b_{i})=-q^{-}_{i}\int \limits_{b_{i}\leqslant\varkappa_{i}} (b_{i}-\varkappa_{i})dF_{i}(b_{i})+q^{+}_{i}\int \limits_{b_{i}>\varkappa_{i}} (b_{i}-\varkappa_{i})dF_{i}(b_{i})=q^{+}_{i}\int \limits_{\Omega}[b_{i}(\omega)-\varkappa_{i}]dp-(q^{+}_{i}+q^{-}_{i})\int \limits_{b_{i}\leqslant\varkappa_{i}} (b_{i}-\varkappa_{i})dF_{i}(b_{i}),
або
Неможливо розібрати вираз (невідома помилка): Q_{i}(\varkappa_{i})=q^{+}_{i}\overline{b}_{i}-q^{+}_{i}\varkappa_{i}-(q^{+}_{i}+q^{-}_{i})\int \limits_{b_{i}\leqslant\varkappa_{i}} (b_{i}-\varkappa_{i})dF_{i}(b_{i}).
(19)
Розглянемо три випадки.
1. Нехай Неможливо розібрати вираз (невідома помилка): \varkappa_{i}<\gamma_{i}.
В цьому випадку
Неможливо розібрати вираз (невідома помилка): \{b_{i}|b_{i}\leqslant\varkappa_{i}\}\neq\varnothing.
Із (19) отримаємо
Неможливо розібрати вираз (невідома помилка): Q_{i}(\varkappa_{i})=q^{+}_{i}\overline{b}_{i}-q^{+}_{i}\varkappa_{i}.
Тобто функція Неможливо розібрати вираз (невідома помилка): Q_{i}(\varkappa_{i})
лінійна на проміжку Неможливо розібрати вираз (невідома помилка): (-\infty, \gamma_{i}).
2. Неможливо розібрати вираз (невідома помилка): \varkappa_{i}\in [\gamma_{i},\delta_{i}].
В цьому випадку
Неможливо розібрати вираз (невідома помилка): \{b_{i}|b_{i}\leqslant\varkappa_{i}\}=\{b_{i}|\gamma_{i}\leqslant b_{i} \leqslant \varkappa_{i}\}.
Функція Неможливо розібрати вираз (невідома помилка): Q_{i}(\varkappa_{i})
на цьому відрізку виражається співвідношенням
Неможливо розібрати вираз (невідома помилка): Q_{i}(\varkappa_{i})=q^{+}_{i}\overline{b}_{i}-q^{+}_{i}\varkappa_{i}-(q^{+}_{i}+q^{-}_{i})\int \limits^{\varkappa_{i}}_{\gamma_{i}}(b_{i}-\varkappa_{i})dF_{i}(b_{i}).
Конкретний вид опуклої функції Неможливо розібрати вираз (невідома помилка): Q_{i}(\varkappa_{i})
залежить від функції розподілу Неможливо розібрати вираз (невідома помилка): F_{i}(b_{i}).
3. Неможливо розібрати вираз (невідома помилка): \varkappa_{i}>\delta_{i}.
В цьому випадку множина Неможливо розібрати вираз (невідома помилка): \{b_{i}|b_{i}\leqslant\varkappa_{i}\}
збігається з усією областю змінної Неможливо розібрати вираз (невідома помилка): b_{i}(\omega)
і
Неможливо розібрати вираз (невідома помилка): \int \limits_{b_{i}\leqslant\varkappa_{i}} [b_{i}(\omega)-\varkappa_{i}]dF_{i}(b_{i})=\int \limits_{\Omega}[b_{i}(\omega)-\varkappa_{i}]dp=\overline{b}_{i}-\varkappa_{i}.
Отже, функція Неможливо розібрати вираз (невідома помилка): Q_{i}(\varkappa_{i})
на проміжку Неможливо розібрати вираз (невідома помилка): (\delta_{i}, \infty)
лінійна
Неможливо розібрати вираз (невідома помилка): Q_{i}(\varkappa_{i})=-q^{-}_{i}\overline{b}_{i}+q^{-}_{i}\varkappa_{i}.
Опукла функція Неможливо розібрати вираз (невідома помилка): Q_{i}(\varkappa_{i})
неперервна на всій числовій прямій.
Характер функції Неможливо розібрати вираз (невідома помилка): Q_{i}(\varkappa_{i})
дозволяє спростити запис задачі (15)-(18) і зробити її більш зручною для якісного і кількісного аналізу.
Введемо змінні Неможливо розібрати вираз (невідома помилка): \varkappa^{(1)}_{i}, \varkappa^{(2)}_{i}, \varkappa^{(3)}_{i},
задовольняють умовам
Неможливо розібрати вираз (невідома помилка): \begin{cases} \varkappa^{(1)}_{i}-\varkappa^{(2)}_{i}-\varkappa^{(3)}_{i}=\overline{b}_{i}-\varkappa_{i}, \\ \varkappa^{(1)}_{i}\geqslant\overline{b}_{i}-\gamma_{i}\geqslant0, \\ \delta_{i}-\gamma_{i}\geqslant\varkappa^{(2)}_{i}\geqslant0, \\ \varkappa^{(3)}_{i}\geqslant0 \end{cases} . (20)
Для стислості обмежимося випадком Неможливо розібрати вираз (невідома помилка): \gamma_{i}>-\infty.
Враховуючи отримані вище вираження для Неможливо розібрати вираз (невідома помилка): Q_{i}(\varkappa_{i})
на різних ділянках, можна переписати завдачу (15)-(18) в наступному вигляді:
Неможливо розібрати вираз (невідома помилка): {\sum\limits_{j=1}^n \(c_{j}x_{j})}\to min,
Список використаних джерел
1. Юдин Д. Б. Математические методы управления в условиях неполной информации. / Юдин Д. Б. М: «Сов. радио», 1974. – 400 с.
