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

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

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

Наведемо формальний запис всіх трьох класів умов екстремальних задач.

У задачах першого класу з детермінованими параметрами умов потрібно обчислити розподіл Неможливо розібрати вираз (невідома помилка): F_{x}

 вектора х при якому:

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

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

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

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

В задачах другого класу потрібно обчислити функцію розподілу Неможливо розібрати вираз (невідома помилка): F_{x}

для якої:

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

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

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

,  (3.6)

В задачах третього класу потрібно обрахувати умовну функцію розподілу Неможливо розібрати вираз (невідома помилка): F_{x|\infty}

для якої

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

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

,      (3.8)

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

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

Неможливо розібрати вираз (невідома помилка): \tilde{y_{i}}= \phi_{i}(x) , i=1,2,...,m , (3.10)

Відображення (3.10) переводить множину Неможливо розібрати вираз (невідома помилка): X \subset R^{n}

в Неможливо розібрати вираз (невідома помилка):  У  \subset R^{m+1} 

. В загальному випадку У- не опукла і не замкнена множина. Позначимо через соУ випуклу оболонку множини У. Задача (3.1)-(3.3) Може бути переписана у вигляді:

Неможливо розібрати вираз (невідома помилка): y_{0} \rightarrow inf

,    (3.11)

Неможливо розібрати вираз (невідома помилка): y_{i} \leqslant 0, i=1,2,...,m , (3.12)

Неможливо розібрати вираз (невідома помилка): y=(y_{0},y_{1},...,y_{m}) \in coY .(3.13)

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

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

Нас цікавлять тільки точки Неможливо розібрати вираз (невідома помилка): y \in Y \subset R^{m+1} , одна із координат Неможливо розібрати вираз (невідома помилка): (y_{0})

яких досягає свого екстремального значення. Такі точки у відповідності із наслідком теореми Каратеодорі можуть бути представлені як випуклі комбінації не більш ніж m+1 точок множини У.

Відповідно, задача (3.11)-(3.13), а разом з нею і початкова задача (3.1)-(3.3) повністю визначається набором m+1 векторів Неможливо розібрати вираз (невідома помилка): x_{k} \in X

і m+1 чисел Неможливо розібрати вираз (невідома помилка):  p_{k} (k=0,1,...,m), p_{k}\geq 0, \sum^{m}_{k=0} p_{k}=1.

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

Потрібно обрахувати вектори Неможливо розібрати вираз (невідома помилка): x_{k}

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

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

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

за умов

Неможливо розібрати вираз (невідома помилка): \sum^{m}_{k=0} {\phi_{і}(x_{k})p_{k}}\leqslant 0,i=1,2,...,m, (3.15)

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

 (3.16)

Вектори Неможливо розібрати вираз (невідома помилка): x_{k}^*

і числа  Неможливо розібрати вираз (невідома помилка):   p_{k}^* 

, що складають оптимальний план задачі (3.14)-(3.16), визначають дискретний розв'язувальний розподіл вихідної задачі (3.1)-(3.3).

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

Позначимо

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

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

Потрібно обрахувати вектори Неможливо розібрати вираз (невідома помилка): x_{k}^*

і числа  Неможливо розібрати вираз (невідома помилка):   p_{k}^* 
 які визначають нижню межу функціоналу:

Неможливо розібрати вираз (невідома помилка): \sum^{m}_{k=0} \tilde {\phi_{0}(x_{k})p_{k}}

(3.18)

за умов

Неможливо розібрати вираз (невідома помилка): \sum^{m}_{k=0} \tilde {\phi_{i}(x_{k})p_{k}} \leqslant 0.

(3.19)

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

(3.20)

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

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

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

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

(3.21)

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

  (3.22)

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

(3.23)

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

(3.24)

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

і відповідні їм вектори Неможливо розібрати вираз (невідома помилка):  x_{k}^* 
визначають апріорні дискретні вирішальні розподіли розглянутої задачі . Наведені міркування справедливі і для множини Х, що складеться із скінченного числа точок. Цей же принцип може бити використаний для наближення апріорного вирішального розподілу у випадку, коли множина Х являє собою компакт. Дискретні значення Неможливо розібрати вираз (невідома помилка):  x_{k} 
відповідають вузлам Неможливо розібрати вираз (невідома помилка):  \epsilon 

- мережі(сети) множини Х.

Виконала: Чуйкова Анна Сергіївна

Редагувала: Кухаренко Анастасія