Перегляд вихідного коду сторінки Екстремальні задачі та розв’язувальні розподіли. Класифікація задач за розв’язувальними розподілами: з детермін.и умовами...

'''''<font color='green' size=5>	Екстремальні задачі та розв’язувальні розподіли.</font>'''''


<font  size=3>  Математичне програмування – це прикладна математична дисципліна, яка досліджує екстремальні задачі (задачі пошуку максимуму або мінімуму) та розробляє методи їх розв'язання. Задачі такого типу ще називають оптимізаційними. Математичне програмування відіграє дуже важливу роль як в подальшій математичній освіті, та і в майбутній професійній діяльності, оскільки дозволяє вирішувати багато управлінських і організаційних задач оптимальним чином.
 Залежно від змісту постановки плану і розв'язання, задачі обчислюються в чистих або змішаних стратегіях. Розв'язок чистих стратегій - це вектор - оптимальний план задачі. Змішані задачі являють собою ймовірнісні розподіли компонент оптимального плану. У відповідності із інформаційною структурою задачі як чисті , так і змішані стратегії можуть залежати або не залежати від спостережених реалізацій випадкових параметрів умов задачі. Розв’язок в чистих стратегіях будемо називати вирішальними правилами, розв’язок в змішаних стратегіях - вирішальними розподілами.
Таким чином, у загальному випадку розв'язком задачі стохастичного програмування є вирішальне правило або вирішальний розподіл, що залежить, взагалі кажучи, від двох груп чинників. Фактори першої групи не пов'язані із спостереженням поточних значень параметрів умов завдання. Вони визначаються апріорною інформацією - деякими характеристиками розподілу або вибіркою можливих значень випадкових параметрів умов. Фактори першої групи можуть бути завчасно використані для побудови вирішального правила або вирішального розподілу. Фактори другої групи визначаються апостеріорною інформацією, що з'являється в результаті спостереження, вирішальні правила і вирішальні розподіли залежать тільки від детермінованих параметрів і статистичних характеристик випадкових параметрів умов задачі.
Умовні екстремальні задачі, в яких змішані стратегії мають змістовний сенс можна розділити на три класи. До першого класу відносять задачі математичного програмування з детермінованими умовами , в яких оптимальний план визначається у вигляді розв’язувального розподілу. Функціонали, що виражають показники якості розв’язку і обмеження таких моделей, замінюються на математичне сподівання. До другого класу включають стохастичні задачі, в яких рішення має бути прийняте до спостережень над реалізацією випадкових параметрів умов. Розв’язувальні розподіли тут не залежать від реалізації випадку. По аналогії з апріорними розв’язувальними правилами такі розв’язувальні розподіли називаються апріорними. До третього класу відносять задачі, в яких можливо і доцільно приймати після спостережень над реалізацією  випадкових параметрів умов задачі. Розв’язувальні розподіли в таких задачах залежать від реалізації випадку і тому їх доцільно називати апостеріорними.


Наведемо формальний запис всіх трьох класів умов екстремальних задач.
 
У задачах першого класу з детермінованими параметрами умов потрібно обчислити розподіл <math>F_{x}</math>  вектора х при якому:

<math>M\phi_{0} (x) =\int \phi_{0} dF_{x} \rightarrow inf </math>,                  (3.1)

<math>M\phi_{i} (x) =\int  \phi_{i} dF_{x} \leqslant  0, i=1,2,...,m </math>,                  (3.2)

<math> x\in X </math>,   (3.3)

де Х задана множина в n-вимірному евклідовому просторі.

В задачах другого класу потрібно обчислити функцію розподілу <math>F_{x}</math> для якої:

<math> M\phi_{0} (\omega,x) =\int \limits_{\tilde{x \times \Omega}} \phi_{0}(\omega,x) dF_{x} dF_{\infty} \rightarrow inf </math>,                  (3.4)

<math> M\phi_{i} (\omega,x) =\int\limits_{\tilde{x \times \Omega}} \phi_{i}(\omega,x) dF_{x} dF_{\infty} \leqslant  0, i=1,2,...,m </math>,                  (3.5)

<math> x\in X </math> ,  (3.6)

В задачах третього класу потрібно обрахувати умовну функцію розподілу <math>F_{x|\infty}</math> для якої

<math> M\phi_{0} (\omega,x) =\int \limits_{\tilde{x \times \Omega}} \phi_{0}(\omega,x) dF_{x|\infty} dF_{\infty} \rightarrow inf </math>,     (3.7)

<math> M\phi_{i} (\omega,x) =\int\limits_{\tilde{x \times \Omega}} \phi_{i}(\omega,x) dF_{x|\infty} dF_{\infty} \leqslant  0, i=1,2,...,m </math> ,      (3.8)

<math> x\in X </math>.   (3.9)

'''1.2. ''' Розглянемо детальніше задачі (3.1)-(3.3) першого класу. Введемо нові змінні:

<math> \tilde{y_{i}}= \phi_{i}(x) ,   i=1,2,...,m  </math>,     (3.10)

Відображення (3.10) переводить множину  <math> X  \subset R^{n} </math> в <math> У  \subset R^{m+1} </math>. В загальному випадку У- не опукла і не замкнена множина. Позначимо через соУ випуклу оболонку множини У. Задача (3.1)-(3.3) Може бути переписана у вигляді:

