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

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

Поточна версія на 21:55, 3 червня 2017

Розглянемо задачу лінійного стохастичного програмування з ймовірнісними обмеженнями типу М-модель:

Неможливо розібрати вираз (невідома помилка): 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)

Відмовимося тепер від умови детермінованості матриці А в задачі (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^{-\frac{\xi^2}{2}}d\xi 

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

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

Неможливо розібрати вираз (невідома помилка): \Phi(-\frac{\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})^{\frac{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_{j,k}\upsilon_{ijk}x_{j}x_{k}+2\sum_{j}\upsilon_{ij}x_{j}+ \vartheta^2_{i})^{\frac{1}{2}}\leqslant \bar{b}_{i}-\sum_{j}\bar{a}_{ij}x_{j}

(1.13)

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

Додатня визначеність форми Неможливо розібрати вираз (невідома помилка): \sum_{j,k}\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_{j,k}\upsilon_{ijk}x_{j}x_{k}+2\sum_{j}\upsilon_{ij}x_{j}+ \vartheta^2_{i})^{\frac{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) [1, c. 66-67].


Список використаних джерел

1. Юдин Д. Б. Математические методы управления в условиях неполной информации. / Юдин Д. Б. М: «Сов. радио», 1974. – 400 с.


Виконала: Овчаренко Мар’яна

Доповнювала: Іванченко Дар’я

Отримано з https://wiki.cusu.edu.ua/index.php?title=Задача_СП:_М-модель_з_імовірнісними_обмеженнями_з_випадковою_матрицею_коефіцієнтів_обмежень._Незалежні_корельовані_умови_обмеження.&oldid=284480