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

Поточна версія на 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{b}_{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 с.

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

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