КАТЕГОРИЯ:


Астрономия- (809) Биология- (7483) Биотехнологии- (1457) Военное дело- (14632) Высокие технологии- (1363) География- (913) Геология- (1438) Государство- (451) Демография- (1065) Дом- (47672) Журналистика и СМИ- (912) Изобретательство- (14524) Иностранные языки- (4268) Информатика- (17799) Искусство- (1338) История- (13644) Компьютеры- (11121) Косметика- (55) Кулинария- (373) Культура- (8427) Лингвистика- (374) Литература- (1642) Маркетинг- (23702) Математика- (16968) Машиностроение- (1700) Медицина- (12668) Менеджмент- (24684) Механика- (15423) Науковедение- (506) Образование- (11852) Охрана труда- (3308) Педагогика- (5571) Полиграфия- (1312) Политика- (7869) Право- (5454) Приборостроение- (1369) Программирование- (2801) Производство- (97182) Промышленность- (8706) Психология- (18388) Религия- (3217) Связь- (10668) Сельское хозяйство- (299) Социология- (6455) Спорт- (42831) Строительство- (4793) Торговля- (5050) Транспорт- (2929) Туризм- (1568) Физика- (3942) Философия- (17015) Финансы- (26596) Химия- (22929) Экология- (12095) Экономика- (9961) Электроника- (8441) Электротехника- (4623) Энергетика- (12629) Юриспруденция- (1492) Ядерная техника- (1748) Arhitektura- (3434) Astronomiya- (809) Biologiya- (7483) Biotehnologii- (1457) Военни бизнесмен (14632) Висока technologies- (1363) Geografiya- (913) Geologiya- (1438) на държавата (451) Demografiya- ( 1065) Къща- (47672) журналистика и смирен (912) Izobretatelstvo- (14524) външен >(4268) Informatika- (17799) Iskusstvo- (1338) историята е (13644) Компютри- (11,121) Kosmetika- (55) Kulinariya- (373) културата е (8427) Lingvistika- (374) Literatura- (1642) маркетинг-(23702) математиците на (16968) Механична инженерно (1700) медицина-(12668) Management- (24684) Mehanika- (15423) Naukovedenie- (506) образователна (11852) truda- сигурност (3308) Pedagogika- (5571) Poligrafiya- (1312) Politika- (7869) Лево- (5454) Priborostroenie- (1369) Programmirovanie- (2801) производствено (97 182 ) индустрия- (8706) Psihologiya- (18388) Religiya- (3217) Svyaz (10668) Agriculture- (299) Sotsiologiya- (6455) на (42831) спортист строително (4793) Torgovlya- (5050) транспорт ( 2929) Turizm- (1568) физик (3942) Filosofiya- (17015) Finansy- (26596) химия (22929) Ekologiya- (12095) Ekonomika- (9961) Electronics- (8441) Elektrotehnika- (4623) Мощност инженерно ( 12629) Yurisprudentsiya- (1492) ядрена technics- (1748)

Лекция 26 Dynamic Програмиране

Един от методите за решаване на екстремални проблеми, свързани с оптимизиране на процеса на контрол, включително в областта на транспорта е динамично програмиране.

Динамично програмиране е различна с това, че не разполага с уникален математика т еска език в хода на неговото използване е необходимо да се използва методологията на изчисленията на някои последователни етапа, и след достигане на следващия етап от границата отново да се поставят цели, за да се постигне нов полезност в нов етап.

В общи схеми на чакащи и решават проблеми на базата на типичните модели на начин за решаване на проблеми, той стои.

С помощта на динамично програмиране за решаване на проблемите, свързани с процесите, които могат да бъдат разделени на няколко етапа (стъпки). Оптимизиране на контрола на всяка стъпка не е отделно осигурява по-оптимизация на процесите като цяло.

Методът на прилагане алгоритъм е изградена въз основа на разделението на общи задачи в отделните стъпки.

Ако броят на етапи и възможните решения на всеки етап (офиси) е ограничен, а след това на оптимално решение като цяло (оптималната стратегия), можете да намерите изчерпателен търсене на всички възможни варианти.

Въпреки това, в много случаи, този път е неприемлив поради много големия брой варианти.

Динамично програмиране позволява решения без да прави компромис строгост, намаляване на броя на вариантите, които се разглеждат.

Идеята е, че определянето на екстремните стойности на функцията на няколко променливи се заменя с множествена намери екстремните стойности на функция на едно или малък брой променливи.

За този процес изчисление се разделя на фази. Изберете решение на проблема, който ви позволява да се оптимизира този етап.

Въпреки това, такова решение трябва да се вземе предвид не само условията на този етап, но цялата нататъшния ход на процеса, което е необходимо да се предвидят всички решения на проблема в следващите етапи.

Тъй като процесът е към края на последния етап, оптималното решение не следва да се вземе предвид последващото ход. Ако го намерите за всички ситуации, които могат да възникнат в началото на второто, то е възможно да се получи и на конкурентните решения, от които да изберете най-доброто.

След предварителна селекция на всички необходими инструменти математическа формализация осигурява положителен ефект върху всички процедури изчислителни.

