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

Матеріал з Вікі ЦДУ
Перейти до: навігація, пошук
 
(не показано 43 проміжні версії 3 учасників)
Рядок 1: Рядок 1:
−
Розглянемо задачу лінійного стохастичного програмування з  ймовірнісними обмеженнями типу М-модель:
+
<font size=3> Розглянемо задачу лінійного стохастичного програмування з  ймовірнісними обмеженнями типу ''М''-модель: </font>
  
−
<math>M(cx)\rightarrow max</math>
+
<font size=3> <math>M(cx)\rightarrow max</math>
−
(1.1),
+
(1.1), </font>
  
−
<math>P(\sum^{n}_{j=1}{a_{ij}x_{j}}\leqslant b_{i})\geqslant \alpha_{i},i=1,\ldots,m</math>
+
<font size=3> <math>P(\sum^{n}_{j=1}{a_{ij}x_{j}}\leqslant b_{i})\geqslant \alpha_{i},i=1,\ldots,m</math>
−
(1.2),
+
(1.2), </font>
  
−
<math>x_{j}\geqslant 0,j=1,\ldots,n </math>
+
<font size=3> <math>x_{j}\geqslant 0,j=1,\ldots,n </math>
−
(1.3)
+
(1.3) </font>
  
−
C – випадкові числа,  <math>\alpha_{i}>0,5,  \alpha_{i}<1</math>
+
<font size=3> <math>c</math> – випадкові числа,  <math>0,5<\leqslant \alpha_{i}<1</math> </font>
  
 +
<font size=3> При детермінованій матриці <math>\ A=||a_{ij}|| </math> і випадковому веторі <math>b=(b_{ij})</math> задача (1.1)-(1.3) зводиться до детермінованої задачі лінійного програмування. </font>
  
−
При детермінованій матриці <math>\ A=||a_{ij}|| </math> і випадковому веторі <math>b=(b_{ij})</math> дана задача  зводиться до детермінованої  задачі лінійного програмування.
+
<font size=3> Дійсно, нехай <math>\phi(b_{1}...b_{m})</math> – спільна щільність розподілу елементів  <math>b_{i}</math> випадкового вектора ''b''. Щільність розподілу компонента <math>b_{i}</math> дорівнює: </font>
  
 +
<font size=3> <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> </font>
  
−
Дійсно, нехай <math>\phi(b_{1}...b_{m})</math> – загальна щільність розподілу елементів  <math>b_{i}</math> випадкового вектора ''b''. Щільність розподілу компонента <math>b_{i}</math> рівна:
+
<font size=3> Знайдемо <math>\tilde{b_i}</math> з рівняння: </font>
  
−
<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>
+
<font size=3> <math> \int\limits_{\tilde{b_i}}^{\infty}\phi_{i}(b_{i})db_{i}=\alpha_{i}</math>, <math>i=1,\ldots,m</math>
 +
(1.4) </font>
  
−
Знайдемо <math>\tilde{b_i}</math> з рівняння:
+
<font size=3> Якщо розв’язок рівняння (1.4) не є єдиним, то оберемо в якості  <math>\tilde{b_i}</math>   найбільший корінь. </font>
  
−
<math> \int\limits_{\tilde{b_i}}^{\infty}\phi_{i}(b_{i})db_{i}=\alpha_{i}</math>, <math>i=1,\ldots,m</math>
+
<font size=3> Відношення (1.2) еквівалентні нерівностям </font>
−
(1.4)
+
  
−
Якщо рішення рівняння (1.4) не єдине, то обирається в якості <math>\tilde{b_i}</math>  найбільший корінь.
+
<font size=3> <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). </font>
  
−
Відношення (1.2) еквівалентне нерівності
+
<font size=3> Звідси  випливає еквівалентність задачі стохастичного програмування (1.1) – (1.3) та детермінованої задачі лінійного програмування </font>
  
−
<math>\sum^{n}_{j=1}{a_{ij}x_{j}}\leqslant\tilde{b_i}</math>,  <math>i=1,\ldots,m</math>,
+
<font size=3> <math>\bar{c}x\rightarrow max</math>
−
Де <math>\tilde{b_i}</math>   задовольняють відношенням (1.4).
+
(1.5) </font>
  
