Відмінності між версіями «Задача СП з апріорними розв’язувальними розподілами. Зведення до розв’язку задачі скінченно-вимірного нелінійного програмування.»

Матеріал з Вікі ЦДУ
Перейти до: навігація, пошук
 
(не показані 11 проміжних версій 3 учасників)
Рядок 1: Рядок 1:
−
Постановка  задачі записана в 18 пункті(18.4 - 18.6).
+
<font size=3><math>(3.1)\;M\psi_{0}(x)=\int\psi_{0}(x)dF_{x}\rightarrow inf,</math>
−
задача  зводиться до задачі вигляду (19.1) - (19.3). Повторюючи мыркування попереднього пункту, приходимо до висновку, що обчислення апрыорних розв'язуальних розподілів задачі (20.1) - (20.3) еквівалентно рішенню наступної скінченно - мірної задачі математичного програмування.
+
−
Потрібно обчислити вектори <math>\ x_{k}</math> і числа <math> \ p_{k} </math>, які визначають нижню межу функціонала
+
  
−
<math>\ {\sum^{m}_{k=0}(\overline\phi_{0})(x_{k})p_{k}}</math>;  (20.5)
+
<math>(3.2)\;M\psi_{i}(x)=\int\psi_{i}(x)dF_{x}\leq 0,\;i=1,2,..,m,</math>
  
−
За умови
+
<math>(3.3)\;x\in X,</math>
  
−
<math>\ {\sum^{m}_{k=0}(\overline\phi_{i})x_{k}p_{k}\le 0 \  i = 1,...m}</math>; (20.6)
+
<math>(3.4)\;M\psi_0(\omega,x)=\int\limits_{X\times\Omega}\psi_0(\omega,x)dF_xdF_{\omega}\rightarrow inf,</math>
  
 +
<math>(3.5)\;M\psi_i(\omega,x)=\int\limits_{X\times\Omega}\psi_i(\omega,x)dF_xdF_{\omega}\leq 0,\;i=1,..,m,</math>
  
−
<math>\ x_{k}\in X, \ p_{k}\ge 0 , \  k = 0,1,...m,    \sum^{m}_{k=0} p_{k}=1  </math>,(20.7)
+
<math>(3.6)\;x\in X,</math>
  
 +
<math>(3.7)\;M\psi_0(\omega,x)=\int\limits_{X\times\Omega}\psi_0(\omega,x)dF_{x|\omega}dF_{\omega}\rightarrow inf,</math>
  
 +
<math>(3.8)\;M\psi_i(\omega,x)=\int\limits_{X\times\Omega}\psi_i(\omega,x)dF_{x|\omega}dF_{\omega}\leq 0,\;i=1,..,m,</math>
  
−
Вектори <math>\ x\ast_{k}</math> і числа <math> \ p\ast_{k} </math>, що становить оптимальний план задачі (20.5) - (20.7), визначають дискретний розв'язувальний розподіл вихідної задачі (20.1) - (20.3).
+
<math>(3.9)\;x\in X.</math>
  
−
В випадку , коли множина <math>\ X </math> складається із скінченного числа <math>\ s </math> точок <math>\ (x_1,...,x_s )</math> , обчислення розв'язувального розподілу зводиться до розв'язу задачі лінійного програмування.
+
3.3. Визначення апріорних розв'язувальних розподілів задач другого класу - стохастичних задач виду (3.4) - (3.6) може бути аналогічним чином зведено до розв'язку задач скінчено-вимірного нелінійного програмування.
  
−
<math>\  {\sum^{s}_{k=1}(\overline\phi_{0})(x_{k})p_{k}}\rightarrow min </math>  (20.8)
+
Введемо наступне позначення:
  
−
<math>\ {\sum^{s}_{k=1}(\overline\phi_{i})x_{k}p_{k}\le 0 \  i = 1,...m}</math>; (20.9)
+
<math>(3.17)\;\int\limits_{\Omega}\overline{\psi_i}(\omega,x)dF_{\omega}=\overline{\psi_i}(x),\;i=0,1,...,m.</math>
  
 +
В цих позначеннях задача (3.4) - (3.6) зводиться до задачі виду (3.1) - (3.3).
  
