Беллман Р. Прикладные задачи динамического программирования (2013) (1246769), страница 66
Текст из файла (страница 66)
Из первого уравнения величина х, определяется как функция от с. Лифференцируя второе соотношение с учетом этого факта, получаем: 7', (с) = [д', (х .) — ~~, (с — х .)] х' Я вЂ”; У', (с — х ) = =,ГА, 1(с — х ). (12.27) лго 1гл. хп числвнныИ АнАлиз 8. УСТОЙЧИВОСТЬ Теперь обсудим вопрос, который мы систематически обходили во всем предшествующем изложении. Это — вопрос о точности решения. Рассматривая типичное функциональное уравнение, с которым мы имеем дело, например уравнение (12.25), мы вводим два вида аппроксимации. Сначала заменяем функцию непрерывно меняюшепся величины на множество ее значений в точках некотороИ дискрегноИ сетки и за1ем максимизацию по непрерывноИ области заменяем максимизациеИ по конечному множеству значений. В некоторых частных случаях исходная задача уже сформулирована таким образом, ч~о никакой аппроксимации не требуется.
Однако в общем случае мы должны рассмотреть вопрос о сравнении решения аппрок- симируюшеИ задзчи с решением исходной задачи. В эгом и состоит проблема устоИчивости. Изменяя, как мы надеемся, незначительно структуру уравнения, полученного из рассмотрения некоторого конкретного процесса, изменяем ли мы столь же незначительно структуру решенияу Хорошо известно, что на вопросы такого рода трудно ответить даже в классическоИ теории, где первостепенную роль играют линейные уравнения.
Несколько работ в этом направлении было сделано в рамках динамического программирования, но н их немного. Мы попыгаемся пролить свет на эту проблему с помощью простого сравнения решениИ некоторых задач вариационного исчисления, полученных точно с помощью аналитического аппарзта и численно с помощью метода функциональных уравнений. 9. ЗАДАЧА О БРАХИСТОХРОНЕ В качестве примера рассмотрим одну из первых задач, к которым Рис. 91.
было применено варизционное ис- .числение, хотя постзвлена она была значительно раньше еще Галилеем. Фактически э1а задача стимулировала развитие вариационного аппарата. Пусть в пространстве даны две точки; мы хотим наи~и такой путь от верхней точки к нижней, по которому частица, движущаяся под действием силы тяжести без трения, соскаль- 421 ВАРИАЦИОННОВ РВШЯИИР зывает за минимальное время. Легко видеть, что по прямой линии, изображенной на рис.
91, частица пройдет наименьшее расстояние, но с низкой средней скоростью. На криволинейном пути частицз быстрее приобретет большую скорость, но пройдет большее расстояние. Сопоставление этих соображения и приводит к решению. 10. МАТЕМАТИЧЕСКАЯ ФОРМУЛИРОВКА Возьмем исходную точку за начало координат и обозначим конечную точку (х, у), как показано на рис. 92. (( Х Тогда, согласно уравнениям механики, частица, пронзя по вертикали расстояние у, приобрете( скорость (2ду)"К независимо от ее горизон- ° ((ЕЯ (ального смешения. Так как длина ~Ь бесконечно малого участка пути дается выражением (1+у')0 в(х, то время спуска, т. е. интеграл от отношения пройденного пути к скорости, равно Мы ищем такую функцию у(х), чтобы у(0)=0, у(Е)=у и время 1 было наименьшим. 11.
ВАРИАЦИОННОЕ РЕШЕНИЕ Решение задачи должно удовлетворять уравнению Эйлера, т. е. дифференциальному уравнению второго порядка и дг дг — —,— — =О, дх ду' ду где 1 определено выше формулой (12.29). В данном случае возможно аналитическое решение уравнения (12.30). Это редкое обстоятельство и является причи- 422 [гл. хп числвнный анализ пой того, что задача о брахистохроне занимает в изложении вариационного исчисления исключительное положение.
После замены переменной и у' = — 13- 2 (12.31) решение прининает вид х — а=Ь(и+гйплт), у — а=Ь(1+сова). (1232) Для граничных точек (О; О) и (2; 1,8323) постоянные а и Ь легко определяются и х=г+а+ я!пи, у=1+соли, (12.33) — я ( и ( — 0,5874, время = 0,4501 сек. ) Именно это решение, как и решение аналогичной задачи с ненулевой начальной скоростью, ллы будем сравнивать с решением, полученным посредством динамического программирования. 12. ПОСТАНОВКА ЗАДАЧИ В ТЕРМИНАХ ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ Обозначим у(л, у) — время спуска от точки (х, у) до точки (л, у) по траектории, обеспечивающей' (12.34) наименьшее время. Тогда хя-л» 7"(х, у)=пп'п ~ ~ (,~~ )~ с(хл+ х +~(х+ с1х, у+у'1х) ~. (12.35) Первое слагаемое правой части (12.35) есть время пересечения вертикальной полосы ширины ах под углому', а второе слагаемое есть оставшееся время для достижения (х, у).
Мы предполагаем, что в каждом бесконечно малом интервзле движение происходит по прямой линии. Важно отметить, что при использовании более точной аппроксимации легко может быть получен и лучший результат. 423 13! Вычислительная пяопвдтпл Если мы сделзеи дополнительное упрощение, предположив, что скоросгь (20)" остаелся посгоянной в течение каждого малого интервала, то получим уравнение аа т (х, у)= пн(п!(, ) Ьх+ 2зу + У(х+ лх, у+у Зх)~. (12.36) Обсудим численное решение рекуррентного соотношения. 13.
ВЫЧИСЛИТЕЛЬНАЯ ПРОЦЕДУРА Разобьем плоскость (х, у) на части посредством сетки с к шагом бх в направлении х и Рис. 93 бу в направлении у, как изображено на рис. 93. Допустимыми путями считаются ломаные с вершипаии в узлах сети. Вычислительный пропесс состоит из рассмотрения кзждого начального значения у для частного значения х и нахождения значений >'(х, у) вдоль этой вертикальной линии с помощью рекуррентного соотношения в форме (12.35) или (12.36).
Сделаем следующие упрощающие предположению Никакой путь не лежит над прямой линней, соединяющей его начальн>ю и конечную точки. (1237) Если, при начале (х, у>, оптимальное значение у при х + дх есть у, то при начале (х, уь), где уь лежит ниже у, оптимальное значение у лежит ниже, челг у. (12.38) Если дхя все более крутых спусков, начинающихся в данной точке, время сначала тбывает, а затем начинает возрастать, то предполагается, что миинмулл иайдсн и никаких дальнейших поисков политики дая данной исходной точки нс предпринимается. (12.39) Эти свойства решения могут быть установлены строго, правда с некоторым трудом.
(гл. 311 424 числвннып хнллйВ 14. ЧИСЛЕННЫЕ РЕЗУЛЬТАТЫ Так как формулировка, требующая сохранения скорости постоянной и равной начальной на любом интервале, приводит к скорости, равной О, и, следовательно, бесконечному времени на первом итттервале, мы решили в этом случае использовать среднее арифметическое между начальной и конечной скоростями. Такая формулировка названа «случаем А», а случай точного приращения времени (12.2) — «случаем В». Для начальной точки (О; О) и конечпон точки (2; 1,8323) результаты сведены в таблицу 12.2 (точное минимальное время равно 0,4оО! сек.). Таблица 12? Время проке«де- нна траектории у очность оолнтнкн лл Случай ау 0,3843 0,3976 0,4395 0,4546 0,4513 0,451! 0,5 0,8 1,2 0,05 0,02 0,01 0,25 0,05 0,01 0,25 0,05 0,04 0,09161 0,0! 832 0,01832 0,09161 0,01832 0,01221 А А А В В В Табдипа 12.3 Время протапдеиин траектории точное ть политики ае Случай 0,01832 0,0! 0,0!832 ~ 0 О1 0,1092 О,!092 0,125 0,125 А В Заметим, что вследствие того, что начало траектории находится в особой точке, аппроксимация А приводит к большои ошибке в политике и сравнительно малой ошибке во времени.
Аппроксимация В дает наилучший желаемыи результат для выбранной сетки. Были произведены вычисления для траектории, исходюнеи из точки (О; 1,3558) до точки (1; 1,8323) при начальной 161 АНАЛИТИЧЕСКОЕ РЕШЕНИЕ скорости (2у)ого. Такие странные начальная и конечная точки были взяты нами для удобства пользования тригонометрическими таблицами.
В этом случае точное время спуска равно 0,1092. Употребляя те же обозначения, что и раньше, получим таблицу 12.3. Мы видим, что за исключением особой точки (0,0) результат очень хорош. 15, ОДНА ЗАДАЧА С ОГРАНИЧЕНИЯМИ Чтобы продолжить оценку точности решений динзмического программирования и исследовать вопрос о применении лагранжевых множителей, рассмотрим еще одну задачу, которая также решена аналитически, Мы будем искать кривую заданной длины, связывающую две фиксированные точки, такую, чтобы площадь области между кривой и осью х была минимальна.
Будем также требовать, чтобы тангенс угла наклона по абсолютной величине не превосходил 1. Аналитически мы имеем зздачу: Найти пп'п ~ уо1х (12.40) при ограничениях «1 ~'1+ ун г(х = г, «о (12.41) )(1 у (хо) = уо у (хо) =уг. 16. АНАЛИТИЧЕСКОЕ РЕШЕНИЕ Аналитическое решение принздлежит М. Хестенсу. Простота этой задачи дает возможность найти точное решение, хотя задача с ограничениями в общем виде не имеет прямого метода решения.
Можно показзть, что оптимзльное решение состоит из двух (пли нуля) прямолцнейных отрезков и дуги окружности. 426 1гл. хп ЧИСЛВННЫй АНАЛИЗ Для конечных точек (2 р 2, 4) и ( — 2 р'2, 4) при длине 4+ к решение имеет вид у = 4 — 2 ~' 2 + х, рг2 ( х 2 рг2, — 2$' 2 (х( — у 2, у=4 — 1'4 — хя, — 1~2 - х р'2, (12.42) 17. ПОСТАНОВКА В ТЕРМИНАХ ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ Применим метод лагранжевых множителей, введенный в глзве П. Затем, определяя «обобпсенную площадь» как площадь, сложенную с длиной, умноженной на Ль положим г" (с, у, Л) равной минимальной обобщенной площади под кривой, начинающейся в точке (л', у) и кончающейся а фиксированной точке (хо у,), (12 43) Для этой функции имеем следующее рекурренгное соотношение: где у' постоянно на всем интервале.
Дальнейшее упрощение первого члена в правой части дает; 1(х, у, Л) = пнп ! ~,~ ' + 1. (!+у') "а Ьх+ 2у+у Дх 1Х1-~ +У(х+Ьх, у+у'Ьх, Л)). (12.45) С каждой точкой (х, у) связывается оптимальная (по отношению к данному значению Л) кривая. Обозначив длину дуги этой кривой через 8(х, у, Л), мы получаем: 8(х, у, Л)=-(1+у")Н +8(х+Ьх, уту'Ьх, Л). (1246) ~(Х, у, А)= ППП ~ ~ (у+1,(!+у")На)Г1Х+ 1Х~ ~ х .+ г (х+ Ьх, у + у' дх, Л) 1, (1 2 44) вычислитвльпая пвоцгдт яд 427 !8. ВЫЧИСЛИТЕЛЬНАЯ ПРОЦЕДУРА Будем рассматривать задачу, сформулированную в $ 16. Как и в задаче о брахпстохроне, разделим все пространство на прямоугольники с помощью некоторой сетки и рассмотрим только кривые, проходящие через узлы сетки.
Так как задача симметрична относительно оси у, мы можем ограничиться только рассмотрением интервала 0(х~2 ~/2. Пропедура для фиксированного Л состоит в итерировании и обратном направлении до тех пор, пока нам не станет известна )"л(у)— : у(0, у), 0 ~ у л=, 4 — 2 ~/2. Затем определяется минимум гл(у) по всем у, и минимизирующее значение у служит исходным моментом вычислений для ЛТ4-г 7) определения политики. Ясно, что именно это значение у было бы равно у(0), если бы мы рассма- сг тривали весь ин~ервал— 2 уг2 (х ~ 2 р'2 "). Когда у(0) определено, при фиксированном Л, Ял(у(0))= =о(0, у(0)) дает нам длину дуги. Если эта длина дуги пас не устраивает, мы выбираем другое Л и повторяем первую фазу вычислений, приводящую нас к другому значению ул(у), не заботясь об определении оптимальной политики.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
