Випадок скінченного числа реалізацій випадкового вектору обмежень.
Нехай,як і раніше випадковим параметром умов двоетапної стохастичної задачі являються тільки компоненти вектора обмежень b. Розглянемо випадок скінченного числа реалізацій вектора b.
Нехай вектор обмежень b в приймає скінченну кількість значень
Неможливо розібрати вираз (невідома помилка): b_{(1)}, b_{(2)},…,b_{(N)}
відповідно з ймовірностями
Неможливо розібрати вираз (невідома помилка): p^{(1)}, p^{(2)},…, p^{(N)}
Неможливо розібрати вираз (невідома помилка): \sum^{N}_{j=1}{p^{j}}=1
В цьому випадку двоетапна задача може бути записана в наступному вигляді. Необхідно знайти вектори Неможливо розібрати вираз (невідома помилка): x,y^{(1)}, y^{(2)},…, y^{(N)}
які мінімізують лінійну форму:
Неможливо розібрати вираз (невідома помилка): L=cx+\sum^{N}_{j=1}p^{(j)}qy_{(j)}
(2.1)
За умов
Неможливо розібрати вираз (невідома помилка): Ax+B y^{(1)} = b_{(1)}
(2.2)
Неможливо розібрати вираз (невідома помилка): Ax+B y^{(2)} = b_{(2)}
Неможливо розібрати вираз (невідома помилка): Ax+B y^{(N)} = b_{(N)}
Неможливо розібрати вираз (невідома помилка): x\geqslant 0, y^{j}\geqslant 0, j=1,\ldots N
(2.3)
Раніше доведені наступні необхідні і достатні умови оптимальності плану двоетапної задачі зі скінченним числом реалізацій випадкового вектора обмежень.
Теорема 2.1.
Для оптимальності плану Неможливо розібрати вираз (невідома помилка): x^{* }
двоетапної задачі необхідно і достатньо, щоб при Неможливо розібрати вираз (невідома помилка): x=x^{* }
існував розв'язок
Неможливо розібрати вираз (невідома помилка): z^{* }(b, x^{* })
задачі двоїстої до задачі другого етапу, яка задовольняє відношення
Неможливо розібрати вираз (невідома помилка): c_{x*}=M[c- z^{* }(b, x^{* })A]\geqslant 0
(2.4)
Неможливо розібрати вираз (невідома помилка): L_{x*}(x*)=M[c- z^{* }(b, x^{* })A]x*= 0
(2.5)
Теорема є уточненням теореми 5.1 розділ 6 для випадку скінченного числа реалізацій вектора b коли умови теореми 5.1 порушуються.
Запишемо задачу, двоїсту по відношенню до задачі (2.1)-(2.3) . У якості змінних двоїстої задачі тут приймаються параметри Неможливо розібрати вираз (невідома помилка): p^{(j)}z^{(j)}
Потрібно максимізувати лінійну форму
Неможливо розібрати вираз (невідома помилка): p^{(1)}z^{(1)}b_{(1)}+…+ p^{(N)}z^{(N)}b_{(N)}
(2.6)
За умов
Неможливо розібрати вираз (невідома помилка): p^{(1)}A^{T}z_{(1)}+…+ p^{(N)}A^{T}z_{(N)} \leqslant c
(2.7)
Неможливо розібрати вираз (невідома помилка): B^{T}z^{1}\leqslant q
(2.8)
Неможливо розібрати вираз (невідома помилка): B^{T}z^{2}\leqslant q
Неможливо розібрати вираз (невідома помилка): B^{T}z^{N}\leqslant q
Розв'язуючи задачу (2.6)-(2.8) методом розкладу, доречно прийняти умови (2.7) в якості «зацепляющих» обмежень, а умови (2.8) розглядати як єдиний блок. Відповідна z- задача буде містити Неможливо розібрати вираз (невідома помилка): n_{1}+1
умов. z - задача має вигляд
Неможливо розібрати вираз (невідома помилка): \sum^{s}_{v=1}{\sigma_{v}z_{v}}\rightarrow max
За умов
Неможливо розібрати вираз (невідома помилка): \sum^{s}_{v=1}{P_{v}z_{v}}\leqslant c
(2.9)
Неможливо розібрати вираз (невідома помилка): \sum^{s}_{v=1}{ z_{v}}=1
Неможливо розібрати вираз (невідома помилка): z_{v} \geqslant 0, v=1,\ldots s
(для спрощення приймається, що область , визначена умовам (2.8) , обмежена.)
Ясно, що Неможливо розібрати вираз (невідома помилка): n_{1}
- мірний вектор оцінок умов(2.9) відносно оптимального базису z - задачі співпадає з оптимальним планом x* двоетапної задачі стохастичного програмування.
Виконала: Овчаренко Мар'яна Миколаївна
