Беллман Р. Прикладные задачи динамического программирования (2013) (1246769), страница 22
Текст из файла (страница 22)
б4. ВЫВОДЫ 'г4а предшествующих страницах нашей целью было обсудить новые задачи, вызываемые многомерностью. В некоторых случаях мы можем применять сгандартный подход при условии, если в нашем распоряжении имеешься современнзя вычислительная машина и мы готовы расходовзгь определенное время и усилия. В других случаях требования к памяти значительно превосходят возможности наиболее мощных из современных вычислительных мзшин. Для того чтобы справиться с многомерными задачами, возникающими при более реалистичном описании экономических процессов распределения, чы должны привлечь более мощные мегоды классического анзлиза — метод последовательных приближений и метод непрерывности.
Мы обсудили несколько примеров, чтобы показать, что эти методы можно применять и что в ряде случаев они будут давзть удовлетворительные результаты. Далее мы перейдем к рассмотрению дополнительных примеров, которые можно использовать о~дельно или совместно с уже рассмотренными, Следует ожидать, что очень сложные процессы потребуют привлечения всех эгих средств в совокупности, вмесзе с использованием классического анализа, линейного и нелинейного программирования и т. д. При рассмотрении этих процессов мы встретимся с задачей метапрограммирования, в которой одной из главных трудностей будет определение того, какими математическими методами пользоваться и в каком порядке. Все они близко связаны с понятием адаптивных процессов управления, к которому мы снова обратимся в глзве Н!П.
бб, ЗАДАЧА О кТРУДНОЙ ПЕРЕПРАВЕя В качестве продолжения анализа, проведенного в ф 32, где рассматривалась транспортная задача Хичкока — Купманса„ рассмотрим одну математическую головоломку, которая часто 571 ао нкпиональныв аштвнвння всгречае~ся в ма»е»1агической литературе развлекательного характера. Типичный вопрос состоит в следующем. «Группа, состоюпая из трех людоедов и трех миссионеров, пытзется переправиться через реку.
Имеется лодка, в которую помещается два человека и которой можно упрзвлять с помощью любой комбинации людоедов и миссионеров из одно~о или двух человек. Если количество людоедов по одну сгорону реки или в лодке превосходит в какой-нибудь момент число миссионеров, то людоеды предаются своим кровожадным инстинктзм и пожирают миссионеров. Каким образом нужно составить план перевозки, чтобы быть уверенным, что группа людоедов и миссионеров благополучно пересечет реку?» В следующем параграфе мы сформулируем задачу в более общем виде, а затем решим ее методом функциональных уравнений. бб. ОБЩАЯ ЗАДАЧА Рассмотрим теперь более общую ситуацию, когда мг исходим из того, что по одну сторону реки находи~ся л», людоедов и и, миссионеров, а по другую сторону т, людоедов и пя миссионеров.
Пусть правило, предотвращающее пожирание миссионеров, заключается соответственно в выполнении ограничения )с,(щь л,))0 на одном берегу, ограниьения )?,рлм ля))0 на другом и Рса(т, и)'= 0 иа лодке, вмещающей не более )г человек. Если заданы произвольные пелые числа ть пн гль ль то совсем не ясно, когда возможен план безопасной перевозки.
Поэтому мы начнем с рассмотрения следующей задачи. Если исходить из заданных начальных данных, то каково максимальное число людей, которых можно перевезти с одного берега, скажем с первого берега на другой, не подвергая кого-либо из миссионеров опасности быть съеденным? 57. ФУНКЦИОНАЛЬНЫЕ УРАВНЕНИЯ Поскольку общее число людоедов и миссионеров остается в пропессе перевозки постоянныч, то состояние системы в любой момент определяешься введенными выше числзми тл, и л,. 1зб 1гл. и ашогомь ныв пгоцьссы гдспгядвляння Введем функцию уи(тн и,) — максимальное число людей на втором берсту после Ф шагов, если мы начинаем с и, людоедов и и, мне- (2,149) сионсров иа первом берегу и согпвстствснно с и, и иа на втором берегу.
Предположим, что на любом шаге допустимо не возвращать ни одного человека на первый берег со второ~о, если все уже находятся на втором берегу. Один шаг процесса состоит из перевозки х, шодоедов и у, миссионеров с первого берега на второй, а затем из обратной перевозки х, людоедов иув миссионеров на первый берег. Используя принцип оптимальности, получим для ттт~ 2 рекуррентное соотношение уи(ть и)=шакти 1(т,— хт+х„и,— у,+ув), (2.150) «, т где величины хо х,, ун у, подчинены ограничениям (а) О ( хт =.
то О -у,(пн (Ь) 0 —.хв -та+хи 0 =.у -.и +уо (с) х, +у, =- /г, х, +у, ( ут, (б) )та(хо у,))0, йа(хт, ут) — О, (е) Й,(тт — хь и,— у,))0, (1) й,(т, — х, +х,, п, — у,-',— ув) =-О, (К) )св(та+хо и,+у,)=--0, (Ь) й„(та+ х, — х„п, + у, — уа) ) О. (2.151) Множества хи х,, уо у„удовлетворяюшие этим ограничениям, сушествуют, так как по предположению им удовлетворяют значения х,=ха=у~=ут=О Для ттт=1 имеем: У,(тн п,)=шах((тв+х~)+(и,+у,)1 (2.152) «,у где хн у, подчинены написанным выше ограничениям.
б8. ОБСУЖДЕНИЕ Для небольших значений Ф и тн тв, ио и, значения уп(тн и,) можно легко вычислить вручную. Во многих случаях условия (2.!б 1) столь ограничительны, что имеется един- 137 59) числвннов Рвшвнив ственная возможная политика, которая автоматически будет опгимальной. Указанным выше способом мы одновременно определяем минимальное число перевозок, необходимое для перемещения всех людей с одного берега на другой, всякий раз, когда это возможно.
Чтобы получить это минимальное число, иы продолжаем процесс до тех пор, пока не получится значение И, для которого 1м = т~ + та + л, + ла. 59. ЧИСЛЕННОЕ РЕШЕНИЕ 1~ (О, 1)=6, 1,(1, 1)=6, 1,(2, 2)=3, 1,(3, 2)=2, 1~(3, 1)=2, 1~(О, 2)=6, 1,(О, з)=4, 1,(з, з)=1. Замечая, что если1„(1, /)=6, го1ю,(51)=Опля 1=1, 2. мы игерируем рекуррентное соотношение для всех значения, пе равных 6, и получаем: 1я(3, 1)=3, 1я(2 2)=4 1а(З 2)=2 1я(0, 3)=.6 1, (3, 3) = 2.
Продолжая процесс, получнч: 1аР 1)='1 1з(2, 2)=6, 1,(З, 2)=З, 1т(3 2)=4 1а(3 3)=з, 1 (3, 2)=6, 1а (3, 3) = 2, 1~ (3, 1) = 6, 1,(з, з)=4, 1 (з, з)=6. Проиллюстрируем приведенный выше алгоритм на примере зздачи, сформулированнон в 9 55. Сначала устанавливаем, что для Х-шагового процесса возможны только определенные начальные состояния. Все другие начальные состояния приводят к немедленному людоедству.
Если мы обозначим через (1, /) состояние, при котором 1 миссионеров и / людоедов находятся на первом берегу, а 3 — 1 миссионеров и 3 — г' людоедов на втором берегу, то возможны только следующие состояния: (О, 1), (1, 1), (3, 1), (О, 2), (2, 2), (3, 2), (О, 3) и (3, 3). Используем алгоритм, данныи в ф 57, для вычисления значении 138 многомгРКНР пРОЦБссы РаспРРдвлвния [Гл. н Следовательно, требуемое число перевозок, если начинать с трех людоедов и трех миссионеров на первом берегу, равно шести. Оптимальная политика легко определится, если запоминать максимизируюшее решение на каждом шаге. КОММЕНТАРИИ И БИБЛИОГРАФИЯ Задача максимизапии или минимизапии функции Аг переменных является одним из основных вопросов анализа, и вполне естественно, что на:1се решение были направлены огромные усилия.
Поскольку нас интересуют только функции весьма специального вида, мы не обращаем никакого внимания на какие-либо из сущсстнующих общих методов. Классический метод «наискорейшего спуска» описан в работе: Г. С. К о э си Ь1о о ш, ТЬс шейся о1 э!еерса деэсеп1, 1Ч«пгпег!са! Апа1тэ!э, Ргоссеб!пйэ о1 !Ьс 5!хй Зушронош 1п Аррнеб Майепта!!сэ, МСС«гаж-Н1!! Воой Со., 1пс., Хечч Уогй, 1956. Здесь можно найти много ссылок.
Об этол«методе см. также статью: й Т о б «1, Мо!ша1!оп 1ог ччогйпй 1п пншепса1 апа1узнь Сошш. Рагс АРР1. Май., чо1. !3, 1955, рр. 97 — 116. 9 14. Строгое рассмотрение фундаментального понятия выпуклости можно найти в книгах: Т. В о п е э а с п апб чч'. Р с и с Ь с!, Тйеог!е бег Копчсхеп Когрсг, 1:гйсЬп!ээе бег Мзй., чо1. 8, !934; Н. Сь Вид!ел!оп, Сопчех1!у, Сап»ЬТ!бпе Тгас!э., Хо. 47, СашЬбдйе !Уг!!чсгэ1!у Ргсэа, СашЬПбйе, 19о8. С некоторыми аналитическими применениями методов этого параграфа можно познакомиться по книге: Е.
Р, В е с К с п Ь а с Ь апб К. В е11 ш а и, !пеццарл1еэ, ВгйсЬп1гже бег Май., 5рппйег, Всгйп, 1961. Мы пользуемся двойственностью евклидовой геометрии для получения дальнейшего упрощения процессов. Это свойство бтдет снова использовано при изучении вариапионного исчисления. З 15, Об интерпретации множителя Лагранжа в качсгтве «цены» см. книгу П. Самуэльсона, упомянутую в конце главы 1, а также приложение !1, написанное С.
Лрейфусом и М. Фреймером. 9 16. Использование множителя Лзгранжа а динамическом программировании впервые дано в статье: К. В е1! ш а п, !Уупаш!с ргойгашш!пй апб Ьайгапце шпн!р!!егэ, Ргош Ыат. Асаф 5с!. !!ЗА, чо!. 42, 1956, рр. 767 — 769. 139 КОММБНТАРИИ И БИБЛИОГРАФИЯ 9 20.
Приведенные злесь рассуткленин заимствованы из работы: К. В е 1! в а п, 1. О 1 ! с Ь я Ь е г д апб О. С г о я я, Эовс Аяресы о1 йе Майевайса1 ТЬеогу о1 Сон!го! Ргоссяяея, Т1к КА14О Согрогаг)оп, Керогс К-З!3, 1958, рр. 49 — 50 !Русский перевод: Р. Везлиан, И. Гликсберг, О. Гросс,Некоторысвопросы математической теории процессов управления, ИЛ, 196Ц.
ф 21. Эттс результаты имеются в работе; 5. О ге у1и я, Оупапис РгоКгаппп)п3 5О1н11оп о1 Айоса1»оп РгоЫевя, ТЬе КАНО Согрога!!оп, Рарег Р-1083, Мау 9, 1957. ф 27. Приведенные результаты были опубликованы в статье: К. В е11 гп а п апб 5. П г е у 1 ц я, Пупав!с ргоКгавв!ИК апс1 йе ге1!аЬй!у о1 пийкогпропеп1 дсвсея, Орегасгопя КеяеагсЬ, то). 6, 1958, рр.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
