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

Матеріал з Вікі ЦДУ
Перейти до: навігація, пошук
Рядок 1: Рядок 1:
Відмовимося тепер від умови детермінованості матриці А в [[Задача СП. М-модель з імовірнісними обмеженнями з детермінованою матрицею коефіцієнтів обмежень. Детермінована задача. Двоїста задача.|задачі (1.1)-(1.3)]]. Нехай елементи матриці А та складові вектора  ''b'' – незалежні між собою нормально розподілені випадкові величини.
+
<font size=3> Відмовимося тепер від умови детермінованості матриці ''А'' в [[Задача СП. М-модель з імовірнісними обмеженнями з детермінованою матрицею коефіцієнтів обмежень. Детермінована задача. Двоїста задача.|задачі (1.1)-(1.3)]]. Нехай елементи матриці ''А'' та складові вектора  ''b'' – незалежні між собою нормально розподілені випадкові величини. </font>
  
Запис <math>a_{ij}\in N(\bar{a}_{ij},\sigma^2_{ij})</math>, <math>b_{i}\in N(\bar{b}_{i},\vartheta^2_{i})</math>  означає що <math>a_{ij}</math>  та <math>b_{i}</math>  - нормально розподілені в.в. з математичними сподіваннями <math>\bar{a}_{ij}</math> та <math>\bar{b}_{i}</math> і дисперсіями  <math>\vartheta^2_{i}</math> ,<math> \sigma^2_{ij}</math>.
+
<font size=3> Запис <math>a_{ij}\in N(\bar{a}_{ij},\sigma^2_{ij})</math>, <math>b_{i}\in N(\bar{b}_{i},\vartheta^2_{i})</math>  означає, що <math>a_{ij}</math>  (відповідно <math>b_{i}</math>) - нормально розподілені випадкові величини з математичним сподіваннями <math>\bar{a}_{ij}</math> (відповідно <math>\bar{b}_{i}</math>) та дисперсіями  <math>\vartheta^2_{i}</math> (відповідно <math> \sigma^2_{ij}</math>). </font>
  
Нехай крім того  
+
<font size=3> Нехай крім того, </font>
  
<math>\alpha{i}\geqslant 0,5,i=1,\ldots,m </math>.
+
<font size=3> <math>\alpha_{i}\geqslant 0,5,i=1,\ldots,m </math>. </font>
  
При зроблених припущеннях лінійна стохастична задача (1.1)-(1.3), розв'язок якої  визначається в розв’язувальних правилах нульового порядку, зводиться до детермінованої задачі випуклого програмування з лінійною цільовою функцією і квадратичними обмеженнями.
+
<font size=3> При зроблених припущеннях [[Задача СП. М-модель з імовірнісними обмеженнями з детермінованою матрицею коефіцієнтів обмежень. Детермінована задача. Двоїста задача.|лінійна стохастична задача(1.1)-(1.3)]], розв'язок якої  визначається в розв’язувальних правилах нульового порядку, зводиться до детермінованої задачі опуклого програмування з лінійною цільовою функцією та квадратичними обмеженнями. </font>
  
Дійсно, при прийнятих припущеннях нев’язка ''і''- ї умови – випадкова величина
+
<font size=3> Дійсно, при прийнятих припущеннях нев’язка ''і''-ої умови – випадкова величина </font>
  
<math>\delta_{i} = \sum^{n}_{j=1}{a_{ij}x_{j}}- b_{i}</math>
+
<font size=3> <math>\delta_{i} = \sum^{n}_{j=1}{a_{ij}x_{j}}- b_{i}</math> </font>
  
є нормально розподіленою величиною з математичним сподіванням
+
<font size=3> є нормально розподіленою величиною з математичним сподіванням </font>
  
<math>\bar{\delta}_{i}(x) = \sum^{n}_{j=1}\bar{a_{ij}x_{j}}- \bar{b_{i}}</math>
+
<font size=3> <math>\overline{\delta_{i}(x)} = \sum^{n}_{j=1}\bar{a}_{ij}x_{j}- \bar{b}_{i}</math> </font>
  
І дисперсією  
+
<font size=3> та дисперсією </font>
  
