Беллман Р. Прикладные задачи динамического программирования (2013) (1246769), страница 67
Текст из файла (страница 67)
Это означает, что в процессе итерирования необходимо выбирать Л корректным образом, данные же политики нег необходимости ни запоминать, нп использовать. Как сказано в 2 24 главы П, для определения Л использовалось следующее правило эксграполяции: ! о где Л, и Л, — предшествующие значения Л, дающие соответственно длины 8л и 8п а 8 — желаемая длина. Так как при выборе Л= О мы не имеем никакого ограничения на длину, в результате получим решение с длиной, л) В силу симметрии. (Прим. редд 428 [гл. хц ЧИСЛИННЫй АНАЛИЗ равной 8 (рис. 94).
Эта информация была использована для вычисления начального значения Лл и ом Выбрав )т, мы можем начинать вычисления. Итак, один цикл вычислений состоит из следующих этапов: 1) задание наугад некоторого разумного значения Х; 2) направленное назад итерирование уравнения (!2.46), 3) одновременная оценка длины через уравнение (12.46), 4) определение у так, чтобы )л(у) было минимальным, 5) пересчет Х в зависимости от ос(у). !9.
ЧИСЛЕННЫЕ РЕЗУЛЬТАТЫ Ниже выписаны результаты: ах ау Начальное значение 1 Конечное значение Х Номер итерации ... Макеилтальная ошибка Ошибка в площади . 0,03 0,0! 1,5 2,0121 0,0! 0,01 0,4 0,03 1,4 2,034 в политике . 0,03 0,01 20. АППРОКСИМАЦИЯ КУСОЧНО-ЛИНЕЙНЫМИ ФУНКЦИЯМИ Во многих случаях удобно аппроксимировать функцию А (х) на интервале [а, Ь[ посредством кусочно-линейной функции А (х) = аг+ Ьг (х), ит т и- х ( и,, 7' = 1, ..., Ат'= 1, (12.47) где и,=а, и =Ь. ПостоЯнные ар Ь| и интеРвалы [ит ь ит) удобно вычислять, пользуясь тем условием, что функция Е(ат, а„..., ал.й й Ьь Ь„..., Ьн+ 6 иь и,, ин)= А'+! ~ (А'(х) — а; — Ьух)к г)х (12 48) 7=! и достигает минимума. Если действовать прямо, то эта задача минимизации приведет нас к сложной вычислительной про.
блеме. Линамическое программирование дает нам простой вичислительный алгоритм для вычисления величин ар Ь! и ий 22[ ововщвния 21. ОСНОВНОЕ РЕКУРРЕНТНОЕ СООТНОШЕНИЕ Пусть для фиксировзнных а и Ь==-а ~,„(Ь)= ппп Е(ае, ..., а; Ьь ..., Ь; иь .:., и„). 1а., Ь! ау1 (12.49) Тогда а! г ! (Ь) = ш ш ~ $ (д (х) — а, — Ь,л )' гул + а Ь -'; ') (Е(л) — а, — Ьех)' е(х], (12.50) е! где минимум берется по облзсти — со(ае, ае, Ь„ЬЬ< со, а -.и, - Ь. Эта функпия вполне определена, так как мы можем сначала вычислить минимум по а; и Ьь а затем минимизировать по и, посредством дискретного поиска. Легко видеть, по при Х)2 мы имеем: Ь Ух(Ь)= пнп [ пнп ~(д(х) — а,— Ь х)есгх-1- а аа! ~ Ь 1аж, ЬМ1 -[-У, !(им)1, (12б1) Это одно из приложений принпипз оптимальности.
Так как минимум по а, Ь, может быть найден в явном виде, мы можем переписать (12б1) следуюшим образом: Ух(Ь) = ш!и [lг (ил„Ь) — Уе ! (ил4. (12.б2) а ам-.Ь Численное решение на этом пути требует нескольких секунд нз каждый из Л' шагов. 22. ОБОБЩЕНИЯ Требуется очень немного дополнительных усилий, чтобы аппроксимировать д(х) полиномами второй степени или полиномами любой другой фиксированнон степени. Аналогично мы можем вычислить минимум УУ+ 1 ат ~ (а(х) — Ь(х, ау, Ь|))я!ах ' ' (12.63) е=! а., 14 Р.
Веььмая, С. Дрезеуа '1гл. хп 430 численный Анализ при условии, что мы знаем, как минимизировать функпщо ь $ !д!х) — гт!х, а» 5 ))вс(х (12.54) ЯА при а и 5 , или минимум гч+! гпах , 'д(х) — Д !х, ар 57) /. (12.55) я. х я. /-т l КОММЕНТАРИИ И БИБЛИОГРАФИЯ 55 1 — 6. Мы слсловали статье: к. В е1! ш а п апб 5. Тт г е у 1п в, Енпс!!опа! арргох1ша!1оп апб бупаппс ргоегашш!пй, Май. ТаЫсв ап«1 Ойсг Агйв !о Сошрчгаиоп, то!. 13, 1950, рр. 247 — 2ьЬ 5 3. По поводу систематичсгкого использования полиномиальной аппроксил~апии для понижении размерности мы отсылаем читателв к статье: С. %. М е г г ! а ш, Ш, Ап оргппиапоп йсогу 1ог 1еес1Ьас!с сои!- го! вувтеш бсв!еп, 1п1оггпаиоп апб Соп1го1, то!.
3,!960, рр. 32 — 59. В слсдугощих работах можно найти примеры использования изложенного метода в математической физике: 6. СЬ ап йг авсКЬ а г, Распаивс Тгапв1ег. Ох!огб Нп!н, Ргеввч 1948. !Т. Ве11гпап, В. Ка1аЬа ап«1 М. Ргсвтгн«1, 1пгалап1 1шйсбб!гвй апб !Тайга!!т'с Тгапв1сг 1п Р1апе Рага11е! 51аЬв о1 Ьйпгте Т1нсйпсщ (Моггсгп Апа111!с апс! Сошрптапопа! Мсйобв !п Вс!епсе апс! Майеша1йв, то!. 1), Емег!ег Рпйй Со., Нож Уог!г, 1963. 5 8.
Понятие устойчивости для лиффсрснпиальных уравнений исследуется в книге: К. В с !!и» а п, 81аЬгп!у Тйеогу о!51!1!егепг!а1 Ег!на!!опт, МсОгажГВП Воо!г Со., 1пс., Хечг Тогх, 1954. Здесь же можно найти много других ссылок. В главе 1 книги «Динамическое ггрограл~мирование» йл~сется краткое рассмотрение устойчивости решений функциональных уравнений, которой лгы касались в настоящей книге. ДОПОЛНИТЕЛЬНАЯ ЛИТЕРАТУРА Изложение современной теории устойчивости дано в книге: И. Г. М а л к и н, Устойчивос~ь движения, Гостехиздат, 1952. ПРИЛОЖЕНИЕ ТРАНСЦЕНДЕНТНАЯ КРИВАЯ О. Грове Рассмотрим вопрос о точках перегиба семейства кривых, определяемых уравнением у(х)= — [1 — е г+' [т+Хг, х= О, (1) с параметрами, удовлетворяющих!и неравенствам у -=- 1, х) О, 1.) О.
1. ЧИСЛО ТОЧЕК ПЕРЕГИБА Мы утверждзем, что каждая кривая семейства имеет не более одноп точки перегиба. Чтобы зто доказать, доста!очно проверить, что продолженная в область е) — у кривая имеет в точности одну точку перегиба. Проведем такую проверку. Заметим, что для сформулированного результата присутствие 1, в (1) несущественно. Кроме того, поскольку не- особенные линейные преобразования сохраняют число точек перегиба, мы можем положить х=хв — у. Тогда условие з) — у зквивалентно условию п)О, и задача, таким образом, сводится к определению числа точек перегиба функции 1!(в)=(1 — е ).", и) О.
(з) Из (2) получим ! ! — =(1 — е )' е — ч (ге) гг ! и 1 мр !4Ф 432 [п. с твлнсцвндинтнля кгивая Теперь точки перегиба кривой (2) соответствуют оиюсительныи минимумам сс максимумам функции (3). По так как преобразование ив= 1/сс является гомеоморфным отображением интервала (О, со), причем с(ш/с(сс(0, то мы видим, что точки перегиба (2) соответствуют относительным внутренним минимумам и максимумам функции Х(сс)=(! — е ™)» 'е "сс', и)0. (4) Последние в свою очередь содержатся среди положительных корней уравнения Л (и)= О.
Теперь, поскольку функция е "и' имеет ровно один внутренний локальный максимум (и= 2) и не имеет внутренних локальных минимумов, можно предположить, что у ) 1. Таким обрззом, из (4) получаем: Л" (сс) = 2и (1 — е ")» 'е "— (1 — е ")» 'е "ссс+ + (у — 1) (1 — е ")' 'е Явив = О. (5) Так как и (1 — е ")» "е " ~ О, то нз (5) следует: 2(1 — е ") — и(1 — е ")+(у — 1) пе "=О, или 2 — сс + е " (иу — 2) = О. Теперь, поскольку у) 1, значение и = 2 не является корнем написанного выше уравнения, и мы получим: е" = ,, 2 ~ и) О.
и» вЂ” 2 (6) Так как е') 1 при и) 0 и (иу — 2)/(и — 2) (1 при 0(и(2, то мы видим, что в интервале (О, 2) нет ни одного корня. С другой стороны, е" строго возрастает до бесконечности, в то время как для и ) 2 функция (пу — 2)/(сс — 2) строго убывае~ от бесконечности до некоторого конечного значения. Таким образом, видно, что у написа>шого выше уравнения имеется ровно один положительный корень. Поскольку порядок кзсания, очевидно, равен нулю, отсюдз следует, что этот корень соответствует единственной точке перегиба функции (2), и наше утверждение доказано.
433 УСЛОВИИ ВЫПУКЛОСТИ 2. НЕОБХОДИМОЕ И ДОСТАТОЧНОЕ УСЛОВИЕ ВЫПУКЛОСТИ Как видно из (1), член, не содержащий Л, положителен и стремится к нудят при г-+Со. Тогда наличие единственной 7 У г,У 4 Х К УЮ,РУУИаУУУДа У Рис. 95. Область выпуклости функции у(в) =((1 — е "'-т+ю(У+ лай л) О двя в О, где параметры удовлетворяют усаовиям у 1, х ) О. точки перегиба на продолженной кривой гарантирует, что у — выпуклая функпия. Отсюда следует, что для выпуклости функпии у в области г ) О необходимо и достаточно, чтобы (п. г тялнсцвндвнтная кгивля точка перегиба г на продолженной кривой удовлетворяла условию а = О, т, е., согласно преобрззованиям 9 1, хю — у ( О или х~и — у -.
О, где в силу (6) иу — 2 Разрешая это последнее уравнение относительно у, получим: у = е" + — (1 — е") = Р' (гг). и (7) Теперь, замечая, что правая часть (6) есть строго возрастающая функция от у при и) 2 и что е'строго возрастает, мы заключаем, что корень и является строго возрастающей функцией от у; такил1 образом, необходимым и достаточным условием того, что х,'и — у(О, т. е. и)х/у, является условие у)е(х/у). Иными словами, у ~ еггт+ ау (1 — еггт) Граничную кривую у = ли(х1у) можно параметризовать сле- дующим образом: х = гг'(1), у=Г(1), Е) 2, где Р(1)=е + — (1 — е').
Таким образом, мы получаем на плоскости (х, у) область, в которой У' выпукла, как зто показано на рис. 96. ПРИЛОЖЕНИЕ Н НОВЫЙ ПОДХОД К ТЕОРИИ ДВОЙСТВЕННОСТИ МАТЕМАТИЧЕСКОГО ПРОГРАММИРОВАНИЯ С. Дреифус и аг. Фреемер 1. ВВЕДЕНИЕ В настоя|нем приложении будет развит зппарат, позволяющий включить задачу математического программирования в более общую задачу, в которой оптимальный доход рассматривается как функция имеющихся ресурсов.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
