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

Матеріал з Вікі ЦДПУ
Перейти до: навігація, пошук
 
Рядок 78: Рядок 78:
  
 
<font size=3> <math>\zeta = min \{y|G_{i}(y)\geqslant \beta{j}\}</math>. </font>
 
<font size=3> <math>\zeta = min \{y|G_{i}(y)\geqslant \beta{j}\}</math>. </font>
 +
 +
<font size=3> Зрозуміло, що для неперервних строго монотонних функцій розподілу необхідність в наведених застереженнях відпадає. </font>
  
 
<font size=3> Попередня задача (1.9)-(1.11) може бути записана у вигляді </font>
 
<font size=3> Попередня задача (1.9)-(1.11) може бути записана у вигляді </font>
Рядок 105: Рядок 107:
 
<font size=3> де  <math>\alpha = \{\alpha_{i}\}</math> , <math>\beta=\{\beta_{j}\}</math> , <math>F^{-1}= \{F^{-1}_{i}\}</math>,  <math>G^{-1}= \{G^{-1}_{j}\}</math>. </font>
 
<font size=3> де  <math>\alpha = \{\alpha_{i}\}</math> , <math>\beta=\{\beta_{j}\}</math> , <math>F^{-1}= \{F^{-1}_{i}\}</math>,  <math>G^{-1}= \{G^{-1}_{j}\}</math>. </font>
  
<font size=3> Отриманий результат дозволяє для розглядуваного випадку стохастичних задач з ймовірнісними обмеженнями використовувати інтерпретації теорем  двоїстості для якісного аналізу розв'язку та оцінки параметрів задачі [1, c. 64-66]. </font>
+
<font size=3> Отриманий результат, який належить Бен-Ізраелю, дозволяє для розглядуваного випадку стохастичних задач з ймовірнісними обмеженнями використовувати інтерпретації теорем  двоїстості для якісного аналізу розв'язку та оцінки параметрів задачі [1, c. 64-66]. </font>
  
  

Поточна версія на 22:54, 6 квітня 2021

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

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); \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}.

Якщо 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 0 (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. 64-66].


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

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


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

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