Беллман Р. Прикладные задачи динамического программирования (2013) (1246769), страница 12
Текст из файла (страница 12)
К а о 1 щ а и, Мейойев е! Мой«1ея йе 1а Кссйегсйе Орегацоппсне, Пипой, Рапя, 1959. Р. Кояепв!!ен! апй А. 0)гоп!!а-Ноог), Бея с)го!х есопош!наев, йес!я!опя яеццеп!!е11ев е! Мшц!а!!оп, )улпой, Рапв, 1960. одномниггьгн пвописоы ввспиндвдинив (гл. г Р. А. Ба в и с1ь о и, 1эггнгг!а!гонь о1 Есопопнг Лна1лаз, Нагган! Уптвегяту Ргеыь СавЬпбде, Мальве(юаейя, 1947. ф 4. Некоторыс дальнейшие трудности нрн построении моделей рассмотрены в работах; К. Ве(!птап, С. С(агй, С.
Сга11, О. Ма!со!в апбр. К(ос(а г г(1, Оп йе сопатгнс1юп о( а пюййрегаоп, вв111-з1аде Ьияпезз даве, Орега!юпа Кеэеагсй, то1. 5, 1957, рр. 469 — 503. К. В е(! т а и апг( Р. В г о с 1г, Оп йе сопсергз о1 а ргоЫепт а~ге! ргоЫев-зо1г гпдг, Агпсг. Маг!т. МопгЫу, л о1.
67, 1960, рр. 119 — 134. 9 !О. Аналитический подход к этой задаче дзн в приложении Г, где коротко изложены нскгкорыс резлльгаты Бсллмана и Кар) ша. Талл же лана ссылка на дрлгл ю рабогл Каруша. ч 14. Эта работа по численномл решению флнкпиональпых уравнений, полученных из нриннипа оптимальности, была начата авторами в 1956 голл' и продолжена в ряде дрлтнх работ (в основном нсоплбликованных). Несколько работ, на которые чы бллсм часто ссылаться, были онлбликованы.
Первой нз ннх была статьи; К. В е(1пг а п апб Б. 0 г с л 1в и Оп йс соврв1а1(опа! ло!ч1юп о1 бупапнс ргодгавпнпд ргоссэзеа — Ь оп а гаспса1 агг маг(аге птобе! о( Мепде!, Орсгапопа Кеэеагсй, ло(. 6, 1958, рр. 65 — 78. и 27. Эти результаты изложены в статье: К.
В с11в а п апб Б. 0 г е у( в а, 0упав(с ргодгавпнпд апб йс ге1гаЬг10у о1 внййсогпропсп! г(сг!сез, Орсгагюпа Кеасагс11, го1. 6, 1958, рр. 200- 206. Нскоторыс дальнейшие результаты, а также многочисленные ссылки даны в работах; А. !. М а у п с, Ботс гс(!аЬйиу войс!а о1 ргггбвсйоп 1(псэ ж(й ареаа( гс(егспсс !о согпро1ег орсгайоп апб ьсйебв1(пд, Орсга!(опа Кеэеагс1г Оваггсг1у, то(.
11, 1960, рр. 16 — 30. О. Б. Бго!! е г, КАН0 РвЫка!югж оп Ке!шЬй!т, Т(те КАЬ(0 Согрогайоп, Кезеагсй Мсвогапбвгп КМ-2613, 1960. А. А. М в 11! п, Тйе ргсаеп! йеогу о( ачбгсЫпд апб вопле о1 (тз (в!в!с ггспбз, (ггбвагпа! Май. лггнг., то(. 10, 1959 — 1960, рр, 24— 44. Б. К. 5 ге(п, Тйе тайева!кгап аз ап схр!огсг, Бпепйк Анины сап, Мау 1961, р. !48 И. Зздачн, рассмотренные в Я 22 и 27, можно трактовать как зздачи целочисленного линейного и нелинейного програминрования. Хоти !'онори и другими авторачи было достигнуто некоторое продвижение в направлении решения этих задач с помощью симплекс-метода, многие из основных задач остались нерешенными. См.об этом О. В.
0 а п ! х г д, Оп йе ядпдкапсе о1аорвпд((ггсаг ргодгапнпгпд ргоЫсва ж!!Ь зове гпгсдсг л апаЫеа. Есипово!г!са, л о1. 28 1960, рр. 30 — 44. В работе можно найти др)кис ссылки. комминтлрии и виилмогрлфня Нскоторыс дрп.ис применения методов динамического программирования, ггредставаяюгцис интерес, можно найти в работах: %. А. Н а!! аггд Ы.
В и г а з, ТЬс дунаю!с ргоягавв!пр арргоасЬ то ччатсг геаоигсез бсче1орвепг, Зоиг. ОеорЬуз!са1 1Теьеагсй, чо!. 66, 1961, рр. 517 — 520. й бе О и си ! п, Орг!Шив гйзгпЬипоп о1 еИоги ап ехгепюоп о1 йе Коорвап Ьаа1с !Ьеогу, Орегайопз 17езеагсй, чо1. 9, !961, рр. 1 — 7.
На страницах журназов й!апайевеп1 5с!сисе, 1оигпа! о! 1Ье Бос!ету 1ог !обив!па! апб Аррйеб Ма1Ьептайсз, Орега1гопз 1Тезеагс1т 1;тиаг!ег1у, Зоигпа1 о1йе Орегаггопя 1Тсвеагси Бог!с!у о1 Авспса и речие Егапса1зе бе 1Тесйсгс!ге Орега!йппейе, так же как и других журналов, издаваслгых обществами по иссведованию операций других стран, можно найти бозьшос количество публикаций о других привожсниях динамического программирования. Интересное сообщение о решении задач распрсдевения, где нспоаьзчются довольно тонкие математические средства, дано в работе: 1.
Е. ОиЬ!пз апд Е. Н. Врап!ег, Нож то си1 а саде 1а1г1у, Авег. Май. Мопй1у, чо!. 68, 1961, рр. 1 — 17. ДОПОЛНИТЕЛЬНАЯ ЛИТЕРАТУРА Современное состояние теории линейного, целочисленного и выпуклого программирования детально освещено в книге О. В. О а п г т ~ Кг, 1йпсаг ргойгашпнпй апб ехтепагопз, Рппсетоп Сп1ч. Ргеш, 1963. (Готовится русский перевод.) 3 Р. Беаяиеи. С.
Дрейфус ГЛАВА й МНОГОМЕРНЫЕ ПРОЦЕССЫ РАСПРЕДЕЛЕНИЯ 1. ВВЕДЕНИЕ В предыдущей глзве мы нзшли оптимзльные политики для некоторых процессов распределения, когда в наличии имелся лишь один тип ресурсов и на его использование было наложено только одно ограничение. В этой главе мы хотим рассмотреть ряд более сложных задач, возникающих из более реалистических описаний экономических процессов. Как мы увидим, основной формальный аппарат динамического программирования переносится на эти случаи без изменения.
Тем не менее, на пути стандартного решения, полученного в главе 1, возникают значительные трудности. Чтобы преодолеть эти трудности частично нли полностью, мы применим ряд мощных и тонких математических приемов. Наиболее мощный из них — метод лагранжевых множителей. Хотя обычно считают, что множители тесно связаны с классическим анализом, мы покажем, что это не единствен. ная возможность их применения. Синтез метода функциональных уравнений динамического программирования и метода множителей Лагранжа позволяет разложить сложный процесс на более простые части. Это разложение делает разрешимыми весьма общие классы задач оптимизации. Мы используем также различные формы метода последовательных приближений.
Одно из ценных качеств теории динамического программирования заключается в том, что метод последовательных приближений можно применять как непосредственно к получающимся функциональным уравнениям, так и для определения оптимальных политик. Послед- 2] нлспнядвланин для днах типов нвстнсов 67 ний прием носит название «приближения н пространстве политика. Он всегда дает если не монотонную сходимость, то по крайней мере монотонную аппроксимацию. Классическим применением метода последовательных приближений является его приложение к функционзльным уравнениям. Оно совсем не обязагельно приводит к монотонной сходимости.
Как и в глазе 1, мы приведем большое количество численных результатов. Основная часть результатов этой главы базируется на экспериментах, и поэтому бессмысленно считать их окончательными или оптимальными. Как читатель убедится сам, сущестнуют возможности для важных исследований в этих областях, равно как н необходимость в них. 2.
ПРОЦЕСС РАСПРЕДЕЛЕНИЯ ПРИ НАЛИЧИИ ДВУХ ТИПОВ РЕСУРСОВ Прямым обобщением простого процесса распределения, рассмотренного в й 2 главы 1, является процесс разделения двух различных типов ресурсов на части, предназначенные для использования в ряде независимых технологических процессов. Пусть двз типа ресурсов имеются соответственно в количествзх х и у, а х! и у; — количества этих ресурсов, выделенные для 1-го процесса. Как и раньше, предположим, что задана функция полезности и!(лн у!) — доход от Г-го процесса, если на него оп!ущено х! ресурсов 1-го типа н у; — 2-го гипа.
(2.1) прн огрзничениях у', хг=х, х!)о, г-! ~х;у!=у, у,~о. ! ! (а) (2.3) (Ь) Стоящая перед нами матемагическая задача выбора наиболее эффективного использования ресурсов сводится к максимизации функции 2А7 переменных К(хг, х„..., ха! ун у„...! у7т)= У дг(ха, у!) (2.2) г=! 68 МНОГОМЕРНЫЕ ПРОЦЕССЫ РАСПРЕДЕЛЕНПЯ [ГЛ. и Мы назовем ситуацию, когда в наличии имеются два различных вида ресурсов, двумерным процессом распределения (независимо ог величины А!). Как буде~ показано, численное решение этоп задачи основывается на вычислении последоватег!ьностей функций двух переменных.
3. РЕКУРРЕНТНЫЕ СООТНОШЕНИЯ (2.5) которое является прямым следствием принципа опгимальности, Прежде чем исследовать вычислительную осуществимость этого алгоритма, обсудим другие задачи, которые приводят к функциям двух переменных. 4. ПРОЦЕСС РАСПРЕДЕЛЕНИЯ С ДВУМЯ ТИПАМИ ОГРАНИЧЕНИЙ Во многих случаях мы встречаемся с задачей распределения одного типа ресурсов при двух видах ограничений. В задаче о загрузке судна это, например, ограничения, налагаемые на вес и объем. Такой тип задач можно рассматривать как часы!ый случая предыдущен задачи, в которой х! и у, связаны соотношением у; = й!(х!).
Аналитическая задача в этом случае состоит в нахождении максимума функции К (хв хм..., ха!) = А ! (хг) + ата (ФД+ ... + дл (хл) (2.7) Идя по тому же пути, что и в первой главе, введем по- следовательность функ!гий [7А!(х, у)[: ДА!(х, у)=шах йх(х„хя ., хА', у! уь, ул), (24) !я,т! где максимум берется по области значения хп уп определя- емой условиями (2.3). Здесь А! принимает значения 1, 2, х и у — любые неотрицательные числа. )с!!я А!=1 имеем равенство у! (х, у) = А'! (х, у), а для А7) 2 — рекуррентное соотношение Б(х, у) = шах шах ~ди(хль уА)+ О «А! я О ЕА е +УА! ! (х — ха, у — ул)], (2.6) б) РЕКУРРЕНТНЫЕ СООТНОШЕНИЯ при ограничениях (а) (Ь) (28) 4, (]! (х!) (у.
(=! (с) 11редположив, что а( (х() и Ь! (х;) — монотонно возрастающие функции хп стремяшиеся к со, когда х(-и со, мы могли бы при желании сделать замену переменных, переводюцую а;(х;) в х; при условии, что х! изменяешься непрерывно. Если же х; принимает дискретное множество значенип, например О, (, '2,..., такая замена переменных невозможна. 3аметим, что ограничения (2.3), выраженные равенствами, мы заменили неравенствами. 11о тех пор, пока речь идет и о процессе и о численном решении, это несушественное изменение позволяет избежать рассмотрения некоторых математических тонкостей. б.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
