Стохастично програмиране
| Категория: Информатика Тип: Курсова Размер: 141.7kb. изтегляне |
Федерална държавна образователна институция за средно професионално образование
"Омски индустриален и икономически колеж"
по дисциплина "Математически методи"
Тема: "Стохастично програмиране"
Коркунов Иля Андреевич
3-та година, BP 1 - 117
Белгородцева Наталия Александровна
1. Концепцията за стохастично програмиране
2. Детерминистично формулиране на задачи за стохастично програмиране
3. Решаване на STP проблеми
Библиография
Стохастичното програмиране е подход, който отчита несигурността в оптимизационните модели.
Докато проблемите с детерминирана оптимизация се формулират с помощта на дадени параметри, реалните приложни проблеми обикновено съдържат някои неизвестни параметри. Когато параметрите са известни само в определени граници, един подход за решаване на такива проблеми се нарича стабилна оптимизация. Този подход е да се намери решение, което е осъществимо за всички такива данни и оптимално в известен смисъл.
Моделите за стохастично програмиране са подобни, но използват знания за вероятностните разпределения за данните или техните оценки. Целта тук е да се намери някакво решение, което е валидно за всички (или почти всички) възможни стойности на данните и максимизира средната стойност на някаква функция от решения и случайни променливи. Като цяло, такива модели се формулират, решават аналитично или числено и техните резултати се анализират, за да предоставят полезна информация на вземащите решения.
Най-широко използвани и добреизучават се двуетапни линейни модели на стохастично програмиране. Тук вземащият решение предприема някакво действие на първия етап, след което възниква случайно събитие, което влияе върху резултата от решението на първия етап. Във втората стъпка може да се вземе коригиращо решение, което компенсира всички нежелани ефекти, произтичащи от решението в първата стъпка.
Оптималното решение на такъв модел е едно решение от първия етап и набор от коригиращи решения (правила за вземане на решения), които определят какво действие трябва да се предприеме във втория етап в отговор на всеки случаен резултат.
При написването на дисертацията използвах следните източници:
Въведението е написано с помощта на сайта: http://ru.wikipedia.org/wiki/ Стохастично програмиране. Взех информацията от този сайт, защото беше представена в тази статия, разкрита и разбираема.
За да разкрием първия въпрос от темата на курсовата работа „Концепцията за стохастично програмиране“, почти цялата информация е взета от книгата „Математически методи и модели за управление“ / Глухов В.В., тук са разгледани основните понятия, взети са дефиниции като: какви задачи се отнасят до проблемите на стохастичното програмиране, същността на стохастичната М-настройка на целевата функция. Информацията е допълнена и от книгата "Математически методи в програмирането" / Агалцов В.П. Книгата на Глухов "Математически методи и модели за управление" представи информацията по много достъпен начин и затова я използвах. Информацията за "Детерминирана постановка на задача на стохастично програмиране" е взета от сайта http://matesha.ru/book/lp8.php, там е описан алгоритъмът на този въпрос, но е много ясен.
ПриКато се има предвид въпросът „Решаване на проблемите на STP“, беше използвана и книгата „Математически методи и модели за управление“ / Глухов В.В. Използвана е и книгата "Изследване на операциите в икономиката":
При разглеждането на последния въпрос „какъв метод може да се използва за намиране на приблизително решение на проблем с нелинейно програмиране, ако целевата функция и функциите в системата от ограничения са разделими“, се използва само „Математически методи и модели за управление“ / Глухов В. В., тъй като само там материалът е описан подробно, а в други източници само той е споменат.
При писането на курсовата работа са използвани и други книги, но там материалът не е описан подробно и (или) неразбираемо.
1. Концепцията за стохастично програмиране
Стохастичното програмиране е раздел от математическото програмиране, набор от методи за решаване на проблеми с вероятностна оптимизация. Това означава, че или параметрите на ограниченията (условията) на проблема, или параметрите на целевата функция, или и двете са случайни променливи (съдържат случайни компоненти).
В проблемите на приложната математика могат да се разграничат детерминистични и стохастични проблеми. В процеса на решаване на последното се е развила вече обширна математическа дисциплина - теорията на вероятностите.
В същото време вероятностните методи се прилагат досега изключително за решаване на задачи от описателен тип.Оптимизационните стохастични проблеми започнаха да се разработват едва през последното десетилетие. Горното се отнася и за стохастичните варианти на задачите за оптимално програмиране.
Въпреки това, стохастичното оптимално програмиране е много важен и обещаващ клон на приложната математика, макар и само защото "на практикаВземането на решения винаги се извършва в условия на известна несигурност. Също така е ясно, че проблемите на стохастичното програмиране се оказват много по-сложни от съответните детерминирани варианти.
В проблем с линейно програмиране:
дадени количества с j и ij ,, bi , dj, Dj. Често на практика стойностите cj , aij bj , могат да бъдат произволни. Така че, ако bi е ресурс, тогава той зависи от редица фактори. По същия начин, cj - цените - ще зависят от търсенето и предлагането, aij - факторите на разходите - от нивото на технологията и технологията. Задачи, в които c j и ij , bi са случайни променливи, се класифицират като проблеми на стохастичното програмиране. Преходът от чисти към смесени стратегии разширява обхвата на дефинирането на проблема. Достижимият максимум на целевата функция в този случай може само да нараства, а достижимият минимум може само да намалява. Изчисляването на оптималната смесена стратегия понякога се нарича определяне на разпределението на решението на стохастичен проблем.
Проблемът на стохастичното програмиране предвижда стохастична формулировка както на целевата функция, така и на ограниченията. При проблеми със стохастично програмиране, съответстващи на ситуации, в които трябва да се вземе решение преди да се наблюдава реализацията на случайни условия и е невъзможно да се коригира решението при получаване на информация за реализираните стойности на случайни параметри, естествено е да се определи оптималният план под формата на детерминиран вектор. Ето как се дефинира клас от стохастични проблеми, за които естествените правила за вземане на решения са правила от нулев ред. Решаването на проблемите на стохастичното програмиране под формата на случаен вектор позволява да се установи връзка между компонентите на оптималния план, реализациите на параметрите на условията на проблема и техните априорни статистически характеристики. Всяко изпълнение на условията на проблемаследователно съответства на изпълнението на решението. Ето защо е препоръчително да се определи решението на проблем със стохастично програмиране под формата на случаен вектор в ситуации, в които може да се вземе решение след наблюдение на изпълнението на условията на проблема. Препоръчително е да се използват разпределения на решенията (смесени стратегии) в стохастични проблеми, съответстващи на повтарящи се ситуации, когато общите ресурси са ограничени и само средният ефект от избраното решение представлява интерес. Естествено е проблемът да се решава в смесени стратегии, които не зависят от прилагането на случайни параметри в повтарящи се ситуации, в които изборът на оптимален план трябва да предшества наблюдението. Разпределението на решенията, което зависи от изпълнението на случайни параметри, е условното разпределение на компонентите на оптималния план - рационална основа за управление в повтарящи се ситуации, в които изборът на решение се прави след наблюдение на изпълнението на параметрите на условията на проблема.
Стохастичната формулировка на целевата функция може да бъде от два вида: M-установка и P-установка.
В M-изявлението случайната променлива се заменя с нейното математическо очакване и проблемът се свежда до оптимизиране на детерминираната целева функция:
където c j е математическото очакване на случайна променлива с j.
В R-изявлението целевата функция ще изглежда така:
при максимизиране на целевата функция:
означава максимизирането на вероятността случайната променлива ∑ cj xj да бъде поне някаква стойност на r;
при минимизиране на целевата функция:
означава максимизирането на вероятността случайната променлива ∑ cj xj да бъде най-много някаква стойност на r.
Най-често срещаните STP изрази във вероятностни ограничения на формата:
където ai j , bi са произволниколичества; ai са дадени нива на вероятност.
По този начин, ограничение (а) означава, че вероятността за удовлетворяване на неравенството
трябва да бъде не по-малко от ai. Подобно значение и други ограничения.
За случая, когато вероятностните ограничения са представени под формата на тип (a), проблемът STP може да бъде написан в M-изявлението:
в случай на максимизиране на целевата функция
в случай на минимизиране на целевата функция
където cj, ai j, bi са случайни променливи.
За други случаи на ограничения (b, c, d) формулировката на задачите за стохастично програмиране е подобна.
Задачи (1.7), (1.8), (1.9) не могат да бъдат решени директно. Един възможен метод за решаването им би бил да ги представим като детерминиран еквивалент.
2. Детерминистична постановка на проблемите на стохастиката
Стохастичното програмиране позволява нов подход за решаване на проблеми, чиято информационна структура (естествена или определена от стохастично разширение) е предварително известна. Процесът на решаване на задача за стохастично програмиране може да бъде разделен на два етапа. Първият, предварителният етап, обикновено отнема много време. На първия етап се изгражда закон за управление - правила за решаване или разпределения на решения, които свързват решението или механизма за генериране на решението с реализираните стойности и дадени статистически характеристики на случайни параметри на условията на проблема. Предварителният етап не изисква познаване на специфични реализации на стойностите и ограниченията на параметрите на целевата функция. Конструирането на решаващи правила или разпределения изисква само информация за структурата на проблема и за някои статистически характеристики на произволни първоначални данни. Следователно процесът на проектиране на решаващи механизми обикновено не е ограничен от липса на време и може да започне с товамоментът на осъзнаване важността на задачата, веднага щом се изгради стохастичният модел и се провери съответствието му с изследваното явление. Инвестицията на време и ресурси за подготовка на правила за вземане на решения или разпределение обикновено е оправдана. Получените по този начин закони за управление позволяват да се решават не само отделни специфични проблеми; те са приложими за различни задачи на дадена информационна структура. Правилата за вземане на решения или разпределенията са формули, таблици, инструкции или произволни механизми с фиксирани или променящи се статистически характеристики в зависимост от прилагането на произволни параметри на условията. На втория етап от анализа на стохастичния модел се използват правила за вземане на решения или разпределения за бързо решаване на проблема. Вторият етап естествено се нарича оперативен етап от анализа на стохастичния модел. Обърнете внимание, че при липса на статистически характеристики на случайни първоначални данни, на предварителния етап е възможно да се замени директният начин за конструиране на механизми за вземане на решения с адаптивен, итеративен метод за решаване на стохастичен проблем, като се използват последователни набори от реализации на случайни параметри на условията на проблема. Стохастичното програмиране определя нов подход към алгоритмизацията на управлението в сложни системи. Математическата поддръжка на сложни екстремални системи за управление е целесъобразно да се съставя не от алгоритми за решаване на екстремални проблеми, а от решаващи правила на съответните стохастични разширения. В същото време формирането на закони за управление - решаващи правила или решаващи разпределения - е свързано не с оперативната работа, а с етапа на проектиране на системата за управление. По този начин стохастичното програмиране и по-специално стохастичното разширение отварят пътя за оперативен анализ на сложни проблеми, алтернатива на които са експертните оценки и волевитерешения.
За да се реши проблемът със стохастичното програмиране в P-изявлението и с вероятностни ограничения, се преминава към детерминиран еквивалент.
За целевата функция детерминираният еквивалент е:
при минимизиране на целевата функция
при максимизиране на целевата функция
където σ 2j е дисперсията на случайната променлива cj. Решението на такива проблеми е трудно, следователно по-долу разглеждаме целевата функция само в М-изявлението. Детерминираният еквивалент на вероятностно ограничение от тип (a)
може да се сведе до:
където ai j , bi са математически очаквания; , σ i j 2 , ө i 2 са дисперсии на случайни променливи aij , bi ; ta \u003d Ф * -1 (ai) е обратната функция на нормалното разпределение с функцията на разпределение:
където ai е дадено ниво на вероятност (Таблица 2.1).
Обикновено решавайте проблеми, когато ai > 0,5, така че стойностите на ta са дадени само за положителни ta ..