−
<math>\sum^{m}_{k=0} p_{k}=1  </math>, (20.10)
+
Повторюючи міркування попереднього пункту, прийдемо до висновку, що обчислення апріорних розв'язувальних розподілів задачі (3.4) - (3.6) еквівалентно розв'язку наступної скінчено-вимірної задачі математичного програмування.
  
 +
Вимагається обчислити вектори <math>x_k</math> і числа <math>p_k</math>, які визначають нижню грань функціонала:
  
−
<math>\   p_{k}\ge 0 , \ k = 0,1,...m,   </math>, (20.11)  
+
<math>(3.18)\;{\sum^{m}_{k=0}\overline{\psi_{0}}(x_k)p_{k}},</math>
 +
 
 +
за умови
 +
 
 +
<math>(3.19)\;{\sum^{m}_{k=0}\overline{\psi_{i}}(x_{k})p_{k}}\le 0,</math>
 +
 
 +
<math>(3.20)\;x_{k}\in X,p_{k}\ge 0,k = 0,1,...m,\sum^{m}_{k=0} p_{k}=1.</math>
 +
 
 +
Оптимальний план <math>x^\ast_{k}</math>, <math>p^\ast_{k}</math>, <math>k=0,1,...,m,</math> задачі (3.18) - (3.20) визначає дискретний розв'язувальний розподіл задачі (3.4) - (3.6).
 +
 
 +
У випадку, коли множина <math>X</math> складається із скінченного числа <math>s</math> точок <math>x_1,...,x_s</math>, обчислення розв'язувального розподілу зводиться до розв'язку задачі лінійного програмування:
 +
 
 +
<math>(3.21)\;{\sum^{s}_{k=1}\overline\psi_{0}(x_{k})p_{k}}\rightarrow min,</math>
 +
 
 +
<math>(3.22)\;{\sum^{s}_{k=1}\overline\psi_{i}x_{k}p_{k}\le 0,\;i = 1,...m},</math>
 +
 
 +
<math>(3.23)\;\sum^{s}_{k=1}p_{k}=1,</math>
 +
 
 +
<math>(3.24)\;p_{k}\ge 0,k = 1,...s.</math>
 
   
 
   
−
Крім умов невід'ємності змінних задача має <math>\  m+1 </math>,обмеження. Тому оптимальний план задачі(20,8) - (20,11) містить не більше  <math>\  m+1 </math> додатних значень <math>\  p_{k}</math>.  
+
Крім умов невід'ємності змінних задача має <math>m+1</math> обмеження. Тому оптимальний план задачі (3.21) - (3.24) містить не більше  <math>m+1</math> додатних значень <math>p_{k}</math>. Величини <math>p^\ast_{k}>0</math> і відповідні їм вектори <math>x^\ast_{k}</math> визначають апріорний дискретний розв'язувальний розподіл розглянутої задачі. Приведені нижче міркування справедливі і для множини <math>X</math>, що складається зі зліченого числа точок. Цей же принцип може бути використаний для наближення апріорного розвязувального розподілу у випадку, коли множина <math>X</math> являє собою компакт. Дискретне значення <math>x_k</math> відповідає вузлам <math>\varepsilon</math>-мережі множини <math>X</math>.
−
Величини <math> \ p\ast_{k}>0 </math> і відповідні їм вектори  
+
 
−
<math>\ x\ast_{k}</math> визначають апріорний ' розподіл розглянутої задачі.
+
3.4. Обчислення апостеріорних розв'язувальних правил стохастичної задачі (3.7) - (3.9) в загальному випадку пов'язано зі значними труднощами. Однак у випадку, коли простір <math>\Omega</math> елементарних подій складається зі скінченого числа <math>(r)</math> елементів, ймовірність яких задана, розв'язок спрощується. Побудова опуклої оболонки множини
 +
 
 +
<math>Y=\left \{y_i=\psi_i(\omega,x),\;i=0,1,...,m,\;x\in X \right \},</math>
 +
 
 +
можна уявити у вигляді двоетапної операції. На початку будуються опуклі оболонки множини <math>Y</math> при фіксованих значеннях <math>\omega</math>, а потім у відповідності з дискретною ймовірнісною мірою на <math>\Omega</math> визначається опукла комбінація множин, побудованих на першому етапі. Ясно, що отримане в результаті зазначених побудов множина опукла.
 +
 
 +
