Беллман Р. Прикладные задачи динамического программирования (2013) (1246769), страница 65
Текст из файла (страница 65)
Следующие работы представляют интерес в связи с предыду- щей главой; Еь В!а с и лк е11, Оп тйе 1опсйопа! ег!оайоп о1 йупавк ргоигагпв!пц, 3. Майн Апа1уяз апй Арр!., ко1. 2, 196!. Н. К а111а апй К. БсЬ1а11е г, Арр!гей 51а1В1ка1 Осси!оп ТЬеогу, Нагтагй Вояпегм 5сйоо1, 196!. Д 1.. Г1з Ь е г, А с1ая о1 а!осйаа!к втещвепт ргоЫева, Орега!1- опа Кезеагсп, то!. 9, 1961, рр. 53 — 65. ДОПОЛНИТЕЛЬНАЯ ЛИТЕРАТУРА Изложение теории марковских цепей дано в книге: В.
И. Романовский, Дискретные цепи Маркова, Гостехиздат, 1948. По поводу связи с линейным програмллированиеы (6 22) сль А. Б. Маппе, Ыпеаг ргоцгапип1пд апй зецпеп!1а1 йесгяопз, Ма пац. Бсь, ло1. 6, 1960, рр. 259 — 267. ГЛАВА ХИ ЧИСЛЕННЫЙ АНАЛИЗ 1. ВВЕДЕНИЕ 2. ТРУДНОСТИ, СВЯЗАННЫЕ С РАЗМЕРНОСТЬЮ Рассмотрим задачу максимизации функции е, (х,) + дя (ха) +... + Кч (хл) (12.1) по всем неотрицательным хп удовлетворяющим условиям: л Ьг|хт = г,, 1=1 еде (гы ) О. 1=1, 2, ..., М, (12.2) В нзстоягпей заклюнпельной главе мы наиерены обсудить ряд вопросов, общих для всех рассмотренных ранее задач.
К ннм относягся вопросы точности, сокращения вреиени вычислений и понижения размерности. Так как в этих областях до сих пор сделано очень мало, наше изложение неизбежно будет эскизным. Мы начнем с вопроса о полиномиальной аппроксимации и приведем теоретические и практические результаты. Затем мы рассмотрим применение вытекающих отсюда методов к решению задач о процессах распределения ресурсов и управления. В ааключенне сравниваются результаты, полученные с помощью метода функциональных уравнений, с точными решениями некоторых простых задач вариационного исчисления. 414 1'гл. хп числвнный «нализ Как известно, эта задача приводит нас к рекуррегпному соотношению У,(си с,, см)=шах~д (х )+Уж,(с, — Ь, х„, кл ся — Ья х „..., см Ьмлхл)), 112.3) где Ь,,хт(сг !=1, 2..., М.
(12.4) Прн М=1 решение требует несложных вычислений, прн М=2 счет будет немногим сложнее, если мы привлечем описанные выше методы. При М) 3 мы должны либо перейти к более грубой сетке, либо к более тонким методам, чтобы преодолеть ограниченность памяти вычислительной машины. 3. ПОЛИНОМИАЛЬНАЯ АППРОКСИМАЦИЯ Рассмотрим один из наиболее многообещающих методов преодоления «проклятия размерности» вЂ” приближение функций полиномами. Если у 1х) — непрерывная функция, заданная на интервале О -=.х( 1, то мы можем хранить ее, протабулировав ее значения в точках сетки х=О, Ь, 2Ь,, „МЬ=1. Точность такого представления функции определяется величиной ц. Однако чем меньше величина Ь, тем больше значений функции должно быть вычислено и запомнено. Следовательно, в любом случае мы должны стремиться к компромиссу между издержками вследствие увеличения времени счета и издержками, обусловленными неточностью результатов.
Когда мы имеем дело с функциями нескольких переменных, основным ограничением являются не издержки или время, а объем оперативной памяти вычислительной машины. В случае фУнкции четыРех пеРеменных т 1хь х„ха, х,), опРеделенной в области О ~ хв х„ха, х«( 1, даже при шаге ц = О, 1 по каждой нз переменных, мы приходим к необходимости табулирования функции в 1О' точек. Нам хотелось бы найти более экономное представление для функции. Возвращаясь к функциям одной переменной, 415 41 оятогондльныя полнномы исследуем осуществимость аппроксимации с помощью полипом ов л 7"(х) = ~Ч ', а„х'. (12.5) а=о Теперь функция может храниться в виде набора коэффициентов ]аи а,, а,] и правила вычисления значений соответствующего полинома. Таким образом, мы можем получить значение 7(х) для произвольного х в интервале ]О, 1], затратив огносительно малую долка ячеек памязи.
4, ОРТОГОНАЛЬНЫЕ ПОЛИНОМЫ Теперь возникает задача об определении для заданной функции г (х) коэффициентов ам аь ..., ам Несмотря на то, что весьма соблазнительно использовать первые М + 1 членов разложения 7'(х) в ряд Тейлора в окрестности х = 0 пли, может быть, х= 0,5, мы отвергнем эту идею по двум причинач. Во-первых, ряд Тейлора может расходиться вне малого интервала, содержащего точку х= 0 или х= 112.
Еще более важной является вторая причина — мы всегда относимся с большой подозрительностью к не~оду, когорый требуег знания производных функции, заданной численно илп графически. Вернемся к полиномам, но заменим разложение Тейлора более мощным разложением в ряд по ортогональным полиномам.
Для интервала [О, 1] мы будем использовать полиномы Лежандра. Для упрощения обозначений заменим интервал ]О, 1] на интервал ] — 1, 1], чтобы иметь возможною.ь применять полииомы Лежандра в их обычной форме. Вал г~звестно, полиномы Лежандра ]Р„(х)], л = О, 1. Р,(х) = 1, образуюг последовательность полипомов возрастающей степени, обладающих тем свойством, что 1 ~ Р,„(х) Р„(х) Ых=О, и — п. (12.6) — г Нормируя полиноиы соответствующим образом, можно обе-. спечить, чтобы ') Р„'(х) г(х = 1.
(12.7) 1 416 !гл. хп численный анализ Отсюда чисто формально заключаем, чго если записагь У(х)= ~Ч ~ а„Р„(х), «=.0 (12.8) — 1 =х~ 1, то коэффициенты а„можно определить из соотношения 1 а„= г) г (х) Р„(х) ьгх. (12.9) — ! Следовательно, в качестве нашего приближения для т'(х) полиномом степени Аг мы берем частную сумму этого ряда "а т-пР,(х)+, . +псРл (х) (12.10) где а, определяюася согласно (12.9). Это предсгавление коэффициентов имеет большое преимущество, так как оно зависит только от значений самой функции и не зависит от значений ее производных. б.
ГАУССОВЫ КВАДРАТУРЫ ~ У(х) Р„(х) г(х = '~,Х(йб) Р„(Ы) (Ь), (12,11) то мы столкнемся с прежними трудностями табулирования значений через равные интервалы. Если бы мы предполагали табулировагь г(х), то могли бы с тем же успехом дела~в эго с самого начала. Мы обойдем эту трудность, воспользовавшись одной из квадратурных формул, в данном случае квадратурной формулой Гаусса. Вместо того чтобы пользоваться римановыми суммами, применим приближенную квадратурную формулу.
Окончательная формула примет вид (12.12) Возникает вопрос о вычислении коэффициентов а. Если мы попытаемся получить их значения, аппроксимируя интеграл в (1'2.9) римановой суламой 417 61 чиглвнныд пгимвР где веса р„ и точки л„ зависят от й. Мы можем выбрать К величин Ри Р, , гг„, и й точек хи х, ..., х, так, чтобы соотношение (12.12) было точным для любого полинома ь (х) степени не выше 2)с — 1. Боэффициенты а„, определенные через интегрзл, фигурирующий в (12.11), вычисляются с помощью выражения а„= ~, Р,7 (хь) Р„(х„). (12.13) Величины и„Р„(ха), lг=!, 2,,„, Я, п=!, 2...„вычисляются заранее и ззклздываются в измять.
Чтобы получить значение функции )"(х), мы теперь воспользуемся выражением 1(х) = ~,' а,Р„(х), я=а (12.! 4) где а„задаются формулой (!2.13). Вычисление Р„(х) в отдельных точках легко проводится с помощью трехчленного рекуррентного соотношения 6. ЧИСЛЕННЫЙ ПРИМЕР Посмотрим, как этот метод применяется на практике. Будем минимизировать функцию и Ж Рл=хиь+ Х ь (!2.!6) а=! й-1 где (а) пя ы = 2и„— и„' + о„и, = с, (12.17) (Ь) о„выбираются так, чтобы и„,, находилось в интервале [ — 1,1].
Обозначим (с)=пп'пР гя1 (12.18) (л + 1) Р„, (х) — (2п+. 1) Р„(х) + пР„, (х) = О, (12.15) имеющего льесто для ненормированных полиномов ЛЕжандра. !гл. хп числвннып анализ для 1с((1. При М) 2 мы имеем: Уг (с) = с', У,(с) = ппп(са+ па+ Уч, (2с — сз+ о)). ( ' ) Первые шесть членов этой последовательности были вычислены обычным образом для сетки значении, покрывающей интервал ( — 1, 1). Затем мы применили метод полиномиальной аппроксимации, записав каждую функцию в виде У,(с) = ~ аа „Ра (с), а=о (12.20) где 14 а„, = ~ ~л(с) Ра(с) Ыс= ~ рт„,(с ) Р„(г ). (12.21) — 1 7=! Так как с; — фиксированные величины, не зависящие от д7, последовательность функций (7",(с) ( требует вычисления только в точках сь ся, ..., см. Однако, чтобы оценить выра.
жение) ч, (2с — с'+ о), фигурирующее в правов части (12.19), мы должны воспользовзться формулой з ~л,(2с — ст-1 — и) = ~4 а„,,Р„(2с — ст+в). (12.22) Для вычисления же величин Ра(2с — с'+и) прибегнем 7, 6 а и ц, !2 ! к РекУРРентномУ соотношению (12.15) и ззтем введем соответ- гч к! б ил с помощью (1'2.19) и полино миальной аппроксимации. Как можно видеть, результаты хо роша соглзсуются.
1,0 0,8 0,2 0,0 -0,2 — 0,8 — 1,0 1,782 1,370 0,153 0,006 0,202 4,876 8,660 1,77 1,36 0,145 0,0 0,20 4,89 8,67 ствующий нормирующин множитель. В тзблице 12.1 приведено сравнение полученных результатов. Последовзтельность (2'„(с)) получена из (12.!9) путем непосредственных вычислении, а (Д (с) ) получена 7] использОВАние математического АнхлизА 419 7. ИСПОЛЬЗОВАНИЕ МАТЕМАТИЧЕСКОГО АНАЛИЗА В некоторых случаях, когдз для получения более эффективного алгоритма, можно использовать аппарат анализа, мы можем комбинировать два метода — метод непрерывной вариации и метод функциональных уравнений.
Рассмотрим задачу максимизации функции Ув= Ас(х,) †'- у,(х,) + ... + д,(х ) (12.23) при ограничениях хс 1 ха+ ° ° +х, =с, х;)О. (12,24) Мы имеем функциональное уравнение 7А,(с) = шах [ЕА (хл) +1„, (с — х )]. (12 25) О-сл-с Если все рассматриваемые функции дифференцируемы и если мы тем или иным способом определили, что максимизнруюшая точка лежит внутри интервала О(х, .-.с, то из (12.25) мы получаем два соотношения: д' . (х ) — У... (с — х,) = О, (12.26) У~(с) =Аъ(хл)+У~- ~ (' — хх) ) Следовательно, мы имеем два уравнения: а' (х )=[,',,(с — х ), ~ ~.()=.у„,( — м) ]' (12.28) Мы видим, что оптимальная политика определяется маргиналь- ными доходами, т, е. последовательностью (7А(с)].
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