<math>  y_{0}  \rightarrow inf </math> ,    (3.11)

<math>  y_{i} \leqslant  0, i=1,2,...,m </math>,  (3.12)

<math>  y=(y_{0},y_{1},...,y_{m}) \in coY  </math>.(3.13)

Згідно з теоремою Каратеодорі для побудови випуклої оболонки з множини У із m+1- вимірного простору потрібно в загальному випадку не більше m+2 точок <math> y \in Y </math>. Це означає, що соУ може бути представлена у вигляді:

<math>\ coY= \{\sum^{m+1}_{k=0} {\phi_{i}(x_{k})p_{k}}; i=0,1,...,m; p_{k}\geq 0 ,  \sum^{m+1}_{k=0} p_{k}=1, x_{k} \in X \} </math>.

Нас цікавлять тільки точки <math> y \in Y  \subset R^{m+1} </math>, одна із координат <math> (y_{0}) </math> яких досягає свого екстремального значення. Такі точки у відповідності із наслідком теореми Каратеодорі можуть бути представлені як випуклі комбінації не більш ніж m+1 точок множини У.

Відповідно, задача (3.11)-(3.13), а разом з нею і початкова задача (3.1)-(3.3) повністю визначається набором m+1  векторів <math> x_{k} \in X </math> і m+1 чисел <math> p_{k} (k=0,1,...,m), p_{k}\geq 0, \sum^{m}_{k=0} p_{k}=1.</math>

Задача (3.1)-(3.3)еквівалентна, таким чином, наступній скінченно вимірній задачі.

Потрібно обрахувати вектори <math> x_{k} </math> і числа  <math>  p_{k} </math>, які визначають нижню грань функціонала:

<math> \sum^{m}_{k=0} {\phi_{0}(x_{k})p_{k}}</math>, (3.14)

за умов 

<math> \sum^{m}_{k=0} {\phi_{і}(x_{k})p_{k}}\leqslant 0,i=1,2,...,m, </math>(3.15)

<math>  x_{k} \in X, p_{k} \geq  0, k=0,1,...,m, \sum^{m}_{k=0} p_{k}=1.</math>  (3.16)

Вектори <math>  x_{k}^* </math> і числа  <math>  p_{k}^* </math>, що складають оптимальний план задачі (3.14)-(3.16), визначають дискретний розв'язувальний розподіл  вихідної задачі (3.1)-(3.3).

'''1.3. '''Визначення апріорних вирішальних розподілів завдань другого класу - стохастичних задач виду (3,4)-(3,6) може бути аналогічним образом зведена до рішення задач кінцево-метричного нелінійного програмування.

Позначимо

<math> \int\limits_{\tilde{ \Omega}} \phi_{i}(\omega,x) dF_{\infty} =  \tilde \phi_{i}(x), i=0,1,...,m </math>,   (3,17)   

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

Потрібно обрахувати вектори <math>  x_{k}^* </math> і числа  <math>  p_{k}^* </math>  які визначають нижню межу функціоналу:

<math> \sum^{m}_{k=0} \tilde {\phi_{0}(x_{k})p_{k}} </math> (3.18)

за умов

<math> \sum^{m}_{k=0} \tilde {\phi_{i}(x_{k})p_{k}} \leqslant  0.</math> (3.19)

<math> x\in X, p_{k} \geq  0, k=0,1,...,m,  \sum^{m}_{k=0} p_{k}=1. </math> (3.20)

Оптимальний план <math> x_{k}^*, p_{k}^*, k = 0,1,...,m, </math> задачі (3.18) - (3.20) визначає дискретний розв'язувальний розподіл задачі (3.4) - (3.6). 

У випадку, коли множина X складається з скінченного числа s точок <math> x_{1}, ..., x_{s},</math>. обрахунок вирішального розподілу зводиться до вирішення задачі лінійного програмування

<math> \sum^{s}_{k=1} \tilde {\phi_{0}(x_{k})p_{k}} \rightarrow min </math> (3.21)

<math> \sum^{s}_{k=1} \tilde {\phi_{i}(x_{k})p_{k}} \leqslant  0i=1,2,...,m.</math>   (3.22)

<math>\sum^{s}_{k=1} p_{k}=1, </math> (3.23)

<math>p_{k} \geq  0, k=1,...,s. </math> (3.24)

Крім умов невід'ємності змінних задача має обмеження. Тому оптимальний план задачі ( 3.21 ) - ( 3.24 ) містить не більше m+1 додатних значень <math>  p_{k} </math>. Величини <math> p_{k}^* \geq 0</math> і відповідні їм вектори <math> x_{k}^* </math> визначають апріорні дискретні вирішальні розподіли розглянутої задачі . Наведені міркування справедливі і для множини Х, що складеться із скінченного числа точок. Цей же принцип може бити використаний для наближення апріорного вирішального розподілу у випадку, коли множина Х являє собою компакт. Дискретні значення <math> x_{k} </math> відповідають вузлам <math> \epsilon </math>- мережі(сети) множини Х. 

</font>
 
Виконала: [[Користувач:Чуйкова Анна|Чуйкова Анна Сергіївна]]

Редагувала: [[Користувач:Кухаренко Настя|Кухаренко Анастасія]]