<math> \sigma^2_{i}(x)= \sum^{n}_{j=1}\sigma^2_{ij}x^2_{j}+ \vartheta^2_{i}</math>.
+
<font size=3> <math> \sigma^2_{i}(x)= \sum^{n}_{j=1}\sigma^2_{ij}x^2_{j}+ \vartheta^2_{i}</math>, </font>
  
тобто
+
<font size=3> тобто </font>
  
<math>\delta_{i}(x)\in N(\bar{\delta_{i}},\sigma^2_{i}(x))</math>.
+
<font size=3> <math>\delta_{i}(x)\in N(\overline{\delta_{i}(x)},\sigma^2_{i}(x))</math>. </font>
  
Співвідношення (1.2) еквівалентні нерівностям
+
<font size=3> Співвідношення (1.2) еквівалентні нерівностям </font>
  
<math>P(\delta_{i}(x)\leqslant0)\geqslant\alpha_{i}</math> , <math>i=1,\ldots,m</math>,
+
<font size=3> <math>P(\delta_{i}(x)\leqslant0)\geqslant\alpha_{i}</math> , <math>i=1,\ldots,m</math>, </font>
  
Або , в нашому випадку те саме  
+
<font size=3> або, в нашому випадку те саме </font>
  
<math>\ \frac{1}{\sqrt{2 \pi}\sigma_{i}(x)} \int\limits_{\infty}^{0} e^{(-\xi-\bar{\delta_{i}(x)})^2/2\sigma^2_{i}(x)}d\xi \geqslant\alpha_{i} </math>,  <math>i=1,\ldots,m</math>,.
+
<font size=3> <math>\ \frac{1}{\sqrt{2 \pi}\sigma_{i}(x)} \int\limits_{\infty}^{0} e^{-\frac{\xi-\bar{\delta}_{i}(x))^2}{2\sigma^2_{i}(x)}}d\xi \geqslant\alpha_{i} </math>,  <math>i=1,\ldots,m</math>,. </font>
  
Позначивши
+
<font size=3> Позначивши </font>
  
<math>\ \Phi(t)=\frac{1}{\sqrt{2 \pi}} \int\limits_\infty^0 e^{-\xi^2/2}d\xi </math> - функція Лапласа [https://ru.wikipedia.org/wiki/Функция_ошибок],
+
<font size=3> <math>\ \Phi(t)=\frac{1}{\sqrt{2 \pi}} \int\limits_\infty^0 e^{-\xi^2/2}d\xi </math> - [https://ru.wikipedia.org/wiki/Функция_ошибок функція Лапласа], </font>
  
 +
<font size=3> перепишемо останню нерівність у вигляді </font>
  
перепишемо останню нерівність у вигляді
+
<font size=3> <math>\Phi(-\bar{\delta}_{i}(x)/\sigma_{i}(x))\geqslant\alpha_{i}</math>, </font>
  
<math>\Phi(-\bar{\delta_{i}(x)}/\sigma_{i}(x))\geqslant\alpha_{i}</math>,
+
<math>\Phi(-\bar{\delta}_{i}(x)/\sigma_{i}(x))\geqslant\alpha_{i}</math>
  
Або те саме , що  
+
<font size=3> Або те саме , що </font>
  
<math>\bar{\delta_{i}(x)}+\Phi^{-1}(\alpha_{i}\sigma_{i}(x))\leqslant 0</math>.
+
<font size=3> <math>\bar{\delta_{i}(x)}+\Phi^{-1}(\alpha_{i}\sigma_{i}(x))\leqslant 0</math>. </font>
  
Враховуючи вирази для <math>\bar{\delta_{i}(x)}</math> та  <math>\sigma_{i}(x)</math> отримаємо  
+
<font size=3> Враховуючи вирази для <math>\bar{\delta_{i}(x)}</math> та  <math>\sigma_{i}(x)</math> отримаємо </font>
  
<math>\Phi^{-1}(\alpha_{i})(\sum^{n}_{j=1}\sigma^2_{ij}x^2_{j}+ \vartheta^2_{i})^{1/2})\leqslant \bar{b_{i}}-\sum^{n}_{j=1}\bar{a_{ij}x_{j}}</math>, <math>i=1,\ldots,m</math>.
+
<font size=3> <math>\Phi^{-1}(\alpha_{i})(\sum^{n}_{j=1}\sigma^2_{ij}x^2_{j}+ \vartheta^2_{i})^{1/2})\leqslant \bar{b_{i}}-\sum^{n}_{j=1}\bar{a_{ij}x_{j}}</math>, <math>i=1,\ldots,m</math>.
(1.12)
+
(1.12) </font>
  
