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

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

Математичне програмування – це прикладна математична дисципліна, яка досліджує екстремальні задачі (задачі пошуку максимуму або мінімуму) та розробляє методи їх розв'язання. Задачі такого типу ще називають оптимізаційними. Математичне програмування відіграє дуже важливу роль як в подальшій математичній освіті, та і в майбутній професійній діяльності, оскільки дозволяє вирішувати багато управлінських і організаційних задач оптимальним чином.

Прикладом використання знань з математичного програмування може бути розв’язання таких виробничих задач:
1. Отримання максимального прибутку або випуску максимального об’єму продукції при заданих матеріальних, трудових, енергетичних або часових витратах;
2. Забезпечення планових показників підприємства при мінімальному розмірі фінансових вкладень;
3. Досягнення максимально короткого терміну виготовлення продукції, будівництва об'єкту, товарообігу, виробничого циклу і тому подібного при існуючих або заданих виробничих ресурсах;
4. Вибір параметрів об’єкту або процесу, при яких забезпечується його максимальна корисність.

Поняття - максимум i мiнiмум - об'єднанi єдиним термiном "екстремум". Задачі на відшукання максимуму та мінімуму називають екстремальними задачами.
Точно поставлена екстремальна задача мiстить такi елементи:

* простiр елементiв X, який є нормованим з нормою k·k, множина допустимих елементiв (обмежень) C ⊆ X,

* цiльовий функцiонал f: X→R ̅, який потрiбно мiнiмiзувати або максимiзувати на множинi допустимих елементiв, деR ̅ := R ∪ {±∞}.

 
  Таким чином, потрiбно звести поставленi задачi до вигляду Неможливо розібрати вираз (невідома помилка):  f(x)  \rightarrow extr  
.

Пiсля формалiзацiї екстремальної задачi виникає питання про її розв’язнiсть. Зауважимо, що в силу рiвностi:
Неможливо розібрати вираз (невідома помилка): supf(x) = -inf(-f(x))

бiльшiсть теоретичних результатiв сформулюємо лише для задачi мiнiмiзацiї. При розв’язаннi екстремальної задачi розрiзняють глобальний i локальний екстремум.
Залежно від властивостей функцій у і f математичне програмування розпадається на декілька самостійних дисциплін, що займаються дослідженням і розробкою методів розв’язання окремих класів задач.

---

Методи розв’язування стохастичних задач поділяють на дві групи — прямі та непрямі.

Прямі методи використовують для розв’язування задач стохастичного програмування, коли існують способи побудови функцій f (X ,ω) і gi (X ,ω) ≤ ,0 i = ,1 m на базі інформації щодо параметра ω.

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

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

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

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

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

Розв’язок в чистих стратегіях називатиметься вирішальними правилами, розв’язок в змішаних стратегіях - вирішальними розподілами.

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

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

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

Умовні екстремальні задачі, в яких змішані стратегії мають змістовний сенс можна розділити на три класи.

♦ перший клас: до нього відносять задачі математичного програмування з детермінованими умовами , в яких оптимальний план визначається у вигляді розв’язувального розподілу. Функціонали, що виражають показники якості розв’язку і обмеження таких моделей, замінюються на математичне сподівання.

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

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

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

Таким чином далі можна навести формальний запис трьох класів умов екстремальних задач. Задачі, які належать до першого класу, а саме задачі з детермінованими параметрами умов:

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

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

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

за умови

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

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

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

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