Беллман Р. Прикладные задачи динамического программирования (2013) (1246769), страница 47
Текст из файла (страница 47)
23. ЗАДАЧИ БОЛЕЕ ВЫСОКОЙ РАЗМЕРНОСТИ Как мог заметить читатель, все иллюстративные задачи, собранные в этой главе, являются задачами с малой размерностью, поскольку они связаны с динамическим программированием. Задача о наборе высоты самолетом за минимальное задача о путвшвствиях время, рассмотренная в 5 4, привела к быстрому и легко программируемому способу грубой аппроксимации оптимальной трзектории. Хотя это и является желземым результатом, хотелось бы также иметь возможность вычислять решения для задач, включающих значительно большее число реальных факторов, подобных тем, которые были включены в формулировку, приведенную в 9 9.
Для осуществления этой программы необходимы большие и более быстродействуюпше вычислительные машины, дополнительное время и усилия. Сходное положение имеет место и для задзч о раке~ах и межпланепаых космических полетах. Некоторые способы понижения размерности, например введение множителей Лагранжа, уже были изложены. В то же время для «усмирения» неподатливых траекторных задач необходимы и другие аналитические построения. Некоторые методы — «кандидаты в укротители проблемыа будут рассмотрены в параграфах главы Х11, посвюценных численному анализу.
Задачи могут быть обобщены не только посредством увеличения размерности. Так, в математическую модель могут, и часто должны быть, введены элементы случайности. Наконец, должны быть рассмотрены модели приспособления адаптации, ~де система обучаеася в окружающей ее среде и оптимально приспосабливается к ней. Мы будем обсуждать эти вопросы в главе об управлении с обратной связью (глава 1Х). 24. ЗАДАЧА 0 ПУТЕШЕСТВИЯХ В качестве дальнейшего примера прилоакения этих идей рассмотрим следуюнгую задачу о путешествиях, которая возникает в самых разнообразных прикладных вопросах.
Предположим, что имеются Аг городов, занумерованных индексом 1 = 1, 2, ..., Аг в некотором порядке, н задан ряд чисел 1;,, где Гц — время, потребное иа путешествие из бго города з чй. (6. 31) Начав с первого города, мы хотим провести путь в М-й, который потребует минимального времени. Мы можем идти прямо или заходить по пути в любой другой город. В тех случаях, когда между некоторыми городами не имеется никакой связи, мы будем считать соответствующее Тьг 296 (гл.
чг оптимлльныв тпхгктопии бесконечным плп, прн использовании цифровых вычислительных машин, очень большим положительным числом. Если Аг велико, то любое решение путем простого перебора невозможно. Попытаемся решить задачу с помощью метода функциональных уравнений. Рассмотрим общую задачу об определении минимального времени, потребного для перехода из т-го города в Аг-й. Пусть у; — время, потребное для путешествия из Ого в тт'-й город при использовании оптимальной политики.
~т = пнп [1т +Я, 1= 1, 2... Аг — 1, ) (6.32) Х =О. Легко можно показать, что эта система уравнений имеет единственное решение, а следовательно, что решение этого ряда задач эквивалентно решению исходной задачи. 25. ВЫЧИСЛИТЕЛЬНЫЕ АСПЕКТЫ Уравнение (6.
32) обладает особенностью, которая ранее не встречалась; именно здесь неизвестная функция появляется и в левой и в праной частях уравнения. Следовательно, мы не имеем готовой итерационной схемы для его решения. Необходимо использовать какой-либо метод последовательных приближений. Мы могли бы, например, положить юг го> т т = пц1п 1т:1 (т = 1, 2,..., Аг — 1); У, = О, /~т гл1 (л — 11 цч у,.
=пипЯт+Ут ]; (1=1, 2,..., Аг — 1)Пб, =О. 1~' (6. 33) Это приводит к монотонной сходимости снизу. С другой стороны, мы можем мыслить в терминах политик. Рассмотрим сначала те пути, которые ведут прямо из т в Аг, затем те, в которых делается одна остановка. и т. д. Это Тогда те же самые доводы, которые мы использовали при рассмотрении предшествующей траекторной задачи, приведут к соотношению и-й ПО КРАТКОСТИ ПУТЬ 26] приводит к следующей схеме: го> го~ д.
= С, ; (1 = 1, 2,..., Аг — 1); е л = О, г пт гл) (л — 1) дг =пцп [(;т+ д. ]; (1=1,2,..., Аг— пц 1 (6.34) 1);л„=о, ( ! гфг 26. и-Й ПО КРАТКОСТИ ПУТЬ Иногдз бываег ингересно определить не только крзтчзйший путь, но и вгорой по краткости, третий по краткости и т.п. Тем самым мы сможем оценить, насколько важно использовагь наикратчайший путь по сравнению, скажем, с десятым по краткости.
Лля того чтобы проиллюстрировать метод, введем последовательность величин оь равных времени, потребному иа переход от 1 к М (6,35) нри использовании второго но краткости пути, ( = 1, 2,..., Аг — 1, при которой осуществляется монотонная сходимость сверху, причем за конечное число шагов. Метод (6.33) оценивает наилучший путь длины л, начинакицийся от города !.
Однако уравнения имею~ то свойство, что Аг является стоком, и если путь достигает Аг менее челг за л шагов, то там люжно осгановиться. Для любого другого города путь не может оборваться ранее л шагов. Следовательно, когда л становится большим, все пути стремятся прийти в город Аг, а минимизация гарантирует, что они сделаю~ это наилучшим образом. В методе (6.34) считается, что каждый город достижим на каждой «перации, но потребное время не обязательно является оптимальным. !!оследовательные приближения сходятся к наилучшему пути. Этот пример иллюстрирует различие между итерапиями в нрослранстве функций и в пространстве политик (поведений), рассмотренное в ф 44 главы 11.
Метод (6.33) дает при каждой итерации огнимальное решение задачи, отличающейся от исходной. Метод (6. 34), прежде чем осуществится сходимость, дает неоптимальное решение исходной задачи. Оба метода пригодны для ручного или машинного счета при умеренных значениях Аг, т.е. Аг=--100, и для машинного счета для Аг порядка нескольких тысяч. 2г8 ОПТИМАЛЬНЫЕ ТРАЕКТОРИИ ~гл. ш )1ля получения соотношений для о, заметим, что если первая остановка на пути из т в Ат делается в у, то продолжение движения из у в Аг должно происходить либо по пути, который минимизирует время путешествия от у к Аг, либо по пути, который является вторым по крзткости для переходз из у в Аг. Пусть пнп, от есть абсолютный иннимум о; (1=1, 2,..., ттб, (6.36) пнпао; есть вторая но малости величина оь Тогда мы имеем уравнение пг=пцп)ш1пт((ту+и ); шгпа(!ту+)у)); (т=1, 2,..., Аг — 1); ут:4 у~т о,=б, а уу определены в 9 24.
Аналогичные, но несколько более громоздкие уравнения можно вывести для п-го по краткости пути. 27. ЗАКЛЮЧЕНИЕ Пелью этой глзвы было продемонстрнронзть чигзгелю, что большое число классов задач об оптимальных траекториях может быть быстро и точно решено численно с помощью метода динамического программирования. Преимушество подхода с помощью динамического програмьгирования заключаешься в том, что реалисти.еские уравнения движения и реалистические ограничения легко учесть при решении функциональных уравнений. Основной трудностью, которую мы должны преодолегь, является разлгерноспль.
К проблеме о том, как обращаться с функциями нескольких переиенных, мы еще будем возврзшаться. КОММЕНТАРИИ И БИБЛИОГРАФИЯ Б 1. Прил!енснию вариационного исчисления к траекторным задачам были посвящены разносторонние исследования. Рассмотреюм некоторых результатов, а также ссылки на многие другие статьи см.
в работах: 1. Ту. В г е а К тч е11, Тйс орйщыа!Рзп о1 !Га1ес!опеа, 1. Вос. 1пбиз!. Арр!. Ма!В., чо1. 7; 1959. коммш!Т<Рии и БиялиоГРлвия Н. ). К с!1с у, Ога<Веп! !Ьсог< о1 ориша1 В<81<! Ра!Ьз, Ашег. Коскс! Зос, 1., < о!. 30, 1960. 66 2 — 8. Представленные здесь результаты первоначально изложены в работе: Б. С а г ! а < и о апб 5.
П г е у 1 п з, АРР11са!1оп о1 бупапис ргоягашш!п8 1о ГЬе а1гр!апе ш!и!шиш гцпе-1о-сйшЬ ргоЫеш, Асго. Епя. Кот., 1957. 6 10. Задача была рассмотрена в работе: Д. Е. Ох они м с к и й, Т. М. Энес в, Некоторые вариацион- ные задачи, связанныс с запуском искусственного спутника Земли, УФН, т. !.Х!11, вьш. 1, 1957, с использованием вариацнонных методов и в работе К. В< 11ша и, Тт ге у1п з, Ап арр1!саг!оп о) дупаппс ргонгап<пипс 1о гис бе!всю!па!юп о1 орггша! загс!!1!е гга)есгопеа, ).
ВП1В1< 1птсгР!апс1агУ Зосч во1. 17, 1959 — 1960, РР. 78 — 83, с использованием динамического программирования. См. также Р. Т. 5 шг! Ь, ТЬе Ор!!Гпиайоп о! Мцйы!айе ОгЫ! Тгапз)ег Ргосеззез Ьт Тгупапг!с Рго8гапип!пй, ТЬе КАХТ7 Согрога!1оп, Рарег Р-2177, 1961. Р. 1. !!ге!6 < и 8 апб ). 51<1п нег, А ргоЫеш ш чеЫс1е 1пе! сопзцшрпоп, Орет. Кез. О., то1. 11, 1960, рр. 197 — 204.
К. Ве11ш а п, 5. Ьгс 71в з апб К. К а1аЬ а, Аррйса!юп о1 Пупаш!с Рго8<ашш<пК 1о Зрасе Опгбапсе, Заге011ез апб Тга)сс1ог<ев, ТЬе КАХО !.огрога11оп, Рарег Р-1923, 1960. 3. Х. Ргапй11п, ТЬе танце о! а Пее! о1 а!гсгарб ). Зос.1пбцз!. АРР1. Ма1Ь„< о1. 8, ]960, рр. 541 548. 5. Е. П ге у 1ц з, ТЬе апа1гжз апб во!пйоп о1 орйгпопт 1га)ссгогу ргоЫешз, Зугпров!пш оп Магйсша1!са1 Ор!цп!тайоп Тесйпп]цез; 5ап!а Моп<са, СаЫогша, 1960. Лругой подход изложен в А.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
