Відмінності між версіями «Детерм. аналог для довільного розподілу вип. вектора b: нормальний розподіл, розподіл Вейбулла, рівномірний розподіл, гамма-розподіл.»
| (не показані 6 проміжних версій 2 учасників) | |||
| Рядок 1: | Рядок 1: | ||
| + | Зведення задачі стохастичного програмування до еквівалентної детермінованої задачі є ефективним способом аналізу стохастичних моделей у тих випадках, коли детерміновані еквіваленти є задачами лінійного або випуклого програмування. | ||
| + | |||
| + | Наведемо деякі класи лінійних задач з ймовірнісними обмеженнями, для яких детерміновані еквіваленти являють собою задачі випуклого програмування. Покажемо, що вони можуть бути перетворені у зручний, для використання ефективних методів рішення, вигляд. | ||
| + | Потрібно обчислити детерміновані вектори <math> x </math> та <math> g(x) </math>, за яких | ||
| + | |||
| + | <math> \overline{c}x \to \max </math> | ||
| + | |||
| + | <math> F_{x}(g(x))=F_{x}(Ax- \tilde{b})=\alpha </math> | ||
| + | |||
| + | <math> g(x) = Ax- \tilde{b} , x\geqslant 0 </math> | ||
| + | |||
| + | Тут | ||
| + | |||
| + | <math> F_{x}(Ax- \tilde{b})= P \{ Ax-b<Ax- \tilde{b} \} = P \{b> \tilde {b} \} </math> | ||
| + | |||
| + | У випадку, коли складові <math> b_i </math> вектора <math> b </math> - незалежні випадкові величини: | ||
| + | |||
| + | <math> P \{b \geqslant \tilde {b} \} = \prod_{i =1}^m P \{b_i \geqslant \tilde{b_i} \} = \prod_{i =1}^m [1-P \{b_i < \tilde{b_i}) ] = \prod_{i =1}^m [1- F_{b_{i}}(\tilde{b_{i}}) ] </math> | ||
| + | |||
| + | де <math> F_{b_{i}}(\tilde{b_{i}}) </math> - функція розподілу компоненти <math> b_i </math> вектора <math> b </math>. | ||
| + | |||
| + | Еквівалентна детермінована задача при цьому набуває вигляду: | ||
| + | |||
| + | <math> \overline{c}x \to \max </math> | ||
| + | |||
| + | <math> Ax\leqslant \tilde{b} </math> | ||
| + | |||
| + | <math> \prod_{i =1}^m [1- F_{b_{i}}(\tilde{b_{i}}) ] \geqslant \alpha </math> | ||
| + | |||
| + | <math> x\geqslant 0 </math> | ||
| + | |||
Розглянемо випадок, коли щільності розподілів складових <math> b_i </math> вектора обмежень визначаються однією з наступних функцій: | Розглянемо випадок, коли щільності розподілів складових <math> b_i </math> вектора обмежень визначаються однією з наступних функцій: | ||
| Рядок 4: | Рядок 35: | ||
<math> 2) \varphi_{i}^{(2)}(y_i)=\begin{cases} | <math> 2) \varphi_{i}^{(2)}(y_i)=\begin{cases} | ||
| + | |||
\lambda_i\zeta_i(y_i-\beta_i)^{\zeta_i-1}e^{-\lambda_i(y_i-\beta_i)^{\zeta_i}},y_i\geqslant \beta_i\\ | \lambda_i\zeta_i(y_i-\beta_i)^{\zeta_i-1}e^{-\lambda_i(y_i-\beta_i)^{\zeta_i}},y_i\geqslant \beta_i\\ | ||
| + | |||
0, y_i<\beta_i | 0, y_i<\beta_i | ||
| + | |||
\end{cases}</math> | \end{cases}</math> | ||
| Рядок 11: | Рядок 45: | ||
<math> 3) \varphi_{i}^{(3)}(y_i)=\begin{cases} | <math> 3) \varphi_{i}^{(3)}(y_i)=\begin{cases} | ||
| − | \frac{n_i}{\overline{a}_i-\underline{a}_i}(\frac{y_i-\underline{a}_i}{\overline{a}_i-\underline{a}_i})^{n_i-1},y_i \in [\overline{a}_i,\underline{a}_i]\\ | + | |
| + | \frac{n_i}{\overline{a}_i-\underline{a}_i}(\frac{y_i-\underline{a}_i}{\overline{a}_i-\underline{a}_i})^{n_i-1},y_i \in | ||
| + | |||
| + | [\overline{a}_i,\underline{a}_i]\\ | ||
| + | |||
0, y_i \overline{\in} [\overline{a}_i,\underline{a}_i] | 0, y_i \overline{\in} [\overline{a}_i,\underline{a}_i] | ||
| + | |||
\end{cases}</math> | \end{cases}</math> | ||
<math> 4) \varphi_{i}^{(4)}(y_i)=\begin{cases} | <math> 4) \varphi_{i}^{(4)}(y_i)=\begin{cases} | ||
| + | |||
\frac{\lambda_i}{\Gamma(\zeta_i)}(\lambda_i y_i)^{\zeta_i-1}e^{-\lambda_i y_i},y_i\geqslant 0\\ | \frac{\lambda_i}{\Gamma(\zeta_i)}(\lambda_i y_i)^{\zeta_i-1}e^{-\lambda_i y_i},y_i\geqslant 0\\ | ||
| + | |||
0, y_i<0 | 0, y_i<0 | ||
\end{cases}</math> | \end{cases}</math> | ||
| Рядок 23: | Рядок 64: | ||
Щільність розподілу 1) відповідає нормальному закону. Формула 2) відповідає розподілу Вейбулла. Розподіл 3) включає рівномірний розподіл (<math> n_i=1 </math>). Щільність 4) визначає гамма-розподіл. Формули 2) і 4) включають експоненційний розподіл (<math> \zeta_i=1 </math>). | Щільність розподілу 1) відповідає нормальному закону. Формула 2) відповідає розподілу Вейбулла. Розподіл 3) включає рівномірний розподіл (<math> n_i=1 </math>). Щільність 4) визначає гамма-розподіл. Формули 2) і 4) включають експоненційний розподіл (<math> \zeta_i=1 </math>). | ||
| − | |||
У всіх цих випадках розглянута задача – задача опуклого програмування. Однак ліві частини обмежень <math> \prod_{i =1}^m [1- F_{b_{i}}(\tilde{b_{i}}) ] \geqslant \alpha </math> – не є опуклими вверх функціями. Замінимо цю умову на еквівалентну нерівність: | У всіх цих випадках розглянута задача – задача опуклого програмування. Однак ліві частини обмежень <math> \prod_{i =1}^m [1- F_{b_{i}}(\tilde{b_{i}}) ] \geqslant \alpha </math> – не є опуклими вверх функціями. Замінимо цю умову на еквівалентну нерівність: | ||
| − | |||
<math> \sum_{i=1}^m \ln[1-F_{b_{i}}(\tilde{b_{i}})] \geqslant \ln(\alpha) </math> | <math> \sum_{i=1}^m \ln[1-F_{b_{i}}(\tilde{b_{i}})] \geqslant \ln(\alpha) </math> | ||
| − | |||
Ця заміна дозволяє перейти для всіх вищезазначених розподілів до еквівалентних детермінованих задач, у яких ліві частини обмежень – лінійні та опуклі вверх функції. | Ця заміна дозволяє перейти для всіх вищезазначених розподілів до еквівалентних детермінованих задач, у яких ліві частини обмежень – лінійні та опуклі вверх функції. | ||
| Рядок 40: | Рядок 78: | ||
<math> \frac{d}{d\tilde{b}_i} \gamma(\tilde{b_{i}})=\frac{d}{d\tilde{b}_i} \ln[1-F_{b_{i}}(\tilde{b_{i}})]=-\frac{\varphi_i^{(1)}(y_i)}{1-\Phi_i(\tilde{b}_i)} </math> | <math> \frac{d}{d\tilde{b}_i} \gamma(\tilde{b_{i}})=\frac{d}{d\tilde{b}_i} \ln[1-F_{b_{i}}(\tilde{b_{i}})]=-\frac{\varphi_i^{(1)}(y_i)}{1-\Phi_i(\tilde{b}_i)} </math> | ||
| + | де <math> \varphi_{i}^{(1)}(y_i)=\frac{1}{\sqrt{2\pi}\sigma_i} e^{-\frac{(\tilde{b}_i-\mu_i)^2}{2\sigma_i^2}}</math>, | ||
| + | <math> \Phi_i(\tilde{b}_i)= \int\limits_{-\infty}^{\tilde{b_{i}}} e^{-\frac{(y_i-\mu_i)^2}{2\sigma_i^2}} </math> | ||
| + | Маємо: | ||
| + | <math> \frac{d^2}{d\tilde{b}_i^2} \gamma(\tilde{b_{i}})=-\frac{\varphi_i^{(1)}(y_i)\Theta_i(\tilde{b}_i)}{[1-\Phi_i(\tilde{b}_i)]^2} </math> | ||
| + | |||
| + | де <math>\Theta_i(\tilde{b}_i)=-\frac{\tilde{b}_i-\mu_i}{\sigma_i^2}[1-\Phi_i(\tilde{b}_i)]+\varphi_i^{(1)}(\tilde{b}_i) </math> | ||
| + | |||
| + | Легко побачити, що | ||
| + | |||
| + | <math>\frac{d\Theta_i(\tilde{b}_i)}{d\tilde{b}_i}=-\frac{1-\Phi_i(\tilde{b}_i)}{\sigma_i^2}<0 </math> | ||
| + | |||
| + | тобто, спадна функція від <math> \tilde{b}_i </math>. Але <math>\Theta_i(\infty)=0 </math>. Тому <math>\Theta_i(\tilde{b}_i)\geqslant 0 </math> і <math>\frac{d^2}{d\tilde{b}_i^2}\gamma(\tilde{b}_i)\leqslant 0 </math>, що і необхідно було довести. | ||
| + | |||
| + | Для розподілу Вейбула маємо: | ||
| + | |||
| + | <math> F_{b_{i}}(\tilde{b_{i}})= \int\limits_{-\infty}^{\tilde{b_{i}}} \varphi_{i}^{(2)}(y_i)dy_i=\begin{cases} | ||
| + | 1-e^{-\lambda_i(\tilde{b_{i}}-\beta_i)^{\zeta_i}},\tilde{b_{i}}\geqslant \beta_i\\ | ||
| + | 0, \tilde{b_{i}}<\beta_i | ||
| + | \end{cases}</math> | ||
| + | |||
| + | Тому <math> \frac{d^2}{d\tilde{b}_i^2} \gamma(\tilde{b_{i}})=\begin{cases} | ||
| + | -\zeta_i(\zeta_i-1)\lambda_i(\tilde{b}_i-\beta_i)^{\zeta_i-2},\tilde{b_{i}}\geqslant \beta_i\\ | ||
| + | 0, \tilde{b_{i}}<\beta_i | ||
| + | \end{cases}</math> | ||
| + | |||
| + | Звідси випливає, що ліва частина нерівності (5) для <math>b_i </math>, розподілених за Вейбулом, є функцією, опуклою вверх. | ||
| + | |||
| + | Нехай розглянемо частковий випадок, коли складові <math>b_i</math> вектора обмежень розподілені за експоненційним законом з параметрами <math>\lambda_i </math> і <math>\beta_i </math>. Експоненційний розподіл отримується з розподілу Вейбула при <math>\zeta_i=1 </math>. Обмеження (2) і (5), можуть бути в даному випадку записані у вигляді: | ||
| + | |||
| + | <math> \sum_{j=1}^n a_{ij}x_j \leqslant \tilde{b}_i, i=1,2,...,m </math> | ||
| + | |||
| + | <math>-\sum_{i=1}^m \lambda_i(\tilde{b}_i-\beta_i)\geqslant \ln(\alpha) </math> | ||
| + | |||
| + | Або, оскільки <math>\lambda_i \geqslant 0 </math> | ||
| + | |||
| + | <math> \sum_{j=1}^n a_{ij}x_j \leqslant \tilde{b}_i, i=1,2,...,m </math> | ||
| + | |||
| + | <math> -\sum_{i=1}^m \sum_{j=1}^n \lambda_i a_{ij} x_j \geqslant \ln(\alpha) - \sum_{i=1}^m \lambda_i \beta_i </math> | ||
| + | |||
| + | Таким чином детермінована задача, що еквівалентна стохастичній задачі з ймовірнісними обмеженнями, в якій випадкові складові вектора b незалежні між собою і розподілені по експоненційному закону, виявляється задачею лінійного програмування. | ||
Виконав: [[Користувач:Олійник_Артем|Олійник Артем Олександрович]] | Виконав: [[Користувач:Олійник_Артем|Олійник Артем Олександрович]] | ||
| + | |||
| + | Редагувала: [[Користувач:Катя Зотько|Чеголя Катерина]] | ||
Поточна версія на 09:52, 22 травня 2018
Зведення задачі стохастичного програмування до еквівалентної детермінованої задачі є ефективним способом аналізу стохастичних моделей у тих випадках, коли детерміновані еквіваленти є задачами лінійного або випуклого програмування.
Наведемо деякі класи лінійних задач з ймовірнісними обмеженнями, для яких детерміновані еквіваленти являють собою задачі випуклого програмування. Покажемо, що вони можуть бути перетворені у зручний, для використання ефективних методів рішення, вигляд. Потрібно обчислити детерміновані вектори Неможливо розібрати вираз (невідома помилка): x
та Неможливо розібрати вираз (невідома помилка): g(x)
, за яких
Неможливо розібрати вираз (невідома помилка): \overline{c}x \to \max
Неможливо розібрати вираз (невідома помилка): F_{x}(g(x))=F_{x}(Ax- \tilde{b})=\alpha
Неможливо розібрати вираз (невідома помилка): g(x) = Ax- \tilde{b} , x\geqslant 0
Тут
Неможливо розібрати вираз (невідома помилка): F_{x}(Ax- \tilde{b})= P \{ Ax-b<Ax- \tilde{b} \} = P \{b> \tilde {b} \}
У випадку, коли складові Неможливо розібрати вираз (невідома помилка): b_i
вектора Неможливо розібрати вираз (невідома помилка): b - незалежні випадкові величини:
Неможливо розібрати вираз (невідома помилка): P \{b \geqslant \tilde {b} \} = \prod_{i =1}^m P \{b_i \geqslant \tilde{b_i} \} = \prod_{i =1}^m [1-P \{b_i < \tilde{b_i}) ] = \prod_{i =1}^m [1- F_{b_{i}}(\tilde{b_{i}}) ]
де Неможливо розібрати вираз (невідома помилка): F_{b_{i}}(\tilde{b_{i}})
- функція розподілу компоненти Неможливо розібрати вираз (невідома помилка): b_i вектора Неможливо розібрати вираз (невідома помилка): b
.
Еквівалентна детермінована задача при цьому набуває вигляду:
Неможливо розібрати вираз (невідома помилка): \overline{c}x \to \max
Неможливо розібрати вираз (невідома помилка): Ax\leqslant \tilde{b}
Неможливо розібрати вираз (невідома помилка): \prod_{i =1}^m [1- F_{b_{i}}(\tilde{b_{i}}) ] \geqslant \alpha
Неможливо розібрати вираз (невідома помилка): x\geqslant 0
Розглянемо випадок, коли щільності розподілів складових Неможливо розібрати вираз (невідома помилка): b_i
вектора обмежень визначаються однією з наступних функцій:
Неможливо розібрати вираз (невідома помилка): 1) \varphi_{i}^{(1)}(y_i)=\frac{1}{\sqrt{2\pi}\sigma_i} e^{-\frac{(y_i-\mu_i)^2}{2\sigma_i^2}}
Неможливо розібрати вираз (невідома помилка): 2) \varphi_{i}^{(2)}(y_i)=\begin{cases} \lambda_i\zeta_i(y_i-\beta_i)^{\zeta_i-1}e^{-\lambda_i(y_i-\beta_i)^{\zeta_i}},y_i\geqslant \beta_i\\ 0, y_i<\beta_i \end{cases}
Неможливо розібрати вираз (невідома помилка): \zeta_i\geqslant 1, \lambda\geqslant 0;
Неможливо розібрати вираз (невідома помилка): 3) \varphi_{i}^{(3)}(y_i)=\begin{cases} \frac{n_i}{\overline{a}_i-\underline{a}_i}(\frac{y_i-\underline{a}_i}{\overline{a}_i-\underline{a}_i})^{n_i-1},y_i \in [\overline{a}_i,\underline{a}_i]\\ 0, y_i \overline{\in} [\overline{a}_i,\underline{a}_i] \end{cases}
Неможливо розібрати вираз (невідома помилка): 4) \varphi_{i}^{(4)}(y_i)=\begin{cases} \frac{\lambda_i}{\Gamma(\zeta_i)}(\lambda_i y_i)^{\zeta_i-1}e^{-\lambda_i y_i},y_i\geqslant 0\\ 0, y_i<0 \end{cases}
Неможливо розібрати вираз (невідома помилка): \zeta_i\geqslant 1, \lambda\geqslant 0;
Щільність розподілу 1) відповідає нормальному закону. Формула 2) відповідає розподілу Вейбулла. Розподіл 3) включає рівномірний розподіл (Неможливо розібрати вираз (невідома помилка): n_i=1
). Щільність 4) визначає гамма-розподіл. Формули 2) і 4) включають експоненційний розподіл (Неможливо розібрати вираз (невідома помилка): \zeta_i=1
).
У всіх цих випадках розглянута задача – задача опуклого програмування. Однак ліві частини обмежень Неможливо розібрати вираз (невідома помилка): \prod_{i =1}^m [1- F_{b_{i}}(\tilde{b_{i}}) ] \geqslant \alpha
– не є опуклими вверх функціями. Замінимо цю умову на еквівалентну нерівність:
Неможливо розібрати вираз (невідома помилка): \sum_{i=1}^m \ln[1-F_{b_{i}}(\tilde{b_{i}})] \geqslant \ln(\alpha)
Ця заміна дозволяє перейти для всіх вищезазначених розподілів до еквівалентних детермінованих задач, у яких ліві частини обмежень – лінійні та опуклі вверх функції.
Доведемо це твердження для розподілів 1) і 2). Твердження буде доведене, якщо буде встановлена нерівність:
Неможливо розібрати вираз (невідома помилка): \frac{d^2}{d\tilde{b}_i^2} \gamma(\tilde{b_{i}})=\frac{d^2}{d\tilde{b}_i^2} \ln[1-F_{b_{i}}(\tilde{b_{i}})] \leqslant 0
де Неможливо розібрати вираз (невідома помилка): F_{b_{i}}(\tilde{b_{i}})= \int\limits_{-\infty}^{\tilde{b_{i}}} \varphi_{i}(y_i)dy_i
Для нормального розподілу 1) маємо:
Неможливо розібрати вираз (невідома помилка): \frac{d}{d\tilde{b}_i} \gamma(\tilde{b_{i}})=\frac{d}{d\tilde{b}_i} \ln[1-F_{b_{i}}(\tilde{b_{i}})]=-\frac{\varphi_i^{(1)}(y_i)}{1-\Phi_i(\tilde{b}_i)}
де Неможливо розібрати вираз (невідома помилка): \varphi_{i}^{(1)}(y_i)=\frac{1}{\sqrt{2\pi}\sigma_i} e^{-\frac{(\tilde{b}_i-\mu_i)^2}{2\sigma_i^2}}
,
Неможливо розібрати вираз (невідома помилка): \Phi_i(\tilde{b}_i)= \int\limits_{-\infty}^{\tilde{b_{i}}} e^{-\frac{(y_i-\mu_i)^2}{2\sigma_i^2}}
Маємо:
Неможливо розібрати вираз (невідома помилка): \frac{d^2}{d\tilde{b}_i^2} \gamma(\tilde{b_{i}})=-\frac{\varphi_i^{(1)}(y_i)\Theta_i(\tilde{b}_i)}{[1-\Phi_i(\tilde{b}_i)]^2}
де Неможливо розібрати вираз (невідома помилка): \Theta_i(\tilde{b}_i)=-\frac{\tilde{b}_i-\mu_i}{\sigma_i^2}[1-\Phi_i(\tilde{b}_i)]+\varphi_i^{(1)}(\tilde{b}_i)
Легко побачити, що
Неможливо розібрати вираз (невідома помилка): \frac{d\Theta_i(\tilde{b}_i)}{d\tilde{b}_i}=-\frac{1-\Phi_i(\tilde{b}_i)}{\sigma_i^2}<0
тобто, спадна функція від Неможливо розібрати вираз (невідома помилка): \tilde{b}_i
. Але Неможливо розібрати вираз (невідома помилка): \Theta_i(\infty)=0
. Тому Неможливо розібрати вираз (невідома помилка): \Theta_i(\tilde{b}_i)\geqslant 0
і Неможливо розібрати вираз (невідома помилка): \frac{d^2}{d\tilde{b}_i^2}\gamma(\tilde{b}_i)\leqslant 0
, що і необхідно було довести.
Для розподілу Вейбула маємо:
Неможливо розібрати вираз (невідома помилка): F_{b_{i}}(\tilde{b_{i}})= \int\limits_{-\infty}^{\tilde{b_{i}}} \varphi_{i}^{(2)}(y_i)dy_i=\begin{cases} 1-e^{-\lambda_i(\tilde{b_{i}}-\beta_i)^{\zeta_i}},\tilde{b_{i}}\geqslant \beta_i\\ 0, \tilde{b_{i}}<\beta_i \end{cases}
Тому Неможливо розібрати вираз (невідома помилка): \frac{d^2}{d\tilde{b}_i^2} \gamma(\tilde{b_{i}})=\begin{cases} -\zeta_i(\zeta_i-1)\lambda_i(\tilde{b}_i-\beta_i)^{\zeta_i-2},\tilde{b_{i}}\geqslant \beta_i\\ 0, \tilde{b_{i}}<\beta_i \end{cases}
Звідси випливає, що ліва частина нерівності (5) для Неможливо розібрати вираз (невідома помилка): b_i
, розподілених за Вейбулом, є функцією, опуклою вверх.
Нехай розглянемо частковий випадок, коли складові Неможливо розібрати вираз (невідома помилка): b_i
вектора обмежень розподілені за експоненційним законом з параметрами Неможливо розібрати вираз (невідома помилка): \lambda_i і Неможливо розібрати вираз (невідома помилка): \beta_i
. Експоненційний розподіл отримується з розподілу Вейбула при Неможливо розібрати вираз (невідома помилка): \zeta_i=1 . Обмеження (2) і (5), можуть бути в даному випадку записані у вигляді:
Неможливо розібрати вираз (невідома помилка): \sum_{j=1}^n a_{ij}x_j \leqslant \tilde{b}_i, i=1,2,...,m
Неможливо розібрати вираз (невідома помилка): -\sum_{i=1}^m \lambda_i(\tilde{b}_i-\beta_i)\geqslant \ln(\alpha)
Або, оскільки Неможливо розібрати вираз (невідома помилка): \lambda_i \geqslant 0
Неможливо розібрати вираз (невідома помилка): \sum_{j=1}^n a_{ij}x_j \leqslant \tilde{b}_i, i=1,2,...,m
Неможливо розібрати вираз (невідома помилка): -\sum_{i=1}^m \sum_{j=1}^n \lambda_i a_{ij} x_j \geqslant \ln(\alpha) - \sum_{i=1}^m \lambda_i \beta_i
Таким чином детермінована задача, що еквівалентна стохастичній задачі з ймовірнісними обмеженнями, в якій випадкові складові вектора b незалежні між собою і розподілені по експоненційному закону, виявляється задачею лінійного програмування.
Виконав: Олійник Артем Олександрович
Редагувала: Чеголя Катерина
