Відмінності між версіями «Задача СП: P-модель з імов. обмеж. з нормально розподіленими коефіц. цільвої функції, випадк. матрицею коефіц. обмежень. Детер. еквів. Приклад»

Матеріал з Вікі ЦДУ
Перейти до: навігація, пошук
(Скасування редагування № 373787 користувача 3241243 (обговорення))
 
(не показані 9 проміжних версій 5 учасників)
Рядок 1: Рядок 1:
−
[[Файл:2014-03-24 144053.png]]
+
<font size=3> Стохастичні задачі, в яких оптимізують ймовірність перевищення лінійної форми деякого порогу <math>P\{cx \geq c^0 x^0\}</math> називають Р-моделями. В цю групу також включають задачі, де потрібно мінімізувати поріг '''''k''''', який не перевищує лінійної форми '''''cx''''' з заданою ймовірністю '''''α''''': </font><br />
−
[[Файл:2014-03-24_144109.png]]
+
 
−
[[Файл:12194f5e6eb020cb-0.png|700px]]
+
<font size=3><math>k \to min, P\{cx \leq k\}=\alpha</math> </font><br />
−
[[Файл:12194f5e6eb020cb-1.png|700px]]
+
 
−
[[Файл:12194f5e6eb020cb-2.png|700px]]
+
<font size=3> Еквівалентна детермінована задача дещо ускладняється, якщо замінити показник якості розв’язку стохастичної задачі і замість максимізації <math>M(cx)</math> використати мінімізацію границі при умові, що  </font><br />
 +
 
 +
<font size=3><math>P\{\sum_{j=0}^n\ c_j x_j \leq k\}=\alpha_0</math> </font><br />
 +
 
 +
<font size=3>Будемо вважати при цьому, що випадкові коефіцієнти <math>c_j</math>  розподілені нормально з математичним сподіванням <math>c_j</math> і кореляційною матрицею <math>c=\parallel c_ij\parallel</math>, де </font><br />
 +
<font size=3><math>c_{ij}=M(c_i - \bar{c_j})(c_j - \bar{c_j})</math></font><br />
 +
 
 +
<font size=3>При прийнятих припущеннях про розподілення коефіцієнтів <math>c_j</math> лінійна форма <math>cx</math> є нормально розподіленою випадковою величиною з математичним сподіванням <math>\sum_{j=0}^n\ \bar{c_j} x_j</math> і дисперсією <math>\sum_{i,j=1}^n\ c_{ij} x_i x_j</math>: </font><br />
 +
<font size=3><math>cx \in N \{\sum_{j=0}^n\ \bar{c_j} x_j \sum_{i,j=1}^n\ c_{ij} x_i x_j \}</math></font><br />
 +
<font size=3> </font><br />
 +
 
 +
<font size=3>Тому співвідношення (1) може бути переписане в іншому вигляді. </font><br />
 +
 
 +
 
 +
<font size=3>Звідси видно, що мінімізація k при умові (1) еквівалентна мінімізації </font><br />
 +
<font size=3><math>k= \sum_{j=0}^n\ \bar{c_j} x_j + F^{-1} (a_0) \sqrt{\sum_{i,j=1}^n\ c_{ij} x_i x_j} </math></font><br />
 +
 
 +
<font size=3>При <math>a_0=0,5K</math> є випуклою вниз функцією <math>x</math>.</font><br />
 +
 
 +
<font size=3>Таким чином, при зроблених припущеннях задачі СП </font><br />
 +
<font size=3><math>k \to min, P\{cx \leq k\}=\alpha_0</math> </font><br />
 +
 
 +
<font size=3>Відповідає детермінований еквівалент </font><br />
 +
<font size=3><math>k= \sum_{j=0}^n\ \bar{c_j} x_j + F^{-1} (a_0) \sqrt{\sum_{i,j=1}^n\ c_{ij} x_i x_j} \to min        (2)</math></font><br />
 +
 
 +
<font size=3>Задача (2) є задачею випуклого програмування. Для її розв’язку може бути використаний метод січних площин або один з варіантів методу можливих напрямків.</font><br />
 +
<font size=3>
 +