При умові    <math>\alpha_{i}\geqslant 0,5</math>. В цьому випадку <math>\Phi^{-1}(\alpha_{i})\geqslant 0</math> , і область обмежена умовами (1.12) – випукла.  
+
<font size=3> За умовою <math>\alpha_{i}\geqslant 0,5</math>. В цьому випадку <math>\Phi^{-1}(\alpha_{i})\geqslant 0</math> , і область, обмежена умовами (1.12) – опукла. </font>
  
Аналогічний результат отримається і тоді коли випадкові елементи умови – рядки корельовано між собою .
+
<font size=3> Аналогічний результат отримауться і тоді, коли випадкові елементи умови – рядки, корельовані між собою. </font>
  
Ведемо позначення
+
<font size=3> Ведемо позначення </font>
  
<math>\upsilon_{ij}= M((b_{i}-\bar{b_{i}})(a_{ij}-\bar{a_{ij}}))</math>, <math>\upsilon_{ijk}= M((a_{ij}-\bar{a_{ij}})(a_{ik}-\bar{a_{ik}}))</math>.
+
<font size=3> <math>\upsilon_{ij}= M((b_{i}-\bar{b_{i}})(a_{ij}-\bar{a_{ij}}))</math>, <math>\upsilon_{ijk}= M((a_{ij}-\bar{a_{ij}})(a_{ik}-\bar{a_{ik}}))</math>. </font>
  
Міркуючи як і раніше отримаємо при <math>\alpha_{i}\geqslant 0,5</math>
+
<font size=3> Міркуючи як і раніше, отримаємо при <math>\alpha_{i}\geqslant 0,5</math> </font>
  
<math>\Phi^{-1}(\alpha_{i})(\sum_{jk}\upsilon_{ijk}x_{j}x_{k}+2\sum_{j}\upsilon_{ij}x_{j}+ \vartheta^2_{i})^{1/2})\leqslant \bar{b_{i}}-\sum_{j}\bar{a_{ij}x_{j}}</math>
+
<font size=3> <math>\Phi^{-1}(\alpha_{i})(\sum_{jk}\upsilon_{ijk}x_{j}x_{k}+2\sum_{j}\upsilon_{ij}x_{j}+ \vartheta^2_{i})^{1/2})\leqslant \bar{b_{i}}-\sum_{j}\bar{a_{ij}x_{j}}</math>
(1.13)
+
(1.13) </font>
  
<math>i=1,\ldots,m</math>.
+
<font size=3> <math>i=1,\ldots,m</math>. </font>
  
Додатня визначеність форми <math>\sum_{jk}\upsilon_{ijk}x_{j}x_{k}</math>  гарантує випуклість форми,  обмеженої умовами (1.13).
+
<font size=3> Додатня визначеність форми <math>\sum_{jk}\upsilon_{ijk}x_{j}x_{k}</math>  гарантує опуклість форми,  обмеженої умовами (1.13). </font>
  
Таким чином при прийнятих припущеннях лінійна стохастична задача (1.1)-(1.3) з ймовірнісними обмеженнями зводиться до детермінованої задачі випуклого програмування з лінійною цільовою функцією і квадратичними умовами - нерівностями:
+
<font size=3> Таким чином, при прийнятих припущеннях лінійна стохастична задача (1.1)-(1.3) з ймовірнісними обмеженнями зводиться до детермінованої задачі опуклого програмування з лінійною цільовою функцією та квадратичними умовами-нерівностями: </font>
  
<math>\sum^{n}_{j=1}\bar{c_{j}}\rightarrow max</math>,           
+
<font size=3> <math>\sum^{n}_{j=1}\bar{c_{j}}\rightarrow max</math>,           
(1.14)
+
(1.14) </font>
  
