Перегляд вихідного коду сторінки Задача СП. М-модель з імовірнісними обмеженнями з детермінованою матрицею коефіцієнтів обмежень. Детермінована задача. Двоїста задача.

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

<math>M(cx)\rightarrow max</math>
(1.1),

<math>P(\sum^{n}_{j=1}{a_{ij}x_{j}}\leqslant b_{i})\geqslant \alpha_{i},i=1,\ldots,m</math>
(1.2),

<math>x_{j}\geqslant 0,j=1,\ldots,n </math>
(1.3)

<math>c</math> – випадкові числа,  <math>0.5<alpha_{i}<1</math>


При детермінованій матриці <math>\ A=||a_{ij}|| </math> і випадковому веторі <math>b=(b_{ij})</math> дана задача  зводиться до детермінованої  задачі лінійного програмування.


Дійсно, нехай <math>\phi(b_{1}...b_{m})</math> – загальна щільність розподілу елементів  <math>b_{i}</math> випадкового вектора ''b''. Щільність розподілу компонента <math>b_{i}</math> рівна:

<math>\phi_{i}(b_{i})= \int\limits_{\infty}^{\infty}... \int\limits_{\infty}^{\infty}\phi(b_{1}...b_{m})\prod^{j\not=i}db_{j}</math>

Знайдемо <math>\tilde{b_i}</math> з рівняння:

<math> \int\limits_{\tilde{b_i}}^{\infty}\phi_{i}(b_{i})db_{i}=\alpha_{i}</math>, <math>i=1,\ldots,m</math>
(1.4)

Якщо рішення рівняння (1.4) не єдине, то обирається в якості  <math>\tilde{b_i}</math>   найбільший корінь.

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

<math>\sum^{n}_{j=1}{a_{ij}x_{j}}\leqslant\tilde{b_i}</math>,  <math>i=1,\ldots,m</math>, 
де <math>\tilde{b_i}</math>   задовольняють відношення (1.4).

Звідси  випливає еквівалентність задачі  стохастичного програмування (1.1) – (1.3)  і детермінованої  задачі лінійного програмування

<math>\bar{c}x\rightarrow max</math>
(1.5)

<math>Ax\leqslant\tilde{b}</math>
(1.6)

<math>x\geqslant 0</math>
(1.7)

де <math>\bar{c}= M(c)</math>, 

<math>\tilde{b}=(\tilde{b_1}...\tilde{b_m})</math>

Якщо випадкові величини <math>b_{i}</math>  характеризуються функцією розподілу  <math>F_{i}(b_{i})</math>, 

то параметр <math>\tilde{b_i}</math> представляє собою найбільше число, яке задовольняє нерівність <math>1-F_{i}(\tilde{b_i})\geqslant\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>, <math>F_{i}^{-1}(t)=\sup(y|F_{i}(y)\leqslant 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\leqslant b)\geqslant\alpha</math>,

<math>x\geqslant 0</math>,

<math>yF^{-1}(1-\alpha)\rightarrow min</math>,

<math>P(yA\geqslant c)\leqslant\beta</math>,

<math>y\geqslant 0</math>,

Де  <math>\alpha = (\alpha_{i})</math> , <math>\beta=(\beta_{j})</math> , <math>F^{-1}= (F^{-1}_{i})</math>,  <math>G^{-1}= (G^{-1}_{j})</math>.

Отриманий результат дозволяє для розглядуваного випадку стохастичних задач з ймовірнісними обмеженнями використовувати інтерпретації теорем  двоїстості для якісного аналізу розв'язку і оцінки параметрів задачі.