Відмінності між версіями «Одноетапна Р-модель з імовірнісними обмеженнями. Алгоритм побудови розв’язувального правила. Приклад.»

Версія за 18:13, 2 червня 2017

Формально задача записується у наступному вигляді:

Неможливо розібрати вираз (невідома помилка): 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.

Таблиця 4.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 

завжди належить Неможливо розібрати вираз (невідома помилка):  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_1=(1-\alpha_1)+(1-\alpha_2)+p_1,

Неможливо розібрати вираз (невідома помилка): S_2=(1-\alpha_2)+1,

Неможливо розібрати вираз (невідома помилка): S_3=2(1-\alpha_1)+(1-\alpha_2)+p_1,

Неможливо розібрати вираз (невідома помилка): S_4=(1-\alpha_1)+p_1+p_2,

Неможливо розібрати вираз (невідома помилка): S_5=(1-\alpha_1)+2(1-\alpha_2)+p_1,

Неможливо розібрати вираз (невідома помилка): S_6=\frac{1}{2}[(1-\alpha_1)+(1-\alpha_2)+p_1+1],

Неможливо розібрати вираз (невідома помилка): S_7=1.

Очевидно, що Неможливо розібрати вираз (невідома помилка): S_3\geqslant S_1, S_5 \geqslant S_1 . Крім цього, якщо Неможливо розібрати вираз (невідома помилка): S_1 < 1

то  Неможливо розібрати вираз (невідома помилка):  S_6 > 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 .

Неможливо розібрати вираз (невідома помилка): \begin{cases} p_2(u_2^2+u_2^4)+ p_4 u_4^4= \alpha_1-p_1,\\ p_2(u_2^3+u_2^4)= \alpha_2-1+p_2, \\ 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^5 +u_9^6+u_9^7=1, u_i^j \geqslant 0 \end{cases}

 (4.30) 

Система (4.30) може бути переписана у вигляді:

Неможливо розібрати вираз (невідома помилка): \begin{cases} p_2u_2^3+p_4u_4^3= 1-\alpha_1,\\ p_2u_2^2= 1-\alpha_2, \\ 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^5 +u_9^6+u_9^7=1, u_i^j \geqslant 0 \end{cases}

 (4.31) 

Розв’язок системи (4.31), взагалі кажучи, неоднозначний.

б) Неможливо розібрати вираз (невідома помилка): S(\alpha_1,\alpha_2)=S_4= 1-\alpha_1+p_1+p_2 .

В цьому випадку множина розв’язків задачі задовольняє наступній системі співвідношень:

Неможливо розібрати вираз (невідома помилка): p_4(u_4^3+u_4^5)= 1-\alpha_1,

Неможливо розібрати вираз (невідома помилка): p_1u_1^1+p_4(u_4^3+u_4^4)\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.

Умови мають вигляд

В цьому випадку компоненти розв’язку задачі лінійного програмування, еквівалентної стохастичній задачі (4.1)-(4.2), задовольняють співвідношенням

Тут параметри умов задачі задовольняють нерівностям

Модель (4.1)-(4.2) не пов’язана з будь-якими припущеннями про характер областей Неможливо розібрати вираз (невідома помилка): G_i , або функцій, які їх породжують.