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

Версія за 19:42, 2 червня 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)

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

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

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

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

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

.

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

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

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

.

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

– неперервна строго монотонна функція, то остання нерівність еквівалентнa рівнянню Неможливо розібрати вираз (невідома помилка): 1-F_{i}(\tilde{b_i})=\alpha_{i}

.

У всіх випадках будемо записувати

Неможливо розібрати вираз (невідома помилка): \tilde{b}= F_{i}^{-1}(1-\alpha_{i})

Неможливо розібрати вираз (невідома помилка): F_{i}^{-1}(t)=\sup(y|F_{i}(y)\leqslant t) . (1.8)

Для стохастичної задачі (1.1)-(1.3) з детермінованою матрицею А, тобто для задачі (1.5)-(1.7), можна записати двоїсту задачу з ймовірнісними обмеженнями.

Розглянемо задачу

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

(1.9)

Неможливо розібрати вираз (невідома помилка): P(yA\geqslant c)\geqslant\beta

(1.10)

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

(1.11)

Розв'язок якої Неможливо розібрати вираз (невідома помилка): y^*

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

Нехай Неможливо розібрати вираз (невідома помилка): G_{j}(\zeta)

- функція розподілу випадкового коефіцієнта Неможливо розібрати вираз (невідома помилка): c_{j}
лінійної форми (1.1)

Неможливо розібрати вираз (невідома помилка): G_{j}(\zeta)=P(c_{j}\leqslant\zeta) .

Якщо Неможливо розібрати вираз (невідома помилка): G_{j}(\zeta)=\beta{j} , то запис Неможливо розібрати вираз (невідома помилка): \zeta=G_{j}^{-1}(\beta{j})

будемо вважати еквіваленим запису 

Неможливо розібрати вираз (невідома помилка): \zeta = min \{y|G_{i}(y)\geqslant \beta{j}\} .

Попередня задача (1.9)-(1.11) може бути записана у вигляді

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

Неможливо розібрати вираз (невідома помилка): yA\geqslant G^{-1}(\beta) ,

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

Порівнюючи останню задачу з початковою (1.1)-(1.3) отримуємо, що при Неможливо розібрати вираз (невідома помилка): \beta=G(\bar{c})

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

Неможливо розібрати вираз (невідома помилка): G^{-1}(\beta)x\rightarrow max ,

Неможливо розібрати вираз (невідома помилка): P(Ax\leqslant b)\geqslant\alpha ,

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

Неможливо розібрати вираз (невідома помилка): yF^{-1}(1-\alpha)\rightarrow min ,

Неможливо розібрати вираз (невідома помилка): P(yA\geqslant c)\geqslant\beta ,

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

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

, Неможливо розібрати вираз (невідома помилка): \beta=\{\beta_{j}\}
, Неможливо розібрати вираз (невідома помилка): F^{-1}= \{F^{-1}_{i}\}

, Неможливо розібрати вираз (невідома помилка): G^{-1}= \{G^{-1}_{j}\} .

Отриманий результат дозволяє для розглядуваного випадку стохастичних задач з ймовірнісними обмеженнями використовувати інтерпретації теорем двоїстості для якісного аналізу розв'язку та оцінки параметрів задачі [1, c. 65-67].

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

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

Виконала: Ира Ханенко

Доповнювала: Іванченко Олександра