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

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

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

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

Наведемо формальний запис всіх трьох класів умов екстремальних задач. У задачах першого класу з детермінованими параметрами умов потрібно обчислити розподіл Неможливо розібрати вираз (невідома помилка): 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=1,2,...,m, \sum^{m}_{k=0} p_{k}=1.

 (3.16)

Вектори і числа

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