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