3 часть (1081356), страница 61
Текст из файла (страница 61)
называются начальными и конечными условиями. При этом множества Хо и Хк с с„во многих случаях содержат по одной точке (начадо и конец фазовой траектории). Пусть й = (пО>, ц~г~, ..., н~~~) — управление процессом, удовлетворяющее ограничениям (4) и переводящее его из некоторого начального состояния хйй Е Хо в некоторое конечнос состояние х(а«е Хм в соответствии с уравнениями (1) с учетом ограничений (3). Обозначим множество всех таких управлений буквой СУ.
Многошаговая задача оптимизации формулируется следующим образом: среди всех управлений йб(у выбрать такое (й'=(н«~', ц1гу*, ..., ц~нр)), для которого целевая функция (2) принимает минимальное или максимальное (в зависимости огп смысла задачи) значение. Управление й* и соответствующая ему фазовая траектория х' называются оптимальными. Условие многошаговой задачи оптимизации будем записывать следующим образом: 'З' 5.
Дискретное динамическое программирование 421 х(л) =х(" ')+и(ь), 1=1, ...,Л(; х(о) = т, х(~) = М+ т. Из условия задачи вытекают следующие ограничении на массы х(~) и и("): т < х(ь) < М + т, О < и(") < М, т.е. х(ь) б Хь = [т; ЛХ+ т], /с = 1, ..., Л/ -1, и(") Е Уь = [О; М], й = 1, ..., Ж. В результате работы /с-й ступени ракеты приращение скорости станции составит г'[х(~ '),и(ь)), поэтому ее конечнал скорость будет равна ж р[ (ь-1) (ь)) «=1 Таким образом, рассматриваемую задачу можно сформулировать как многошаговую задачу оптимизации следующего вида: )с Г[х(" '), и(ь)) — ) шах, в=с х(ь-1) + „(ь), /с — 1 /У, ./[х, й) хрО = хро б [т; т + Лу], /с = 1, ..., /с' — 1, [О; М], /с = 1, ..., Л/, (')=М+, > и(~) Е х(о) = Сформулировать задачи 17.340 — 17.349 в виде многошаговых задач оптимизации вида [5)-[9); К многошаговым задачам оптимизации сводятсн многие прикладные задачи.
П ример 1. Сформулировать следующую задачу в виде многошаго- вой задачи оптимизации [5)-[9), С помощью Лс-ступенчатой ракеты с заданной стартовой массой М в космос запускаетсл межпланетная станция массой т. За время работы , каждой ступени ракета получает добавочную скорость Ьо = Р[у, «), где у — масса, разгоняемая этой ступенью, « — масса самой ступени. Найти такое распределение обшей массы М ракеты мслсду се ступенями, при котором конечная скорость станции будет максимальной.
з Обозначим и(ь), Л = 1, ..., Л/, массу й-й ступени, считая от межпла- нетной станции [т. е. на старте работает ступень массой ис'с), а в конце разгона — ступень массой и(')). Массу станции вместе с примыкающими к ней /с ступенвми ракеты обозначим х(ь), /с = О, 1, ..., /(/. Тогда, очевидно, 422 Гл. 17. Методы оптимизации 17.340.
Сумма средств Я распределяется между Ф предприятиями. Выделение й-му предприятию средств в размере и приносит доход,уь(и), й = 1, 2, ..., М. Определить, какое количество средств необходимо выделить каждому предприятию, чтобы суммарный доход всех предприятий был максимальным. 17.341. Сумма средств Я выделяется предприятию в течение )1Г лет. Прибыль, получаемая предприятием в результате выделения ему средств и в течение Й-го года, составляет,Уь(и), Й = 1, ..., Ж. Распределить выделяемые средства по годам таким образом, чтобы суммарная прибыль предприятия за М лет была максимальной.
17.342. Найти М неотрицательных чисел и("), й = 1, ..., Ф, сумма которых равна Я, а произведение максимально. 17.343. Совхоз производит посевной материал. Ежегодно часть семян продастся потребителям, а оставшаяся их часть используется для воспроизводства. Доход от продажи и т семян составляет Р(и) руб. Количество посевного материала, оставленное в совхозе, в следующем году увеличивается в А раз (А ) 1). В начале первого года имеется а т семян. В конце Ф-го года их производство прекращается. Сколько семенного материала следует продавать каждый год, чтобы доход совхоза за Ф лет был максимальным? 17.344.
Рассмотреть задачу 17.343 в предположении, что в конце я7-го года производство семян не прекрашастся, и минимальное планируемое их количество к началу (Ж + 1)-го года составляет 6 т. 17.345. Планируется производство на двух предприятиях в течение Ж лет, Начальные средства, предназначенные для выделения предприятиям, составляют Я руб. Средства в размере и руб., вложенные в производство на 1-м предприятии в начале каждого года, приносят к концу етого года доход,У,(и) руб..
а также сумму У,(и), оставляемую для финансирования дальнейшего производства, 1 = 1, 2. Па истечении каждого года все предназначенные для дальнейшего производства средства перераспрсдсляются между предприятиями. Найти такой способ распределения средств предприятиям, при котором суммарный доход двух предприятий за Ж лет будет максимальным. 17.346. Оптовая база вмещает Р т продукции. Запасы продукции могут пополняться и продаваться в начале каждого из М месяцев, причем пополнение предшествует продаже. Хранение 1 т продукции в течение й-го месяца обходится в ггь руб., а продажа того же ее количества в начале Й-га месяца приносит доход УУь руб. Начальное количество продукции на базе составляет а т. Определить количества продукции., которые в начале каждого месяца следует принимать на хранение и продавать, чтобы суммарная прибыль базы за И месяцев была максимальной.
3 5. Дискретное динамическое программирование 423 17.347. Рассмотреть задачу 17.346 в предположении, что в начале каждого месяца продажа продукции предшествует ее пополнению. Ж 17.348. Р(н) = ,'1 1Рс(и(")) — 1 ппп, А — 1 Ж ,'1 аьи(~1 < 6, а=1 и()>0, и()ЕК, 6=1,...,Ж, где аа > О, 6 = 1, ..., М, 6 > 0 (сепарабельнаяэ) задача целочи- сленного программирования с одним линейным ограничением). М 17.349. Р(н) = ~1 Рй(и(~)) -+ пнп, ь=! М Е аиаи <6;,1=1,...,т, (й) а=1 и(") >О, и(й)ЕК, 1=1,...,М, где и, ь, 6; > О, з = 1, ..., т, )с = 1, ..., Ж (сепарабельная задача целочисленного программирования с гп линейными ограничени- ями).
Для решения многошаговой задачи оптимизации (5)-(9) используется метод динамического программирования, основанный на принципе оптимальности Беллмана: Оптимальная траектория о задаче (5) — (9) обладает тем соойстаом, что любая ее зааершающая часть, начинающаяся с 9-го шага, lс = 1, ..., Ю вЂ” 1, является опгаимольной для остающихся шагов процесса. Опишем метод динамического программирования. Заметим прежде всего, что в формулировке многошаговой задачи оптимизации (5) — (9) ограничения на фазовую траекторию (7) и на конечное состояние (9) можно включить в ограничения на выбор управлений, заменив соотношения (7) и (8) слелуюшим эквивалентным ограничением: н1ь1 б (уа(х1" О) = (и~~~ Е (уа/Г1ь~(х~~ '1, н1а~) Е Хд), (10) к = 1, ..., я1.
п ) Функпня и переменных вида у(хы ..., х„) = Ч ~у,(х,) называется сена=1 рабельной. Если все функции, входящие в условие залачн математического программирования, сепарабельны, ть такую задачу называют сепарабельной. Гл. 17. Методы оптимизации 424 С учетом этого перепишем формулировку задачи (5)-(9) в следующем виде: ,у(х, й) = ~,уь(х(' '), п( 9) — ) ехсг, (11) х~'~ = У~'~(х1ь-О п~"~) Й =1 5У п~'~ Е О,(х~ь-О), Й = 1,..., М, (12) (13) х~ ~ЕХе. (14) Предположим, по в результате начальных Й вЂ” 1 шагов процесс перешел в состояние х(ь )). Рассмотрим задачу оптимизации оставшихся (с' — Й + 1 шагов, аналогичную задаче (11)-(14).
Пусть оптимальное управление й*(Й) = (п(с1", ..., п<ж~') последних У вЂ” Й + 1 шагов и оптимальная траектория этих шагов т'(Й) = (х(ь '), х(ь)", ..., х~'~~"), начатая из состояния х(ь (), найдены. )с Целевая функпия У(ь)(х(Й), й(Й)) = ~ ~л((х(( '), пп1) последних М вЂ” Й+ 1 шагов прн 'х(Й) = х'(Й), й(Й) = й*(Й) принимает оптимальное (т. е. минимальное или максимальное) значение, зависящее от начального состонния х(~ О фазовой траектории этих шагов, т.е.
ехггl( 1(т(Й), й(Й)) = л(9(т*(Й), й'(Й)) = Вь(х(' О). (15) (рункцпя Вь(х(ь ')) из (15) нааываетсн функцией Беллмана последних (с' — Й + 1 шагов. Очевидно, Вн(х~ О) = ехсг .())((х( '1, п( )). (16) .(~~ей.('.(~-~)) Вь(х(ь О) = ехгг (Вьз)[г(')(х1ь '~, п~ь~)[+,уь(х~ь (~, п("))), .(")со,(.('- )) Й = 1, ..., ()( — 1. (17) Соотношенин (16) и (17), позволяюшие последовательно найти функции Беллмана В(с(х((с О), В(с ((х((с э)), ..., В((х(е)), называются урааиекилми Беллмаиа.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
