Відмінності між версіями «Ігрова постановка задач СП.»
194668 (обговорення • внесок) |
|||
| (не показано 13 проміжних версій цього учасника) | |||
| Рядок 1: | Рядок 1: | ||
| − | + | <font size=3> Зазвичай в задачах стохастичного програмування спільний розподіл випадкових параметрів умов задачі припускається заданим. В тих випадках, коли за тими чи іншими міркуваннями визначення спільного розподілу випадкових початкових даних не є можливим, стохастична задача може бути розглянута як гра двох осіб з нульовою сумою. </font> | |
| − | [[ | + | |
| − | [ | + | <font size=3> Першим є гравець, який приймає рішення. Він прагне звести до мінімуму середню плату за гру. Йому протистоїть природа, що обирає свої стани, виходячи з тенденції максимізувати середню плату першого гравця. При кожному стані природи та виборі стратегії х першого гравця, функція плати задається як сума відповідних значень лінійної форми задачі та штрафу за нев’язку плану. </font> |
| − | [ | + | |
| − | + | <font size=3> <math> 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] \ </math> (2.1) </font> | |
| − | [[ | + | |
| + | <font size=3> де <math> \phi_i(y),(i=1,2,...,m) </math> – неперервна неспадна функція <math> y </math>, що дорівнює нулю при <math> y \leq 0 </math>. </font> | ||
| + | |||
| + | <font size=3> У термінах теорії ігор план початкової задачі інтерпретується як чиста стратегія першого гравця. Позначимо задану множину чистих стратегій того, хто приймає рішення через <math> M </math>. Множина <math> \Omega </math> станів природи визначає множину <math> N </math> евклідового простору розмірності <math> mn+m+n </math>, що відповідає допустимій області змін елементів <math> a_{ij}(\omega),b_i (\omega),c_j (\omega)</math> умов задачі. </font> | ||
| + | |||
| + | <font size=3> Позначимо через <math> S </math> множину мішаних стратегій першого гравця, тобто множину розподілів <math>F_x</math> вектора <math>x</math>, визначених на <math> M </math>, а через <math> T </math> – множину мішаних стратегій другого гравця – природи, тобто множину спільних розподілів <math> F_{A,b,c} </math> матриці <math> A(\omega) </math> та векторів <math> b(\omega) </math> та <math> c(\omega) </math>, визначених на <math> N </math>. У тих випадках, коли розподіл частини параметрів відомий, розглядаються лише ті мішані стратегії, в яких розподіл цих параметрів збігається з відомим. Нехай вони утворюють множину <math> \tilde{T} \subset T </math>. </font> | ||
| + | |||
| + | <font size=3> У прийнятих позначеннях ігрова постановка задачі стохастичного програмування (задачі управління в умовах часткової невизначеності) може бути сформульована таким чином. </font> | ||
| + | |||
| + | <font size=3> Потрібно обчистити такі мішані стратегії <math> F_x^*\in S </math> та <math> F_{A,b,c}^*\in \tilde{T} </math>, що </font> | ||
| + | |||
| + | <font size=3> <math> \min_{F_x\in S} \max_{F_{A,b,c}^*\in \tilde{T}} \int_{M\times N} g(\xi,\alpha,\beta,\gamma)dF_x(\xi)dF_{A,b,c}(\alpha,\beta,\gamma) = \max_{F_{A,b,c}^*\in \tilde{T}} \min_{F_x\in S} \int_{M\times N} g(\xi,\alpha,\beta,\gamma)dF_x(\xi)dF_{A,b,c}(\alpha,\beta,\gamma)= </math> </font> | ||
| + | |||
| + | <font size=3> <math> =\int_{M\times N} g(\xi,\alpha,\beta,\gamma)dF_x^*(\xi)dF_{A,b,c}^*(\alpha,\beta,\gamma) </math> (2.2) </font> | ||
| + | |||
| + | <font size=3> При досить загальних умовах (компактності множин <math>M</math> та <math>N</math>) існують <math> F_x^*\in S </math> та <math> F_{A,b,c}^*\in \tilde{T} </math>, на яких досягається розв’язок гри. </font> | ||
| + | |||
| + | |||
| + | |||
| + | <font size=3> Зазвичай розглядають два крайніх випадки задачі управління в умовах часткової невизначеності: задачу вибору рішення в умовах невизначеності та задачу вибору розв’язку в умовах ризику. Перша постановка відповідає випадку, коли про спільне розподіл <math> F_{A,b,c} </math> параметрів умов задачі заздалегідь нічого невідомо. У цьому випадку <math> T \equiv \tilde{T} </math> являє собою безліч всіляких розподілів, визначених на <math> N </math>, і розв’язок <math> F_x^* </math> стохастичної задачі визначає, взагалі кажучи, мішану стратегію. </font> | ||
| + | |||
| + | <font size=3> В задачах управління в умовах ризику функція <math> F_{A,b,c} </math> відома заздалегідь і множина <math> \tilde{T} </math> складається з цього єдиного елементу. Залежно від того, як обирається множина <math>M</math> планів задачі, отримаємо різні постановки задач стохастичного програмування. Зокрема, якщо в якості множини <math> M </math> взяти область </font> | ||
| + | |||
| + | <font size=3> <math> \{x: P[A(\omega)x \leq b(\omega)]\} \geq \alpha, 0\le\alpha\le1 </math>, </font> | ||
| + | |||
| + | <font size=3> отримаємо задачу з імовірнісними обмеженнями. </font> | ||
| + | |||
| + | <font size=3> Розв’язком цієї задачі є детермінований план <math> x </math>, тобто оптимальна стратегія першого гравця – чиста стратегія. </font> | ||
| + | |||
| + | <font size=3> Нехай і раніше <math> S </math> – множина мішаних стратегій першого гравця – множина допустимих розподілів <math>F_x</math> вектора <math>x</math>, а <math>T</math> – множина мішаних стратегій природи – множина розподілів <math> F_{\omega} </math> випадкових параметрів умов задачі. При досить загальних умовах існує розв’язок гри в мішаних стратегіях, тобто існує сідлова точка функції плати: </font> | ||
| + | |||
| + | <font size=3> <math> \int_{X\times \Omega} g(\omega,x)dF_xdF_{\omega} </math> </font> | ||
| + | |||
| + | <font size=3> Іншими словами, існують мішані стратегії <math> F_x^*\in S </math> та <math> F_{A,b,c}^*\in \tilde{T} </math> (<math> \tilde{T} </math> – множина, визначена заданими обмеженнями на допустимі мішані стратегії природи), такі, що </font> | ||
| + | |||
| + | <font size=3> <math> \min_{F_x\in S} \max_{F_{\omega}\in \tilde{T}} \int_{X\times \Omega} g(\omega,x)dF_xdF_{\omega} = \max_{F_{\omega}\in \tilde{T}} \min_{F_x\in S} \int_{X\times \Omega} g(\omega,x)dF_xdF_{\omega} = \int_{X\times \Omega} g(\omega,x)dF_x^*dF_{\omega}^* </math> (2.3) </font> | ||
| + | |||
| + | |||
| + | |||
| + | <font size=3> Оптимальна стратегія <math> F_x^* </math> першого гравця являє собою апріорний розв’язувальний розподіл задачі стохастичного програмування в ігровій постановці. </font> | ||
| + | |||
| + | <font size=3> Особливий інтерес, природно, викликають випадки, коли можна отримати розв’язок в чистих стратегіях. </font> | ||
| + | |||
| + | |||
| + | |||
| + | <font size=3> '''Теорема 2.1.''' Нехай непорожня множина <math> \tilde{T} </math> опукла та слабкокомпактна, <math> \phi_i, i=1,...,m. </math> опуклі, а <math> \psi_0(\omega,x) </math> та <math> \phi_i[\psi_i(\omega,x)], i=1,...,m. </math> рівномірно (по <math> F_{\omega}\in \tilde{T} </math>) інтегровані для всіх <math> x\in X = \{x\geq0\} </math>. Тоді </font> | ||
| + | |||
| + | <font size=3> <math> \min_{x\in X} \max_{F_{\omega}\in \tilde{T}} \int_{\Omega} g(\omega,x)dF_{\omega} = \max_{F_{\omega}\in \tilde{T}} \min_{x\in X} \int_{\Omega} g(\omega,x)dF_{\omega} = \int_{\Omega} g(\omega,x^*)dF_{\omega}^* </math> </font> | ||
| + | |||
| + | |||
| + | |||
| + | <font size=3> Оптимальна чиста стратегія <math> x^* </math> першого гравця являє собою апріорне розв’язувальне правило задачі стохастичного програмування в ігровій постановці [1, c. 135-137]. </font> | ||
| + | |||
| + | |||
| + | |||
| + | ==Список використаних джерел== | ||
| + | 1. Юдин Д. Б. Математические методы управления в условиях неполной информации. / Юдин Д. Б. М: «Сов. радио», 1974. – 400 с. | ||
| + | |||
| + | |||
| + | |||
| + | Виконала: [[Користувач:Іванченко Олександра|Іванченко Олександра]] | ||
Поточна версія на 20:50, 3 червня 2017
Зазвичай в задачах стохастичного програмування спільний розподіл випадкових параметрів умов задачі припускається заданим. В тих випадках, коли за тими чи іншими міркуваннями визначення спільного розподілу випадкових початкових даних не є можливим, стохастична задача може бути розглянута як гра двох осіб з нульовою сумою.
Першим є гравець, який приймає рішення. Він прагне звести до мінімуму середню плату за гру. Йому протистоїть природа, що обирає свої стани, виходячи з тенденції максимізувати середню плату першого гравця. При кожному стані природи та виборі стратегії х першого гравця, функція плати задається як сума відповідних значень лінійної форми задачі та штрафу за нев’язку плану.
Неможливо розібрати вираз (невідома помилка): 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}
, що
Неможливо розібрати вираз (невідома помилка): \min_{F_x\in S} \max_{F_{A,b,c}^*\in \tilde{T}} \int_{M\times N} g(\xi,\alpha,\beta,\gamma)dF_x(\xi)dF_{A,b,c}(\alpha,\beta,\gamma) = \max_{F_{A,b,c}^*\in \tilde{T}} \min_{F_x\in S} \int_{M\times N} g(\xi,\alpha,\beta,\gamma)dF_x(\xi)dF_{A,b,c}(\alpha,\beta,\gamma)=
Неможливо розібрати вираз (невідома помилка): =\int_{M\times N} g(\xi,\alpha,\beta,\gamma)dF_x^*(\xi)dF_{A,b,c}^*(\alpha,\beta,\gamma)
(2.2)
При досить загальних умовах (компактності множин Неможливо розібрати вираз (невідома помилка): M
та Неможливо розібрати вираз (невідома помилка): N
) існують Неможливо розібрати вираз (невідома помилка): F_x^*\in S
та Неможливо розібрати вираз (невідома помилка): F_{A,b,c}^*\in \tilde{T}
, на яких досягається розв’язок гри.
Зазвичай розглядають два крайніх випадки задачі управління в умовах часткової невизначеності: задачу вибору рішення в умовах невизначеності та задачу вибору розв’язку в умовах ризику. Перша постановка відповідає випадку, коли про спільне розподіл Неможливо розібрати вираз (невідома помилка): F_{A,b,c}
параметрів умов задачі заздалегідь нічого невідомо. У цьому випадку Неможливо розібрати вираз (невідома помилка): T \equiv \tilde{T}
являє собою безліч всіляких розподілів, визначених на Неможливо розібрати вираз (невідома помилка): N
, і розв’язок Неможливо розібрати вираз (невідома помилка): F_x^*
стохастичної задачі визначає, взагалі кажучи, мішану стратегію.
В задачах управління в умовах ризику функція Неможливо розібрати вираз (невідома помилка): F_{A,b,c}
відома заздалегідь і множина Неможливо розібрати вираз (невідома помилка): \tilde{T}
складається з цього єдиного елементу. Залежно від того, як обирається множина Неможливо розібрати вираз (невідома помилка): M
планів задачі, отримаємо різні постановки задач стохастичного програмування. Зокрема, якщо в якості множини Неможливо розібрати вираз (невідома помилка): M
взяти область
Неможливо розібрати вираз (невідома помилка): \{x: P[A(\omega)x \leq b(\omega)]\} \geq \alpha, 0\le\alpha\le1 ,
отримаємо задачу з імовірнісними обмеженнями.
Розв’язком цієї задачі є детермінований план Неможливо розібрати вираз (невідома помилка): x , тобто оптимальна стратегія першого гравця – чиста стратегія.
Нехай і раніше Неможливо розібрати вираз (невідома помилка): S
– множина мішаних стратегій першого гравця – множина допустимих розподілів Неможливо розібрати вираз (невідома помилка): F_x вектора Неможливо розібрати вираз (невідома помилка): x
, а Неможливо розібрати вираз (невідома помилка): T
– множина мішаних стратегій природи – множина розподілів Неможливо розібрати вираз (невідома помилка): F_{\omega}
випадкових параметрів умов задачі. При досить загальних умовах існує розв’язок гри в мішаних стратегіях, тобто існує сідлова точка функції плати:
Неможливо розібрати вираз (невідома помилка): \int_{X\times \Omega} g(\omega,x)dF_xdF_{\omega}
Іншими словами, існують мішані стратегії Неможливо розібрати вираз (невідома помилка): F_x^*\in S
та Неможливо розібрати вираз (невідома помилка): F_{A,b,c}^*\in \tilde{T}
(Неможливо розібрати вираз (невідома помилка): \tilde{T}
– множина, визначена заданими обмеженнями на допустимі мішані стратегії природи), такі, що
Неможливо розібрати вираз (невідома помилка): \min_{F_x\in S} \max_{F_{\omega}\in \tilde{T}} \int_{X\times \Omega} g(\omega,x)dF_xdF_{\omega} = \max_{F_{\omega}\in \tilde{T}} \min_{F_x\in S} \int_{X\times \Omega} g(\omega,x)dF_xdF_{\omega} = \int_{X\times \Omega} g(\omega,x)dF_x^*dF_{\omega}^*
(2.3)
Оптимальна стратегія Неможливо розібрати вираз (невідома помилка): F_x^*
першого гравця являє собою апріорний розв’язувальний розподіл задачі стохастичного програмування в ігровій постановці.
Особливий інтерес, природно, викликають випадки, коли можна отримати розв’язок в чистих стратегіях.
Теорема 2.1. Нехай непорожня множина Неможливо розібрати вираз (невідома помилка): \tilde{T}
опукла та слабкокомпактна, Неможливо розібрати вираз (невідома помилка): \phi_i, i=1,...,m.
опуклі, а Неможливо розібрати вираз (невідома помилка): \psi_0(\omega,x)
та Неможливо розібрати вираз (невідома помилка): \phi_i[\psi_i(\omega,x)], i=1,...,m.
рівномірно (по Неможливо розібрати вираз (невідома помилка): F_{\omega}\in \tilde{T}
) інтегровані для всіх Неможливо розібрати вираз (невідома помилка): x\in X = \{x\geq0\} . Тоді
Неможливо розібрати вираз (невідома помилка): \min_{x\in X} \max_{F_{\omega}\in \tilde{T}} \int_{\Omega} g(\omega,x)dF_{\omega} = \max_{F_{\omega}\in \tilde{T}} \min_{x\in X} \int_{\Omega} g(\omega,x)dF_{\omega} = \int_{\Omega} g(\omega,x^*)dF_{\omega}^*
Оптимальна чиста стратегія Неможливо розібрати вираз (невідома помилка): x^*
першого гравця являє собою апріорне розв’язувальне правило задачі стохастичного програмування в ігровій постановці [1, c. 135-137].
Список використаних джерел
1. Юдин Д. Б. Математические методы управления в условиях неполной информации. / Юдин Д. Б. М: «Сов. радио», 1974. – 400 с.
Виконала: Іванченко Олександра