Обмеженням (3.8) відповідають обмеження на елементи цієї множини. Задача (3.7) - (3.9) зводиться в цьому випадку, як і задача (3.1) - (3.З) і (3.4) - (3.6), до кінцево-мірної задачі нелінійного програмування. Розв’язок цієї задачі (вектори <math>x^\ast_{k},k=1,...,(m+1)r</math>, і спільні ймовірності <math>p^\ast_{kl}</math> використання <math>x^\ast_{k}</math> і <math>\omega_l,l=1,..,r</math>) визначають дискретний апостеріорний розв’язувальний розподіл задачі (3.7) - (3.9). Ці ж міркування можуть бути використані для побудови наближених апостеріорних розв’язувальних розподілів у випадках, коли множина <math>X</math> і <math>\Omega</math> компактні.
 +
 
 +
З наведених міркувань видно, що, якщо функції <math>\psi_i(\omega,x),i=0,1,...,m,</math> опуклі по <math>x</math> при кожному <math>\omega</math>, то оптимальний розв’язувальний розподіл не дозволяє поліпшити цільовий функціонал в порівнянні з оптимальним розв’язувальним правилом. Чисті стратегії дозволяють в цьому випадку отримати той же ефект, що і мішані стратегії. Ясно, що цей висновок справедливий і в тому випадку, коли <math>\Omega</math> не є дискретною множиною. У <math>\S</math> 5 буде доведено результат, відповідно до якого при неперервній мірі <math>F_{\omega}</math> на <math>\Omega</math> можна, не погіршуючи якості розв’язку задачі (3.7) - (3.9) і не вимагаючи опуклості <math>\psi_i(\omega,x),i=0,1,...,m,</math> при кожному <math>\omega</math>, замінити апостеріорні розв’язувальні розподіли на апостеріорні розв’язувальні правила.
 +
 
 +
Було отримано умови оптимальності для задач виду (3.7) - (3.9). Вони дозволяють побудувати методи обчислення апостеріорних розв’язувальних розподілів для стохастичних задач загального вигляду. При заданому розподілі <math>F_{\omega}</math> розв’язувальні розподіли можуть бути побудовані за допомогою методів, узагальнюючих методи можливих напрямків. У випадках, коли можна спостерігати реалізацію <math>\omega</math>, для побудови апостеріорних розв’язувальних розподілів пропонуються ітеративні обчислювальні схеми, узагальнюючі методи стохастичної апроксимації.
  
 
Виконала: [[Користувач:Юрченко Тетяна Сергіївна|Юрченко Тетяна Сергіївна ]]
 
Виконала: [[Користувач:Юрченко Тетяна Сергіївна|Юрченко Тетяна Сергіївна ]]
 +
 +
Доповнювала: [[Користувач:65890|Татьяненко Марина Олександрівна]]<font>

Поточна версія на 16:53, 9 квітня 2019

Неможливо розібрати вираз (невідома помилка): (3.1)\;M\psi_{0}(x)=\int\psi_{0}(x)dF_{x}\rightarrow inf,


Неможливо розібрати вираз (невідома помилка): (3.2)\;M\psi_{i}(x)=\int\psi_{i}(x)dF_{x}\leq 0,\;i=1,2,..,m,


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


Неможливо розібрати вираз (невідома помилка): (3.4)\;M\psi_0(\omega,x)=\int\limits_{X\times\Omega}\psi_0(\omega,x)dF_xdF_{\omega}\rightarrow inf,


Неможливо розібрати вираз (невідома помилка): (3.5)\;M\psi_i(\omega,x)=\int\limits_{X\times\Omega}\psi_i(\omega,x)dF_xdF_{\omega}\leq 0,\;i=1,..,m,


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


Неможливо розібрати вираз (невідома помилка): (3.7)\;M\psi_0(\omega,x)=\int\limits_{X\times\Omega}\psi_0(\omega,x)dF_{x|\omega}dF_{\omega}\rightarrow inf,