−
Звідси  випливає еквівалентність задачі  стохастичного програмування (1.1) – (1.3) і детермінованої  задачі лінійного програмування
+
<font size=3> <math>Ax\leqslant\tilde{b}</math>
 +
(1.6) </font>
  
−
<math>\bar{c}x\rightarrow max</math>
+
<font size=3> <math>x\geqslant 0</math>
−
(1.5)
+
(1.7) </font>
  
−
<math>Ax\leqslant\tilde{b}</math>
 
−
(1.6)
 
  
−
<math>x\geqslant 0</math>
 
−
(1.7)
 
  
−
Де <math>\bar{c}= M(c)</math>,
+
<font size=3> де <math>\bar{c}= M(c)</math>;  <math>\tilde{b}=(\tilde{b_1}...\tilde{b_m})</math>. </font>
  
−
<math>\tilde{b}=(\tilde{b_1}...\tilde{b_m})</math>
+
<font size=3> Якщо випадкові величини <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>. </font>
  
−
Якщо випадкові величини <math>b_{i}</math> арактеризуються функцією розподілу  <math>F_{i}(b_{i})</math>,
+
<font size=3> Якщо <math>F_{i}(b_{i})</math> – неперервна строго монотонна функція, то остання нерівність еквівалентнa рівнянню <math>1-F_{i}(\tilde{b_i})=\alpha_{i}</math>. </font>
  
−
то параметр <math>\tilde{b_i}</math> представляє собою найбільше число, яке задовольняє нерівність <math>1-F_{i}(\tilde{b_i})\geqslant\alpha_{i}</math> .
+
<font size=3> У всіх випадках будемо записувати </font>
  
−
Якщо <math>F_{i}(b_{i})</math> – неперервна строго монотонна функція, то остання нерівність еквівалентнa рівнянню <math>1-F_{i}(\tilde{b_i})=\alpha_{i}</math> .
+
<font size=3> <math>\tilde{b}= F_{i}^{-1}(1-\alpha_{i})</math> </font>
  
−
У всіх випадках будемо записувати <math>\tilde{b}= F_{i}^(-1)(1-\alpha_{i})</math>, <math>F_{i}^(-1)(t)=\sup(y|F_{i}(y)\geqslant t)</math>.
+
<font size=3> <math>F_{i}^{-1}(t)=\sup(y|F_{i}(y)\leqslant t)</math>. (1.8) </font>
−
(1.8)
+
  
−
Для стохастичної задачі (1.1)-(1.3) з детермінованою матрицею А, тобто для задачі (1.5)-(1.7), можна записати '''двоїсту задачу''' з ймовірнісними обмеженнями.
+
<font size=3> Для стохастичної задачі (1.1)-(1.3) з детермінованою матрицею ''А'', тобто для задачі (1.5)-(1.7), можна записати '''двоїсту задачу''' з ймовірнісними обмеженнями. </font>
  
−
Розглянемо задачу  
+
<font size=3> Розглянемо задачу </font>
  
−
<math>y\tilde{b}\rightarrow min</math>
+
<font size=3> <math>y\tilde{b}\rightarrow min</math>
−
(1.9)
+
(1.9) </font>
  
−
<math>P(yA\geqslant c)\geqslant\beta</math>
+
<font size=3> <math>P(yA\geqslant c)\geqslant\beta</math>
−
(1.10)
+
(1.10) </font>
  
−
<math>y\geqslant o</math>
+
<font size=3> <math>y\geqslant 0</math>
−
(1.11)
+
(1.11) </font>
  
−
Розв'язок  якої  <math>у*</math> визначається у вигляді детермінованого вектора.
+
<font size=3> Розв'язок  якої  <math>y^*</math>
 +
визначається у вигляді детермінованого вектора. </font>
  
−
Нехай <math>G_{j}(\zeta)=P(c_{j}\leqslant\zeta)</math>.
+
<font size=3> Нехай <math>G_{j}(\zeta)</math> - функція розподілу випадкового коефіцієнта <math>c_{j}</math> лінійної форми (1.1)</font>
  
