Відмінності між версіями «Задача СП. М-модель з імовірнісними обмеженнями з детермінованою матрицею коефіцієнтів обмежень. Детермінована задача. Двоїста задача.»
| Рядок 53: | Рядок 53: | ||
Якщо <math>F_{i}(b_{i})</math> – неперервна строго монотонна функція, то остання нерівність еквівалентнa рівнянню <math>1-F_{i}(\tilde{b_i})=\alpha_{i}</math> . | Якщо <math>F_{i}(b_{i})</math> – неперервна строго монотонна функція, то остання нерівність еквівалентнa рівнянню <math>1-F_{i}(\tilde{b_i})=\alpha_{i}</math> . | ||
| − | У всіх випадках будемо записувати <math>\tilde{b}= F_{i}^(-1)(1-\alpha_{i}), <math>F_{i}^(-1)(t)=\sup(y|F_{i}(y)\geqslant t)</math>. | + | У всіх випадках будемо записувати <math>\tilde{b}= F_{i}^(-1)(1-\alpha_{i})</math>, <math>F_{i}^(-1)(t)=\sup(y|F_{i}(y)\geqslant t)</math>. |
| + | (1.8) | ||
| + | |||
| + | Для стохастичної задачі (1.1)-(1.3) з детермінованою матрицею А, тобто для задачі (1.5)-(1.7), можна записати '''двоїсту задачу''' з ймовірнісними обмеженнями. | ||
| + | |||
| + | Розглянемо задачу | ||
| + | |||
| + | <math>y\tilde{b}\rightarrow min</math> | ||
| + | (1.9) | ||
| + | |||
| + | <math>P(yA\geqslant c)\geqslant\beta</math> | ||
| + | (1.10) | ||
| + | |||
| + | <math>y\geqslant o</math> | ||
| + | (1.11) | ||
| + | |||
| + | Розв'язок якої <math>у*</math> визначається у вигляді детермінованого вектора. | ||
| + | |||
| + | Нехай <math>G_{j}(\zeta)=P(c_{j}\leqslant\zeta)</math>. | ||
| + | |||
| + | Якщо <math>G_{j}(\zeta)=\beta{j}</math>, то запис <math>\zeta=G_{j}^(-1)(\beta{j})</math>) будемо вважати еквіваленою запису | ||
| + | |||
| + | <math>\zeta = min (y|G_{i}(y)\geqslant \beta{j})</math>. | ||
| + | |||
| + | Попередня задача (1.9)-(1.11) буде записана у вигляді | ||
| + | |||
| + | <math>y\tilde{b}\rightarrow min</math>, | ||
| + | |||
| + | <math>yA\geqslant G^(-1)(\beta)</math>, | ||
| + | |||
| + | <math>y\geqslant o</math>. | ||
| + | |||
| + | Порівнюючи останню задачу з початковою (1.1)-(1.3) отримуємо, що при <math>\beta=G(\bar{c})</math> наступні дві одно етапні задачі стохастичного програмування з ймовірнісними умовами та апріорними розв’язувальними правилами являють собою двоїсту пару : | ||
| + | |||
| + | <math>G^(-1)(\beta)x\rightarrow max</math>, | ||
| + | |||
| + | <math>P(Ax\leqslantb)\geqslant\alpha</math>, | ||
| + | |||
| + | <math>x\geqslant\0</math>, | ||
| + | |||
| + | <math>yF^(-1)(1-\alpha)\rightarrow min</math>, | ||
| + | |||
| + | <math>P(yA\geqslant)\leqslantb\beta</math>, | ||
| + | |||
| + | <math>x\geqslant\0</math>, | ||
Версія за 22:02, 13 березня 2013
Розглянемо задачу лінійного стохастичного програмування з ймовірнісними обмеженнями типу М-модель:
Неможливо розібрати вираз (невідома помилка): M(cx)\rightarrow max
(1.1),
Неможливо розібрати вираз (невідома помилка): P(\sum^{n}_{j=1}{a_{ij}x_{j}}\leqslant b_{i})\geqslant \alpha_{i},i=1,\ldots,m
(1.2),
Неможливо розібрати вираз (невідома помилка): x_{j}\geqslant 0,j=1,\ldots,n
(1.3)
C – випадкові числа, Неможливо розібрати вираз (невідома помилка): \alpha_{i}>0,5, \alpha_{i}<1
При детермінованій матриці Неможливо розібрати вираз (невідома помилка): \ A=||a_{ij}||
і випадковому веторі Неможливо розібрати вираз (невідома помилка): b=(b_{ij})
дана задача зводиться до детермінованої задачі лінійного програмування.
Дійсно, нехай Неможливо розібрати вираз (невідома помилка): \phi(b_{1}...b_{m})
– загальна щільність розподілу елементів Неможливо розібрати вираз (невідома помилка): b_{i}
випадкового вектора b. Щільність розподілу компонента Неможливо розібрати вираз (невідома помилка): b_{i}
рівна:
Неможливо розібрати вираз (невідома помилка): \phi_{i}(b_{i})= \int\limits_{\infty}^{\infty}... \int\limits_{\infty}^{\infty}\phi(b_{1}...b_{m})\prod^{j\not=i}db_{j}
Знайдемо Неможливо розібрати вираз (невідома помилка): \tilde{b_i}
з рівняння:
Неможливо розібрати вираз (невідома помилка): \int\limits_{\tilde{b_i}}^{\infty}\phi_{i}(b_{i})db_{i}=\alpha_{i} , Неможливо розібрати вираз (невідома помилка): i=1,\ldots,m
(1.4)
Якщо рішення рівняння (1.4) не єдине, то обирається в якості Неможливо розібрати вираз (невідома помилка): \tilde{b_i}
найбільший корінь.
Відношення (1.2) еквівалентне нерівності
Неможливо розібрати вираз (невідома помилка): \sum^{n}_{j=1}{a_{ij}x_{j}}\leqslant\tilde{b_i} , Неможливо розібрати вираз (невідома помилка): i=1,\ldots,m , Де Неможливо розібрати вираз (невідома помилка): \tilde{b_i}
задовольняють відношенням (1.4).
Звідси випливає еквівалентність задачі стохастичного програмування (1.1) – (1.3) і детермінованої задачі лінійного програмування
Неможливо розібрати вираз (невідома помилка): \bar{c}x\rightarrow max
(1.5)
Неможливо розібрати вираз (невідома помилка): Ax\leqslant\tilde{b}
(1.6)
Неможливо розібрати вираз (невідома помилка): x\geqslant 0
(1.7)
Де Неможливо розібрати вираз (невідома помилка): \bar{c}= M(c) ,
Неможливо розібрати вираз (невідома помилка): \tilde{b}=(\tilde{b_1}...\tilde{b_m})
Якщо випадкові величини Неможливо розібрати вираз (невідома помилка): b_{i}
арактеризуються функцією розподілу Неможливо розібрати вираз (невідома помилка): F_{i}(b_{i})
,
то параметр Неможливо розібрати вираз (невідома помилка): \tilde{b_i}
представляє собою найбільше число, яке задовольняє нерівність Неможливо розібрати вираз (невідома помилка): 1-F_{i}(\tilde{b_i})\geqslant\alpha_{i}
.
Якщо Неможливо розібрати вираз (невідома помилка): F_{i}(b_{i})
– неперервна строго монотонна функція, то остання нерівність еквівалентнa рівнянню Неможливо розібрати вираз (невідома помилка): 1-F_{i}(\tilde{b_i})=\alpha_{i}
.
У всіх випадках будемо записувати Неможливо розібрати вираз (невідома помилка): \tilde{b}= F_{i}^(-1)(1-\alpha_{i}) , Неможливо розібрати вираз (невідома помилка): F_{i}^(-1)(t)=\sup(y|F_{i}(y)\geqslant t) . (1.8)
Для стохастичної задачі (1.1)-(1.3) з детермінованою матрицею А, тобто для задачі (1.5)-(1.7), можна записати двоїсту задачу з ймовірнісними обмеженнями.
Розглянемо задачу
Неможливо розібрати вираз (невідома помилка): y\tilde{b}\rightarrow min
(1.9)
Неможливо розібрати вираз (невідома помилка): P(yA\geqslant c)\geqslant\beta
(1.10)
Неможливо розібрати вираз (невідома помилка): y\geqslant o
(1.11)
Розв'язок якої Неможливо розібрати вираз (невідома помилка): у*
визначається у вигляді детермінованого вектора.
Нехай Неможливо розібрати вираз (невідома помилка): G_{j}(\zeta)=P(c_{j}\leqslant\zeta) .
Якщо Неможливо розібрати вираз (невідома помилка): G_{j}(\zeta)=\beta{j} , то запис Неможливо розібрати вираз (невідома помилка): \zeta=G_{j}^(-1)(\beta{j}) ) будемо вважати еквіваленою запису
Неможливо розібрати вираз (невідома помилка): \zeta = min (y|G_{i}(y)\geqslant \beta{j}) .
Попередня задача (1.9)-(1.11) буде записана у вигляді
Неможливо розібрати вираз (невідома помилка): y\tilde{b}\rightarrow min ,
Неможливо розібрати вираз (невідома помилка): yA\geqslant G^(-1)(\beta) ,
Неможливо розібрати вираз (невідома помилка): y\geqslant o .
Порівнюючи останню задачу з початковою (1.1)-(1.3) отримуємо, що при Неможливо розібрати вираз (невідома помилка): \beta=G(\bar{c})
наступні дві одно етапні задачі стохастичного програмування з ймовірнісними умовами та апріорними розв’язувальними правилами являють собою двоїсту пару :
Неможливо розібрати вираз (невідома помилка): G^(-1)(\beta)x\rightarrow max ,
Неможливо розібрати вираз (невідома помилка): P(Ax\leqslantb)\geqslant\alpha ,
Неможливо розібрати вираз (невідома помилка): x\geqslant\0 ,
Неможливо розібрати вираз (невідома помилка): yF^(-1)(1-\alpha)\rightarrow min ,
Неможливо розібрати вираз (невідома помилка): P(yA\geqslant)\leqslantb\beta ,
Неможливо розібрати вираз (невідома помилка): x\geqslant\0 ,