Неможливо розібрати вираз (невідома помилка): (3.8)\;M\psi_i(\omega,x)=\int\limits_{X\times\Omega}\psi_i(\omega,x)dF_{x|\omega}dF_{\omega}\leq 0,\;i=1,..,m,


Неможливо розібрати вираз (невідома помилка): (3.9)\;x\in X.


3.3. Визначення апріорних розв'язувальних розподілів задач другого класу - стохастичних задач виду (3.4) - (3.6) може бути аналогічним чином зведено до розв'язку задач скінчено-вимірного нелінійного програмування.

Введемо наступне позначення:

Неможливо розібрати вираз (невідома помилка): (3.17)\;\int\limits_{\Omega}\overline{\psi_i}(\omega,x)dF_{\omega}=\overline{\psi_i}(x),\;i=0,1,...,m.


В цих позначеннях задача (3.4) - (3.6) зводиться до задачі виду (3.1) - (3.3).

Повторюючи міркування попереднього пункту, прийдемо до висновку, що обчислення апріорних розв'язувальних розподілів задачі (3.4) - (3.6) еквівалентно розв'язку наступної скінчено-вимірної задачі математичного програмування.

Вимагається обчислити вектори Неможливо розібрати вираз (невідома помилка): x_k 

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

, які визначають нижню грань функціонала:

Неможливо розібрати вираз (невідома помилка): (3.18)\;{\sum^{m}_{k=0}\overline{\psi_{0}}(x_k)p_{k}},


за умови

Неможливо розібрати вираз (невідома помилка): (3.19)\;{\sum^{m}_{k=0}\overline{\psi_{i}}(x_{k})p_{k}}\le 0,


Неможливо розібрати вираз (невідома помилка): (3.20)\;x_{k}\in X,p_{k}\ge 0,k = 0,1,...m,\sum^{m}_{k=0} p_{k}=1.


Оптимальний план Неможливо розібрати вираз (невідома помилка): x^\ast_{k} , Неможливо розібрати вираз (невідома помилка): p^\ast_{k} , Неможливо розібрати вираз (невідома помилка): k=0,1,...,m, 

задачі (3.18) - (3.20) визначає дискретний розв'язувальний розподіл задачі (3.4) - (3.6).

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

складається із скінченного числа Неможливо розібрати вираз (невідома помилка): s
точок Неможливо розібрати вираз (невідома помилка): x_1,...,x_s

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

Неможливо розібрати вираз (невідома помилка): (3.21)\;{\sum^{s}_{k=1}\overline\psi_{0}(x_{k})p_{k}}\rightarrow min,


Неможливо розібрати вираз (невідома помилка): (3.22)\;{\sum^{s}_{k=1}\overline\psi_{i}x_{k}p_{k}\le 0,\;i = 1,...m},


Неможливо розібрати вираз (невідома помилка): (3.23)\;\sum^{s}_{k=1}p_{k}=1,


Неможливо розібрати вираз (невідома помилка): (3.24)\;p_{k}\ge 0,k = 1,...s.


Крім умов невід'ємності змінних задача має Неможливо розібрати вираз (невідома помилка): m+1 

обмеження. Тому оптимальний план задачі (3.21) - (3.24) містить не більше  Неможливо розібрати вираз (невідома помилка): m+1
додатних значень Неможливо розібрати вираз (невідома помилка): p_{k}

. Величини Неможливо розібрати вираз (невідома помилка): p^\ast_{k}>0 

і відповідні їм вектори Неможливо розібрати вираз (невідома помилка): x^\ast_{k}
визначають апріорний дискретний розв'язувальний розподіл розглянутої задачі. Приведені нижче міркування справедливі і для множини Неможливо розібрати вираз (невідома помилка): X

, що складається зі зліченого числа точок. Цей же принцип може бути використаний для наближення апріорного розвязувального розподілу у випадку, коли множина Неможливо розібрати вираз (невідома помилка): X 

являє собою компакт. Дискретне значення Неможливо розібрати вираз (невідома помилка): x_k
відповідає вузлам Неможливо розібрати вираз (невідома помилка): \varepsilon

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

