Одноетапна Р-модель з імовірнісними обмеженнями. Алгоритм побудови розв’язувального правила. Приклад.
Формально задача записується у наступному вигляді:
Неможливо розібрати вираз (невідома помилка): P({x(\omega)\in G_0(\omega)})\rightarrow sup,
(4.1)
Неможливо розібрати вираз (невідома помилка): P({x(\omega)\in G_i(\omega)})\ge\alpha_i,i=1,2,...,m
(4.2)
Можна вказати наступні дев'ять попарно несумісних ситуацій взаємного розміщення множин Неможливо розібрати вираз (невідома помилка): G_i, i=0,1,2,
які показують всі можливі випадки:
1. Неможливо розібрати вираз (невідома помилка): G_1\cap G_2 \cap G_0 \ne \varnothing
2. Неможливо розібрати вираз (невідома помилка): G_1\cap G_2 \cap G_0 = \varnothing, G_1\cap G_2 = \varnothing, G_1\cap G_0 \ne \varnothing, G_2\cap G_0 \ne \varnothing
3. Неможливо розібрати вираз (невідома помилка): G_1\cap G_2 \cap G_0 = \varnothing, G_1\cap G_2 \ne \varnothing, G_1\cap G_0 \ne \varnothing, G_2\cap G_0 = \varnothing
4. Неможливо розібрати вираз (невідома помилка): G_1\cap G_2 \ne \varnothing, G_1\cap G_0 = \varnothing, G_2\cap G_0 \ne \varnothing
5. Неможливо розібрати вираз (невідома помилка): G_1\cap G_2 = \varnothing, G_1\cap G_0 \ne \varnothing, G_2\cap G_0 \ne \varnothing
6. Неможливо розібрати вираз (невідома помилка): G_1\cap G_2 = \varnothing, G_1\cap G_0 = \varnothing, G_2\cap G_0 = \varnothing
7. Неможливо розібрати вираз (невідома помилка): G_1\cap G_2 = \varnothing, G_1\cap G_0 \ne \varnothing, G_2\cap G_0 = \varnothing
8. Неможливо розібрати вираз (невідома помилка): G_1\cap G_2 = \varnothing, G_1\cap G_0 = \varnothing, G_2\cap G_0 \ne \varnothing
9. Неможливо розібрати вираз (невідома помилка): G_1\cap G_2 = G_1\cap G_0 = G_2\cap G_0 = \varnothing
Нехай Неможливо розібрати вираз (невідома помилка): \Omega_i
‒ множина тих Неможливо розібрати вираз (невідома помилка): \omega \in \Omega при яких реалізується і-та ситуація і Неможливо розібрати вираз (невідома помилка): p_i=P\Omega_i, i=1,...,9.
Розчленуємо множину Неможливо розібрати вираз (невідома помилка): U=\bigcup\limits_{k=0}^2 G_k
на 7 підмножин Неможливо розібрати вираз (невідома помилка): U^j
, які попарно не перетинаються, наступним чином:
Неможливо розібрати вираз (невідома помилка): U^1=G_0 \cap G_1 \cap G_2 ,
Неможливо розібрати вираз (невідома помилка): U^2=(G_0 \cap G_1)\setminus G_0 \cap G_1\cap G_2 ,
Неможливо розібрати вираз (невідома помилка): U^3=(G_0 \cap G_2) \setminus G_0 \cap G_1\cap G_2 ,
Неможливо розібрати вираз (невідома помилка): U^4=(G_1 \cap G_2)\setminus G_0 \cap G_1\cap G_2 ,
Неможливо розібрати вираз (невідома помилка): U^5=G_0\setminus [(G_0\cap G_1)\cup (G_0 \cap G_2)] ,
Неможливо розібрати вираз (невідома помилка): U^6=G_1 \setminus [(G_0\cap G_1)\cup (G_1 \cap G_2)] ,
Неможливо розібрати вираз (невідома помилка): U^7=G_2 \setminus [(G_0\cap G_2)\cup (G_1 \cap G_2)] ,
Очевидно, що Неможливо розібрати вираз (невідома помилка): U=\bigcup\limits_{j=0}^7 U^j; U^i \cap U^j = \varnothing
Введемо змінні Неможливо розібрати вираз (невідома помилка): u_i^j
Неможливо розібрати вираз (невідома помилка): u_i^j=P({x\in U^j | i})
Неможливо розібрати вираз (невідома помилка): u_i^j
- умовна ймовірність події Неможливо розібрати вираз (невідома помилка): x \in U^j за умови, що має місце і-та ситуація взаємного розміщення множин Неможливо розібрати вираз (невідома помилка): G_k
.
Мають місце співвідношення: Неможливо розібрати вираз (невідома помилка): \sum^{T}_{j=1} u_i^j =1, i=1,...,9 . Задача (4.1)-(4.2) еквівалентна наступній задачі лінійного програмування:
Неможливо розібрати вираз (невідома помилка): f(u)=\sum^{9}_{i=1} p_i(u_i^1+u_i^2+u_i^3+u_i^5) \rightarrow sup,
(4.3)
Неможливо розібрати вираз (невідома помилка): \sum^{9}_{i=1} p_i(u_i^1+u_i^2+u_i^4+u_i^6) \geqslant \alpha_1
(4.4)
Неможливо розібрати вираз (невідома помилка): \sum^{9}_{i=1} p_i(u_i^1+u_i^3+u_i^4+u_i^7) \geqslant \alpha_2
(4.5)
Неможливо розібрати вираз (невідома помилка): \sum^{9}_{i=1}u_i^j =1 , i=1,...9,
(4.6)
Неможливо розібрати вираз (невідома помилка): u_i^j \geqslant 0 , i=1,...9, j=1,...,7
. (4.7)
Деякі зі змінних Неможливо розібрати вираз (невідома помилка): u_i^j
для окремих ситуацій дорівнюють 0. Маємо:
Неможливо розібрати вираз (невідома помилка): \begin{cases} u_i^1=0, i=2,...,9, \\ u_i^2=0, i=4,6,8,9, \\ u_i^3=0, i=3,6,7,9,\\u_i^4=0, i=5,7,8,9 \end{cases}
(4.8)
Побудуємо двоїсту задачу до задачі (4.3)-(4.8):
Неможливо розібрати вираз (невідома помилка): g(\lambda)=-\alpha_1 \lambda_1 - \alpha_2\lambda_2+ \sum^{9}_{i=1}\lambda_{i+2} \rightarrow inf
(4.9)
Неможливо розібрати вираз (невідома помилка): \begin{cases} \lambda_{i+2}\geqslant\begin{cases} p_i(1+\lambda_1+\lambda_2), i=1,\\ p_i(1+\lambda_1+\lambda_2)-\lambda_i^1, i=2,...,9,\end{cases}\\ \lambda_{i+2}\geqslant\begin{cases} p_i(1+\lambda_1), i=1,2,3,5,7,\\ p_i(1+\lambda_2)+\lambda_i^2, i=1,2,3,5,7,\end{cases}\\ \lambda_{i+2}\geqslant\begin{cases} p_i(1+\lambda_2), i=1,2,3,5,7,\\ p_i(1+\lambda_2)-\lambda_i^3, i=3,6,7,9,\end{cases}\\ \lambda_{i+2}\geqslant\begin{cases} p_i(\lambda_1+\lambda_2), i=1,2,3,4,6,\\ p_i(\lambda_1+\lambda_2)-\lambda_i^4, i=5,7,8,9,\end{cases}\\ \lambda_{i+2}\geqslant p_i, i=1,...,9,\\ \lambda_{i+2}\geqslant p_i\lambda_1, i=1,...,9,\\ \lambda_{i+2}\geqslant p_i\lambda_2, i=1,...,9, \end{cases}
(4.10)
Неможливо розібрати вираз (невідома помилка): \lambda_1 \geqslant 0,\lambda_2 \geqslant 0
(4.11)
Тут двоїсті змінні Неможливо розібрати вираз (невідома помилка): \lambda_1 ,\lambda_2
відповідають обмеженням (4.4) та (4.5) прямої задачі, змінні Неможливо розібрати вираз (невідома помилка): \lambda_{i+2} (i=1,...,9)
відповідають умовам (4.6), а Неможливо розібрати вираз (невідома помилка): \lambda_i^j(i=1,...,9, j=1,2,3,4)
- умовам (4.8).
Позначимо через Неможливо розібрати вираз (невідома помилка): \phi_i^k (\lambda_1, \lambda_2), (i=1,...,9; k=1,...7)
лінійні функції змінних Неможливо розібрати вираз (невідома помилка): \lambda_1 ,\lambda_2 які входять у праві частини умов (4.10), а через лінійні функції змінних Неможливо розібрати вираз (невідома помилка): K(i) - множину індексів, для яких відповідні умови із співвідношень (4.10) не містять змінних Неможливо розібрати вираз (невідома помилка): \lambda_i^k
. Тоді нерівності (4.10) можна переписати у вигляді:
Неможливо розібрати вираз (невідома помилка): \lambda_{i+2}\geqslant \begin{cases}\phi_i^k, k\in K(i), \\ \phi_i^k - \lambda_i^k, k\notin K(i). \end{cases}
(4.12)
Маємо наступні функції:
Неможливо розібрати вираз (невідома помилка): \phi_i(\lambda_1,\lambda_2) = max_{k\in K(i)} ({\phi_i^k (\lambda_1,\lambda_2)})
(4.13)
Неможливо розібрати вираз (невідома помилка): \zeta_i(\lambda_1,\lambda_2, \lambda_i^k) = max_{k \in K(i)} ({\phi_i^k (\lambda_1,\lambda_2) - \lambda_i^k })
(4.14)
Тоді:
Неможливо розібрати вираз (невідома помилка): \lambda_{i+2} \geqslant max ({\phi_i, \zeta_i})
(4.15)
Лема 4.1. На оптимальному плані задачі (4.9)-(4.11) мають місце рівності
Неможливо розібрати вираз (невідома помилка): \lambda_{i+2} = \phi_i(\lambda_1,\lambda_2), (i=1,...,9)
(4.16)
Теорема 4.2. Якщо умови задачі (4.1)-(4.2) сумісні, то Неможливо розібрати вираз (невідома помилка): supf(x)
за умов (4.4.)-(4.7) дорівнює найменшому із семи чисел:
Неможливо розібрати вираз (невідома помилка): S_1=(1-\alpha_1)+p_1-p_9,
Неможливо розібрати вираз (невідома помилка): S_2=(1-\alpha_2)+1-p_3-p_6-p_7-p_9,
Неможливо розібрати вираз (невідома помилка): S_3=2(1-\alpha_1)+(1-\alpha_2)+p_1-p_8-p_9,
Неможливо розібрати вираз (невідома помилка): S_4=(1-\alpha_1)+1-p_4-p_6-p_8-p_9,
Неможливо розібрати вираз (невідома помилка): S_5=(1-\alpha_1)+2(1-\alpha_2)+p_1-p_7-p_9,
Неможливо розібрати вираз (невідома помилка): S_6=\frac{1}{2}[(1-\alpha_1)+(1-\alpha_2)+1-p_1-p_6-p_9],
Неможливо розібрати вираз (невідома помилка): S_7=1
Умова Неможливо розібрати вираз (невідома помилка): f(u)-S_k
разом з обмеженнями (4.10), (4.11) висікає множину оптимальних планів задачі. Для кожного набору параметрів умов задачі Неможливо розібрати вираз (невідома помилка): (\alpha_1,\alpha_2,p_i) оптимальні значення Неможливо розібрати вираз (невідома помилка): u_i^j належать одній із семи множин. Використовуючи другу теорему двоїстості лінійного програмування, можна виділити серед компонент розв'язку "вільні" та "закріплені". Таким чином отримаємо можливість, не розв'язуючи задачі, визначити оптимальні значення частини змінних, незалежно від реалізації випадкових параметрів умов задачі. Маючи на увазі, крім цього, співвідношення (4.8), отримаємо таблицю 4.1.
Використовуючи таблицю 4.1. можна спростити рівняння і нерівності, які визначають сім (по числу Неможливо розібрати вираз (невідома помилка): S_k ) можливих багатогранних множин оптимальних планів задачі (4.3)-(4.7). Маємо:
Неможливо розібрати вираз (невідома помилка): \begin{cases} p_2(u_2^2+u_2^4)+ p_4 u_4^4+ p_5 u_5^2+ p_9 u_9^6 =\alpha_1 - p_1 - p_3 - p_6 - p_7,\\ p_2(u_2^2+u_2^4)+ p_4 u_3^4 + p_5 u_5^2+ p_9 u_9^6 =\alpha_2 - p_1 - p_4 - p_6 - p_8,\\ u_2^2 +u_2^3+u_2^4=1, u_3^2+u_3^4 =1, \\ u_4^3 +u_4^4=1, u_5^2+u_5^3 =1,\\ u_9^2 +u_9^6+u_9^7=1, u_i^j \geqslant 0 \end{cases}
(4.19)
Неможливо розібрати вираз (невідома помилка): \begin{cases} p_3(u_3^2+u_3^5)+ p_6 u_6^5+ p_7( u_7^2+u_7^5)+p_9 u_9^5 =1-\alpha_2,\\ p_2u_1^1+ p_3 (u_3^2 u_3^4)+ p_6 u_6^4 + p_7 u_7^2=\alpha_1 \\ u_1^1 +u_1^3=1, u_3^2+u_3^4 + u_3^5+u_3^7=1, \\ u_5^4 +u_6^5+u_6^7=1, u_7^2+u_7^5+u_7^7 =1,\\ u_5^9 +u_9^7=1, u_i^j \geqslant 0 \end{cases}
(4.20)
Неможливо розібрати вираз (невідома помилка): \begin{cases} p_3 u_2^2+p_3 u_3^5= (1-\alpha_1)+(1-\alpha_2)- p_5 - p_7 - p_8 - p_9,\\ p_8u_8^3= 1-\alpha_1, p_8u_8^6= p_8-1+\alpha_1,\\ u_2^2 +u_2^4=1, u_3^2+u_3^4 =1, u_i^j \geqslant 0 \end{cases}
(4.21)
Неможливо розібрати вираз (невідома помилка): \begin{cases} p_4(u_3^4+u_4^5)+ p_6 u_6^5+ p_8( u_8^3+u_8^5)+p_9 u_9^5 =1-\alpha_1,\\ p_1u_1^1+ p_4 (u_4^3 u_4^4)+ p_6 u_6^4 + p_8 u_8^3\geqslant\alpha_2 \\ u_1^1 +u_1^2=1, u_4^3+u_4^4 + u_4^5+u_4^6=1, \\ u_6^4 +u_6^5+u_6^6=1, u_8^3+u_8^5+u_8^6 =1,\\ u_9^5 +u_9^6=1, u_i^j \geqslant 0 \end{cases}
(4.22)
Неможливо розібрати вираз (невідома помилка): \begin{cases} p_2 u_2^3+p_4 u_4^3= (1-\alpha_1)+(1-\alpha_2)- p_5 - p_7 - p_8 - p_9,\\ p_7u_7^2= 1-\alpha_2, p_7u_7^7= p_7-1+\alpha_2,\\ u_2^3 +u_2^4=1, u_4^3+u_4^4 =1, u_i^j \geqslant 0 \end{cases}
(4.23)
Неможливо розібрати вираз (невідома помилка): \begin{cases} p_2 u_2^2+p_5 u_5^2= \frac{1}{2}(\alpha_1-\alpha_2+ p_2 + p_4 - p_3 + p_5 - p_7 + p_8),\\ p_6u_6^4= \frac{1}{2}(\alpha_1+\alpha_2 -1 - p_1 + p_6 + p_9),\\ u_2^2 +u_2^3=1, u_5^2+u_5^3 =1, u_6^4+u_6^5 =1, u_i^j \geqslant 0 \end{cases}
(4.24)
Неможливо розібрати вираз (невідома помилка): \begin{cases} p_1(u_1^1+u_1^2)+ p_2 u_2^2+ p_3 u_3^2+ p_5 u_5^2 + p_7 u_7^2 \geqslant\alpha_1,\\ p_1(u_1^1+u_1^3)+ p_2 u_2^3+ p_4 u_4^3+ p_5 u_5^3 + p_8 u_8^3 \geqslant\alpha_2,\\ u_1^1 +u_1^2+u_1^3+u_1^5=1, u_2^2+u_3^2+u_5^2 =1, \\ u_3^2+u_3^5=1, u_4^3+u_4^5 =1,\\ u_5^2 +u_5^3+u_5^5=1, \\ u_7^2+u_7^5=1, u_8^3+u_8^5 =1, u_i^j \geqslant 0 \end{cases}
(4.25)
Таким чином, маємо:
Наслідок 4.2. Множина оптимальних планів задачі (4.3)-(4.7) визначається таблицею 4.1. та однією із систем (4.19)-(4.25) (в залежності від значень Неможливо розібрати вираз (невідома помилка): \alpha_2, \alpha_1
та Неможливо розібрати вираз (невідома помилка): p_i
).
Теорема 4.3. Якщо задача (4.1)-(4.2) сумісна, то існує ф-я Неможливо розібрати вираз (невідома помилка): x^*(\omega)
яка є розв'язком задачі. При цьому, якщо верхня грань цільового функціонала Неможливо розібрати вираз (невідома помилка): S(\alpha_1,\alpha_2) дорівнює k-му числу Неможливо розібрати вираз (невідома помилка): S_k системи, яка визначається теоремою 4.2., тоді розв'язки задачі і тільки вони задовольняють умовам (4.2) та k-му рівнянню наступної системи:
Приклад. Розглянемо наступну задачу стохастичного програмування:
Неможливо розібрати вираз (невідома помилка): P\{c(\omega) x(\omega) \geqslant L{\omega) } \rightarrow sup,
(4.26)
Неможливо розібрати вираз (невідома помилка): \begin{cases} P\{A(\omega) x(\omega) \leqslant b{\omega)} \geqslant \alpha_1,\\ P{x(\omega) \geqslant 0} \geqslant \alpha_2\end{cases}
(4.27)
Припускається, що випадкова величина Неможливо розібрати вираз (невідома помилка): L(\omega)
, всі компоненти випадкових векторів Неможливо розібрати вираз (невідома помилка): c(\omega) i b(\omega) та елементи випадкової матриці Неможливо розібрати вираз (невідома помилка): A(\omega) невід'ємні майже при всіх Неможливо розібрати вираз (невідома помилка): \omega Тоді з ймовірністю 1 множина Неможливо розібрати вираз (невідома помилка): G_1 \cap G_2 \ne \varnothing
. (точка Неможливо розібрати вираз (невідома помилка): x(\omega)
завжди належить Неможливо розібрати вираз (невідома помилка): G_2 та Неможливо розібрати вираз (невідома помилка): G_2
).
Нехай крім цього Неможливо розібрати вираз (невідома помилка): P \{ c(\omega) =0\}=0 . Це означає, що Неможливо розібрати вираз (невідома помилка): G_1 \cap G_2 \ne \varnothing
з ймовірністю 1.
Таким чином, з 9 ситуацій з додатною ймовірністю з'язляються тільки три: 1, 2 та 4. Відповідно: Неможливо розібрати вираз (невідома помилка): p_3=p_5=p_6=p_7=p_8=p_9=0
(4.28)
Неможливо розібрати вираз (невідома помилка): p_1+p_2+p_4=1
(4.29)
Випишемо, враховуючи (4.28)-(4.29), можливі значення верхньої грані цільової функції задачі (4.1)-(4.2):
Очевидно, що Неможливо розібрати вираз (невідома помилка): S_3\geqslant S_1, S_5 \geqslant S_1 . Крім цього, якщо Неможливо розібрати вираз (невідома помилка): S_1 < 1
то Неможливо розібрати вираз (невідома помилка): S_6 > S_1
. Якщо ж Неможливо розібрати вираз (невідома помилка): S_1 \geqslant S_1
то Неможливо розібрати вираз (невідома помилка): S_6 \geqslant S_1
.Отже, Неможливо розібрати вираз (невідома помилка): S_2 \geqslant S_7 . Тобто оптимальне значення цільової функції задачі (4.1)-(4.2) може дорівнювати одному з 3-х чисел Неможливо розібрати вираз (невідома помилка): S_1, S_4, S_7 . Розглянемо ці випадки послідовно:
А) Неможливо розібрати вираз (невідома помилка): S(\alpha_1,\alpha_2)=S_1= (1-\alpha_1)+(1-\alpha_2)+p_1 .