<math>\Phi^{-1}(\alpha_{i})(\sum_{jk}\upsilon_{ijk}x_{j}x_{k}+2\sum_{j}\upsilon_{ij}x_{j}+ \vartheta^2_{i})^{1/2})\leqslant \bar{b_{i}}-\sum_{j}\bar{a_{ij}x_{j}}</math>
+
<font size=3> <math>\Phi^{-1}(\alpha_{i})(\sum_{jk}\upsilon_{ijk}x_{j}x_{k}+2\sum_{j}\upsilon_{ij}x_{j}+ \vartheta^2_{i})^{1/2})\leqslant \bar{b_{i}}-\sum_{j}\bar{a_{ij}x_{j}}</math> </font>
  
<math>i=1,\ldots,m</math>
+
<font size=3> <math>i=1,\ldots,m</math>
(1.15)
+
(1.15) </font>
  
<math>x_{j}\geqslant 0</math>, <math>j=1,\ldots,n</math>
+
<font size=3> <math>x_{j}\geqslant 0</math>, <math>j=1,\ldots,n</math>
(1.16).
+
(1.16). </font>

Версія за 12:12, 2 червня 2017

Відмовимося тепер від умови детермінованості матриці А в задачі (1.1)-(1.3). Нехай елементи матриці А та складові вектора b – незалежні між собою нормально розподілені випадкові величини.

Запис Неможливо розібрати вираз (невідома помилка): a_{ij}\in N(\bar{a}_{ij},\sigma^2_{ij}) , Неможливо розібрати вираз (невідома помилка): b_{i}\in N(\bar{b}_{i},\vartheta^2_{i})

 означає, що Неможливо розібрати вираз (невідома помилка): a_{ij}
 (відповідно Неможливо розібрати вираз (невідома помилка): b_{i}

) - нормально розподілені випадкові величини з математичним сподіваннями Неможливо розібрати вираз (невідома помилка): \bar{a}_{ij}

(відповідно Неможливо розібрати вираз (невідома помилка): \bar{b}_{i}

) та дисперсіями Неможливо розібрати вираз (невідома помилка): \vartheta^2_{i}

(відповідно Неможливо розібрати вираз (невідома помилка):  \sigma^2_{ij}

).

Нехай крім того,

Неможливо розібрати вираз (невідома помилка): \alpha_{i}\geqslant 0,5,i=1,\ldots,m .

При зроблених припущеннях лінійна стохастична задача(1.1)-(1.3), розв'язок якої визначається в розв’язувальних правилах нульового порядку, зводиться до детермінованої задачі опуклого програмування з лінійною цільовою функцією та квадратичними обмеженнями.

Дійсно, при прийнятих припущеннях нев’язка і-ої умови – випадкова величина

Неможливо розібрати вираз (невідома помилка): \delta_{i} = \sum^{n}_{j=1}{a_{ij}x_{j}}- b_{i}


є нормально розподіленою величиною з математичним сподіванням

Неможливо розібрати вираз (невідома помилка): \overline{\delta_{i}(x)} = \sum^{n}_{j=1}\bar{a}_{ij}x_{j}- \bar{b}_{i}


та дисперсією

Неможливо розібрати вираз (невідома помилка): \sigma^2_{i}(x)= \sum^{n}_{j=1}\sigma^2_{ij}x^2_{j}+ \vartheta^2_{i} ,

тобто

Неможливо розібрати вираз (невідома помилка): \delta_{i}(x)\in N(\overline{\delta_{i}(x)},\sigma^2_{i}(x)) .

Співвідношення (1.2) еквівалентні нерівностям

Неможливо розібрати вираз (невідома помилка): P(\delta_{i}(x)\leqslant0)\geqslant\alpha_{i}

, Неможливо розібрати вираз (невідома помилка): i=1,\ldots,m

,

або, в нашому випадку те саме

Неможливо розібрати вираз (невідома помилка): \ \frac{1}{\sqrt{2 \pi}\sigma_{i}(x)} \int\limits_{\infty}^{0} e^{-\frac{\xi-\bar{\delta}_{i}(x))^2}{2\sigma^2_{i}(x)}}d\xi \geqslant\alpha_{i} , Неможливо розібрати вираз (невідома помилка): i=1,\ldots,m ,.