3.4. Обчислення апостеріорних розв'язувальних правил стохастичної задачі (3.7) - (3.9) в загальному випадку пов'язано зі значними труднощами. Однак у випадку, коли простір Неможливо розібрати вираз (невідома помилка): \Omega 

елементарних подій складається зі скінченого числа Неможливо розібрати вираз (невідома помилка): (r)
елементів, ймовірність яких задана, розв'язок спрощується. Побудова опуклої оболонки множини

Неможливо розібрати вираз (невідома помилка): Y=\left \{y_i=\psi_i(\omega,x),\;i=0,1,...,m,\;x\in X \right \},


можна уявити у вигляді двоетапної операції. На початку будуються опуклі оболонки множини Неможливо розібрати вираз (невідома помилка): Y 

при фіксованих значеннях Неможливо розібрати вираз (невідома помилка): \omega

, а потім у відповідності з дискретною ймовірнісною мірою на Неможливо розібрати вираз (невідома помилка): \Omega 

визначається опукла комбінація множин, побудованих на першому етапі. Ясно, що отримане в результаті зазначених побудов множина опукла.

Обмеженням (3.8) відповідають обмеження на елементи цієї множини. Задача (3.7) - (3.9) зводиться в цьому випадку, як і задача (3.1) - (3.З) і (3.4) - (3.6), до кінцево-мірної задачі нелінійного програмування. Розв’язок цієї задачі (вектори Неможливо розібрати вираз (невідома помилка): x^\ast_{k},k=1,...,(m+1)r , і спільні ймовірності Неможливо розібрати вираз (невідома помилка): p^\ast_{kl} 

використання Неможливо розібрати вираз (невідома помилка): x^\ast_{k}
і Неможливо розібрати вираз (невідома помилка): \omega_l,l=1,..,r

) визначають дискретний апостеріорний розв’язувальний розподіл задачі (3.7) - (3.9). Ці ж міркування можуть бути використані для побудови наближених апостеріорних розв’язувальних розподілів у випадках, коли множина Неможливо розібрати вираз (невідома помилка): X 

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

З наведених міркувань видно, що, якщо функції Неможливо розібрати вираз (невідома помилка): \psi_i(\omega,x),i=0,1,...,m, 

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

, то оптимальний розв’язувальний розподіл не дозволяє поліпшити цільовий функціонал в порівнянні з оптимальним розв’язувальним правилом. Чисті стратегії дозволяють в цьому випадку отримати той же ефект, що і мішані стратегії. Ясно, що цей висновок справедливий і в тому випадку, коли Неможливо розібрати вираз (невідома помилка): \Omega 

не є дискретною множиною. У Неможливо розібрати вираз (невідома помилка): \S
5 буде доведено результат, відповідно до якого при неперервній мірі Неможливо розібрати вираз (невідома помилка): F_{\omega}
на Неможливо розібрати вираз (невідома помилка): \Omega
можна, не погіршуючи якості розв’язку задачі (3.7) - (3.9) і не вимагаючи опуклості Неможливо розібрати вираз (невідома помилка): \psi_i(\omega,x),i=0,1,...,m,
при кожному Неможливо розібрати вираз (невідома помилка): \omega

, замінити апостеріорні розв’язувальні розподіли на апостеріорні розв’язувальні правила.

Було отримано умови оптимальності для задач виду (3.7) - (3.9). Вони дозволяють побудувати методи обчислення апостеріорних розв’язувальних розподілів для стохастичних задач загального вигляду. При заданому розподілі Неможливо розібрати вираз (невідома помилка): F_{\omega} 

розв’язувальні розподіли можуть бути побудовані за допомогою методів, узагальнюючих методи можливих напрямків. У випадках, коли можна спостерігати реалізацію Неможливо розібрати вираз (невідома помилка): \omega

, для побудови апостеріорних розв’язувальних розподілів пропонуються ітеративні обчислювальні схеми, узагальнюючі методи стохастичної апроксимації.

Виконала: Юрченко Тетяна Сергіївна

Доповнювала: Татьяненко Марина Олександрівна

Отримано з https://wiki.cusu.edu.ua/index.php?title=Задача_СП_з_апріорними_розв’язувальними_розподілами._Зведення_до_розв’язку_задачі_скінченно-вимірного_нелінійного_програмування.&oldid=341410