−
Якщо <math>G_{j}(\zeta)=\beta{j}</math>, то запис  <math>\zeta=G_{j}^(-1)(\beta{j})</math>) будемо вважати еквіваленою запису
+
<font size=3> <math>G_{j}(\zeta)=P(c_{j}\leqslant\zeta)</math>. </font>
  
−
<math>\zeta = min (y|G_{i}(y)\geqslant \beta{j})</math>.
+
<font size=3> Якщо <math>G_{j}(\zeta)=\beta{j}</math>, то запис  <math>\zeta=G_{j}^{-1}(\beta{j})</math> будемо вважати еквіваленим запису </font>
  
−
Попередня задача (1.9)-(1.11) буде записана у вигляді
+
<font size=3> <math>\zeta = min \{y|G_{i}(y)\geqslant \beta{j}\}</math>. </font>
  
−
<math>y\tilde{b}\rightarrow min</math>,
+
<font size=3> Зрозуміло, що для неперервних строго монотонних функцій розподілу необхідність в наведених застереженнях відпадає. </font>
  
−
<math>yA\geqslant G^(-1)(\beta)</math>,
+
<font size=3> Попередня задача (1.9)-(1.11) може бути записана у вигляді </font>
  
−
<math>y\geqslant o</math>.
+
<font size=3> <math>y\tilde{b}\rightarrow min</math>, </font>
  
−
Порівнюючи останню задачу з початковою (1.1)-(1.3) отримуємо, що при <math>\beta=G(\bar{c})</math> наступні дві одно етапні задачі стохастичного програмування з ймовірнісними умовами та апріорними розв’язувальними правилами являють собою двоїсту пару :
+
<font size=3> <math>yA\geqslant G^{-1}(\beta)</math>, </font>
  
−
<math>G^(-1)(\beta)x\rightarrow max</math>,
+
<font size=3> <math>y\geqslant 0</math>. </font>
  
−
<math>P(Ax\leqslantb)\geqslant\alpha</math>,
+
<font size=3> Порівнюючи останню задачу з початковою (1.1)-(1.3) отримуємо, що при <math>\beta=G(\bar{c})</math> наступні дві одноетапні задачі стохастичного програмування з ймовірнісними обмеженнями та апріорними розв’язувальними правилами являють собою двоїсту пару: </font>
  
−
<math>x\geqslant\0</math>,
+
<font size=3> <math>G^{-1}(\beta)x\rightarrow max</math>, </font>
  
−
<math>yF^(-1)(1-\alpha)\rightarrow min</math>,
+
<font size=3> <math>P(Ax\leqslant b)\geqslant\alpha</math>, </font>
  
−
<math>P(yA\geqslant)\leqslantb\beta</math>,
+
<font size=3> <math>x\geqslant 0</math>, </font>
  
−
<math>x\geqslant\0</math>,
+
 
 +
 
 +
<font size=3> <math>yF^{-1}(1-\alpha)\rightarrow min</math>, </font>
 +
 
 +
<font size=3> <math>P(yA\geqslant c)\geqslant\beta</math>, </font>
 +
 
 +
<font size=3> <math>y\geqslant 0</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>
 +
 
 +
 
 +
 
 +
==Список використаних джерел==
 +
1. Юдин Д. Б. Математические методы управления в условиях неполной информации. / Юдин Д. Б. М: «Сов. радио», 1974. – 400 с.
 +
 
 +
 
 +
 
 +
Виконала: [[Користувач:Ира Ханенко|Ира Ханенко]]
 +
 
 +
Доповнювала: [[Користувач:Іванченко Олександра|Іванченко Олександра]]

Поточна версія на 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 с.


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

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

Отримано з https://wiki.cusu.edu.ua/index.php?title=Задача_СП._М-модель_з_імовірнісними_обмеженнями_з_детермінованою_матрицею_коефіцієнтів_обмежень._Детермінована_задача._Двоїста_задача.&oldid=373789