Відмінності між версіями «Постановки задач стохастичного програмування. Жорсткі постановки, межі застосування. Імовірнісні, статистичні та мішані умови обмеження.»
3241243 (обговорення • внесок) |
|||
| (не показані 7 проміжних версій 2 учасників) | |||
| Рядок 18: | Рядок 18: | ||
(1.3) | (1.3) | ||
| − | Запис (1.1)‒(1.3), визначений при детермінованих значеннях параметрів умов задачі, є невизначеним і потребує додаткових пояснень при випадкових значеннях параметрів вихідної інформації. | + | Запис (1.1)‒(1.3), визначений при детермінованих значеннях параметрів умов задачі, є невизначеним і потребує додаткових пояснень при випадкових значеннях параметрів вихідної інформації. В багатьох прикладних задачах коефіцієнти цільової функції, елементи матриці умов або складові вектора обмежень - випадкові величини. |
| − | Можна навести ряд моделей вибору розв'язків в умовах неповної інформації, в яких обмеження задачі повинні задовольнятись при всіх реалізаціях випадкових параметрів. Відповідні постановки задач стохастичного програмування називають '''жорсткими постановками'''. Жорсткі постановки природні у тому випадку, коли кожна (чи майже кожна) поява | + | Можна навести ряд моделей вибору розв'язків в умовах неповної інформації, в яких обмеження задачі повинні задовольнятись при всіх реалізаціях випадкових параметрів. Відповідні постановки задач стохастичного програмування називають '''жорсткими постановками'''. Жорсткі постановки природні у тому випадку, коли кожна (чи майже кожна) поява невязки в умовах задачі загрожує занадто великими штрафами і зменшує ефективність оптимізації лінійної форми. Але задача (1.1)‒(1.3) в жорсткій постановці може не мати планів. Область визначення задачі СП в жорсткій постановці являє собою перетин багатогранних множин (1.2) ‒ (1.3), які відповідають за кожну реалізацію параметрів умов задачі. Цей перетин може виявитись пустим. Жорстка постановка задачі СП в цьому випадку втрачає сенс. |
В багатьох задачах управління в умовах неповної інформації, пов'язаних з ситуаціями, що повторюються, немає необхідності у тому, щоб обмеження задачі задовольнялись при кожній реалізації випадку. | В багатьох задачах управління в умовах неповної інформації, пов'язаних з ситуаціями, що повторюються, немає необхідності у тому, щоб обмеження задачі задовольнялись при кожній реалізації випадку. | ||
| − | Часто, конкретний зміст задачі потребує, щоб ймовірність попадання рішення в допустиму область перевищувала деяке наперед задане число <math> \alpha > 0 </math>. В тих випадках, коли можливі неув'язки в окремих обмеженнях викликають різноманітний збиток, доцільно диференційовано підходити до різних умов. Щоб врівноважити збиток, що визначається | + | Часто, конкретний зміст задачі потребує, щоб ймовірність попадання рішення в допустиму область перевищувала деяке наперед задане число <math> \alpha > 0 </math>. В тих випадках, коли можливі неув'язки в окремих обмеженнях викликають різноманітний збиток, доцільно диференційовано підходити до різних умов. Щоб врівноважити збиток, що визначається невязками в різних умовах задачі, природно обмежити знизу ймовірність виконання кожного з них різноманітними числами <math> \alpha_{i} > 0 </math>. Зазвичай <math> \alpha_{i} > 1/2 </math>. |
Подібні постановки задач СП називаються '''моделями з ймовірнісними обмеженнями'''. Якщо коефіцієнти лінійної форми задачі <math> cx </math> детерміновані, то показник якості (1.1) є одночасно і цільовою функцією задачі з ймовірнісними обмеженнями. Якщо компоненти вектора с випадкові, то в якості цільової функції задачі з ймовірнісними обмеженнями обирають математичне сподівання лінійної форми (1.1) або ймовірність перевищення лінійної форми сх деякого фіксованого порогу. | Подібні постановки задач СП називаються '''моделями з ймовірнісними обмеженнями'''. Якщо коефіцієнти лінійної форми задачі <math> cx </math> детерміновані, то показник якості (1.1) є одночасно і цільовою функцією задачі з ймовірнісними обмеженнями. Якщо компоненти вектора с випадкові, то в якості цільової функції задачі з ймовірнісними обмеженнями обирають математичне сподівання лінійної форми (1.1) або ймовірність перевищення лінійної форми сх деякого фіксованого порогу. | ||
| − | Можна навести ситуації, в яких змістовна постановка задачі дозволяє замінити обмеження з випадковими параметрами на нерівності, що обмежують перші або перші і другі моменти розподілу лівих частин умов (1.2). Інколи замість обмеження других моментів розподілу лівих частин умов | + | Можна навести ситуації, в яких змістовна постановка задачі дозволяє замінити обмеження з випадковими параметрами на нерівності, що обмежують перші або перші і другі моменти розподілу лівих частин умов (1.2). Інколи замість обмеження других моментів розподілу лівих частин умов обмежують другі моменти деяких функцій від невязок умов. При цьому гарантуються обмежені дисперсії деяких заздалегідь обраних характеристик розв'язків задачі. Такі постановки задач стохастичного програмування будемо називати '''моделями зі статистичними умовами'''. |
| − | В задачах СП зі статистичними умовами | + | Ми розглядали стохастичні аналоги задач лінійного програмування. В задачах СП зі статистичними умовами невязка в обмеженнях виключена не у всіх випадках, як в жорстких постановках, і не у більшості випадків, як в задачах з ймовірнісними обмеженнями (при <math> \alpha_{i} > 1/2 </math>),а в середньому. Це означає, що невязки умов, які відповідають за різні реалізації стану природи, компенсують один одного так, що середня невязка умов рівна нулю. |
Серед додатків математичних методів управління в умовах неповної інформації розглядаються також умовні екстремальні задачі, які містять як ймовірнісні так і статистичні і жорсткі умови. Такі моделі стохастичного програмування називають '''моделями з мішаними умовами'''. | Серед додатків математичних методів управління в умовах неповної інформації розглядаються також умовні екстремальні задачі, які містять як ймовірнісні так і статистичні і жорсткі умови. Такі моделі стохастичного програмування називають '''моделями з мішаними умовами'''. | ||
| Рядок 48: | Рядок 48: | ||
Якщо будь-яка з компонент <math> \psi_{k} </math> вектор-функції <math> \psi(\omega,x)</math> являє собою характеристичну функцію деякої випадкової множини <math> G_{k}(\omega) </math> , що задана системою рівностей і нерівностей або будь-яким іншим чином, то відповідний рядок системи обмежень (1.5) може бути записаний у вигляді: | Якщо будь-яка з компонент <math> \psi_{k} </math> вектор-функції <math> \psi(\omega,x)</math> являє собою характеристичну функцію деякої випадкової множини <math> G_{k}(\omega) </math> , що задана системою рівностей і нерівностей або будь-яким іншим чином, то відповідний рядок системи обмежень (1.5) може бути записаний у вигляді: | ||
| − | <math> P{x \in G_{k}(\omega)}\geqslant b_{k} </math> | + | <math> P{{x \in G_{k}(\omega)}}\geqslant b_{k} </math> |
Таким чином, запис (1.4)-(1.6) включає в себе і задачі з ймовірнісними обмеженнями. Деякі ускладнення дозволяють в аналогічній формі записувати й багатоетапні стохастичні задачі з умовними і безумовними обмеженнями. | Таким чином, запис (1.4)-(1.6) включає в себе і задачі з ймовірнісними обмеженнями. Деякі ускладнення дозволяють в аналогічній формі записувати й багатоетапні стохастичні задачі з умовними і безумовними обмеженнями. | ||
| Рядок 54: | Рядок 54: | ||
| − | Виконала: [[Користувач: | + | Виконала: [[Користувач:Маргаритка Дроздова|Дроздова Маргарита Вікторівна ]] |
| + | |||
| + | Доповнювала: [[Користувач:65890|Татьяненко Марина Олександрівна ]] | ||
Поточна версія на 17:26, 6 квітня 2021
Розглянемо задачу лінійного програмування:
Неможливо розібрати вираз (невідома помилка): \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) включає в себе і задачі з ймовірнісними обмеженнями. Деякі ускладнення дозволяють в аналогічній формі записувати й багатоетапні стохастичні задачі з умовними і безумовними обмеженнями.
Виконала: Дроздова Маргарита Вікторівна
Доповнювала: Татьяненко Марина Олександрівна