Принципът на оптималност за първи път се формулира и доказа Белман: заявява, че оптималната стратегия, като се започне от всяка фаза, не зависи от предишната стратегия, но само за състоянието на системата на този етап, и стратегия за проследяване, т.е. решенията за следващите фази ...

За да се изследва техниките, които представят примери за решаване на проблеми.



Да разгледаме пример на метод геометрична интерпретация (ris.18.1) (източник [3]) Значението е както следва.

Фиг. 18.1. Геометрична интерпретация на проблема

Вертикалните линии съответстват на часовете, в които считат проблема в процес на проучване.

В началния момент T 0 = 0, процес на (система) се намира в един от възможните първоначални състояния, множеството от които отговаря на набор от точки и .Nachalnoe условие A могат да се задават или площ на възможни състояния, или конкретна стойност, в този случай, четири A 1 A 2 A 3 и а 4. Да приемем също за простота, че всеки път, когато системата е само една от четирите възможни състояния, показани в съответните точки вертикали.

Окончателното състояние на системата - един от четирите точки B 1 B 2 B 3 и B 4

Системата се прехвърля от първоначалното състояние към друго с помощта на прехода, който все още е nazyvayutupravleniem система на всеки един от възможните състояния това etape.Dlya, има своя собствена функция преход (или много от тях), което поставя системата в редица държави в следващия път.

Тази функция - количествено характеристика на прехода към следващото състояние в зависимост от предишното - изразява печалба или разходи. Тъй като стойността на прехода зависи от предишната функция X (I) и следващите X (I + 1) състояния на системата, може да бъдат записани общо като:

Всеки допустим стратегия се изразява с прекъсната линия, свързваща вертикална Т = 0 с вертикалната T N = T

Тя се състои от набор от контроли на всеки етап, т.е., че е възможно да се сравни броят ..:

Оптималната стратегия съответства на прекъснатата линия с най-ниската стойност F.

Следователно, първоначалното проблема могат да бъдат формулирани както следва: е необходимо на всички допустими многоъгълна свързване вертикална T 0 = 0 вертикално в т п = Т, за да изберете този, който съответства на най-малката стойност на Е.

Решаване на проблема в този ред.

За всички възможни състояния на системата в началото на последната фаза на х (п - 1) определяне на оптималния контрол - изберете функцията за преход в една от

крайните състояния с минимална стойност. Преходите, съответстващи на минималната стойност на Q N 1 за всяко състояние (N - 1), са показани на Фиг. 18.1 смела линия. По този начин, без значение къде системата не е била в началото на последния етап, винаги можем да предложим оптималната стратегия за неговото прехвърляне към крайното състояние, може да получи брой квази-оптимални решения. Състоянието на оптималност на всеки такива решения - състояние на системата в началото на разглеждания период.

Сега, за всяко състояние на системата в началото на предпоследния етап X (N-2) може да се определи условно оптимална стратегия за трансфер на един от крайните членки вече общите функции минимален преход в последните два етапа: мин

Q стойности на N -1 вече са известни от предишни изчисления. След това, по същия начин да се определи условно оптимална стратегия за последните три етапи на състояние минути (Q N -2 + Q N -1 ), където Q N -1 вече е известно. Изчисленията продължават до целия процес все още не е в се извършва в обратната посока.

Всеки от получените полилинии (смела линия) съответства на стратегията на квази-оптимално за целия процес. От снимачната площадка на първоначални състояния на системата отговаря на набор от точки на вертикалната линия, а след това всеки условно оптимална стратегия съответства на първоначалното си състояние на системата (точката, от която става въпрос). Така, условно оптималната стратегия е оптимално, при условие, че първоначалното състояние се намира в съответната точка. Всеки условно оптимална стратегия прогнозна стойност на функцията F:

На него можете да изберете на първоначалното състояние на системата, и в зависимост от това най-накрая да се определи оптималната стратегия, т. Е., процесът вече е преминал от началото до края, определя на всеки етап от оптималните решения.

Оптималност Принцип на Белман в тази интерпретация на проблемите и динамични програмни средства включват оптимален път от всяка точка, отразяващ състоянието на системата по всяко време, не зависи от траекторията, водеща до пункта. Следователно, за да определят оптималните решения в общото винаги трябва да има, за да се намери оптималното продължаване на процеса по отношение на състоянието, постигнато с решение на предишния етап.

Математическият формулирането на проблема е както следва.

Като пример за динамични техники за програмиране може да доведе задачата да оптимизира начина на провеждане на влака в един от сайтовете (фиг. 18.2.).

Фиг. 18.2 Определяне на най-изгодна начина на провеждане на влак на сайта

<== Предишна лекция | На следващата лекция ==>
| Лекция 26 Dynamic Програмиране

; Дата: 05.01.2014; ; Прегледи: 225; Нарушаването на авторските права? ;


Ние ценим Вашето мнение! Беше ли полезна публикуван материал? Да | не



ТЪРСЕНЕ:


Вижте също:



ailback.ru - Edu Doc (2013 - 2017) на година. Тя не е автор на материали, и дава на студентите с безплатно образование и използва! Най-новото допълнение , Al IP: 11.45.9.26
Page генерирана за: 0.049 сек.