Тема 4 «Стохастичне програмування»
План лекції
1. Загальна характеристика задач стохастичного програмування. Методи розв’язання задач стохастичного програмування.
2. Приклади задач стохастичного програмування.
1. Загальна характеристика задач стохастичного програмування. Методи розв’язання задач стохастичного програмування.
Стохастичне програмування використовується для вирішення задач, в яких обмеження носять вірогідний, випадковий характер і необхідно ураховувати вплив яких-небудь непередбачених обставин. Як цільова функція, в такого роду задачах служить математичне очікування критерію, вибраного як цільова функція.
До числа такого роду задач відносяться:
комплектування ремонтних підприємств верстатним парком, коли відомий
об'єм на ті або інші об'єкти;
визначення спожитої кількості і продуктивності транспортних засобів за маршрутами, коли об'єм перевезень носить випадковий характер;
визначення запасів деяких ресурсів.
В стохастическом программировании рассматриваются проблемы принятия решений в условиях действия случайных факторов, которые необходимо учитывать в соответствующих математических моделях.
До одноетапних задач стохастичного програмування відносяться задачі, у яких рішення приймаються на основі відомих стохастичних характеристик розподілу випадкових параметрів умов задачі до спостереження за їхніми реалізаціями. При цьому повинне прийматися найкраще в середньостатистичному змісті рішення.
Постановки задач стохастичного програмування розрізняються по трьох ознаках:
1) характеру рішень;
2) вибору показника якості рішення (критерію);
3) способу декомпозиції обмежень задачі.
Обмеження на вид функції.
У задачі стохастичного програмування звичайно приймають такі функціонали, як математичне сподівання або дисперсія цільової функції, або ймовірність перевищення цільовою функцією деякого порога.
Задачі
із цільовою функцією виду
називають
М-моделями, задачі в які потрібно
мінімізувати дисперсію
називають V-моделями, а стохастичні
задачі, у яких максимізується ймовірність
,
називають Р-моделями .
В
останню групу моделей включають також
і задачі, де потрібно мінімізувати поріг
,
що не повинен бути перевищений із заданою
ймовірністю
,
наприклад:
мінімізувати
за умови
.
Обмеження можуть бути представлені в одній з наступних форм:
а)
б)
в)
Розглянемо деякі варіанти моделей одноетапних задач стохастичного програмування.
1. Нехай задана задача лінійного стохастичного програмування з імовірнісними обмеженнями типу а):
максимізувати (13)
при умовах
;
(14)
.
(15)
При
детермінованій матриці
й випадковому векторі
задача (13)–(15) зводиться до еквівалентної
детермінованої задачі ЛП у такий спосіб.
Нехай
–
спільна щільність розподілу складових
випадкового
вектора
.
Знаходимо щільність розподілу
:
Обчислимо
з
рівняння
.
(16)
Якщо рішення рівняння (16) неєдине, то в якості виберемо найбільший корінь.
Очевидно, що умови (14) при цьому еквівалентні нерівностям
,
де задовольняє співвідношенням (16). Звідси треба, що задачі стохастичного програмування (13)-(15) буде еквівалентна наступна детермінована задача ЛП:
……………………………..
(17)
при умовах
,
(18)
,
(19)
де
;
–
корінь рівняння
,
або
,
–
функція розподілу випадкової величини
.
Для
стохастичної задачі (13)–(15) з детермінованою
матрицею
можна записати двоїсту задачу з
імовірнісними обмеженнями.
Розглянемо задачу
(20)
при умовах
,
(21)
.
(22)
Її
рішення визначається у вигляді
детермінованого вектора. Нехай
–
функція розподілу випадкового коефіцієнта
функції (13), тобто
.
Якщо
,
то запис
еквівалентний запису
.
Задача (20)-(22) може бути переписана у вигляді
(23)
за умови
.
(24)
Порівнюючи
цю задачу з вихідної (13)–(15), переконуємося,
що при
наступні дві одноетапні задачі
стохастичного програмування з
імовірнісними обмеженнями являють
собою двоїсту пару:
;
(25)
.
(26)