Відмінності між версіями «Задача з імовірнісними обмеженнями. Детермінований аналог для довільного розподілу випадкового вектора b.»
Roshen (обговорення • внесок) м |
Roshen (обговорення • внесок) |
||
| (не показано одну проміжну версію цього учасника) | |||
| Рядок 1: | Рядок 1: | ||
| − | Зведення задачі стохастичного програмування до еквівалентної детермінованої задачі є ефективним засобом аналізу стохастичних моделей лише в тих випадках, коли детерміновані еквіваленти виявляються задачами лінійного або опуклого програмування. | + | <font size=3>Зведення задачі стохастичного програмування до еквівалентної детермінованої задачі є ефективним засобом аналізу стохастичних моделей лише в тих випадках, коли детерміновані еквіваленти виявляються задачами лінійного або опуклого програмування. |
Крім того, не всі задачі опуклого програмування пристосовані до використання ряду відомих ефективних методів розв'язку. Застосування таких методів опуклого програмування, як методи можливих напрямків, метод січних площин і інших методів, пов'язаних з обчисленням градієнтів функцій, що визначають обмеження задачі, припускає опуклість кожної із цих функцій у відповідну сторону (залежно від знака нерівності). | Крім того, не всі задачі опуклого програмування пристосовані до використання ряду відомих ефективних методів розв'язку. Застосування таких методів опуклого програмування, як методи можливих напрямків, метод січних площин і інших методів, пов'язаних з обчисленням градієнтів функцій, що визначають обмеження задачі, припускає опуклість кожної із цих функцій у відповідну сторону (залежно від знака нерівності). | ||
| Рядок 5: | Рядок 5: | ||
Приведемо деякі класи лінійних стохастичних задач із імовірнісними обмеженнями, для яких детерміновані еквіваленти являють собою задачі опуклого програмування. Покажемо також, як вони можуть бути перетворені до виду, зручного для використання ефективних методів розв'язку. | Приведемо деякі класи лінійних стохастичних задач із імовірнісними обмеженнями, для яких детерміновані еквіваленти являють собою задачі опуклого програмування. Покажемо також, як вони можуть бути перетворені до виду, зручного для використання ефективних методів розв'язку. | ||
| − | Вже була розглянута лінійна стохастична задача з імовірнісними обмеженнями в 5 пункті, у якій випадковими були тільки незалежні між собою складові вектора b | + | Вже була розглянута лінійна стохастична задача з імовірнісними обмеженнями в 5 пункті, у якій випадковими були тільки незалежні між собою складові вектора b: |
| − | <math> M(cx)\to \max </math> | + | <math> M(cx)\to \max, </math> |
| − | <math>P(\sum^{n}_{j=1}{a_{ij}x_{j}}\leqslant b_{i}) \geqslant \ | + | <math>P(\sum^{n}_{j=1}{a_{ij}x_{j}}\leqslant b_{i}) \geqslant \alpha_i, i=1, 2, \ldots,m, </math> |
| − | <math> x_j\geqslant 0, j=1,\ldots,n </math> | + | <math> x_j\geqslant 0, j=1, 2, \ldots,n. </math> |
| − | Еквівалентна детермінована задача у цьому випадку виявилася лінійною | + | Еквівалентна детермінована задача у цьому випадку виявилася лінійною: |
| − | <math> \overline{c}x \to \max </math> | + | <math> \overline{c}x \to \max, </math> |
| − | <math> Ax\leqslant \tilde{b} </math> | + | <math> Ax\leqslant \tilde{b}, </math> |
| − | <math> x\geqslant 0 </math> | + | <math> x\geqslant 0. </math> |
| − | Трохи складніше ситуація в тому випадку, коли імовірнісне обмеження задане у формі (б), | + | Трохи складніше ситуація в тому випадку, коли імовірнісне обмеження задане у формі (б), |
| − | + | ||
| − | + | ||
| − | <math> \ | + | <math> P(Ax \geqslant b) \geqslant \alpha, 0 \leqslant \alpha \leqslant 1, </math> |
| − | <math> | + | навіть якщо при цьому окремі компоненти вектора <math> b </math> незалежні між собою. Еквівалентна детермінована задача в цьому випадку формулюється наступним чином. Вимагається обчислити детерміновані вектори <math> x </math> і <math> g(x) </math> (або <math> x </math> і <math> \tilde{b} </math>), при яких |
| − | <math> | + | <math> \overline{c}x \to \max, </math> |
| − | + | <math> F_{x}(g(x))=F_{x}(Ax- \tilde {b})=\alpha, </math> | |
| − | + | <math> g(x) = Ax- \tilde{b} , x \geqslant 0. </math> | |
| − | <math> P \{b \geqslant \tilde {b} \} = \prod_{i =1}^m P \{b_i \geqslant \tilde{b_i} \} = \prod_{i =1}^m [1-P \{b_i < \tilde{b_i}) ] = \prod_{i =1}^m [1- F_{b_{i}}(\tilde{b_{i}}) ] </math> | + | Тут |
| + | |||
| + | <math> F_{x}(Ax- \tilde{b})= P \{ Ax-b<Ax- \tilde{b} \} = P \{b> \tilde {b} \}. </math> | ||
| + | |||
| + | У випадку, коли складові <math> b_i </math> вектора <math> b </math> - незалежні випадкові величини, | ||
| + | |||
| + | <math> P \{b \geqslant \tilde {b} \} = \prod_{i =1}^m P \{b_i \geqslant \tilde{b_i} \} = \prod_{i =1}^m [1-P \{b_i < \tilde{b_i}) ] = \prod_{i =1}^m [1- F_{b_{i}}(\tilde{b_{i}}) ], </math> | ||
де <math> F_{b_{i}}(\tilde{b_{i}}) </math> - функція розподілу компоненти <math> b_i </math> вектора <math> b </math>. | де <math> F_{b_{i}}(\tilde{b_{i}}) </math> - функція розподілу компоненти <math> b_i </math> вектора <math> b </math>. | ||
| Рядок 41: | Рядок 45: | ||
Еквівалентна детермінована задача при цьому набуває вигляду: | Еквівалентна детермінована задача при цьому набуває вигляду: | ||
| − | <math> \overline{c}x \to \max </math> | + | <math> \overline{c}x \to \max, </math> |
| − | <math> Ax\leqslant \tilde{b} </math> | + | <math> Ax\leqslant \tilde{b}, </math> |
| − | <math> \prod_{i =1}^m [1- F_{b_{i}}(\tilde{b_{i}}) ] \geqslant \alpha </math> | + | <math> \prod_{i =1}^m [1- F_{b_{i}}(\tilde{b_{i}}) ] \geqslant \alpha, </math> |
| − | <math> x\geqslant 0 </math> | + | <math> x\geqslant 0. </math> <font> |
Поточна версія на 16:52, 9 квітня 2019
Зведення задачі стохастичного програмування до еквівалентної детермінованої задачі є ефективним засобом аналізу стохастичних моделей лише в тих випадках, коли детерміновані еквіваленти виявляються задачами лінійного або опуклого програмування.
Крім того, не всі задачі опуклого програмування пристосовані до використання ряду відомих ефективних методів розв'язку. Застосування таких методів опуклого програмування, як методи можливих напрямків, метод січних площин і інших методів, пов'язаних з обчисленням градієнтів функцій, що визначають обмеження задачі, припускає опуклість кожної із цих функцій у відповідну сторону (залежно від знака нерівності).
Приведемо деякі класи лінійних стохастичних задач із імовірнісними обмеженнями, для яких детерміновані еквіваленти являють собою задачі опуклого програмування. Покажемо також, як вони можуть бути перетворені до виду, зручного для використання ефективних методів розв'язку.
Вже була розглянута лінійна стохастична задача з імовірнісними обмеженнями в 5 пункті, у якій випадковими були тільки незалежні між собою складові вектора b:
Неможливо розібрати вираз (невідома помилка): M(cx)\to \max,
Неможливо розібрати вираз (невідома помилка): P(\sum^{n}_{j=1}{a_{ij}x_{j}}\leqslant b_{i}) \geqslant \alpha_i, i=1, 2, \ldots,m,
Неможливо розібрати вираз (невідома помилка): x_j\geqslant 0, j=1, 2, \ldots,n.
Еквівалентна детермінована задача у цьому випадку виявилася лінійною:
Неможливо розібрати вираз (невідома помилка): \overline{c}x \to \max,
Неможливо розібрати вираз (невідома помилка): Ax\leqslant \tilde{b},
Неможливо розібрати вираз (невідома помилка): x\geqslant 0.
Трохи складніше ситуація в тому випадку, коли імовірнісне обмеження задане у формі (б),
Неможливо розібрати вираз (невідома помилка): P(Ax \geqslant b) \geqslant \alpha, 0 \leqslant \alpha \leqslant 1,
навіть якщо при цьому окремі компоненти вектора Неможливо розібрати вираз (невідома помилка): b
незалежні між собою. Еквівалентна детермінована задача в цьому випадку формулюється наступним чином. Вимагається обчислити детерміновані вектори Неможливо розібрати вираз (невідома помилка): x
і Неможливо розібрати вираз (невідома помилка): g(x)
(або Неможливо розібрати вираз (невідома помилка): x
і Неможливо розібрати вираз (невідома помилка): \tilde{b}
), при яких
Неможливо розібрати вираз (невідома помилка): \overline{c}x \to \max,
Неможливо розібрати вираз (невідома помилка): F_{x}(g(x))=F_{x}(Ax- \tilde {b})=\alpha,
Неможливо розібрати вираз (невідома помилка): g(x) = Ax- \tilde{b} , x \geqslant 0.
Тут
Неможливо розібрати вираз (невідома помилка): F_{x}(Ax- \tilde{b})= P \{ Ax-b<Ax- \tilde{b} \} = P \{b> \tilde {b} \}.
У випадку, коли складові Неможливо розібрати вираз (невідома помилка): b_i
вектора Неможливо розібрати вираз (невідома помилка): b - незалежні випадкові величини,
Неможливо розібрати вираз (невідома помилка): P \{b \geqslant \tilde {b} \} = \prod_{i =1}^m P \{b_i \geqslant \tilde{b_i} \} = \prod_{i =1}^m [1-P \{b_i < \tilde{b_i}) ] = \prod_{i =1}^m [1- F_{b_{i}}(\tilde{b_{i}}) ],
де Неможливо розібрати вираз (невідома помилка): F_{b_{i}}(\tilde{b_{i}})
- функція розподілу компоненти Неможливо розібрати вираз (невідома помилка): b_i вектора Неможливо розібрати вираз (невідома помилка): b
.
Еквівалентна детермінована задача при цьому набуває вигляду:
Неможливо розібрати вираз (невідома помилка): \overline{c}x \to \max,
Неможливо розібрати вираз (невідома помилка): Ax\leqslant \tilde{b},
Неможливо розібрати вираз (невідома помилка): \prod_{i =1}^m [1- F_{b_{i}}(\tilde{b_{i}}) ] \geqslant \alpha,
Неможливо розібрати вираз (невідома помилка): x\geqslant 0.
Виконав: Олійник Артем Олександрович
Доповнювала: Татьяненко Марина Олександрівна
