3 часть (1081356), страница 62
Текст из файла (страница 62)
Находя функции Вь(х(ь О), Й = ()), ("(' — 1, ..., 1, из (16) и (17), мы одновременно определяем и управления п(ь)*(х(ь )), которым отвечают оптимальные значения соответствующих величин я)ч — — .у)ч (х(~ ' )п( ) ) Кроме того, функции Беллмаиа связаны между собой следующими рекур- рентиыми соотношенинми, вытекаюшими нз принципа оптимальности: з 5. Дискретное динамическое программирование 425 и Яя — — Вьь1[Г(ь)(х(ь '), н(ь))]+,ут(х(ь '), н(ь)), Й = р) — 1, Ж вЂ” 2, ..., 1, из правых частей равенств (16) и (17): [ (к-~) (>ч)*( (>ч-1))] ех(г Ян(х(~ '), н(ьк)) = Вж(х(~ ')), (18) „ьюсс, ~мн-о) аль[к(ь — 1) и(ь> (х(ь-1))] сх(г Яь(х(ь '>, н(')) = Вь(х(ь ')), (19) .о) а ем.н- о ~ Вь(х(')*) = ехсг В1(х( )) жь)акр (20) (если множество Хе из (14) состоит из единственной точки х("), то полагаем х(">' = х(о>) Далее, используя найденные условные оптимальные управления, а также уравнения состояний (12), последовательно находим н(')', х(')*, н(а)", х(т)", ..., и(~)*, х(к)* из следующих соотношений: и(1)' = н(')*(х(е)') х(1>* = у(')(х(о)* ц(')") цбй* = н(э)*(х(1) ) х(т) — У(э)(х(1) н(з) ) (21) н(>ч>* = н(к)*(х(к ')*) х(>ч)' = >'(>ч)(х(н 1)' н(к)*) Й = Ж вЂ” 1,..., 1.
Управления н(ь)*(х(" ')), Й = 1, ..., >У, называются условными оптимальными управлениями, а процесс их нахождения — условной оптимизацией. Отметим, что управления н(ь)*(х(ь ')), найденные в соответствии с (19), удовлетворяют принципу оптимальности, т.е. в зависимости от начального состояния х(ь ') управление н(ь>*(х( ')), Й = 1, ..., ))( — 1, учитывает оптимизацию не только Й-го шага, но и следующих за ним М вЂ” Й шагов. Итак, в результате условной оптимизации находятся функции Беллмана Вь(х(ь ')) и условные оптимальные управления ц(ь)'(х(ь ')), Й=1,...,Ж. После этого можно осуществить безусловную оптимизацию в задаче (11) — (14), т.с.
определить искомые оптимальное управление процессом й' = (ц(')', ..., н(~)*) и оптимальную фазовую траекторию х' = = (х(е)',..., х(к)*) следующим образом. Так как функция Беллмена В1(х(а)) для каждого начального состояния х( ) е Хе равна оптимальному значению целевой функции >у шагов, т. е. всего процесса, начатого из состояния х(е), то оптимальное начальное условие х(о)' Е Хе находим из соотношения Гл. 17. Методы оптимизации 426 Алгоритм метода динамического программирования. Э т а п 1 (условная оптимизация). Шаг 1.
Находим условное оптимальное управление н~~~'(х~м О) и функцию Беллмана Вп(х~н О) в соответствии с (16), (18). Шаг 2. Используярезультатпервогошага,находимн(м О*(х~м з~) и Вм ~(х~н т~) с помощью равенств (17) и (19) при А = М вЂ” 1. Ш а г Х. С помощью результатов (М вЂ” 1)-го шага определяем ио")' и х1о>* по формулам (21). Окончательно имеем й' = (иО~", ..., ибч~'), х* = (х~о~',:, х~~~" ).
Пример 2. Методом динамического программирования решить задачу из примера 1 со следующими исходными данными: Ж = 3, М = 63, т = 1, Р(у, х) = г/у. О Лля указанных исходных данных многошаговая задача оптимизации примера 1 формулируется следующим образом: з 2(х, й) = ~~~ —, -+ шах, ь=~ 00 ~ь-О + „<ы х<ь~ Е [1; 64], и00 Е [О; 63], 00 )с = 1, 2, 3, 1=1,2, й = 1, 2, 3, х1н~ = 64. (22) Определим множества Уь(т~~ О) из (10): Оь(х~ь О) = (и00 Е [О; 63][х~ь О + и~ ~ Е [1; 64]) = [О; 64 — х~ь 1=1,2,3,таккакх~~ О >1.
Проведем вычисления по методу динамического программирования в соответствии с описанным выше алгоритмом. Шаг А1. Используя результаты (Ж вЂ” 1)-го шага, опрелеляем и~О" (х~о~) и В~(х~о~) в соответствии с (17) и (19) при й = 1. Э т а п Н (безусловная оптимизация). Ш а г О. Находим оптимальное начальное состояние к~о~* в соответствии с (20).
Шаг 1. Определяем оптимальные управление н(О' и конечное состояние хО~' первого шага процесса по формулам (21). Шаг 2. Используя результаты предыдущего шага, находим и~в~* и хдт~" в соответствии с (21). з 5. Дискретное динамическое программирование 427 (2>'(х(2) ) = 64 — х('). (23) Тогда В (х(2)) — т (х(2) н(з)*(х(2))) 64 — х(2> х(2) (24) Шаг 2. В соответствии с (17) прил = 2 с учетом (24) и (22) получаем г'64 — х(') — и('> и('> ') В2(х('>) = гпах ],, + —,] .
ыие(0;64-мн) х( > + н( Найдем точку максимума и(2>'(х('>) функции 64 — х(2) — и(2> и(2> г (х( ) (2)) + х(') + и(2) х(') на отрезке [О; 64 — х('>] в зависимости от х('>. Длл определения стационарных точек функции Я2(х('>, и(2>) решим уравнение Ог, (и('>)2+ 2и(2>х(') — (х('>) — 64х('> ( > (, откуда получим и(2)(х(~))о = 8Ъ'х(1> — х(1> (25) (очевидно, и(2)(х('>)о Е [О; 64 — х('>], так как х('> < 64). Сравним значения функции Я2(х(г), и(2>) в точке и(2>(х('>)о иа (25) и на концах отрезка [О; 64 — х(1>]; а) Я~(х('), 0) = — 1; б) Я~(х('), 64 — х('>) = 0; 64 х(1) в) Я (х('>, и(2)(х(')) ) = 2 — — 1 8 Отсюда следует, что Я (х('>, 64 — х('>) < У~(х('), 0) < Я2(х('), и(2>(х('>)о) Этап? (условная оптимиаация). ц(з) 1Паг 1.
Из (16) находим Вз(т('>) = п1ах —. Так как мне(о' аз хиц> х( Яз(х(2), и(з>) = и(2)/х(2) при всех х(2> Е [1; 64] является возрастающей функцией аргумента и( >, то ее максимум достигаетсн при максимально возмоа;ном значении и(з>, т.е. Гл. 17. Методы оптимизации 428 при х(') б (1; 64] (проверьте!). Поэтому (')"(х(')) = и(э)(х('))о — — 8/х~'~ — х(') (26) 8 В,(х(')) = гэ( ('),и(')"(х('))] = 2 — 1 . (27) ,l~(1) Ш а г 3. Учитывая равенства (27) и (22), из (17) при й = 1 получаем ( 8 и(') 1 В) (х(0)) = шах 2 + о — *(') .( ° )') Как и на втором шаге, исследуя функцию на максимум по и(') на отрезке (О; 64 — хбб] (проведите исследование самостоятельно!), получим к(1) (х(0)) 4( (0))э/э (О) (28) В((х(о)) 12(х(0))-)/з 3 (29) Э т а п И (безусловная оптимизация).
Шаг О. Так как множество Хо состоит из единственной точки х(0) = 1, то полагаем х(0)* (30) Ш а г 1. Из формул (21) с учетом (28), (30) и (22) находим и(1)* = и(')'(1) = 3, х(1)' = х(0)* + и(')* = 4. Шаг 2. Аналогичным образом из формул (21), (26) и (22) получаем и(э)' = и("(4) = 12, х")" = х0)'+ и(э)* = 16. Шаг 3. Используя равенства (21), (23) и (22), находим и(э)" = и(э)*(16) = 48, х(э)' = х(~)'+ и(~)' = 64. Окончательно получаем П" = (3, 12, 48), х* = (1, 4, 16, 64).
Таким образом, массы верхней, средней и нижней ступеней ракеты должны равняться соответственно 3, 12 и 48 единицам. При этом межпланетная станция достигнет максимально возможной в данных условиях скорости, равной В1 (х(0)*) = 9 единицам (см. формулы (29), (30)).
С з 5. Дискретное динамическое программирование 429 Задача, рассмотренная в примерс 2, свелась к нелрерьионой модели многошагового процесса оптимизации. В втой модели управления и1а1, векторы состояний х~ь1 и другие величины могут непрерывно изменять си на соответствующих множествах. Длл многих экономических и производственных задач характерной лвллетсл дискретнал модель, прелполагаюшал, гго величины, описывающие процесс, могут принимать только дискретный ряд значений. Функциональные зависимости в таких задачах задаются, как правило, в виде таблиц, а нс аналитичсски.
Однако обшал схема их решения методом динамического программирования остается без изменений. П р имер 3. Общая сумма в 4 млн руб. распределлетсл мел ду тремя предприятиями в количествах, кратных 1 млн руб. В результате выделения средств Й-му предприятию в размере и оно дает доход да(и), к = 1, 2, 3, величина которого может быть найдена из таблицы 5.1; Таблица 5.1 Распределить средства между предприятиями так, чтобы их суммарный доход был максимальным. з Обозначив средства, выделенные (с-му прелприлтию (1с = 1, 2, 3), символом и1ь~, а сумму средств, вьщеленных прелприлтилла с номерами от 1 ло Й, символом х1а1, сформулируем рассматриваемую задачу как многошаговую задачу оптимизации (11)-(14): з д(х, й) = ~ дв(и~ 1) -+ шах, ь — — ! х1ь1 = х1ь '1+ и1а>, й = 1, 2, 3, и~ь1 Е(0;4 — х<ь '1)С1К 1=1,2,3, х1о1 = О, х1з~ = 4. Длл решенил атой задачи применим метод динамического программировании.
Э т а п 1 (условная оптимизация). Шаг 1. Найдем Вз(хйй) = шах дз(и1 ~). Так как функ- Ыме(о; 4 — асв)гъх цил яз(х<т1, и1а1) = дз(и<а>) является возрастаюшей функцией аргумента и~з1 (см, таблицу 5.1), то ес максимум достигается при манси- Гл. 17. Методы оптимизации 430 мальном допустимом значении и~з>, т.с. иРМ( 00) [4 х(з~) 1о) (31) Отсюда Вз(х~з~) = Уз(х~з~, и(зы(х~з~)) = уз((4 — х~4)). Значения Вз(хрй), найденные с помощью таблицы 5.1, представлены в таблице 5.2. Таблица 5.2 Шаг 2. Вычислим Вз(х01) = глах (Вз(х01+ ибй) + уз(ибй)).
ыи е(о; ч-со ййе Для нахождения максимума функции зз(х~'~, ибй) = Вз(хй~ + сзйй) + + уз(и~з>) составляем таблицу 5.3 значений атой функции, используя данные таблиц 5.1 и 5.2. Таблнпа 5.3 В таблице 5.3 рамками обведены максимальные по и<з~ значения функции Яз(хы~, и~з~), соответствующие различным значениям хр~. Используя таблицу 5.3, находим функции Вз(х01) и и~в~(х00), представив их значения в таблицах 5.4 и 5.3. Таблкпа 5,4 Таблица 5.5 Шаг 3.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