Необхідно звернути увагу, що при <math> a_0<5    F^{-1} (a_0 )<0 </math>, і цільова функція k (2) являє собою опуклу вгору функцію компонент вектора x. В цьому випадку задача (2) є багато екстремальною. Однак задача максимізації k при умові (2) знову виявляється задачею опуклого програмування.
 +
Розглянемо приклад.
 +
Потрібно обчислити детермінований вектор x, для вирішення наступної стохастичної задачі:<br />
 +
 
 +
<math>
 +
k \to max,
 +
</math>
 +
<br />
 +
<math>
 +
P(x_j x_1 + c_2 x_2 \leq k)=0,37,
 +
</math>
 +
<br />
 +
<math>
 +
P(3x_1 + 2x_2 \leq b_1) \geq 0,9,
 +
</math>
 +
<br />
 +
<math>
 +
P(-x_1 + 4x_2 \leq b_2) \geq 0,9,
 +
</math>
 +
<br/>
 +
<math>
 +
x_1, x_2 \geq 0.
 +
</math>
 +
<br/>
 +
 
 +
<math>c_1, c_2 </math>  і <math> b_1, b_2 </math> – дві нормально розподілені незалежні між собою пари випадкових величин з математичними очікуваннями<br/> <math> \bar{c} = (-1,2) </math>  і <math> \bar{b} = (3,3) </math> <br/>з кореляційними матрицями<br/>
 +
 
 +
<math>
 +
\parallel c_ij\parallel = \parallel (10 20 7 7)\parallel
 +
</math>
 +
<br/>
 +
<math>
 +
\parallel b_ij\parallel = \parallel (1 0 0 1)\parallel
 +
</math>
 +
 
 +
Детермінований еквівалент цієї задачі буде мати такий вигляд:<br/>
 +
 
 +
<math>
 +
k=-x_1+2x_2-0,33    \sqrt{10x_1^2+14x_1 x_2+20x_2^2 }\to max,
 +
</math>
 +
<br/>
 +
<math>
 +
3x_1-2x_2\leq2,72,
 +
</math>
 +
<br/>
 +
<math>
 +
-x_1+4x_2\leq2,72,
 +
</math>
 +
<br/>
 +
<math>
 +
x_1,x_2\geq0.
 +
</math>
 +
 
 +
Оптимальни значеннями отриманої задачі опуклого програмування є таким<br/>
 +
<math>
 +
x^*=(0;0,68); k^*=0,346.
 +
</math>
 +
</font>
 +
 
 +
Виконала: [[Користувач:2533128|Сандирєва Марина]] <br />
 +
Доповнював: [[Користувач:222658|Ізовіта Олесь]]

Поточна версія на 22:45, 6 квітня 2021

Стохастичні задачі, в яких оптимізують ймовірність перевищення лінійної форми деякого порогу Неможливо розібрати вираз (невідома помилка): P\{cx \geq c^0 x^0\} 

називають Р-моделями. В цю групу також включають задачі, де потрібно мінімізувати поріг k, який не перевищує лінійної форми cx з заданою ймовірністю α:

Неможливо розібрати вираз (невідома помилка): k \to min, P\{cx \leq k\}=\alpha

Еквівалентна детермінована задача дещо ускладняється, якщо замінити показник якості розв’язку стохастичної задачі і замість максимізації Неможливо розібрати вираз (невідома помилка): M(cx) 

використати мінімізацію границі при умові, що

Неможливо розібрати вираз (невідома помилка): P\{\sum_{j=0}^n\ c_j x_j \leq k\}=\alpha_0

Будемо вважати при цьому, що випадкові коефіцієнти Неможливо розібрати вираз (невідома помилка): c_j 

 розподілені нормально з математичним сподіванням Неможливо розібрати вираз (невідома помилка): c_j
і кореляційною матрицею Неможливо розібрати вираз (невідома помилка): c=\parallel c_ij\parallel

, де
Неможливо розібрати вираз (невідома помилка): c_{ij}=M(c_i - \bar{c_j})(c_j - \bar{c_j})

При прийнятих припущеннях про розподілення коефіцієнтів Неможливо розібрати вираз (невідома помилка): c_j 

лінійна форма Неможливо розібрати вираз (невідома помилка): cx
є нормально розподіленою випадковою величиною з математичним сподіванням Неможливо розібрати вираз (невідома помилка): \sum_{j=0}^n\ \bar{c_j} x_j
і дисперсією Неможливо розібрати вираз (невідома помилка): \sum_{i,j=1}^n\ c_{ij} x_i x_j

