Беллман Р. Прикладные задачи динамического программирования (2013) (1246769), страница 4
Текст из файла (страница 4)
Во-первых, мы имеем систематическое средство получения точных числовых ответов на конкретные числовые вопросы в задачах руководства и контроля, составления расписаний и управления запасами. Во-вторых, мы имеем средство получения точных ответов, которые можно использовзть в качестве этзлонз для приближенных результзтов, полученных другими, возможно, более простыми и быстрыми путями. Таким образом, мы можем проверять действенность приближенных методов.
При столкновении с новыми классами математических задзч, которые не поддаются решению с помощью существуюпгих аналитических средств, краИне важно уметь исследовать классы численных решениИ в надежде распознзть поведение решения. Они могутдать ценный ключ к выяснению аналитической структуры решений и таким образом направить наши исследования в выгодном направлении. В конце концов,математика зарождалась как экспериментальная наука. Если мы не хотим духовно оскудеть подобно иным кабинетным философам, мы должны время от времени, засучив рукава, приниматься за некоторую черную работу. С помощью динамического программирования и вычислительных машин мы можем систематически заниматься математическим экспериментированием.
20 пягдисловие автова Заметим, наконец, чго во многих случаях нас больше интересует природа огнимальных политик, чем точные числовые значения, которые обращают в максимум или минимум целевую функцию. Точные оптимальные политики для простых процессов решения могут быть нспользовзны для получения простых приближенных политик в более сложных процессах решения. Опишем теперь вкратце содержание различных глав.
Основное функциональное уравнение динамического программирования имеет вид у(р)=шах(Н(р, д, у(Т(р, д)))~. Предмет может быть подразделен несколькими способами; можно принять зз основу точную форму уравнения (1), илн тип процесса, приводящего к (1), или же свойство детерминированности, стохастичности или адаптивности и т. д. Для целей численного исследования целесообразно сначала обрагить внимание на размерность вектора состояния р.(В главе ! мы рассматриваем неко~орые простые процессы, приводящие к последовательностям функций от одной переменной, с целью подвести читателя как к основным идеям динамического программирования, так и к стандартным вычислительным методам, которые будут неоднократно применяться в дальнейшем. Обладая необходимыми предварительными сведениями, мы рассматриваем в главе 1! некоторые интересные задачи, приводящие к последовательностям функций от двух переменных.
После обсуждения трудностей, связанных с размерностью, которые начинают явственно вырисовываться на горизонте, мы показываем, как в ряде случаев их можно смягчить с помощью множителей Лагранжа. В главе !!! мы сосредоточиваем наши усилия на основном предмете книги и даем некоторые аналитические и численные решения для различных классов процессов сглаживания и составления расписаний.
Глава !'тг посвящена исследованию задач динамического программирования, которые возникают в ходе численного решения самих задач динамического программирования. уравнение (1) требуе~ определения максимума по д. Поскольку по ряду причин, указанных далее в тексте, нежелательно пявдисловив лвтоял 2! использование методов классического анализа, мы должны будем прибегнуть к процессу поиска для определения максимизируюшего значения д.
В некоторых случаях можно выдержать процесс прямого перебора; в других же случаях существенно использовать секвенциальный ") метод. Глава является введением в эту очень трудную и увлекательную область. До сих пор речь шла о дискретных во времени пропессзх. В главе.7 показано, как теория динамического программирования может быть использована для получения очень простой трактовки вариационных задач, содержащих функции от одной независимой переменной. Принцип оптимальности приводит к нелинейному уравнению в частных производных, из которого быстро получаются все классические результаты.
В главе 7! мы переходим к одному из наиболее интересных современных приложений динамического программирования — определению оптимальных траекториИ. рассматриваются конкретные задачи и даются их численные решения. Следующая глава Л! является кратким экскурсом в область математической экономики. Используя модель затрат-выпуска, ставшую знаменитой благодаря работе Леонтьева, мы рассматриваем оптимальную эксплуатацию комплекса взаимосвязанных отраслей производства.
В главах Ч)!! и )Х рассматриваются различные аспекты быстро развивающейся теории процессов управления. Первая нз этих глав посвящена рассмотрению различных типов детерминированных стохастических и адаптивных процессов; вторая следует работе Масанао Аоки и посвящена некоторым вычислительным результатам. Главз Х представляет собой краткое введение в очень интересное и благодарное исследование процессов оптимизации, связанных с линейными уравнениями и квадратичными критериями. Эти результаты важны не только сами по себе, но также и благодаря возможности их использования при Решении более сложных задач методом последовательных приближений.
г)злее иы рассматриваем несколько подробнее марковские процессы решения и дзем ряд применений. Некоторые важные части этой главы основаны на работе Р. Говарда. *) То есть метод последовательного миогошагового поиска, в котором нл каждом шаге используется информация, полученная иа предыдущих шагах. (При.я. ред.) пввдисловив автова Последняя глава посвящена некогорым предвзрительным результатам по точности и устойчивости метода динамического программирования.
Эта область исследования относительно мало разработана и многие важные задачи остаются здесь неисследованными. В конце текстз помещены четыре приложения, содержащие более подробные результаты, з также некоторые более поздние результзты, полученные О. Гроссом, М. Фреймером и В. Кзрушем в сотрудничестве с рзаличными авторзми. Пятое приложение содержит описание вычислительной машины КАКО-Джонниак, использованной нами при вычислениях. Насколько это было возможно, мы старались сделать книгу самостоятельной. Читатель, желающий познакомиться с более глубоким обоснованием динамического програмлаирования, может посмотреть книжку Р.
Беллмана «Динамическое программирование», М., ИЛ, 1960; детальное рассмотрение современной теории процессов управления можно найти в книге Р. Беллмана «Процессы регулирования с адаптацией» (изд-во «Наука», 1964). Многочисленные ссылки на применения и оригинальные научные статьи можно найти в конце глав. Желающим познакомиться с обширной библиографией мы рекомендуем книгу: Ч. К!1еу апд Я. Оа за, 1.!пеаг Ргойгаппп!пд апд Аззос!а!ед Тесин!9цез. ОрегаВопз Кезеагсй О!Все, Зойпз Нор!Дна Ргезз, 1958.
Ряд приведенных результатов получен в сотрудничестве с другими математиками или же основзн на их индивидуальных усилиях. За использование этих исследований мы приносим, в частности, благодарность М. Аоки, Т. Картано, М. Фреймеру, О. Гроссу, Р. Говарду, С. Джонсону, Р. Калаба и В.
Карушу. Помещенные в книге математические результаты были получены в процессе исследований, выполненных в корпорации КАНО по широкой программе научных изыскзний для военно-воздушных сил Соединенных Штатов. Нам хотелось бы выразить блзгодарность за возможности, предоставленные нам этой программой. Ричард Беллман, Стюарт Дрейфус Корпорация ЯАМ11 Санта Моиива, июль 1961 ГЛАВА 1 ОДНОМЕРНЫЕ ПРОЦЕССЫ РАСПРЕДЕЛЕНИЯ 1. ВВЕДЕНИЕ в области значений, задаваемой соотношениями х, + ха+... +хм =х, х,) О. а) Ь) (1.2) Мы начинаем изложение с изучения простого класса процессов распределения, встречающихся в математической экономике и исследовании операций.
Основная задача состоит в эффективном использовании ресурсов различных типов. Для того чтобы облегчить читателю усвоение методов, которые мы примем на вооружение, рассмотрим сначала несколько элементарных моделей, приводящих к минимальным магематическим трудностям. Простота этих вводных задач позволит нам опробовать и проанализировать методы, которые будут использованы впоследствии для исследования более реальных и сложных схем. Как мы увидим, все взжные для приложений процессы обладают целым рядом неприятных особенностей и, вообще говоря, требуют различных методов, применяемых в сочетании друг с другом, а также ловкости и изобретательности.
Все наши усилия будут направлены на достижение главной цели — получения численных решений для конкретных задач. Г!ервые вычисления, которые мы производим, относятся к определению максимума функции Аг переменных Я(хь хм..., хм)=а~ (х1)+сгя(хя)+...— г.сгм(хм) (1.1) 24 одномьвныв пяоцвссы ялспввдвлвнпя [гл. г Существует много трудностей, которые возникают при рассмотрении этой, на первый взгляд, просгой и ясной задачи. В ходе тщательного и обстоятельного обсуждения этих препятствий мы обнаружим достаточные основания для введения нового подхода — метода функциональных уравнений динамического программирования.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
