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

Версія за 22:42, 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.$

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

@@ Рядок 83: / Рядок 83: @@
 </math>
-Оптимальни значеннями отриманої задачі опуклого програмування є таким<br/>
+Оптимальни значеннями отриманої задачі опуклого програмування є<br/>
 <math>
 x^*=(0;0,68); k^*=0,346.

Версія за 22:42, 6 квітня 2021

Навігаційне меню

Перегляди

Особисті інструменти

Навігація

Пошук

Інструменти

портфоліо