Відмінності між версіями «Випадок скінченного числа реалізацій випадкового вектору обмежень.»

Версія за 08:53, 21 травня 2019

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^*
двоетапної задачі стохастичного програмування.

Виконала: Сандирєва Марина
Доповнювала: Неділько Аліна