Випадок скінченного числа реалізацій випадкового вектору обмежень.
27. Випадок скінченого числа реалізацій вектора b(w)
Нехай випадковими параметрами умов двухетапної стохастичної задачі є тільки компоненти вектора обмежень b. Розглянемо випадок скінченого числа реалізацій вектора b.
Нехай вектор обмежень b приймає скінчене число значень Неможливо розібрати вираз (невідома помилка): b_{(1)}, b_{(2)},..., b_{(M)}
відповідно з ймовірностями Неможливо розібрати вираз (невідома помилка): p^{(1)}, p^{(2)},..., p^{(M)}
(Неможливо розібрати вираз (невідома помилка): \sum_{j=1}^{M} p^{j}=1
)
В цьому випадку двухетапна задача може бути записана в наступному вигляді. Треба обчислити вектори Неможливо розібрати вираз (невідома помилка): x, y^{(1)}, y^{(2)},..., y^{(M)}
, які мінімізують лінійну форму:
Неможливо розібрати вираз (невідома помилка): L=cx+\sum_{j=1}^{M} p^{(j)} qy^{(j)}
при умовах Неможливо розібрати вираз (невідома помилка): \left\{\begin{matrix} Ax+By^{(1)}=b_{(1)} \\ Ax+By^{(2)}=b_{(2)} \\ ... \\ Ax+By^{(M)}=b_{(M)} \end{matrix}\right.
Неможливо розібрати вираз (невідома помилка): x\geq 0, y^{j}\geq 0, j=1,2,...N
Теорема. Для оптимального плану Неможливо розібрати вираз (невідома помилка): x^*
двухетапної задачі необхідно і достатньо, щоб при Неможливо розібрати вираз (невідома помилка): x=x^*
існував розв’язок Неможливо розібрати вираз (невідома помилка): z^* (b,x^*)
задачі Неможливо розібрати вираз (невідома помилка): Q(x,A,b)=max_{x} z(b-Ax), zB\leq q
, двоїстої до задачі другого етапу, що задовольняє відношенням
Неможливо розібрати вираз (невідома помилка): c_{x^{*}}=M\left [ c-z^{*}(b,x^{^{*}}) A \right ] \geq 0
Неможливо розібрати вираз (невідома помилка): L_{x^{*}} \left(x^{*} \right )=M\left [ c-z^{*}(b,x^{^{*}}) A \right ]x^{*}= 0
Запишемо задачу, двоїсту до задач (1)-(3). (В якості змінних двоїстої задачі тут приймаються параметри Неможливо розібрати вираз (невідома помилка): p^{(j)}z^{(j)}
.)
Треба обчислити максимум лінійної форми
Неможливо розібрати вираз (невідома помилка): p^{(1)}z^{(1)}b_{(1)}+p^{(2)}z^{(2)}b_{(2)}+...+p^{(M)}z^{(M)}b_{(M)}
при умовах Неможливо розібрати вираз (невідома помилка): p^{(1)}A^T z^{(1)}+p^{(2)}A^T z^{(2)}+...+p^{(M)}A^T z^{(M)}\leq c
Неможливо розібрати вираз (невідома помилка): \left\{\begin{matrix} B^Tz^{(1)}\leq q \\ B^Tz^{(2)}\leq q \\ ... \\ B^Tz^{(M)}\leq q \end{matrix}\right.
Структура задачі (27.6)-(27.8) дозволяє, використовуючи методи блочного програмування, визначити план двухетапної задачі.
Розв’язуючи задачу (27.6)-(27.8) методом розкладу, доцільно прийняти умови (27.7) в якості «чіпляючих» обмежень, а умови (27.8) розглядати як єдиний блок. Відповідна z-задача буде містити 𝑛_1+1 умов. Вона має вигляд
Неможливо розібрати вираз (невідома помилка): \sum_{v=1}^{x}=\sigma _{\nu } z_{\nu }\rightarrow max
при умовах Неможливо розібрати вираз (невідома помилка): \sum_{\nu =1}^{x} P_{\nu }z_{\nu }\leq c, \sum_{\nu =1}^{x} z_{\nu }=1, z_{\nu }\geq 0, \nu =1,2,..., s
(для спрощення приймається, що область, визначена умовам (8), обмежена.)
Ясно, що Неможливо розібрати вираз (невідома помилка): n_{1}
– мірний вектор Неможливо розібрати вираз (невідома помилка): \Lambda ^{(1)}
оцінок умов (9) відносно оптимального базису z – задачі співпадає з оптимальним планом Неможливо розібрати вираз (невідома помилка): x^*
двоетапної задачі стохастичного програмування.
Список використаних джерел
1. Юдин Д. Б. Математические методы управления в условиях неполной информации. / Юдин Д. Б. М: «Сов. радио», 1974. – 400 с.
Виконала: Сандирєва Марина
Доповнювала: Неділько Аліна
