Відмінності між версіями «Постановки задач стохастичного програмування. Жорсткі постановки, межі застосування. Імовірнісні, статистичні та мішані умови обмеження.»

Версія за 22:08, 15 травня 2016

Розглянемо задачу лінійного програмування:

Неможливо розібрати вираз (невідома помилка): \sum^{n}_{j=1}{c_{j}x_{j}}\rightarrow min

Неможливо розібрати вираз (невідома помилка): \sum^{n}_{j=1}{a_{ij}x_{j}}\leqslant b_{i}, i=1,\ldots,n

Неможливо розібрати вираз (невідома помилка): \ x_j\geqslant 0, j=1,\ldots,n

Або у векторному записі:

Неможливо розібрати вираз (невідома помилка): cx\rightarrow min

(1.1)

Неможливо розібрати вираз (невідома помилка): Ax-b\leqslant 0

(1.2)

Неможливо розібрати вираз (невідома помилка): x\geqslant 0

(1.3)

Запис (1.1)‒(1.3), визначений при детермінованих значеннях параметрів умов задачі, є невизначеним і потребує додаткових пояснень при випадкових значеннях параметрів вихідної інформації. В багатьох прикладних задачах коефіцієнти цільової функції, елементи матриці умов або складові вектора обмежень - випадкові величини. Можна навести ряд моделей вибору розв'язків в умовах неповної інформації, в яких обмеження задачі повинні задовольнятись при всіх реалізаціях випадкових параметрів. Відповідні постановки задач стохастичного програмування називають жорсткими постановками. Жорсткі постановки природні у тому випадку, коли кожна (чи майже кожна) поява неув'язки в умовах задачі загрожує занадто великими штрафами і зменшує ефективність оптимізації лінійної форми. Але задача (1.1)‒(1.3) в жорсткій постановці може не мати планів. Область визначення задачі СП в жорсткій постановці являє собою перетин багатогранних множин (1.2) ‒ (1.3), які відповідають за кожну реалізацію параметрів умов задачі. Цей перетин може виявитись пустим. Жорстка постановка задачі СП в цьому випадку втрачає сенс.

В багатьох задачах управління в умовах неповної інформації, пов'язаних з ситуаціями, що повторюються, немає необхідності у тому, щоб обмеження задачі задовольнялись при кожній реалізації випадку.

Часто, конкретний зміст задачі потребує, щоб ймовірність попадання рішення в допустиму область перевищувала деяке наперед задане число Неможливо розібрати вираз (невідома помилка): \alpha > 0 . В тих випадках, коли можливі неув'язки в окремих обмеженнях викликають різноманітний збиток, доцільно диференційовано підходити до різних умов. Щоб врівноважити збиток, що визначається неув'язками в різних умовах задачі, природно обмежити знизу ймовірність виконання кожного з них різноманітними числами Неможливо розібрати вираз (невідома помилка): \alpha_{i} > 0 . Зазвичай Неможливо розібрати вираз (невідома помилка): \alpha_{i} > 1/2 .

Подібні постановки задач СП називаються моделями з ймовірнісними обмеженнями. Якщо коефіцієнти лінійної форми задачі Неможливо розібрати вираз (невідома помилка): cx

детерміновані, то показник якості (1.1) є одночасно і цільовою функцією задачі з ймовірнісними обмеженнями. Якщо компоненти вектора с випадкові, то в якості цільової функції задачі з ймовірнісними обмеженнями обирають математичне сподівання лінійної форми (1.1) або ймовірність перевищення лінійної форми сх деякого фіксованого порогу. 

Можна навести ситуації, в яких змістовна постановка задачі дозволяє замінити обмеження з випадковими параметрами на нерівності, що обмежують перші або перші і другі моменти розподілу лівих частин умов (1.2). Інколи замість обмеження других моментів розподілу лівих частин умов обмежити другі моменти деяких функцій від неув'язок умов. При цьому гарантуються обмежені дисперсії деяких заздалегідь обраних характеристик розв'язків задачі. Такі постановки задач стохастичного програмування будемо називати моделями зі статистичними умовами.

В задачах СП зі статистичними умовами неув'язка в обмеженнях виключена не у всіх випадках, як в жорстких постановках, і не у більшості випадків, як в задачах з ймовірнісними обмеженнями (при Неможливо розібрати вираз (невідома помилка): \alpha_{i} > 1/2 ),а в середньому. Це означає, що неув'язки умов, які відповідають за різні реалізації стану природи, компенсують один одного так, що середня неув'язка умов рівна нулю.

Серед додатків математичних методів управління в умовах неповної інформації розглядаються також умовні екстремальні задачі, які містять як ймовірнісні так і статистичні і жорсткі умови. Такі моделі стохастичного програмування називають моделями з мішаними умовами.

Якщо не обмежуватись стохастичними аналогами лінійних моделей, можна навести більш загальний запис задачі стохастичного програмування, що об'єднує різні постановки стохастичних задач.

Нехай Неможливо розібрати вираз (невідома помилка): \psi_{0}(\omega,x)

‒ випадкова функція; Неможливо розібрати вираз (невідома помилка):  \psi(\omega,x)
‒ випадкова вектор-функція; Неможливо розібрати вираз (невідома помилка):  \omega
‒ набір випадкових параметрів умов задачі; Неможливо розібрати вираз (невідома помилка):  b 
‒ детермінований вектор; Неможливо розібрати вираз (невідома помилка):  G^{0} 
деяка множина (детермінована або випадкова); Неможливо розібрати вираз (невідома помилка):  M f(\omega,x) 
‒ математичне сподівання випадкової функції Неможливо розібрати вираз (невідома помилка): f(\omega,x) 

. Тоді:

Неможливо розібрати вираз (невідома помилка): M \psi_{0}(\omega,x)\rightarrow min

(1.4)

Неможливо розібрати вираз (невідома помилка): M \psi(\omega,x)\geqslant b

(1.5)

Неможливо розібрати вираз (невідома помилка): x\in G^{0}

(1.6)

Якщо будь-яка з компонент Неможливо розібрати вираз (невідома помилка): \psi_{k}

вектор-функції Неможливо розібрати вираз (невідома помилка):  \psi(\omega,x)
являє собою характеристичну функцію деякої випадкової множини Неможливо розібрати вираз (невідома помилка):  G_{k}(\omega) 
, що задана системою рівностей і нерівностей або будь-яким іншим чином, то відповідний рядок системи обмежень (1.5) може бути записаний у вигляді: 

Неможливо розібрати вираз (невідома помилка): P{x \in G_{k}(\omega)}\geqslant b_{k}

Таким чином, запис (1.4)-(1.6) включає в себе і задачі з ймовірнісними обмеженнями. Деякі ускладнення дозволяють в аналогічній формі записувати й багатоетапні стохастичні задачі з умовними і безумовними обмеженнями.

Виконала: Дроздова Маргарита Вікторівна