Класифікація задач стохастичного програмування: за виглядом цільової функції та за умовами обмеження.
Типова постановка задач стохастичного програмування
Типову задачу математичного програмування в детермінованій постановці формулюють так: визначити вектор Неможливо розібрати вираз (невідома помилка): \X=(x_{1},x_{2},…,x_{n}) , для компонент якого:
max(min)F=f(x), q_i (X)≤0(i=(1,m) ̅ ), X≥0.
Якщо функції в даній задачі крім керованих параметрів Х залежать ще і від деяких випадкових величин ω=(ω_1,ω_2,…,ω_n), то маємо задачу стохастичного програмування: max(min)F=f(X,ω), q_i (X,ω)≤0(i=(1,m) ̅ ), X≥0,ω∈Ω. де Ω — простір подій ω.
Залежно від можливості отримати та врахувати інформацію стосовно детермінованості (стохастичності) функцій f(X,ω), q_i (X,ω) постановки задач стохастичного програмування можуть містити:
- стохастичні коефіцієнти цільової функції та детерміновані обмеження;
- детерміновані коефіцієнти цільової функції та стохастичні вільні члени і коефіцієнти системи обмежень;
- стохастичні коефіцієнти цільової функції, вільні члени і коефіцієнти системи обмежень.
Конкретні постановки задач стохастичного програмування мають свою специфіку. Передусім необхідно визначити:
- Детермінованим чи випадковим є вектор Х. Якщо вектор Х є детермінованим, то він не залежить від випадкових параметрів моделі. Якщо ж він випадковий, то тоді Х є функцією від ω — X(ω), тобто залежить від випадкових змінних.
- Як розуміти максимізацію (мінімізацію) цільової функції — як абсолютну (для всіх значень ω∈Ω) чи як максимізацію її математичного сподівання або деякої іншої ймовірнісної характеристики цієї функції (моди, медіани), або як мінімізацію середнього квадратичного відхилення?
- Як виконуються обмеження: абсолютно для всіх ω∈Ω чи в середньому, або з допустимими порушеннями, ймовірність яких мала?
[7, с 392].
В якості цільової функції задачі стохастичного лінійного програмування з імовірнісними обмеженнями зазвичай приймають такі функціонали, як математичне сподівання або дисперсію лінійної форми або ймовірність перевищення лінійною формою деякого фіксованого порога.
- за виглядом цільової функції
1. Задачі з цільовою функцією Неможливо розібрати вираз (невідома помилка): \overline{cx}=M(cx)
називають М- моделями.
2. Задачі, в яких потрібно мінімізувати дисперсію лінійної форми Неможливо розібрати вираз (невідома помилка): \ M \left \{cx-\overline{cx} \right \}^2 , називають V-моделями.
До V –моделей відносять також стохастичні задачі з показниками якості розв’язання Неможливо розібрати вираз (невідома помилка): \ M \left \{cx-c^0 x^0 \right \} , де , взагалі кажучи, Неможливо розібрати вираз (невідома помилка): {c^0 x^0} \ne \overline{cx} .
3. Стохастичні задачі, в яких оптимізується ймовірність перевищення лінійної формою деякого порога Неможливо розібрати вираз (невідома помилка): \ P \left \{cx \geq c^0 x^0 \right \} , називають P-моделями.
У цю ж групу моделей включають задачі, де потрібно мінімізувати поріг Неможливо розібрати вираз (невідома помилка): \ {k} , який не повинен бути перевищений лінійною формою Неможливо розібрати вираз (невідома помилка): \ {cx}
із заданою ймовірністю Неможливо розібрати вираз (невідома помилка): \ {\alpha}
Неможливо розібрати вираз (невідома помилка): \ {k} \rightarrow min,P({cx} \le {k})={\alpha} .
При формалізації стохастичної задачі можна привести у відповідність всій області визначення цільової функції одне або декілька імовірнісних обмежень. Умови задачі (в лінійному випадку) можуть бути представлені у вигляді одного з наступних записів:
- за умовами обмеження
Неможливо розібрати вираз (невідома помилка): \ a)
Неможливо розібрати вираз (невідома помилка): \ P \left \{ \sum^{n}_{j=1} a_{ij}x_j \geq b_{i} \right \} \geq {\alpha}_{i}, 0 \le {\alpha}_{i} \le 1, i=1,...,m
,
Неможливо розібрати вираз (невідома помилка): \ b)
Неможливо розібрати вираз (невідома помилка): \ P \left \{ Ax \geq {b} \right \} \geq {\alpha}, 0 \le {\alpha} \le 1
,
Неможливо розібрати вираз (невідома помилка): \ c)
Неможливо розібрати вираз (невідома помилка): \ P \left \{ \sum^{n}_{j=1} a_{i_kj}x_j \geq b_{i_k}; i_{k}\subset{I_{k}} \right \} \geq {\alpha}_{k}, 0 \le {\alpha}_{k} \le 1, k=1,...,s, \bigcup\limits_{k=1}^s I_k= \left \{ 1,...,m \right \}
.
Будемо називати задачі з імовірнісними обмеженнями, заданими у формі (a), задачами з порядковим ймовірносними обмеженнями , а задачі з обмеженнями у формі (b) - задачами з імовірністним обмеженням.
У задачі, в якій обмеження записані у формі (b), всі випадкові параметри умов можуть бути корельовані. Однак в цьому записі не враховується порівняльна важливість окремих обмежень. У записі (а) можуть бути враховані тільки стохастичні зв'язку випадкових параметрів умов задачі, що належать одному рядку. Однак при цьому запис (а) дозволяє відобразити різне відношення до нев'язок, які виникають у різних обмеженнях задачі. У записі (а) виконання кожного з обмежень - рядків може бути забезпечено різними (для кожного рядка) множинами реалізацій явищ природи Неможливо розібрати вираз (невідома помилка): \ {\omega} , які визначаються випадковими параметрами умов задачі Неможливо розібрати вираз (невідома помилка): \ a_{ij} (\omega)
і Неможливо розібрати вираз (невідома помилка): \ b_i (\omega)
. Множина Неможливо розібрати вираз (невідома помилка): \ {\omega} , для якої одночасно виконуються всі обмеження (а), може виявитися порожньою. Аналогічні зауваження можуть бути зроблені з приводу запису (с).
Вибір значень ймовірностей Неможливо розібрати вираз (невідома помилка): \ {\alpha},{\alpha}_{i},{\alpha}_{k} , є предметом самостійної задачі. Зокрема, ці величини можуть бути обрані в результаті попереднього дослідження і зіставлення витрат, пов'язаних із збільшенням параметрів Неможливо розібрати вираз (невідома помилка): \ {\alpha},{\alpha}_{i},{\alpha}_{k}
і показника якості розв’язання вихідної стохастичної задачі що досягається за рахунок цього ефекту при оптимізації.
У кожному окремому випадку тільки змістовна інтерпретація умов задачі дозволяє вибрати характер розв’язання, вид цільової функції і спосіб розчленовування умов, які найкращим чином відображають істотні аспекти постановки задачі. Нехай, наприклад, умови задачі обмежують вибір параметрів плану виробництва (інтенсивності використання різних технологічних способів), виходячи з вимоги забезпечити з певною ймовірністю задоволення випадкового попиту Неможливо розібрати вираз (невідома помилка): \ b_{i}
на i-й продукт. Запис умов у формі (b) доцільна в тому випадку, коли один і той же споживач багаторазово замовляє всі Неможливо розібрати вираз (невідома помилка): \ {m}
видів вироблених продуктів. Запис умов у формі (а) природна в тих випадках, коли різні продукти замовляються різними споживачами. Аналогічним чином визначається область застосування запису (с) , що включає як крайні окремі випадки записи (а) і (b). У загальному випадку, коли немає необхідності обмежуватися задачами лінійного стохастичного програмування, імовірнісні обмеження записуються у вигляді
Неможливо розібрати вираз (невідома помилка): \ P \left \{ x \in G_{i} (\omega) \right \} \geq {\alpha}_{i} ,
де Неможливо розібрати вираз (невідома помилка): \ G_{i} (\omega) -деяка випадкова область, що задається системою рівностей і нерівностей або будь-яким іншим конструктивним чином [1, c. 64].
Список використаних джерел
1. Юдин Д. Б. Математические методы управления в условиях неполной информации. / Юдин Д. Б. М: «Сов. радио», 1974. – 400 с.
Виконала: Самойленко Тетяна
Доповнювала: Кухаренко Анастасія
