Беллман Р. Прикладные задачи динамического программирования (2013) (1246769), страница 32
Текст из файла (страница 32)
После того как было установлено, что уа пс при и оз, центр тяжести исследований цереиестился в область установившейся политики. Кроме того, эта политика может быть найдена другими путями, которые позволяют обходить неприятные стороны динамическо!о про~раммирования, связанные с размерностью. оо! коммвнтаРип и БиБлиОГРАФия 941. Са. Н. М, [УаЕпег апд Т.
М. [[[|Ы1|п, Оупапцс чегя|опя о| есопопцс |о! Мхе шобе1, Мапа8егпсп[ 5с[епсс, чо1. 5, !958, рр. 89 — 96. 6 42. Решение, приведенное злесь, впервые поаучено другим пттем Джонсоном. См. 5. 1оЬп хоп, Ор[цпа! 1жо-апбйггее-я1айс ргобнсйоп ясйедн1ея ФНй яе!нр [|шея [по[абеб, Хача| Ксясагсй [.о8я. [7., Матей 1954. Дальнейшие результаты и ссьшки см.
в работах: р. М. Т о п 8 е, А НснгХ1й Рго8[аш |ог АяьсшЫу Ыпе Ва!апс[ИЕ, ТЬс КАХГ! Согрогайоп, Рарег Р-!993, 1960. К, Вс|1шап, Майеша[|са! аярес!я о1 ясйебайп8 йеогН Л 5ос. !Ибоя[. Арр|. Майг., то!. 4, 1956, рр. 168 — 205. В. С|111е г, Майешабса| .ъо1нйоп о! Ргобосйоп Р1апп!г[д апб Всйебайп8 РгоЫсгпя, !ВМ Тесйпка! Ксрог[, Абчапссб 5уя[егпя [Усче[оршсп[ [7[На|оп, 1960. |.
Х а Ь с я Ь [ ш а, Тйс ог[1ег о| и Пеша ргосеежеб оп т шасЫпеж 3. Орет. Кея 5ос. Зарап, то|. 3, 1961, рр. 170 — 175; чо!. 4, 1961, рр. 1 — 8. Рассмотрение стохастических процессов принятии решений нано в работах: Е. 5. Рйе! Ря, Тйе Ассншо1а1|оп о1 Кийу СарйаЬА ОВсге[е— 1нпе 5сг[оеп[[а! [[[В[[у Апа1уя[я, СочНея Ь[ясняя!оп Рарег, 1961.
М. 5Ь нЫ К, Арргоасйея 1о йе я1нбу о1 бесы|оп-гпайпй ге|ечап! 1а йс |пш, Л. Ваяпсяя, чо|. 34, 1961, рр. !01 — 118. ДОПОЛНИТЕЛЬНАЯ ЛИТЕРАТУРА Сравнительно элементарное изложение теории управлении за- пасами солержитсн в нелавно вышедшей книге С. Н а 6|е у, Т. М. % Ь ! [| п, Апа1умя о! [пчеп1огу яуя|сшя, Ргсп1йе — Най, ЕИК[ежооб СП1[я, Х. У., 1963. Из новых работ по теории замены оборудоввнин отметим, на- пример, 77. %. уогиспяоп, Д у МсСа[1, Орби|а! гер1асешеп[ роПс|ся Ри а Ьайм[гс ш[яяйе, Мападеп[сп[ 5с[епсе, чо! 9, Х 3, 1963. К. Кабпег, Р. %.
Уогдепзоп, Оррог[нпжйс гер1асешсп[ о1 а я!п81е раг[ |п 1Ье ргсяепсе о1 вече[а! гпопйогеб раг1ь, Ыапаеешеп[ 5с|епсе, чо|. |О, Х 1, 1964, рр. 70 — 84. глдвд ~ч МЕТОДЫ ОПТИМАЛЬНОГО ПОИСКА Е ВВЕДЕНИЕ В предыдущих главах мы неоднокрагно встречались с уравнением вида 1м(х) = шах д(х, у, 1м — 1(у)) у где максимум находился прямым перебором всех возможностей. Если у принимает различные значении уи у, у,и, то такои способ требует вы веления д(х, уь 1л ~ (у1)), д(х уь 1л -~ (уя)) и т. д, и сравнения полученных значении. При больших л1 эти операции зребуют много времени. Возникает вопрос о более эффективном способе определения положения максимума.
Это — важный вопрос, ибо возможность решения задачи тем или иным методом зависит ог количества времени, необходимого для получения решения. Чтобы обеспечигь точность решения, мы часто ножен испробовать на каждом шаге большое число полгпик. Следовательно, нам важно изучить сам процесс поиска. Мы покажем, что в одном важном и часто встречающемся случае существуют способы, феноменально сокращающие требуемое время. Попутно с определением положения максимума функции мы изучим задачу об определении нуля монотонно убывающей функции. Перечисленные вопросы являются частными случаями общеи задачи поиска' — задачи чрезвычайнои трудности, даже когда речь идет только о ее постановке.
Весьма занятно, что при численном решении задач динамического программи- 31 пгоцвсс нахождения точки млксимтмь 203 рования вознпка и новые задачи динамического програмьшрования. Результаты и методы этой главы принадлежат О. Гроссу и С. Джонсону. 2. УНИМОДАЛЬНЫЕ ВУННЦИИ 3. ОДНОМЕРНЫЙ ОПТИМАЛЬНЫЙ ПРОЦЕСС НАХОЖДЕНИЯ ТОЧНИ МАНСИМУМА Очевидно, что своиство унимодальности никогда не лает нам воэможности вычислить точное значение максимума?(х), но оно позволит очень точно определичь положе>ще точки хн Те о р ем а 1. 1?усть у =у(х) является унимодальной на интервале 0 ( х ( 1„.
1?редположи.и, ч то 1, ест ь число, обладаюгнее тель свойством, что точка, в лоторой ?(х) достпгаегп малсп.иульа, может быть локализована внутри интервала единичной длины пулгем вычисления и взаимного сравнения не более п значений 1 (х). Введем величину (4.1) В„=зцр ?т и", = В„, + В„я при и ) 2 Тогда Числа Є— числа Фибоначчи, которые чзсто встречаются в самых неожиданных местах.
Мы рассмотрим их свояства ниже. )(о к аз а тельс тво. Воспользуемся методолг математической индУкции. Заметим, что Рь = 1 и В, = 1, так как единственное значение уничодальной функции, по существу, не дает никакой дополнительной информации относичельно положения точки максимума. Прежде всего введем понятие унимодальноп функции. Определение. Функция ? (х) унимодальна на интервагге (О, Ь), если существует значение хь, 0(ха <Ь, такое, что 1(х) пли строго возрастает при х(хь и строго убывае~ при х)хь или строго возрастает при х(хь н строго убываег п рп х =ч хь. Наиболее важным прииером функции ~акой природы являются вогнутые функции. мвтоды оптимлльпого попскл ]гл, щ 204 гг х, х, Рис. 53. интервалов, даже если нам иавестно, чго максимум достигается на ингервале ]хп хя]. Теперь мы имеем подынтервал интервала ]О, Ев] и значение у (х) в одной из его внутренних точек.
Для л=2, 1.,=2 — а, где а мало, можно выбрать х,=1 — а, х,=1. Это показывает, что зцрпа=-2. С другой стороны, из выщесказанного следует зцр 1.,(2+ 5 для любого В ) О. Следовательно, Ея — — 2=Е,+Ем (4.2) Далее предположим, что Е„= =Ем,-~;Е„я для 1=2,, л — 1. Основываясь на этом предположении, Р х, Рис. 54 мы хотим показать, что Е„= Е„, + Г„м (4.З) Допустим, что мы вычислили У(х) в двух точках х, и х, интервала 10, 1.„] (см. рис. 53).
Если у,)уа то мы нахо- димся в ситуации, изображенной на рис. 54. Отсюда х,(Р„п так как мы можем выбрать еще только л — 2 точек, поскольку наш первый выбор из л — 1 возможных точек пал на хп Кроме того, х,(р„м так как максимум должен находиться на интервале (О, х,) и имеется возможность выбрать еще только л — 2 точек. Аналогично, если уа)уп мы имеем 1-„— х~(Р„п Таким образом, )..
(х, +Е„, <Е„,+~„„ (4 4) огкуда ~л зцр ~л ~ ~л-г + ~л-а (4ьб) Фиксируем птм2 и вычислим у,=~(х,), уа=,г'(х,), где хь х, — две точки из интервала (О, Е„) и х,(хм Если у,)уа, то точка максимума находится в интервале ]О, ха], в то время как при уя .ьу, точка максимума лежит в интервале [хь ь„]. Если у, =у,, то выбираем любой из этих 4! числа ч игоп тччи Остается вывести обратное неравенство. Положим ( О) рп-Ь Е„= (1 — —,, (Е„, + Р„,), х, =(1 — — ) Р„е (4.6) Так как а можно выбрать произвольно малым, то ~п пв ~»-1, ~п- » 4. ЧИСЛА ФИБСНАЧЧИ Несмотря на то, что первые члены последовательности (гч„), порожденной рекуррентным соотношением (4.7) не велики и вначале растут медленно: 1, 1, 2, 3, 5, 8, 13, 21, 34, оо,, (4.8) все же уже гч»п превышает 10000. Таким образом, при количестве точек, не превышавшем 20, мы всегда можем нанти интервал, длина которого составляет 10 ' длины первоначального и который содержит точку максимума.
Чтобы определить аналитический вид тчп, заметим, что гп является решением уравнения (4.7) без граничных условий, если г'=г+1. (4.9) Эти значения г равны (1'+ 1гг б)!2. Следовательно, если мы положим Рп — — с,( — ) +ся( ' ), (4.10) Из этих двух неравенств следует требуемое равенство. Кроме того, отсюда мы получаем для любого малого п оппо мальную процедуру поиска. Сравнив у (х,) и г'(ха), мы получаем интервал длины Е„, = 1 — — Р„., и значение Функ/ »! п- ! 2, и. ции в первои точке оптимального поиска внугри меньшего интервала. Продолжая чаким же образом, имеем !.» = 21 =!1 — — Г» для 2(lг(п. Наконец, 1»= (! — --1 гчп= 2) = 2 — а, так что последний интервал имеет единичную длину.
мвтоды оптимтльного поиска 1гл. ш то, подобрав сооавегсгвувщим образом значения для е, и с„ мы получим решение (4.7). Таким образом, 1=с,+ем 1 = е, ~ + ) ) + е, ~ ) ), (4.1 1) и мы имеем: 1+ г" 5 1 ) )г 5 — 1 у" 5 (4.12) 5. ЗОЛОТОЕ СЕЧЕНИЕ Возьмем па прямой отрезок [О, !.1 и разделим его на две части в отношении (у' 5+1),'2.
Греки считали, что прямоугольник с таким отношением сгорон имеет наиболее приятные пропорции, и часто использовали его в своеи архитектуре. 6. ДИСКРЕТНЫЙ СЛУЧАЙ Рассмотрим случай, когда функция г(х) определена на дискретном множестве точек. В этом случае мы докажем следуюгцую теорему. Теорем а '2. Пусть у=Г (х) — унпмодальная функция, определенная на дискретном множестве, содержа- Так как (1 5+1)Г2)1 и (рг 5 — 1)'2(1, мы видим, что при больших н величина Р„равна 1 )лб 1 с большов точиос ~ ью.
Отсюда следуе г, ч го ценои дополнительных вычислении небольшого объелга можно получи~в экспонеициальнсе возрастание точиосни Оч ношение р„р„, стремится к (у' 5+1)12, что приближенно равно 1,62. Сле. довательно, первые два значения х, и х, следует взять на расстоянии 0,62 7. от концов интервала 10, Ц. Такая политика равномерного выбора является превосходнои приближенной политикои для всего процесса, за исключением нескольких последних шагов, когда уже безразлично, употребляется наилучшая политика или нет. В частности, эза простая политика поиска приемлема для постановки на вычислительные машины.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
