Беллман Р. Прикладные задачи динамического программирования (2013) (1246769), страница 3
Текст из файла (страница 3)
В настоящее время эта проблема оптимизации с~ала одной из основных проблем в технических и экономических науках. Необходимый для ее решения математический аппарат, казалось бы, имелся в готовом виде — это классический анализ и взриационное исчисление. Однако непосредственное применение известного аппарата столкнулось с значительными трудностями. Реальные задачи оптимизации не укладывались непосредственно в классические схемы, что вызвало к жизни пявдислоиив Рвдлктопя пвявводл 19 появление зз последние годы целого ряда новых мзтематическпх исследований.
Среди них важное место занимают работы Р. Белллгана и его сотрудников, результатом которых явилось соадание метода динамического программирования, Предложенный Р. Беллманом аппарат функциональных уравнениИ значительно расширяет возможности решения реальных проблем оптимизации. Его главным достоинством является хорошая «приспособленность» к использованию современной вычислительной техники.
Изложению метода динамического программирования и его приложении были посвящены уже известные советскому читателю книги: Р. Б е л л м а н, Динамическое программирование, ИЛ, 1960; Р. Белли а н, И, Гл и к с берг, О. Гросс, Некоторые вопросы иатематическоп теории управления, ИЛ, 1962; Р. Б е л л м а и, Процессы регулирования с адаптацией, Изд-во «Наука», 1964. Данная книга, впервые появляющаяся в русском переводе, существенно отличается как по содержанию, так и по методическим установкам от ранее вышедших. Ее основноя целью (и основным достоинством) является демонстрация приемов, позволяющих довести решение приклздных зздзч до численных результзтов.
Изложение проблем общего характера сопровождается подробным решением достаточно сложных примеров. При этом приводятся блок-схемы вычислительных плзнов, необходимые для постановки задач на цифровых вычислительных машинах, даются результаты вычислений, а также оценки требуемого машинного времени и объема памяти. В теоретическом отношении наибольший интерес представляют два момента.
Если в предыдущих работах Р. Беллмана динамическое программирование выступало совершенно оторванным от других методов оптимизации, то здесь изложение сопровождается сопоставлением с реаультатами современного 14 пввдисловив ивдьктовл пвивводл вариационного исчисления, основанного на использовании не только уравнений Эйлера, но и более сильных и тонких условий (например, условия Веперштрзссз или близкого к нему принципа максимума Понтрягина). Значительное внимание уделяется связи линейного и динамического программирования. Другим важным моментом является подробная разработка в данной книге идеи последовательного приближения в пространстве политик (управлениИ), позволяющей в значительной мере преодолеть главные прзктические трудности в применении динамического программирования. Вместе с тем надо отметить несколько апологетический характер изложения, в ходе которого авторы постоянно настаивают на решительном превосходстве метода динамического программирования над всеми другими методами оптимизации.
Читателям, практически работавшим в этой области, конечно известно, насколько эффективным в ряде реальных аздач является применение и иных идей, нзпример принципз максимума. К другим недостаткзм книги относятся некоторая небрежность формулировок и нередко встречающиеся неточности в изложении, которые, по-видимому, лишь чзстично удалось исправить при переводе. Однако можно быть уверенным, что, несмотря на указанные недостатки, данная книга будет весьма интересной, а главное, полезной для широкого круга читателеп. Перевод книги выполнили; О. В.
Шалаевскии (гл. 1), А. П. Хусу (гл. !1, Х вЂ” ХН и приложения), Н. М. Митрофанова (гл. В! — 'г) и А. А. Первозванския (гл. т'! — !Х). К большинству глав редактором были сделаны дополнительные библиографические указания. А, Первозвалскпй Памяти ДЖОНА ФОН НЕЙМАНА, вдохновителя и друга ПРЕДИСЛОВИЕ АВТОРА В период после второй мировой войны стало ясно, что целый ряд интересных и важных видов деятельности можно трактовать как многошаговые процессы решения. Вскоре было обнаружено, что возникающие при их исследовании магематическне вопросы выходят за обычные границы классического анализа и требуют для своего успешного разрешения новых методов. Классические методы анализа и вариационного исчисления иногда оказывались ценными и полезными и в этих новых областях, однако они были явно ограничены по диапазону и гибкости и определенно недостаточны, когда речь шла о получении численных ответов.
Признание этих фактов привело к созданию целого ряда новых математических теорий и методов. Среди ннх была теория динамического программирования, представляющая собой новый подход, основанный на использовании функциональных уравнений и принципа опгимальности и учитывающий возможности, заложенные в развитии вычислительной техники. Первой задачей, которую мы ставили себе при разработке теории, было исследование ряда видов деятельности в области техники, экономики, промышленности и в военном деле, с целью выявления круга задач, которые могут быть сформулированы в терминах динамического программирования, а также выяснения уровня их сложности.
Это не всегда являлось стандартной операцией, так как при описании процесса оптимизации имеется много шщсобов выбора параметров состояния и критериев. Часто случается, что определенный тип математической модели хорошо приспособлен к определенному же типу аналитического подхода. Вообще три принципиальные стороны математической модели — смысловая, аналитическая и вычислительная — должны рассматриваться в единстве, а не по отдельности. Следовательно, некогорая 18 пгвдисловив автова доля усилиИ идет на перевод словесных задач, поставленных в таких неопределенных терминах, кзк эффективность, возможность, стоимость и т. д., в точные аналитические задачи, требующие решения уравнениИ и определения экстремумов. Когда подобная переформулировка уже выполнена, важно изучить связь между решениями получаемых функциональных уравнений и оптимальными политиками первоначального процесса решения.
Значит, прежде чем переходить к численному решению или структурному анализу, необходимо исследовать вопрос о существовании и единственности решения. К счастью, в ряде важных случаев доказательство суцгествования и единственности осуществляется легко, так что можно с уверенностью приступать к изучению природы оптимальных политик и максимального дохода, используя основные функциональные уравнения. Сначала мы сосредоточим внимание на тех задачах, когорые по своему характеру формулируются как многошаговые процессы решения. Затем мы воспользуемся привилегией математики изучать любой процесс, который можно рзссматривать как многошаговый процесс решения.
Таким путем мы углубимся в изучение различных разделов вариационного исчисления, в частности, рассмотрим задачи о траекториях и процессы управления с обратной связью. После этого начального периода захвата территории и укрепления на ней мы чувствуем, что настало время выполнить некоторые численные исследования. Хотя с самого начала мы имели в виду именно эту цель и потому постоянно изучали осуществимость наших процедур с этой точки зрения, все же совершенно необходимо провести до конца детальное численное решение. Тот, кто хотя бы даже немного имел дело с вычислительными машинами, скоро начинает относиться с осторожностью к предлагаемым решениям, как бы изящны они ни были.
До тех пор, пока каждая отдельная стадия численного решения задзчи тщательно не проверена и не апробирована практикой, нельзя быть уверенным, что имеющиеся отграничения по точности и устойчивости, объему памяти или загратаы времени не окажутся препятствиями на пути осуществления полного решения. Кроме того, вскоре выясняется, что никакое решение конкретной задачи не является стандартным. Воспользовавшись индивидуальными структурными особенностями, всегда можно сократить требуемое время, повысить точность, приблизить пяздисловив автова модель к резльности без кзкой-либо дополнительноИ потери времени и т.
д. Теория динамического программирования хорогио приспособлена для учета индивидуальных особенностей конкретных процессов. В 1955 году мы начали системзтическое исследование вычислительной реализуемости динамического программирования. Мы собрали целый ряд задач оптимизации из самых разнообразных областей и различными путяии опробовали наши методы. Цель настоящей книги — показать, что динамическое программирование действительно может быть использовано для решения ряда неприятных вариациош<ых задач и задач оптимизации, интересных и взжных для приложений. Некоторые из них лишь с трупом можно было трактовать с помощью других методов, некоторые рассматривались только на основе метода «проб и ошибок> и «научного гадания», а некоторые казались совершенно ускользающими от других методов, Польза от наличия достаточно стандартизованного аппарата для некоторых больших классов задач из области чистой и прикладной математики велика.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