Позначивши

Неможливо розібрати вираз (невідома помилка): \ \Phi(t)=\frac{1}{\sqrt{2 \pi}} \int\limits_\infty^0 e^{-\xi^2/2}d\xi

- функція Лапласа, 

перепишемо останню нерівність у вигляді

Неможливо розібрати вираз (невідома помилка): \Phi(-\bar{\delta}_{i}(x)/\sigma_{i}(x))\geqslant\alpha_{i} ,

Неможливо розібрати вираз (невідома помилка): \Phi(-\bar{\delta}_{i}(x)/\sigma_{i}(x))\geqslant\alpha_{i}


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

Неможливо розібрати вираз (невідома помилка): \bar{\delta_{i}(x)}+\Phi^{-1}(\alpha_{i}\sigma_{i}(x))\leqslant 0 .

Враховуючи вирази для Неможливо розібрати вираз (невідома помилка): \bar{\delta_{i}(x)}

та  Неможливо розібрати вираз (невідома помилка): \sigma_{i}(x)
отримаємо 

Неможливо розібрати вираз (невідома помилка): \Phi^{-1}(\alpha_{i})(\sum^{n}_{j=1}\sigma^2_{ij}x^2_{j}+ \vartheta^2_{i})^{1/2})\leqslant \bar{b_{i}}-\sum^{n}_{j=1}\bar{a_{ij}x_{j}} , Неможливо розібрати вираз (невідома помилка): i=1,\ldots,m . (1.12)

За умовою Неможливо розібрати вираз (невідома помилка): \alpha_{i}\geqslant 0,5 . В цьому випадку Неможливо розібрати вираз (невідома помилка): \Phi^{-1}(\alpha_{i})\geqslant 0

, і область, обмежена умовами (1.12) – опукла. 

Аналогічний результат отримауться і тоді, коли випадкові елементи умови – рядки, корельовані між собою.

Ведемо позначення

Неможливо розібрати вираз (невідома помилка): \upsilon_{ij}= M((b_{i}-\bar{b_{i}})(a_{ij}-\bar{a_{ij}})) , Неможливо розібрати вираз (невідома помилка): \upsilon_{ijk}= M((a_{ij}-\bar{a_{ij}})(a_{ik}-\bar{a_{ik}})) .

Міркуючи як і раніше, отримаємо при Неможливо розібрати вираз (невідома помилка): \alpha_{i}\geqslant 0,5


Неможливо розібрати вираз (невідома помилка): \Phi^{-1}(\alpha_{i})(\sum_{jk}\upsilon_{ijk}x_{j}x_{k}+2\sum_{j}\upsilon_{ij}x_{j}+ \vartheta^2_{i})^{1/2})\leqslant \bar{b_{i}}-\sum_{j}\bar{a_{ij}x_{j}}

(1.13)

Неможливо розібрати вираз (невідома помилка): i=1,\ldots,m .

Додатня визначеність форми Неможливо розібрати вираз (невідома помилка): \sum_{jk}\upsilon_{ijk}x_{j}x_{k}

 гарантує опуклість форми,  обмеженої умовами (1.13). 

Таким чином, при прийнятих припущеннях лінійна стохастична задача (1.1)-(1.3) з ймовірнісними обмеженнями зводиться до детермінованої задачі опуклого програмування з лінійною цільовою функцією та квадратичними умовами-нерівностями:

Неможливо розібрати вираз (невідома помилка): \sum^{n}_{j=1}\bar{c_{j}}\rightarrow max , (1.14)

Неможливо розібрати вираз (невідома помилка): \Phi^{-1}(\alpha_{i})(\sum_{jk}\upsilon_{ijk}x_{j}x_{k}+2\sum_{j}\upsilon_{ij}x_{j}+ \vartheta^2_{i})^{1/2})\leqslant \bar{b_{i}}-\sum_{j}\bar{a_{ij}x_{j}}


Неможливо розібрати вираз (невідома помилка): i=1,\ldots,m

(1.15)

Неможливо розібрати вираз (невідома помилка): x_{j}\geqslant 0 , Неможливо розібрати вираз (невідома помилка): j=1,\ldots,n

(1.16).