Відмінності між версіями «Одноетапні стохастичні задачі з лінійними розв’язувальними правилами. Р-модель.»
9190313 (обговорення • внесок) |
|||
(не показані 8 проміжних версій 3 учасників) | |||
Рядок 1: | Рядок 1: | ||
− | До задачі опуклого програмування може бути зведена і Р-модель | + | <font size=3> До задачі опуклого програмування може бути зведена і ''Р''-модель </font> |
− | <math>\ P(cx\ge c^0 x^0) \rightarrow max </math>, (1.16) | + | <font size=3> <math>\ P(cx\ge c^0 x^0) \rightarrow max </math>, (1.16) </font> |
− | <math>\ P \left( \sum_{j=1}^na_{ij}x_j \le b_i \right) \ge p_i, i=1,..,m </math>, (1.17) | + | <font size=3> <math>\ P \left( \sum_{j=1}^na_{ij}x_j \le b_i \right) \ge p_i, i=1,..,m </math>, (1.17) </font> |
− | <math>\ x=Db </math>. (1.18) | + | <font size=3> <math>\ x=Db </math>. (1.18) </font> |
− | Введемо випадкову змінну | + | <font size=3> Введемо випадкову змінну </font> |
− | <math>\ \eta=\frac{cDb-\bar{c}D\bar{b}}{\sqrt{M(cDb-\bar{c}D\bar{b})^2}} </math>. | + | <font size=3> <math>\ \eta=\frac{cDb-\bar{c}D\bar{b}}{\sqrt{M(cDb-\bar{c}D\bar{b})^2}} </math>. </font> |
− | Будемо розглядати | + | <font size=3> Будемо розглядати лише ті задачі, в яких <math>\ \eta </math> розподілена нормально. До них відносяться, зокрема, задачі вигляду (1.16)-(1.18), у яких компоненти компоненти <math>\ b_i </math> вектора <math>\ b </math> отримують систему нормально розподілених випадкових величин, а вектор <math>\ c </math> детермінований. Одразу можна звернути увагу на те, що </font> |
− | <math>\ \bar{\eta}=0, \sigma_{\eta}^2=\overline{\eta^2}=1 </math>, | + | <font size=3> <math>\ \bar{\eta}=0, \sigma_{\eta}^2=\overline{\eta^2}=1 </math>, </font> |
− | і, | + | <font size=3> і, відповідно, функція розподілу <math>\ \eta </math> не залежить від шуканої матриці <math> D </math>. </font> |
− | Позначимо через <math>\ \eta_0 </math> наступну функцію матриці <math> D </math>: | + | <font size=3> Позначимо через <math>\ \eta_0 </math> наступну функцію матриці <math> D </math>: </font> |
− | <math>\ \eta_0=\frac{c^0x^0-\bar{c}D\bar{b}}{\sqrt{M(cDb-\bar{c}D\bar{b})^2}} </math>. | + | <font size=3> <math>\ \eta_0=\frac{c^0x^0-\bar{c}D\bar{b}}{\sqrt{M(cDb-\bar{c}D\bar{b})^2}} </math>. </font> |
− | Цільову функцію (1.16) за | + | <font size=3> Цільову функцію (1.16) за умови (1.18) можна переписати у наступному вигляді: </font> |
− | <math>\ P(\eta \ge \eta_0)\rightarrow max </math>, | + | <font size=3> <math>\ P(\eta \ge \eta_0)\rightarrow max </math>, </font> |
+ | <font size=3> або в силу прийнятого припущення про нормальність розподілу <math>\ \eta </math>: </font> | ||
− | + | <font size=3> <math>\ \int\limits_{\eta_0}^{\infty} e^{\frac{-t^2}{2}}dt \rightarrow max </math>. </font> | |
− | < | + | <font size=3> Остання вимога еквівалентно відповідає наступному: </font> |
− | + | <font size=3> <math>\ \eta_0\rightarrow min </math>, </font> | |
− | < | + | <font size=3> або, це те ж саме, що </font> |
− | + | <font size=3> <math>\ \frac{\bar{c}D\bar{b}-c^0x^0}{\sqrt{M(cDb-\bar{c}D\bar{b})^2}}\rightarrow max </math>. </font> | |
− | <math>\ \ | + | <font size=3> Введемо нові додаткові змінні <math>\ \omega_0 </math> і <math>\ z_0 </math>: </font> |
− | + | <font size=3> <math>\ \omega_0^2 \ge V(D)=M(cDb-\bar{c}D\bar{b})^2, \omega_0\ge0 </math>, (1.19) </font> | |
− | <math>\ \ | + | <font size=3> <math>\ z_0\le\bar{c}D\bar{b}-c^0x^0 </math>. (1.20) </font> |
− | <math>\ z_0\ | + | <font size=3> Умови (1.17)-(1.18) перейдуть, як і у випадку ''М''-моделі, у нерівності (1.13)-(1.15). Тому задача стохастичного програмування (1.16)-(1.18) зводиться до наступної детермінованої лінійної задачі: <math>\ z_0/\omega_0\rightarrow max</math> за умов (1.19)-(1.20) та (1.13)-(1.15). </font> |
− | + | <font size=3> Практичний інтерес виявляє лише ті задачі, для яких <math>\ V(D)>0 </math>. Для них в силу умови (1.19) <math>\ \omega_0>0 </math>. </font> | |
− | + | <font size=3> Щоб звільнитись від дробово-лінійного показника якості, введемо змінну <math>\ t=1/\omega_0 </math>. Позначимо, крім того, </font> | |
− | + | <font size=3> <math>\ \tilde{D}=tD, \tilde{z}_i=tz_i, \tilde{V}(\tilde{D})=M(c\tilde{D}b-tc^0x^0)^2 </math>, </font> | |
− | <math>\ \tilde{D}= | + | <font size=3> <math>\ \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) </math>. </font> |
− | <math>\ \tilde{ | + | <font size=3> У нових змінних <math>\ (\tilde{d}_{ij}=td_{ij}, \tilde{z}_i=tz_i, i=1,...,m; j=1,...,n; \tilde{z}_0=tz_0)</math> задача стохастичного програмування (1.16) - (1.18) записується як наступна детермінована задача опуклого програмування: </font> |
− | + | <font size=3> <math>\ \tilde{z}_0 \rightarrow max </math>, </font> | |
− | <math>\ \tilde{z}_0 \ | + | <font size=3> <math>\ \bar{c}\tilde{D}\bar{b}-\tilde{z}_0\ge tc^0x^0 </math>, </font> |
− | <math>\ \ | + | <font size=3> <math>\ -\tilde{V}(\tilde{D})+1\ge0 </math>, </font> |
− | <math>\ | + | <font size=3> <math>\ \tilde{\mu}_i(\tilde{D})-\tilde{z}_i\ge0 </math>, </font> |
− | <math>\ \tilde{\ | + | <font size=3> <math>\ -k_i^2[\tilde{\sigma}_i^2(\tilde{D})-\tilde{\mu}_i^2(\tilde{D})]+\tilde{z}_i^2 \ge 0</math>, </font> |
− | <math>\ | + | <font size=3> <math>\ t\ge0, \tilde{z}_i\ge0, i=1,2,...,m </math> [1, c. 87-88]. </font> |
− | + | ||
+ | |||
+ | ==Список використаних джерел== | ||
+ | 1. Юдин Д. Б. Математические методы управления в условиях неполной информации. / Юдин Д. Б. М: «Сов. радио», 1974. – 400 с. | ||
+ | |||
+ | |||
+ | |||
+ | Виконала: [[Користувач: Ира Ханенко|Ира Ханенко]] | ||
+ | |||
+ | Доповнювала: [[Користувач:Іванченко Дар’я|Іванченко Дар’я]] |
Поточна версія на 10:04, 28 грудня 2020
До задачі опуклого програмування може бути зведена і Р-модель
Неможливо розібрати вираз (невідома помилка): \ 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^{\frac{-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
[1, c. 87-88].
Список використаних джерел
1. Юдин Д. Б. Математические методы управления в условиях неполной информации. / Юдин Д. Б. М: «Сов. радио», 1974. – 400 с.
Виконала: Ира Ханенко
Доповнювала: Іванченко Дар’я