Дві часткові стохастичні моделі з розв'язувальними правилами нульового порядку.

Розглянемо 2 часткові P-моделі з детермінованими обмеженнями і випадковими коефіцієнтами лінійної форми. Побудуємо відповідні детерміновані еквіваленти.

Нехай потрібно

Неможливо розібрати вираз (невідома помилка): P(cx\leq{k})\to{max}

(1)

за умов

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

           (2)

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

            (3)

Елементи матриці А та компоненти вектора b детерміновані, а компоненти вектора c випадкові.

Припускають, що розв’язок задачі (1)-(3) визначається серед детермінованих векторів.

До схеми виду (1)-(3) зводиться задача планування виробництва при випадкових втратах, пов’язаних з реалізацією різних технологічних способів. Оптимальний план повинен максимізувати ймовірність того, що сумарні затрати не перевищать деякої, заданої вищою організацією, величини.

Модель №1.

В цій моделі випадковий вектор Неможливо розібрати вираз (невідома помилка): ~c=c(\omega)

припускається рівним Неможливо розібрати вираз (невідома помилка): ~c=c_{0}+c_{1}\tau(\omega)

, де Неможливо розібрати вираз (невідома помилка): ~c_{0},c_{1}

– детерміновані вектори,Неможливо розібрати вираз (невідома помилка): ~\tau(\omega)
– випадкова величина.

Припускають також, що гіперплощина Неможливо розібрати вираз (невідома помилка): ~c_{1}x=0

не перетинається з многогранною множиною (2)-(3). Нехай для визначеності в точках множини (2)-(3) Неможливо розібрати вираз (невідома помилка): ~c_{1}x>0

Детермінована задача представляє собою наступну задачу дробово-лінійного програмування:

Неможливо розібрати вираз (невідома помилка): {\frac{k-c_{0}x}{c_{1}x}}\to{max}

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

Дійсно за прийнятих припущень:

Неможливо розібрати вираз (невідома помилка): P(cx\leq{k})=P\{\omega:c(\omega)x\leq{k}\}=P\{\omega:\tau(\omega)\leq{\frac{k-c_{0}x}{c_{1}x}}\}

Модель №2.

В цій моделі компоненти Неможливо розібрати вираз (невідома помилка): ~c_j

випадкового вектора c припускаються нормально розподіленими з параметрами Неможливо розібрати вираз (невідома помилка): ~\mu_j,\sigma_j

, тобто Неможливо розібрати вираз (невідома помилка): c_j\in N(\mu_j,\sigma_j) .

Припускають також, що точка x=0 не є планом задачі.

Детермінований еквівалент представляє собою задачу нелінійного, точніше неопуклого, програмування:

Неможливо розібрати вираз (невідома помилка): \Big[\Big(k-\sum^{n}_{j=1} {\mu_j x_j}\Big)\Big(\sum^{n}_{j=1} {\sigma_j^2 x_j^2}\Big)^{-1/2}\Big]\to max

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

Дійсно за прийнятих припущень:

Неможливо розібрати вираз (невідома помилка): P(cx\leq{k})=P\Bigg(\sum^{n}_{j=1} {c_j x_j}\leq{k}\Bigg)=P\Bigg\{\frac{\sum^{n}_{j=1} {c_j x_j}-\sum^{n}_{j=1} {\mu_j x_j}}{\sqrt{\sum^{n}_{j=1} {\sigma_j^2 x_j^2}}}\leq{\frac{k-\sum^{n}_{j=1} {\mu_j x_j}}{\sqrt{\sum^{n}_{j=1} {\sigma_j^2 x_j^2}}}}\Bigg\}=P(\eta\leq{\eta_0})

Неможливо розібрати вираз (невідома помилка): \eta=\frac{\sum^{n}_{j=1} {c_j x_j}-\sum^{n}_{j=1} {\mu_j x_j}}{\sqrt{\sum^{n}_{j=1} {\sigma_j^2 x_j^2}}}

Неможливо розібрати вираз (невідома помилка): \eta_{0}=\frac{k-\sum^{n}_{j=1} {\mu_j x_j}}{\sqrt{\sum^{n}_{j=1} {\sigma_j^2 x_j^2}}}

В силу прийнятих припущень випадкова величина Неможливо розібрати вираз (невідома помилка): \eta

нормально розподілена: Неможливо розібрати вираз (невідома помилка): \eta\in N(0,1)

. Тому

Неможливо розібрати вираз (невідома помилка): P(cx\leq{k})=P(\eta\leq{\eta_0})=\frac{1}{\sqrt{2\pi}}\int\limits_{-\infty}^{\eta_{0}}{e^{-t^2/2}}

Відповідно, максимізація цільової функції (1) може бути замінена максимізацією

Неможливо розібрати вираз (невідома помилка): \eta_{0}=\frac{k-\sum^{n}_{j=1} {\mu_j x_j}}{\sqrt{\sum^{n}_{j=1} {\sigma_j^2 x_j^2}}}

При Неможливо розібрати вираз (невідома помилка): ~\mu_j=0

задача зводиться до задачі квадратичного програмування:

Неможливо розібрати вираз (невідома помилка): \sum^{n}_{j=1} {\sigma_j^2 x_j^2}\to min

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

Причому розв’язок не залежить від величини заданого порогу k.

Приклад

Побудувати детермінований аналог задачі стохастичного програмування

Неможливо розібрати вираз (невідома помилка): P(cx\leq{k})\to{max}

за умов

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

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

якщо відомо, що Неможливо розібрати вираз (невідома помилка): c_j\in N(\mu_j,\sigma_j)

Початкові умови:

Неможливо розібрати вираз (невідома помилка): ~c_0 = (2 3 0 1)

Неможливо розібрати вираз (невідома помилка): ~c_1 = (3 4 5 0)