Ф.П. Васильев - Численные методы решения экстремальных задач (1125247), страница 120
Текст из файла (страница 120)
На рис. 7А приведен такой пример — здесь Н = 3, шкалы Н„Н„Н„Н, состоят соответственно иа точек (А), (В, С), Ю, Е), (Р); на дугах, соединяющих точки соседних шкал, указаны их длины. Кратчайшим путем, соединяющим шкалы Н, и Н., является путь АСОР. Если в качестве начального приближения ), взять путь АВВР, то улучшить его методом локальных вариаций не удается. Любопытно также ааметить, что если за ), взять путь АВРР, то в зависимости от того, начнем ли просмотр со шкалы Н, или Н„придем к кратчайшему пути АСОР или уже рассмотренному пути АВЕР.
ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ [Гл. т 5[2 Различные модификации метода локальных вариаций, примеры задач, к которым применялся этот метод, см. в (14, 217, 326). 6. Успех в применении описанных в этом параграфе методов приближенного решения задачи (1.1) — (1.4) во многом зависит от умения строить элементарные операции (1) — (4). По существу элементарная операция представляет собой экстремальнуда аадачу той же трудности, что и исходная задача.
Однако малость отреака Ф< ( 1( й+, позволяет здесь сделать ряд упрощающих предположений. Прежде всего, если шаг сетки по времени достаточно мал, то элементарную операцию строят, исходя из условий (1), (2), (4), полагая, что дуги траекторий или нв нарушают ограничений (3), или этим нарушением можно пренебречь.
Далев, вместо минимизации функции (1) при условиях (2), (4) часто ограничиваются построением какого-либо допустимого управления и соответствующей траектории, удовлетворяющих условиям (2), (4), и в качестве длины дуги Мд(х, у) тогда берут значение функции (1) на полученных управлении и траектории. Во многих задачах полезно задаться каким-либо семейством управлений и(т)= и(Ф, с„..., с„), зависящих от параметров с„..., с„(т~ п). Например, это могут быть алгебраические илн тригонометрические многочлены с коэффициентами с„..., с„ или кусочно-постоянные функции со значениями с„..., с„и т. и.
Значения этих параметров затем можно определить из следующей системы и уравнений с т неизвестными (т~ п): дд[ [ дд+д ) х([)с[[= ) 7'(х([), и([, сдд ..., с )) [[[= у — х (9) д; дд и(Ф, св ..., С„)дву(й), Ф<<Ф<Фд+„ используя для этого различные методы [4, 20, 39, 54, 209]. Если т ) и, то параметры со ..., с„отсюда будут определяться, вообще говоря, неоднозначно, и свободные параметры можно использовать для минимизации функции (1). Для упрощения системы (9) дифференциальное уравнение (2) часто заменяют более простыми уравнениями: х(д) =1(х, и(д), 1) или х([) =7'( ~~, и(1), 8) или другими более точными разностными уравнениями; здесь возможно использование линеарнзованной системы: х(г) = [(х, и(1), 8)+ </„(х, и(г), 1), х(1) — х>. Прн решении задачи (1), (2), (4) часто применяется также провлемл синтеза 5 3) 513 принцип максимума в сочетании с различными упрощающими приемами, описанными выше.
Другие способы построения элементарных операций, примеры решенных конкретных задач см. в 1[4, 2171. 3 3. Проблема синтеза для систем е непрерывным временем Продолжим исследование задачи (1.1) — (1.4) с непрерывно меняющимся временем. Проблема оиитооа для задачи (13) — (1.4) заключается в построении функции и = и(х, г), называемой синтезирующей функцией атой задачи и представляющей собой значение оптимального управления при условии, что в момент г система (1.2) находится в точке х, т. е. х(г) = х. Уогение решать проблему синтеза крайне важно в различных прикладных задачах оптимального управления.
В самом деле, если известна синтезирующая функция и(х, г), то техническое осуществление оптимального хода процесса может быть произведено по следующей схеме, называемой схе. мой с обратной свяаью: с измерительного прибора, замеряющего в каждый момент г фаеовое состояние х(г), па ЭВМ или какое-либо другое вычислительное средство подается величина х(с), вычисляется значение управления и(г) = и(х(г), г), после чего найденное аначение и(с) оптимальнога управления передается на исполнительный механизм, непосредственно реализующий требуемое течение управляемого процесса. 1.
Проблема синтеза для задачи (1Х) †(1.4) сводится к решению следующей вадачи: определить управление ио(т) = ио(т, х, г), доставляющее функции т о (1, х, и ( )) = ) 1 (х (т), и (т), т) йт+ Ф (х (Т)) з минимальное значение при условиях й(т) =У(х(т), и(т), т), г(т(Т; х(г) =х, (2) х(т) ов С(т), г ( т < Т, (3) и = и(т) ш у(т), с < т < Т; и( ) — кусочно-непрерывно, (4) где х — произвольная точка множества С(с), а г — произвольный фиксированный момент времени, со ( г ( Т. Заметим, что при г = го задача (1) — (4) превращается в исходную задачу (1.1) — (1.4). Обозначим через ь(х, г) множество всех управлений и(т) (г (т < т), удовлетворяющих условиям (4) и и(т) = и(т+О) = Иш и(о) (г(т< Т), т+о и таких, что соответствующая траектория х(т) = х(г, и) (г (т< Т), системы (2) определена на всем отрезке [д Т'1 и удовлетворяет фазовому ограничению (3).
положим х(г) = (х: хш с(г), ь(х, г) чь Я) (зо( г < т); х(т) = С(Т). Пару (и(т), х(т)) (г(т(Т) назовем допустимой парой задачи (ц— (4), если х(с) = хоп Х(г), и( ) оиЬ(х, г) и х( ) является решением системы (2), соответствующим рассматриваемому управлению и( ). Аналогично, пару (и(т), х(г)) (оо(т < Т) будем называть допустимой парой исходной задачи (1.1) — (1.4), если х(го) = хо оп Х(го), и( ) она(хо со) и вы.
полнены все соотношения (1.2) — (1.4). Допустимую пару (ио(т), хо (т)) (г(т<Т), задачи (1) — (4) будем навывать решением этой задачи, если У(д х, и ( )) = 1п1 У(г, х, и( )); при этом и„(.) назовем оптимальяым Ых,о) управлением, а хо ( ) — оптимальной траекторией задачи (1) — (4). Зная оптимальное управление ио(т) = ио(т, х, Ф) задачи (1) — (4) при всех тех (х, ю), мопс(г) (го( с < т), при которых эта задача имеет ре- 514 ДИНАМИЧБСКОБ ПРОГРАММИРОВАНИБ [ГЛ. 7 шение, нетрудяо получить синтеаирующую функцию задачи ([Л) — (1.4): достаточно положить и(х, С) еи ио(с, х, С).
Однако получить явное аналитическое выРажение Дла оптимального УпРавлениЯ ио (т, х, С) ааДачи (1)— (4) удается лишь в редких случаях. Поэтому желательно иметь другие подходы к решению проблемы синтеза. Вспомним, что при решении проблемы синтеза для дискретных систем важную роль играло уравнение Беллмана (1.13), (1Л4). Оказывается, аналогичное уравнение может быть получено и для задачи (1) — (4). Введем функцию В (х, С) = [п( х (С, х, и ( )), А(х,с) называемую фУнкцией Беллмана для задачи (1Л) — (1.4). Если аадача (1,1) — (1.4) удовлетворяет некоторым ограничениям и функция В(х, с) непрерывно дифференцируема, то можно показать, что функция Беллмана удовлетворяет следующим условиям, называемым уравнением Беллмана задачи (1Л) — (1.4): 1п( [(Вх (х, с), С (х, и, с)) + Вс (х, С) + ~ (х, и, с)] = О, ия п(х,с) хааХ(с), со(с(Т, (бу В(х, Т) = Ф(х), х ев Х(Т) = Р(Т), (6) где В =(В с, ..., В з), В с Вс — частные производные функции В(х, с), а Р(х, С) — множество всех тех и «п Р(С), для которых существует хотя бы одно управление и( ) «в Ь(х, с) со значением и(с) = и([+О) = и.
Приведем авристические соображения, из которых следуют соотношения (5), (6) в следующей форме: [п( (Ва+ (Ра(х, и)Ц вЂ” [Ва(х) -[-Ре(х, и)] = О, х ш Хс„ хыпа(х) С«=0, 1, ..., ЬС вЂ” 1 (7'г Вх(х) = Ф(х), х«ИХл = Сх. (8) Вспомним также обозначения, связывающие задачи (1.1) — (1.4) и (1,5) — (1.8) и принятые в (7), (8): Ре (х и) — (с — с ) 7~(х, и, Сс), Ра (х, и) = х+((а+с са) У (х и Са).
Исключим из этих обозначений и соотношений (7), (8) индекс й, приняв с„с, ьс = сл»,— см си = т, Вл(х) = В(х, с), Вл»с(у) = В(у, с+ьс), Рл(х) Р(х, с), Ха = Х(с). Тогда соотношения (7), (8) могут быть переписаны в следующей безындексной форме: ш( [В (х + ЬС7 (х, и, С), С+ ЬС) — В (х, С) + ЬЦ~(х, и, С)) = О, имР(х,с) х ом Х(с), Со ~( С ~ (Т, В(х, Т) = Ф(х), х«и Х(Т) = Р(Т). Если теперь поделим первое из этих равенств па Ьс ) 0 и совершим формальный предельный переход при Ьс- + О, то придем к соотношениям (5), (6).
Подчеркнем, что приведенные рассуждения никоим обрааом не претендуют на какую-либо строгость и могут служить лишь наводящими соображениями при получении соотношений (5), (6). Аналогичным образом можно было бы «вывести» зти соотношения, опираясь на уравнения (2.6). Заметим, что уравнение (5) является дифференциальным уравнением в частных пооизводных первого порядка, левая часть которого осложнена 515 ПРОБЛЕМА СНПТЕЗА 9 3) взятием нижней грани, и вопросы существования и единственности решения задачи (5), (6), свойства ее решения в настоящее время исследованы слабо [327[.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
