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

Матеріал з Вікі ЦДУ
Перейти до: навігація, пошук

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

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

C – випадкові числа, Неможливо розібрати вираз (невідома помилка): \alpha_{i}>0,5, \alpha_{i}<1


При детермінованій матриці Неможливо розібрати вираз (невідома помилка): \ A=||a_{ij}||

і випадковому веторі Неможливо розібрати вираз (невідома помилка): b=(b_{ij})
дана задача  зводиться до детермінованої  задачі лінійного програмування.


Дійсно, нехай Неможливо розібрати вираз (невідома помилка): \phi(b_{1}...b_{m})

– загальна щільність розподілу елементів  Неможливо розібрати вираз (невідома помилка): b_{i}
випадкового вектора b. Щільність розподілу компонента Неможливо розібрати вираз (невідома помилка): b_{i}
рівна:

Неможливо розібрати вираз (невідома помилка): \phi_{i}(b_{i})= \int\limits_{\infty}^{\infty}... \int\limits_{\infty}^{\infty}\phi(b_{1}...b_{m})\prod^{j\not=i}db_{j}


Знайдемо Неможливо розібрати вираз (невідома помилка): \tilde{b_i}

з рівняння:

Неможливо розібрати вираз (невідома помилка): \int\limits_{\tilde{b_i}}^{\infty}\phi_{i}(b_{i})db_{i}=\alpha_{i} , Неможливо розібрати вираз (невідома помилка): i=1,\ldots,m

(1.4)

Якщо рішення рівняння (1.4) не єдине, то обирається в якості Неможливо розібрати вираз (невідома помилка): \tilde{b_i}

  найбільший корінь.

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

Неможливо розібрати вираз (невідома помилка): \sum^{n}_{j=1}{a_{ij}x_{j}}\leqslant\tilde{b_i} , Неможливо розібрати вираз (невідома помилка): i=1,\ldots,m , Де Неможливо розібрати вираз (невідома помилка): \tilde{b_i}

  задовольняють відношенням (1.4).

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

Неможливо розібрати вираз (невідома помилка): \bar{c}x\rightarrow max

(1.5)

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

(1.6)

Неможливо розібрати вираз (невідома помилка): x\geqslant 0

(1.7)

Де Неможливо розібрати вираз (невідома помилка): \bar{c}= M(c) , Неможливо розібрати вираз (невідома помилка): \tilde{b}=(\tilde{b_1}...\tilde{b_m}


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

 арактеризуються функцією розподілу  Неможливо розібрати вираз (невідома помилка): F_{i}(b_{i})

, то параметр

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

) ̃представляє собою найбільше число, яке задовольняє нерівність Неможливо розібрати вираз (невідома помилка): 1-F_{i}(\tilde{b_i})\geqslant\alpha_{i}

.