Беллман Р. Прикладные задачи динамического программирования (2013) (1246769), страница 70
Текст из файла (страница 70)
Если исходная траектория допустима, сЛО берется равной нулю. 452 )п. ш вычислительный мвтод Решим теперь систему линейных уравнений Ар= ~~'„)„У)Я1А,!У1+ [Ь'„Л,С„)Л,ГЕ)~ Л,А), РЗ) г=о !=о т г 112= ~~ 1,Г~)Л,(0)1Аглг+ ~~~',).,(0) ~йод 124) г=о !=о относительно Ггг и Йм которые следует использовать в уравнении (20) для улучшения Ачг в целевой функции и поправки 50 в конечном знзчении дополнительно~о условия. Указанный способ можно использовать для включения любого разумного числа дополнительных конечных условий.
В неопубликованной работе Брайсона приведенный выше метод обобщен таким образом, что можно требовать максимального улучшения целевой функции при заданном фиксированном значении суммы т Х Ва)', г-о а также разви~ы методы, которые предохраняют нас ог требования несовместимых изменений в целевой функции и дополнительных условиях. Однако этот анализ лежит за пределами настоящей книги. БИБЛИОГРАФИЯ 1. А. Е. Вгуооп, Р..!.
Саго!1,%. Г. Веп!гав апй М!1гагп1, Ве!егпнпайоп о1 йе 1йг ргоягав йаг ппп1виеа ге-еп!гу Ьеа!1пя чг!!Ь ассе1ега!!оп ог ганзе сопя!та!пга по!пя а а1еереог йоосеп! соври!айоп ргосег!пге, 3. !по!. Аегоярасе Бс!епсеа. 2. Н. 3. Ке!!еу, бгао!еп! 1Ьеогу о1 ор1!ва1 !1!яЫ райю, Ак5 2оогпа1, то1. 30, по. 10, Ос1оЬег 1960. ПРИЛОЖЕНИЕ 1Ч О НОВОМ ФУНКЦИОНАЛЬНОМ ПРЕОБРАЗОВАНИИ В АНАЛИЗЕ: ПРЕОБРАЗОВАНИЕ МАКСИМУМА Р. Бвллман и Б.
1(аруш 1. ВВЕДЕНИЕ В главе ! мы видели, как часто в математической экономике и исследовании операций сталкивзются с задачей определения максимума функции т'(хв хя, ..., хм)=У1(х1)+Уз(хя)+...+Ум(хм) (1) в области )с, определяемой соотношениями х,—;х,+...+х =х, хг--лО.
Г!ри различных допущенная относительно Гг эта задача может быть исследована аналитически (см. Каруш [1), [2)); аналитически она может быть рассмотрена также с помощью теории динамического программирования [б) и, конечно, вычислительным путем, как это было сделано выше. В связи с решением этой задачи естественно ввести понятие «свертки» двух функции т и и, л =у ли, определяемой равенством Л (х) = шах [Г(у) + и(х — у)].
(2) а у л 454 О ноВОН Функционлльном пРВОВРАЗОВАнни [п, гч Для более обшего исследования удобнее ввести вместо этого свертку л =7 З В, определяемую равенством п(х)= шах [у(у)у(х — у)]. О у .к Легко видеть, что операция З коммутативна и ассоциативна при условии, что все входягцие в нее функции неотрица- тельны. По аналогии с соотношением между преобразова- нием Лапласа н обычной сверткой, к у(у) ч 4 (х)= ~у (у)д(х — у)Ыу, о естественно искать функциональное преобразование Л4 ( г') = тч, обладаюшее свойством Л4(у'З тг)=Л4(у)Л4(д), (5) т.
е. гт'(«) = Р(«) О(«), где Н, гч, О представляют собой соответственно преобразования функций Ь, у, д. Мы покажем, что преобразование М существует и имеет очень простой вид. Вдобавок, в ряде случаев Л4 ' имеет весьма простое и изяшное представление. 2. ПРЕОБРАЗОВАНИЕ МАКСИМУМА Пусть преобразование (4) определяется уравнением Р(«)=гпах[е хху(х)), «)О.
(7) х>О Будем предполагать, что у(х) непрерывна и неотрицательна прн х~ О. Кроме того, так как Р(«) не изменится, если у заменить на ее монотонную огибаюшую, то мы будем рассматривать (7) только для монотонных неубывающих функций 7. оБРАтный ОПБРАтоР Докажем теперь (б) прямым мегодом, используемым при обычной свертке. Имеем: [е" шах ]г (у)д(х — у)Ц= О у х шах ]е ху'(у)д(х — у)]=шах шах[ ]= у~а х)у [г (у) шах [е ' г(х — у)Ц= хтх у [е УУ г (у) шах [е "' е(тв)Ц = и~я [еюху (у)] шах [е 'д(ю)]=е(г) 0(г), Н(г) = шах х>О шах х)О п1 ах уахо шах ~О (8) шах у)О я УО что и требовалось доказать.
Чтобы гарантировать сушествование преобразования Р= = Л1(г) для г ) О, достаточно предполагать, что у удовлегворяет соотношению вида г (х) = о[х'] для х ~ О, где е =-. О. 11реобразование Е является убываюшей функцией, непрерывной для г)0; если с=О, то этоостается в силе и для г) О. 3. ОБРАТНЫЙ ОПЕРАТОР Р'(г) — =(~'(х) — гУ(х))е "' — ху (х)е "' — '= = — ху (х) е * — (9) — хх УГх Значит, х — р (г)1Г(г) или г' ( ) ]-хг- (г)=О. (Щ) Определение сушествовзпия и единственности Л ' представляет некоторые трудности, и сейчас мы рассмотрим только частные случаи.
Если для г)0 максимум функции г"(х)е "' можно найти с помошью дифференцирования, то мы находим максимизируюшее значение из уравненияу'(х) — гг (х) = =О. Лопустим, что это уравнение имеет единственное решение х =х(г) и Их/г(г ~ 0 (и, следовательно,(0). ):(ля этого значения х мы имеем гУ(г)=е "у(х). дифференцируя эго соотношение по х, получаем; Но это в точности совпадает с соотношением, которое дает значение г, минимизируюшее функцию Р(г)ех' при фиксированном х. Следовагельно, мы имеем требуемую формулу обрзшения гх(х) = пил ехх Р (г). »О (1 !) Более простым путем получения этого соотношения является следуюший. По формуле (7) мы имеем для х'=-0 Р(г))е "г'(х), (12) откуда Р(г)е"')7'(х).
Если имеет место взаимно однозначное соответствие между значениями х и г, то мы имеем неравенство пип 7«(х)е х)У(х), при этом для одного зна- О чения достигается равенство, откуда следует (11). 4. ПРИМЕНЕНИЕ Пусть У(х)=шах [г! (х!)гя(х!)...7 (х )), (13) где область й — такая же, как в (1). Тогда по индукции Л' Ю л4 (7) = П «и (г"1) или гт (г) = Д гтг (г), (14) откуда формально следует: У (Х) = ПИП [ Ехх П Рг (г) ~. х»О (15) Аналогично, если имеется уравнение «восстановления» У (х) = а (х) + !пах [7 (у) п(х — у) 1, (1О) О«яд х то мы имеем формальное решение (17) гдь.4=А4(а), а=Л4(д). 4М о новом Отнкционлльном пяяовялзовании [п. !ч иппипнение 457 БИБЛИОГРАФИЯ 1.
ВА К а г н вЬ, А г$нен!пп тоде! 1ог ап гинеи!огу ргоЫет, ОрегаИопв $7евеагс1г, чо1. 5, 1957, рр. 693 — 703. 2. В. К а г н в Ь, А бепсга1 А!дог!!Ьпг 1ог 10с Орита! ЕВвгИЬн!гоп о1 ЕПог1, 5$аггап. 5с1., чо1. 9, Ьго 1, 1962, рр. о0 — 72. 3. $7. Ве1! т а и апг$1$г. К а го в Ь, Оп а пен !нос!!опа! 1гапв!огт ги апа1уяк 15с Мах!пгнт Тгапв$огпг, Внг!. Агпсг. Мапп 5ос., чо1. 67, 1961, рр.
501 — 503. 4. $7. В е! 1т а п апг$ %. К а г н в Ь, Ма!!вета!1са! Ргодгапип!пд апг1 !Ьс Махипнт Тгапв1оггп, 1.5ос. 1пднгиг. Арр1. Ма!Ь., го1. 1О, 5$о 3, 1962, 550 — 567. 5. $$. Ве! 1гп ап, Оупат!с Ргопгапгтгпп, Рипсе!оп Йп!чегвд!у Ргевв, Рнпсс!оп, Кечг уегвсу,1957. П Р И.Л О Ж Е Н И Е т' СЧЕТНАЯ МАШИНА ЙАЮ-ДЖОН НИАК С. Дрейфус Ббльшая часть вычислений, приведенных в настоящей книге, выполнена на вычислительной машине Лжонниак корпорации ВАХР. Поскольку в текс~е книги иногда делаются ссылки на время вычислений и другие данные, свойственные этой конкретной машине, мы перечислим вкратце основные характеристики машины Джонниак, какой она была в момент наших исследований по динамическому программированию. Машина, сконструированная по Принстонскому проекту и названная в честь Джона фон Неймана,имела магнитное оперативное запоминающее устройство на сердечниках в 4000 ячеек, магнитный барабан емкостью в 12000 чисел и не имела магнитной ленты.
Ввод осуществлялся с помощью перфокарт, а вывод — через перфоратор по 900 строк в минуту. Каждая ячейка памяти хранила 40 двоичных знаков и содержала илн числовые данные, или две одноадресные команды. Сложение с фиксированной запятой двух чисел требовало около 0,000080 секунды, а на умножение или деление расходовалось до 0,001500 секунды.
Операция с плавающей запятой получалась с помощью интерпретируюшей программы, и при этом вычисления замедлялись примерно в десять раз. В целом характеристики Вжонниак были сравнимы с ее . современником — вычислительной машиной 1ВМ-701. 71ля грубого перевода машинного времени, упоминаемого в тексте книги, на время современных машин(приблизительно 1960 года) нужно поделить его на 10.
Р. Гглллгпн, С. Дреафтс Прикладные задачи двнлчического прогрзмчировпгия М, !96» г., 160 стр. с клт Рсдантор А. А. Корбут Техн. Редактор М Ф. Бртднл Корректор Г. Д. Долгрипн Сдано в набор 4гтЛП 1964 г. Подписано к печын 12Л 196фз г. Бумага 84Х108туз "г Фнз. псч л. 14,34 Уел, псч.л. 23,58 Уч,-над л, 2Г87. Тираж 9000 зкз, Пена «инги ! р, у! к, Заказ зй П98.
Издательство «Наука, 1'лазили релакпип физико-математической литературы, Москва, 0-?1, Ленинский проспент, 16, Ленпнградска» типография К" 1 «Печатный Лва,з имени А. М. Горького ! лавполигр гфпромаз ! осудлрственпого комитета Совета Минисзров СССР по печати, 1 атчинсказ, 26, .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
