Одноетапні стохастичні задачі з лінійними розв’язувальними правилами. Р-модель.

Матеріал з Вікі ЦДУ
Перейти до: навігація, пошук

До задачі опуклого програмування може бути зведена і Р-модель

Неможливо розібрати вираз (невідома помилка): \ P(cx\ge c^0 x^0) \rightarrow max , (1.16)

Неможливо розібрати вираз (невідома помилка): \ P \left( \sum_{j=1}^na_{ij}x_j \le b_i \right) \ge p_i, i=1,..,m , (1.17)

Неможливо розібрати вираз (невідома помилка): \ x=Db . (1.18)

Введемо випадкову змінну

Неможливо розібрати вираз (невідома помилка): \ \eta=\frac{cDb-\bar{c}D\bar{b}}{\sqrt{M(cDb-\bar{c}D\bar{b})^2}} .

Будемо розглядати тільки задачі, в яких Неможливо розібрати вираз (невідома помилка): \ \eta

розподілена нормально. До них відносяться, зокрема, задачі вигляду (1.16) -(1.18), у яких компоненти Неможливо розібрати вираз (невідома помилка): \ b_i 
вектора b отримують систему нормально розподілених випадкових величин, а вектор c детермінований. Легко бачити, що 

Неможливо розібрати вираз (невідома помилка): \ \bar{\eta}=0, \sigma_{\eta}^2=\overline{\eta^2}=1 ,

і, отже, функція розподілу Неможливо розібрати вираз (невідома помилка): \ \eta

не залежить від шуканої матриці D.

Позначимо через Неможливо розібрати вираз (невідома помилка): \ \eta_0

наступну функцію матриці D:

Неможливо розібрати вираз (невідома помилка): \ \eta_0=\frac{c^0x^0-\bar{c}D\bar{b}}{\sqrt{M(cDb-\bar{c}D\bar{b})^2}} .

Цільову функцію (1.16) за умовою (1.18) можна переписати у наступному вигляді:

Неможливо розібрати вираз (невідома помилка): \ P(\eta \ge \eta_0)\rightarrow max ,


або в силу прийнятого припущення про нормальність розподілу Неможливо розібрати вираз (невідома помилка): \ \eta

Неможливо розібрати вираз (невідома помилка): \ \int\limits_{\eta_0}^{\infty} e^{-t^2/2}dt \rightarrow max .

Остання вимога рівносильна наступному:

Неможливо розібрати вираз (невідома помилка): \ \eta_0\rightarrow min ,

або, що те ж саме,

Неможливо розібрати вираз (невідома помилка): \ \frac{\bar{c}D\bar{b}-c^0x^0}{\sqrt{M(cDb-\bar{c}D\bar{b})^2}}\rightarrow max .

Введемо нові додаткові змінні Неможливо розібрати вираз (невідома помилка): \ \omega_0

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

Неможливо розібрати вираз (невідома помилка): \ \omega_0^2 \ge V(D)=M(cDb-\bar{c}D\bar{b})^2, \omega_0\ge0 , (1.19)

Неможливо розібрати вираз (невідома помилка): \ z_0\le\bar{c}D\bar{b}-c^0x^0 . (1.20)

Умови (1.17)-(1.18) перейдуть, як і у випадку М-моделі, у нерівності (1.13)-(1.15). Тому задача стохастичного програмування (1.16)-(1.18) зводиться до наступної детермінованої лінійної задачі: Неможливо розібрати вираз (невідома помилка): \ z_0/\omega_0\rightarrow max

за умов (1.19)-(1.20) і (1.13)-(1.15).

Практичний інтерес становлять тільки ті задачі, для яких Неможливо розібрати вираз (невідома помилка): \ V(D)>0 . Для них в силу умови (1.19) Неможливо розібрати вираз (невідома помилка): \ \omega_0>0 .

Щоб звільнитись від дробово-лінійного показника якості, введемо змінну Неможливо розібрати вираз (невідома помилка): \ t=1/\omega_0 . Позначимо, крім того,

Неможливо розібрати вираз (невідома помилка): \ \tilde{D}=tD, \tilde{z}_i=tz_i, \tilde{V}(\tilde{D})=M(c\tilde{D})b-tc^0x^0)^2 ,

Неможливо розібрати вираз (невідома помилка): \ \tilde{\sigma}_i(\tilde{D})=M(tb_i-a_i\tilde{D}b)^2, \tilde{\mu}_i(\tilde{D}=M(tb_i-a_i\tilde{D}b) .

У нових змінних Неможливо розібрати вираз (невідома помилка): \ \tilde{d}_{ij}=td_{ij}, \tilde{z}_i=tz_i, i=1,...,m; j=1,...,n; \tilde{z}_0=tz_0)

задача стохастичного програмування (1.16) - (1.18) записується як наступна детермінована задача опуклого програмування:

Неможливо розібрати вираз (невідома помилка): \ \tilde{z}_0 \rightarrow max ,

Неможливо розібрати вираз (невідома помилка): \ \bar{c}\tilde{D}\bar{b}-\tilde{z}_0\ge tc^0x^0 ,

Неможливо розібрати вираз (невідома помилка): \ -\tilde{V}(\tilde{D})+1\ge0 ,

Неможливо розібрати вираз (невідома помилка): \ \tilde{\mu}_i(\tilde{D})-\tilde{z}_i\ge0 ,

Неможливо розібрати вираз (невідома помилка): \ -k_i^2[\tilde{\sigma}_i^2(\tilde{D})-\tilde{\mu}_i^2(\tilde{D})]+\tilde{z}_i^2 \ge 0 ,

Неможливо розібрати вираз (невідома помилка): \ t\ge0, \tilde{z}_i\ge0, i=1,2,...,m .