Ігрова постановка задач СП.

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

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

Неможливо розібрати вираз (невідома помилка): g[x,A(\omega),b(\omega),c(\omega)]=\sum^{n}_{j=1} c_j(\omega)x_j + \sum^{m}_{i=1} \phi_i \left[\sum^{n}_{j=1} a_{ij}(\omega)x_j-b_i(\omega)\right] \

(2.1) 

де Неможливо розібрати вираз (невідома помилка): \phi_i(y),(i=1,2,...,m)

– неперервна неспадна функція Неможливо розібрати вираз (невідома помилка):  y 

, що дорівнює нулю при Неможливо розібрати вираз (невідома помилка): y \leq 0 .

У термінах теорії ігор план початкової задачі інтерпретується як чиста стратегія першого гравця. Позначимо задану множину чистих стратегій того, хто приймає рішення через Неможливо розібрати вираз (невідома помилка): M . Множина Неможливо розібрати вираз (невідома помилка): \Omega

станів природи визначає множину Неможливо розібрати вираз (невідома помилка):  N 
евклідового простору розмірності Неможливо розібрати вираз (невідома помилка):  mn+m+n 

, що відповідає допустимій області змін елементів Неможливо розібрати вираз (невідома помилка): a_{ij}(\omega),b_i (\omega),c_j (\omega)

умов задачі.  

Позначимо через Неможливо розібрати вираз (невідома помилка): S

множину мішаних стратегій першого гравця, тобто множину розподілів Неможливо розібрати вираз (невідома помилка): F_x
вектора Неможливо розібрати вираз (невідома помилка): x

, визначених на Неможливо розібрати вираз (невідома помилка): M , а через Неможливо розібрати вираз (невідома помилка): T

– множину мішаних стратегій другого гравця – природи, тобто множину спільних розподілів Неможливо розібрати вираз (невідома помилка):  F_{A,b,c} 
матриці Неможливо розібрати вираз (невідома помилка):  A(\omega) 
та векторів Неможливо розібрати вираз (невідома помилка):  b(\omega) 
та Неможливо розібрати вираз (невідома помилка):  c(\omega) 

, визначених на Неможливо розібрати вираз (невідома помилка): N . У тих випадках, коли розподіл частини параметрів відомий, розглядаються лише ті мішані стратегії, в яких розподіл цих параметрів збігається з відомим. Нехай вони утворюють множину Неможливо розібрати вираз (невідома помилка): \tilde{T} \subset T .

У прийнятих позначеннях ігрова постановка задачі стохастичного програмування (задачі управління в умовах часткової невизначеності) може бути сформульована таким чином.

Потрібно обчистити такі мішані стратегії Неможливо розібрати вираз (невідома помилка): F_x^*\in S

та Неможливо розібрати вираз (невідома помилка):  F_{A,b,c}^*\in \tilde{T} 

, що

При досить загальних умовах (компактності множин М та N) існують F_x^*∈S та F_(A,b,c)^*∈ T ̃, на яких досягається рішення гри.

Зазвичай розглядають два крайніх випадки задачі управління в умовах часткової невизначеності: задачу вибору рішення в умовах невизначеності та задачу вибору розв’язку в умовах ризику. Перша постановка відповідає випадку, коли про спільне розподіл F_(A,b,c) параметрів умов задачі заздалегідь нічого невідомо. У цьому випадку T ̃≡T являє собою безліч всіляких розподілів, визначених на N, і розв’язок F_x^* стохастичної задачі визначає, взагалі кажучи, мішану стратегію.

В задачах управління в умовах ризику функція F_(A,b,c) відома заздалегідь і множина T ̃ складається з цього єдиного елементу. Залежно від того, як обирається множина М планів задачі, отримаємо різні постановки задач стохастичного програмування. Зокрема, якщо в якості множини М взяти область

отримаємо задачу з імовірнісними обмеженнями.

Рішенням цієї задачі є детермінований план х, тобто оптимальна стратегія першого гравця – чиста стратегія.

Нехай і раніше S – множина мішаних стратегій першого гравця – множина допустимих розподілів Fх вектора х, а Т – множина мішаних стратегій природи – множина розподілів Fω, випадкових параметрів умов задачі. При досить загальних умовах існує розв’язок гри в мішаних стратегіях, тобто існує сідлова точка функції плати:

Іншими словами, існують мішані стратегії F_x^*∈S та F_(A,b,c)^*∈T ̃ (T ̃ – множина, визначена заданими обмеженнями на допустимі мішані стратегії природи), такі, що

Оптимальна стратегія F_x^* першого гравця являє собою апріорний розв’язувальний розподіл задачі стохастичного програмування в ігровій постановці.

Особливий інтерес, природно, викликають випадки, коли можна отримати розв’язок в чистих стратегіях.

Теорема 2.1. Нехай непорожня множина Т опукла та стабкокомпактна, φ_i,i=1,…,m, опуклі, а ψ_0 (ω,x) та φ_i [ψ_i (ω,x) ],i=1,…,m рівномірно (по F_ω∈T ̃) інтегровані для всіх x∈X={x≥0}. Тоді

Оптимальна чиста стратегія х* першого гравця являє собою апріорне розв’язувальне правило задачі стохастичного програмування в ігровій постановці.

; ; ; ; ;