Ф.П. Васильев - Численные методы решения экстремальных задач (1125247), страница 121
Текст из файла (страница 121)
Задача (5), (6) здесь нас будет интересовать лишь с точки зрения решения проблемы синтеза. Под решением задачи (5), (6) мы будем понимать функцию В(х, с), которая определена и непрерывна при всех (х, с), хщХ(с) (се <с<Т) обладает кусочно-непрерывными частными производными В, Ва и удовлетворяет уравнению (5) всюду, где существуют эти производные, удовлетворяет условию (6) и, кроме того, для любой допустимой пары (и( ), х( )) задачи (1) — (4) при всех хан х(с) (с,<с< т) функция В(х('с), т) переменной т имеет кусочно-непрерывную производную (или В(х(т), т) абсолютно непрерывна) на отрезке [с, Т[. Теорема 1. Пусть В(х, С) — решение задачи (5), (6) и, кроме того, пусть низенян еранв е левой части (5) доетиеаетея на кусочно ненрермвной УаУнкасии и(х, С) снР(х, С), ха Х(С) (Сз < С < Т).
Тогда и(х, С) — синтезирующая Ссункиил задачи (1.1) — (1.4). Доказательство. Возьмем проиавольвые с (се< с < Т) и хеи щ х(с). Пусть хе (т) (с < т < Т) является решением задачйКоши х(т) = 1(х(т), и(х(с), с), т), с<т < т; х(с) = х, и пусть хе ('с) см Х (т) прк всех 'с ея [С, Т[. ПОлОжим и (т) = и (х„(т) т) (С< с<Т). Ясно, что и„( ) аий(х, С) и (ич ( ), хе( )) — допустимая пара задачи (1) — (4). Для доказательства теоремы достаточно показать, что па- ра (ие(.), хз (.)) является решением аадачи (1) — (4), Сначала покажем, что для любой допустимой пары (и( ), х( )) аада- чи (1) — (4) справедлива формула Т л (с, х, и ( )) = ~ В (х(ъ), и(т), т) дт+ В (х, с), (9) С где В(х, и, с) = [Ве(х, с), [(х, и, с)) + Ва(х, с) + сг(х, и, с).
(10] В самом деле, по условию функция В(х(т), т) переменной т непрерывна и имеет кусочно-непрерывную производную. Тогда в силу уравнения (2] имеем йВ (х (т), т) В (х (т), и(т), с) — Се (х (т), и (с), с) всюду на [с, Т1 за исключением, быть может, конечного числа точек. Интегрируя это тождество по с на [С, Т1 с учетом условия (6) получим г т 6)(х (Т)) — В(х, С) = ) В(х(т), и(т), т) йт — ) С~ (х(т), и(т), т) аста С С что равносильно (9). Заметим, что формула (9) является аналогом формулы (1.21). Уравнение (5) с помощью функции (10) можно переписать в виде 1п1 В (х, и, т) = О.
Отсюда и из определения функции имеем аае В(х,т) В(х, и(х,т), т) =О= 1п1 В(х, и, т)~В(х, и, т) (11) иеВ(х,т) для всех исиР(х, т), х(ИХ(т) (с<т<Т). Если (и( ), х( )) — допустимая пара задачи (1) — (4), то х(т) аи Х(т), и(т) = и(т+ 0) = и аи Р(х(т), т) (с < т < Т). Поэтому из (11) получаем В(х (с),и(х (т)),т)=Я(х (ъ),и (с),ъ) =О~В(х(т),и(с),т), (12) ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ 516 (гл. т г < т < т, для любой допустимой пары вадачи (1) — (4). Отсюда и из формулы (9) с учетом условия х«(е) = х (е) = х имеем т у (г, х, и ( )) — у (ц х, и«( )) = ) В (х(т), и(г), т)дт~ О (13) г для всех допустимых пар (и( ° ), х( )) вадачи (1) — (4). Из (9), (12), (13) следует, что з (ц х, и ( )) = 1п1 з (е, х, и ( )) = В (х, 1).
Мх,ь) Тем самым показано, что функция В(х, е), определяемая соотношениями (5), (6), в самом деле является функцией Беллмана задачи (1Л) — (1.4), и функция и(х, е), на которой достигается нижняя грань в левой части (5), является синтезирующей для атой задачи. С помощью функций В(х, е), и(х, е) нетрудно получить решение и для исходной задачи (1Л) — (1.4). А именно, верна Теорема 2.
Пусть В(х, Е) — решение задачи (5), (6) и пусть нижняя грань в левой части (5) достигается на кусочно-непрерывной фуккзии и(х, Е). Кроме того, пусть точка хе еи Х(Е ) определена из условия о В(х,', 1,) = ш1 В(х, е,), (14) хых(е ) а пара (и«( ), х«( )), где х„(.) — решение задачи Коши х (т) = г (х (т), и (х (т), т),т) С < т < Т; х (е ) = х , и и«(т) =и(х«(т), т), яеляетея допустимой парой задачи (1.1) — (1.4). Тогда нара (и«( ), х«( )) являетея решением задачи (1Л) — (1.4), т.
е. д (ев' хо' и«(')) (п( 1п( л (ге' "' и( )) хых(го) и( 1ыа(х,го) Д о к а з а т е л ь с т в о. Воаьмем произвольную допустимую пару (и(т), х(т)) (ео < т < т), х(ео) = хо гн х(ео) задачи (1л) — (1.4). из Форму- лы (9) и неравенств (12) при г = ео с учетом условия (14) имеем у(ео хз и()) — у(ео *, и.())= т = ) В(х(т), и(т), т) йт+В(х, 1 ) — ш1 В(х, е )~ О, х Х(г) го что и требовалось доказать. 2.
Таким образом, согласно теореме 1 для решения рассматриваемой проблемы синтеза достаточно найти решение задачи (5), (6). Возникает вопрос, как же решить задачу (5), (6)? Прежде всего заметим, что удоб- ное для работы конструктивное описание множеств Х(е), П(х, с), входящих в формулировку задачи (5), (6), часто отсутствует, и поэтому на практике вместо задачи (5), (6) обычно пользуются следующей более конструктив- ной задачей: (н( (( Вх (х, Е), Г' (х, и, Ю)) + ВЕ (х, Е) + Ге (х, и, Ю)] = О, им у(г) х гн С (Е), Ео < Е < Т, В(х, Т) = Ф(х), хем С(Т), (15) 517 ЛРОВлнмА сцнтБЗА 9 3] для нелинейного уравнения с частными производными первого порядка. Для численного решения задачи Коши можно воспользоваться известным арсеналом методов — равностными методами, методом характеристик, методом прямых, методом коллокации и т.
п. (4, 13, 20, 39, 54). Иногда удается найти решение В(х, 1) задачи (15) в виде многочлени по переменным х', ..., х" с неопределенными коэффициентами, вависящими от времени: тг та тл В (х, 1) = Х Х ... Х тр (1) (хг)11 ...(хл)1л. О1 =О го=о 1 Если подставим ато выражение для В(х, 1) в (15), то для определения коэффициентов ф1; (1) получим дифференциальное уравнение следующего вида глг юл В (* )= Х" Х 1уг,.; (1)(')'" (з")"= 1 =о г„=о 1 — !п( )г ~ф о(г), ..., ф,„(1); х ....
х", и, с), (16) *ш Р(1), 1, <1<Т, с начальным условием 1" л Х " ч', фг „,,„(Т) (*') ' ". (*")1" = ф (*), ° а (Т). 1-о 1 =е 1 (17)- Если Ф(х), 1п1 г", в свою очередь, являются многочленами относительно ' ЩН х', ..., х", то, приравняв коэффициенты при одинаковых степенях в (16), (17), получим задачу Коши для системы обыкновенных дифференциальных уравнений относительно фг ~ (1), записанной в нормальной форме Коши. л Далее, адесь можно использовать различные численные методы решении задачи Коши, такие, как методы Эйлера, Адамса, Рунге — Кутта и т. д. (4, 13, 39, 54, 258, 295).
получаю|цойея иа (5), (6) ааменой Р(х, Г), Х(1) на У(1), С(1) соответст- венно. Конечно, здесь надо помнить, что задача (15) может и не иметь ре- шения, в то время как задача (5), (6) может оказаться разрешимой. Наиболее удобными и эффективными при решении задачи (5), (6) илк задачи (15), по-видимому, являются методы, изложенные выше в 9 1, 2,— ренуррентные соотношения (1ЛЗ], (1И4) и (2.6) по существу пред- ставляют собой некоторую дискретную аппроксимацию задач (5), (6) и (15), а функции Вь(х), Сь(х) являются приближенным значением для В(х, гь). Существуют и другие методы решения таких задач. Во многих прикладных задачах часто удается получить явное выражение и = и(*, д В ) для точки и, в которой достигается нижняя грань 1п( ~(Вх, 7(х, и, 1))+7~(х, и, 1)1 иаЩН при фиксированных значениях параметров (х, д В„).
Подставив такое и = и(х, д Вх) в (15), приходим к следующей задаче Коши: Вг+ [<Вх 1(х, и, г)) + У (х, и, с)1)и=и(хдвх) = 0 хшР(г), ги(г<Т, В(х, Т) = Ф(х), х ш 6(Т), ДИНАМИЧБСНОБ ПРОГРАММИРОВАНИИ 618 1ГЛ. т Если же Ф(х) нли 1п1 Е не являются миогочленами относительно у(с) х', ..., х", то условия (16), (17) не могут быть, вообще говоря, удовлетворены во всей области С(с) (с, < с < Т) ни при каком выборе су = (юс+ +1) ... (ю„+1) коэффициентов сгс с (с). В этом случае в [188) пред- лагаетсЯ задать в области С(С) ср кРивых $с(с), ..., $х(с) и РекомендУетсЯ определять фс с (С) из условия удовлетворения равенств (16), (17) не с"' и всюду в С(с), а лишь на этих кривых.
Этот подход перекликается с известными методами коллокаций и интегральных соотношений и приводит к задаче Коши для системы обыкновенных дифференциальных уравнений, не разрешенных относительно производной с)с с (с) (отметим, что эти прои аэводные в уравнение будут входить линейно). Кривые $с(с), ..., зи(с) обычно выбирают так, чтобы они имели достаточно простое аналитическое выражение (например, семейство прямых, параллельных осям координат, семейство парабол и т. п.) и задавали достаточно густую сетку в области С(с) (с < с < Т).
Для иллюстрации вышесказанного приведем пример. Пример 1. Пусть требуется минимизировать функцию т У (и) = ) иэ (С) БС + Лхэ (Т), Л = сопзС > 0 о ари условиях У = и(с), х(0) = х„и = и(с) — кусочно-непрерывная функция; числа Т, хс заданы. Здесь С(с) =з Е', У(с) ан Е' (О < с < Т). Задача (15) в рассматриваемом случае имеет вид с'п( (В (х, с) и+В (х, с)+из|=0, хшЕс, 0(с(Т, (18) зан (19) В(х, Т) = Лхс, хсиЕ'. Нижняя грань в (18) достигается при и = — В с'2, поэтому уравнение (18) аерепишется так: В,(х, С) — В.'(х, С)(4=0, хснЕ', 0<С<Т. (20) Функцию В(х, Ц будем искать в виде многочлена В(х, с) — ср (с) + т (с)х+ т (с)х переменной х. Подставим это выражение в (19), (20); получим с)е+ 91х+ с)сх — (с)с + 2сусх)с/4 = О, х ш Е', 0 <«С «< Т, фе (Т) + 91 (Т) х + рс(Ту У = Лх', х сн Е'.
Приравнивая коэффициенты при одинаковых степенях х, придем к следую. сцей задаче Коши: сре — ср,'/4 = О, ср, — ср,ср, = О, ср, — р,' = О, О Н, С < Т, ф,(Т) =О, 9,(Т) =О, ф,(Т) = Л. Отсюда находим Л 1)о (с) — фс (с) О с) С) = 1 л(с т) ° Таким образом, функция Веллмана адесь имеет вид Лхз В(х, с) = -1 Л'(с Т)' йз) ПРОВЛЕМА СИНТЕЗА 519 синтезирующей является функция и(х, С) = — "= *, хсвВ~, 0(С(Т. 2 1 — х(с-т) ' 3. Предположим, что с помощью того или иного метода нам удалось получить некоторое приближенное решение В(х, с) задачи (5), (6) илв (15).
Если это решение получено разностным методом (например, матодами 4 1, 2) на какой-то дискретной сетке точек, то доопределим ее (например, интерполяцией илн с помощью сплайнов) во всех точках области С(с) (се < с < Т) до некоторой непрерывной кусочно-гладкой функции В(х, с). Тогда функцию и = и(х, с), на которой реализуется точная или приблвженная нижняя грань функции В(х, и, с) из (10) на множестве В(х, с) или Г(с), можем принять в качестве приближенного решения проб лемы синтеза для задачи (1Х) — (1.4).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