Неможливо розібрати вираз (невідома помилка): cx \in N \{\sum_{j=0}^n\ \bar{c_j} x_j \sum_{i,j=1}^n\ c_{ij} x_i x_j \}

Тому співвідношення (1) може бути переписане в іншому вигляді.


Звідси видно, що мінімізація k при умові (1) еквівалентна мінімізації
Неможливо розібрати вираз (невідома помилка): k= \sum_{j=0}^n\ \bar{c_j} x_j + F^{-1} (a_0) \sqrt{\sum_{i,j=1}^n\ c_{ij} x_i x_j}

При Неможливо розібрати вираз (невідома помилка): a_0=0,5K 

є випуклою вниз функцією Неможливо розібрати вираз (невідома помилка): x

.

Таким чином, при зроблених припущеннях задачі СП
Неможливо розібрати вираз (невідома помилка): k \to min, P\{cx \leq k\}=\alpha_0

Відповідає детермінований еквівалент
Неможливо розібрати вираз (невідома помилка): k= \sum_{j=0}^n\ \bar{c_j} x_j + F^{-1} (a_0) \sqrt{\sum_{i,j=1}^n\ c_{ij} x_i x_j} \to min (2)

Задача (2) є задачею випуклого програмування. Для її розв’язку може бути використаний метод січних площин або один з варіантів методу можливих напрямків.
Необхідно звернути увагу, що при Неможливо розібрати вираз (невідома помилка): a_0<5 F^{-1} (a_0 )<0 , і цільова функція k (2) являє собою опуклу вгору функцію компонент вектора x. В цьому випадку задача (2) є багато екстремальною. Однак задача максимізації k при умові (2) знову виявляється задачею опуклого програмування. Розглянемо приклад. Потрібно обчислити детермінований вектор x, для вирішення наступної стохастичної задачі:

Неможливо розібрати вираз (невідома помилка): k \to max,


Неможливо розібрати вираз (невідома помилка): P(x_j x_1 + c_2 x_2 \leq k)=0,37,


Неможливо розібрати вираз (невідома помилка): P(3x_1 + 2x_2 \leq b_1) \geq 0,9,


Неможливо розібрати вираз (невідома помилка): P(-x_1 + 4x_2 \leq b_2) \geq 0,9,


Неможливо розібрати вираз (невідома помилка): x_1, x_2 \geq 0.


Неможливо розібрати вираз (невідома помилка): c_1, c_2 

 і Неможливо розібрати вираз (невідома помилка):  b_1, b_2 
– дві нормально розподілені незалежні між собою пари випадкових величин з математичними очікуваннями
 Неможливо розібрати вираз (невідома помилка):  \bar{c} = (-1,2) 
 і Неможливо розібрати вираз (невідома помилка):  \bar{b} = (3,3) 

з кореляційними матрицями

Неможливо розібрати вираз (невідома помилка): \parallel c_ij\parallel = \parallel (10 20 7 7)\parallel


Неможливо розібрати вираз (невідома помилка): \parallel b_ij\parallel = \parallel (1 0 0 1)\parallel


Детермінований еквівалент цієї задачі буде мати такий вигляд:

Неможливо розібрати вираз (невідома помилка): k=-x_1+2x_2-0,33 \sqrt{10x_1^2+14x_1 x_2+20x_2^2 }\to max,


Неможливо розібрати вираз (невідома помилка): 3x_1-2x_2\leq2,72,


Неможливо розібрати вираз (невідома помилка): -x_1+4x_2\leq2,72,


Неможливо розібрати вираз (невідома помилка): x_1,x_2\geq0.


Оптимальни значеннями отриманої задачі опуклого програмування є таким
Неможливо розібрати вираз (невідома помилка): x^*=(0;0,68); k^*=0,346.

Виконала: Сандирєва Марина
Доповнював: Ізовіта Олесь

Отримано з https://wiki.cusu.edu.ua/index.php?title=Задача_СП:_P-модель_з_імов._обмеж._з_нормально_розподіленими_коефіц._цільвої_функції,_випадк._матрицею_коефіц._обмежень._Детер._еквів._Приклад&oldid=373788