341_3- Сборник задач по математике для втузов. В 4-х ч. Ч.3_ (ред) Ефимов А.В, Поспелов А.С_2002 -576с (987779), страница 61
Текст из файла (страница 61)
определить искомые оптимальное управление процессом й' = (ц(')', ..., н(~)*) и оптимальную фазовую траекторию х' = = (х(е)',..., х(к)*) следующим образом. Так как функция Беллмена В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. Так как множество Хо состоит иа единственной точки х~о~ = О, то найдем только Вз(0) и ий~'(О): В1(0) = щах (Вз(0+ и00) +,71(иф~)). оо>е(о; 4!Ое |о ) Напомним, что символом (а) обозначается полая часть числа а. 5. Дискретное динамическое программирование 431 Для опрелеления максимума в правой части последнего равенства составим таблицу 5.6 значений функции Лт(О,ий~) = Вз(и(О) +,У1(ийй), которые найдем с помощью таблиц 5.1 и 5.4.
Таблица 5.6 Из таблицы 5.6 видно, что Вг(0) = 20, причем и01'(0) = 1 или и(О'(0) = 2, т. е. в данной задаче сушествует два оптимальных управления и две оптимальные траектории. Этап П (безусловная оптимизация). Ш а г 1. а) Пусть и01* = 1. Тогда хн~' = хш~' + ини = 1. б) Пусть он~* = 2. Тогда х01' = хш>' + ин~' = 2. Ш а г 2. а) Для хО~' = 1 имеем и~т~* = и~з~'(1) = 2 (см. таблицу 5.5), х<4' = хй~* + и~т1* = 3. б) Для хО~' = 2 получаем и~т~" (2) = 1 (см. таблицу 5.5), х~т~' = = х~О" + и<т~* = 3. Шаг 3. Так как для обеих оптимальных фазовых траекторий х~т~* = 3, то из (31) находим и~з1' = и~з>'(3) = 1, х~з~" = х~т1' + + и~з~" = 4. Окончательно получаем й* = (1, 2, 1) или й* = (2, 1, 1) и соответственно х' = (О, 1, 3, 4) или х' = (О, 2, 3, 4). Таким образом, существуют два оптимальных варианта распределения средств предприятиям.
Первый вариант: первому предприятию выделяется 1 млн руб., втором — 2 млн руб. и третьему — 1 млн руб. торой вариант; первому — 2, второму — 1 и третьему — 1 млн руб. В обоих случаях суммарный доход препприятий составит Вг(0) = = 20 млн руб. 1> В условиях задачи 17.340 решить задачи 17.350 — 17.352 об оптимальном распределении средств предприятиям со следующими исходными данными: 17.350. Я = 5 млн руб., М = 4. Средства предприятиям распределяются в количествах, кратных 1 млн руб. Функции,уь(и), й = 1, ..., 4, заданы следующей таблицей: Гл.
17. Л!етоды оптиивзации 432 17.351. Я = 5 млн руб., Х = 5. Средства распределяются в количествах, кратных 1 млн руб. Функции Уь(и), й = 1,..., 4, заданы таблицей из условия задачи 17.350, а функция Уа(и)— следующей таблицей: 17.352. Я = 100 тыс. руб., М = 4. Средства каждому предприятию выделяются в количествах, кратных 25 тыс. руб., но не могут превосходить 50 тыс. руб. Функции Уь(и), й = 1, ..., 4, заданы следующей таблицей: В условиях задачи 17.341 решить задачи 17.353-17.357 об оптимальном выделении средств предприятию в течение М лет со следующими исходными данными: 17.353. Я = 500 тыс.
руб., М = 4. Средства, выделяемые в течение каждого года, кратны 100 тыс. руб. Функции,4(и) представлены в таблице. 17.354*. Найти решение задачи 17.353, если начальная сумма Я а) уменьшена на 100 тыс. руб.; б) увеличена на 100 тыс. руб. при следук~щих дополнительных данных о прибыли предприятия при выделении ему в течение й-го года средств в размере 600 тыс. руб.; з 5. Дискретное динамическое программирование 433 17.355. Я = 400 тыс. руб., М = 4. Выделяемые в течение Й-го года средства кратны 20 тыс. руб. и не могут превосходить 200 тыс, руб. грункции Уь(и) заданы таблицей 17.356. Я = 300 тыс. руб., Ж = 3, функции,уа(и), У4 = 1, 2, 3, определяются следующим образом: а) .71(и) =,Уз(и) = Уз(и) = 10 — 10 з (и — 100)~; б) Х1(и) = Яг(и) = 24 — 6 10 4(и — 200)~,,7з(и) = 16 — 4 х х 10-4(ц 200)т 17.357. Я = 150 тыс.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
