Беллман Р. Прикладные задачи динамического программирования (2013) (1246769), страница 23
Текст из файла (страница 23)
200 — 206. 32. Транспортной залаче Хичкока — Купманса посвящено огромное число работ. Первое утонченное иатематическое изучение залая транспортировки и задачи общего линейного программирования выполнено Л. В. Канторовичем в 1939 г. Его работа «Математические методы в организации и планировании произволства», Изд. ЛГУ, 1939 (повторная публикация в сборнине «Применение иатеиатики в экономических исслелованиях», Соцэкгиз, 19о9) недавно переведена на английский язык. См.
Также Г. Ы Н !1с5 с о с 1с, ТЬе бысг»Ьийоп о1 а ргобнс! 1гов яеяега1 яоигсея !о пивегооя 1оса193ся, Ю. Май. РЬуякя, то!. 20, 1941, рр. 224 — 230. К. !) о г1в а п, Р. А. 5 а в н с!я оп апд К. 6 о!он», Ыпеаг Рго!аппп!пц апб Есопо»пк Апа1) янн Мсбга и-Н»В Воо)с Со., 1пс., ест Уог)с, 1960, СЬар1ег 5.
О. В. О а п ! я! й Арр!!сайоп о! !Ье янпр1ех всйоб со а ггапярог1аг)оп ргоЫев, Асйлгу Апа1уяв о1 Ргобнс!!Оп апб Айосайоп, 3. %1!еу апс1 8опя, Нечс Тот)с, 1951, СЬаргег 23. Т. 8. М ос т 1с)п, ТЬс аяяйпгпепг ргоЫсгп, Ргос. 5)х!!г 5тгпроИигп 1п Арр!!ес1 Майегпагкя, то!. 6, 1953. Т.
С. К о о р в а п я апб 8. К е с ! е г, А в обе! о1 1га пярог1 а11оп, 1Ы й, СЬарссг 14. М. М. Г1оо 6, Оп 11»с НйсЬсоск ТВаг!Ьнс)оп ргоЫсгп, Раайс 3. МатЬ., чо1. 3, 1953, рр. 369 — 396. 1.. Г о г д апс) Тт. К. Г н)1с е г я о п, Махггпа) Вож 11»гоняЬ а пе1- чгоггс, Сапайап Л Май., то!. 8, 1956, рр. 399 — 404. Т. Г н !с а о, А соврнга1юпа1 пгейоб 1ог с)упав!с 11псаг ргоцгавв!ОК, Л Орега!1опя КеяеакЬ Эос. )арап, чо!. 2, 1960, рр. 98— 113.
Г. С. Т о я с а п о, Ап Епй!пеег!ИК Апа1уяН о1 Сагйо — Ьапб!!пй— )Х, Пера~!веп! о! Епя!Яеег1гсй», Оп!дега!у о! Са!Иогп)а а! 1.оя Агг3е)ея, 1960. 140 МНОГОМйВНЫН ПноикбсЫ ВДСПВВДВЛВИИЯ !ГЛ. Н 0г. 8 т чг а г с, ТЬе 1прйа! зо1ц1!оп о1 гйе !гапэрог!абоп ргоЫсш, Орсгайопэ Кеэеагсй, то!. 8, 1960, рр. 727 -729. В перечисленных вьнцс статьях иснользуютсн метолы линсйно~ о программировании или итеративныс методы, построснныс спсциально для этой конкретной задачи.
Аналитическис рассуждения в тсксте заимствованы из статьи; К. В с!1 ш а п, 74отсэ оп йте !Ьсогу о1 бупаш!с рго8гапгпг!пй: !гапзрог!айоп шобс!з, Мапа8сшсп! Бс!епсс, чо1. 4, 1958, рр. 191 — 195. В силу интерсса, который предстзвзяст сама задача, а такжс с цслью демонстрации силы метода послсдоватсзьных приближений в дальнейшем были получены численные результаты.
ф 43. Систсматичсскос изложение истода послсдоватсльных»риближсннй лано в статье: К. В с11 ш а п, Рлпс!!опа! ецца!!опз апб аиссеаыте арргох!п»айопз !п Впеаг апб попйпсаг рго8гапип!пй, Хата! Кезсагсй Ьо8ы!. О., чо!. 7, 1960, рр. 63 — 83. О некоторых других аспектах метода последоватслыгых приближений см. статью: К. К а!ай з, Оп поп1!пеаг гВПегепца1 сцца!!опа, !Ьс шахппцш орега1!оп апб гпопо1опе солт'е«8спсе, 7.
Майн апб Мссй., то!. 8, 1959, рр. 519 — 573. Здесь систематически использован мстод квазилинсаризацин, истоки которого лежат в работе Чаплыгина. б 44. Дальнсйшсс рассмотренис метода приближсний в пространстве политик дано в книгах: К. В с 11 ш а п, Пупаш!с Рго8гашш!пр, Рг!псс!оп Пп!тога!!у Ргсаэ, Рипсе1оп, !»!счг Яегзеу, 1957 !русский перевод; Р. Б с л з и а и, Динамическое программировайие, ИЛ, 1960!. К. В е11ш а п, Абар!!тс Соп!го1 Ргосеззез. А Оцгйсд Тонг, Рппсе1оп Сшчегэйу Ргеэа, РНпсе1оп, Хсж уегэе15 1961. !русский перевод; Р.
Б с л л м а н, Процессы регулирования с адантацисй, М., Изл-во «Наука», 1964Б ф 46, Первоначальный вариант риг. 32, помсщснный на стр. 45 книги Р. Бсллмана «Дипамичсскос програимированис», неверен. Мы благодарны А. Б. Брайсону за обнаруженис ошибки. ф 48. Метод динамического програмиирования выгодно сочетать с градиентным л«етодои или с методом Ньютона для решения систсм нелинсйных уравнений; это позволяет повысить быстроту и точность числснного решения. Успех градиентных мстодов, метода Ньютона и других итсративных иетодов обычно зависит от того, начат ли процссс доста- кпммеитхРип и пиплиОГРхипя !4! точно близко от экстремума.
Это можно часто обеспечить, используя метод фтнкционзльиых уравнений с грубой сеткой. В качестве альтернативы мы можелг излгельчзп, сетку по мере дошагочно близкого ириближснцн к экстремуму. Этот метод действует вполне хорошо ири игслсдованпи и<которых задач из статистической мгханикп. См. Р,гботт: К. К г1 и с !т ! апб Я.
%. С а 1т п, ТЬсогу о$ Попка!и %айк $п Огг1сгеб Вгпгсгпгск — И, Ршг Арргохгша1гопк 1ог 5$оптего Тешрсгагпгс., 11одгнк Ксксагсц 1.аЬогатопек, Кскезгс1т Ксрогт, Ко. 177, 1961. Пскоторые математические постановки задач теории организзции в рамках процессов принятии решений даны в работах; й М а г к с 1т а К, Точгагбк зп ссопош1с Итсогу о1 огдапизцоп апд ш$огшзцоп, СЬар.
14 ш Рос!к|оп Ргоссккск, Т1иаИ, Пзщк апд СоошЬк, ебк., 7о1тп %Ису апй Бопк, 14ечг Уогй, 1954, 3. М а г к с Ь а К, Е1ешепгк $ог а Итеогу о1 1езшк, Мападегпсп1 Басист, то!. 1, Хо 2, 1954, рр. 127 — 137. К. К а 6 и с г, ТЬе 1шсаг 1саш: ап ехзшр1е о$1гпеаг ргодгашшшд ипг1сг ипсегтапИП Ргос. Бссопг1 51 шрокгпгп ш 13псзг Ргодгашпипд, $4айопа1 Во!сап о1 51апбагбк, %акЫпд1оп, 195тб. К. К а 6 п е г, ТЬе арр1йа1гоп о1 Инсат ргодгагпшшд 1о 1еаш бес!- к!Оп ргоЫешк, Мападсшеп1 Бе!сисе, то1. 5, $т$о 2, 1959, рр.!43— 150.
С. В. М с С и 1г е, Бошс 1еаш шоде1к о$ а ка1ек огдзшта1$оп, Мападспгспг Бг1спс1с, то1. 7, 1961, рр. 101 — 130. Построение математических лгодслей обсуждается в работах: К. В с 11 гп а и, С. С!а г К, С. С г а 11, $7. М а! с о! ш апб Р. М. К ! с с г а г б г, Оп йе сопк1гисгнзп о1 а шиц1ктаде, шой-рсгкоп Ьоипекк даше, Орсгацопк Кексагси, то1. 5, !957, рр, 469 — 503. К. В с 11ш а п апд Р. В г о г К, Оп йе сопссрм о1 а ргоЫегп апб ргоЫспг-яо1тгггд, Апгсг, Май.
Моп1Ыт, то1. 67, 1960, рр. 119 — 134. Анзлиз общей проблемы распределенип ресурсов содержится н работах: К. Д А г го чг апд 1.. Н и г чг1с т, Песен!гайка!!оп апб сошрщаиоп гп гскоагсс айосз1гоп, Еккатк 1и Есопописк апб Есопопшгыск, 15и сгкцу о$ $т$огй Сагойпа Ргскк, рр. 34-.104. 11 Р. К а г г е ш а и, Ргодгагппипд йе корр1т о1 а ктга!сд1с пштепа1, Раг! $. А попк1осйак1й гпог1е!, Как а1 Кскеагс1т 1.од!к1, О., то1. 7, 1960, рр. 261 — 279. А. $9 опт ото, Ехр1огайоп кециепцсйе, Бгод!а!ге бе Соорега11оп Тесйпгйие би Сотсгпешспт Ггапдагк бе!а лог!е1е й'Е1естгоп19ое ет ЕИАо1оптацкше, 1961.
Я 55 — 53. Подход к задаче о «трудной персгграве» был дан Б. Шварцем в работе: 142 многомБРнын пРОМРссы РЛББРРднлнния !Гл. и В. Б с!» «ч а г ! ж Ап апа1»гк вой»об 1ог сВПкн1! егозя!пй ролл!ез, Майн Май«то!. 34, 1961, рр. 187 — 193, основанной на теории графов и топологии. Приведенные здесь ре- зультаты взяты из стаж.и: !!.
Ве11нтап, Пупапт!с ргойгапнн1ой ан«1 сВПкнй егозя!ой ратт1ез, Мзйь Май., го!. 35, !962. Аналогичные задачи, акзючзющие переливание рззличного роаа жидкостей из одного типа сосудов в другой для лолученин смеси требуемого тина, можно рассматривать методами динамическо»о программирования. См. задачу 38 на стр. !24 книги Р. Беллмана «Динамическое црогрзммированне».
Дополнительная литература Идеи, высказанные в ф 24, весьма близки к методике испо«ьзования «объективно обусловленных оценок», предложенной в книге: Л. В. К а н т о р о в и ч, Экономический расчет наилучшего непользования рсс1рсов, Изд-во АН СССР, 1969. Первая математическая формулировка тра!«спорт»~ой задачи в узком смысле была дана в работе; А. Н.
Т о л с т о й, Методы устранения нера»тиональных перевозок нри планировании, «Социалистический транспорт», !939, Уф 9 По поводу современного состояния проблемы см. сборник «Математические методы в планировании и эксплуатации на транспорте», Тртды научного совещания о применении математических методов в экономических исслсдозаниях и планировании, т.
»', Изд-во АН СССР, !961. Метод С. А. Чаплыгина, содержзщий исходныс положения так называемой квазилинсаризации, изложен н учебнике: Г. И. Петр о иск и й, Лекции по теории обыкновенных дифференциальных»равнений, изд. 4, М. Л., ГИТТЛ, 1962. По поводу построения л»оделей распределения ресурсов см. также дополнительнуго литературу к главе Тг!!. 'ГЛАВА П! ОДНОМЕРНЫЕ ПРОЦЕССЫ СГЛАЖИВАНИЯ И СОСТАВЛЕНИЯ РАСПИСАНИЙ Е ВВЕДЕНИЕ В двух предыдущих главах мы показали, что семеяство статических процессов распределения ресурсов можно рассматривать как динамические процессы и потому к ним применим метод функциональных уравнений динамического программирования. В настоящей главе, также основанной на атом подходе, мы хотим изучить некоторые процессы из области составления расписаний, которые естественным образом возникают в динамической форме. Наряду с выработкой численного алгоритма согласно намеченному ранее плану в ряде случаев л1ы получим аналитическое описание оптимальной политики и аналитические представления для функции дохода.
Результаты такого рода интересны не только вследствие их внутреннего изящества, но и потому, что точные решения для простых случаев могут быть использованы при приближенных решениях более сложных задач. Аналогичную ситузцию можно наблюдать в теории дифференциальных уравнений. Здесь же мы имеем гораздо ббльшую гибкость, так как приближения могут производиться как в пространстве функций, так и в пространстве политик. Важным моме1пом, который будет неоднократно подчеркиваться во всех последующих главах, является то, что метод функциональных уравнений может быть применен различными способами, как в комоипапиях с классическими методами, так и в чистом виде — в зависимости от поставленной цели. !44 сглаживания и составлвнив Расписаний !Гл, н1 Разница между тем, что мы называем явным аналитическим решением, и тем, что мы называем численным решением, есть разница скорее форм, нежели содержания.
И то и другое представляет собой алгоритм получения некоторых чисел. Во многих случаях явное решение практически бесполезно для вычисленных целей. Простейшим примером такого явления служит решение систем линейных уравнений, где решению по правилу Крамера, требующему вычисления частных двух определителей, в случае систем большого порядка предпочитают итеративный метод. Много аналогичных примеров можно найти в теории дифференциальных уравнений. 2.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
