ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ это:

ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ

- раздел математики, посвященный теории и методам решения многошаговых задач оптимального управления.

В Д. п. для управляемых процессов среди всевозможных управлений ищется то, к-рое доставляет экстремальное (наименьшее или наибольшее) значение целевой функции - нек-рой числовой характеристики процесса. Под многошаговостью понимают либо многоступенчатую структуру процесса, либо что управление разбивается на ряд последовательных этапов (шагов), соответствующих, как правило, различным моментам времени. В ряде задач многошаговость проистекает из существа процесса (напр., в задаче определения оптимальных размеров ступеней многоступенчатой ракеты или при нахождении наиболее экономичного режима полета самолетов), но она может вводиться искусственно для того, чтобы обеспечить возможность применения метода Д. п. Таким образом, в названии Д. п. под программированием понимают принятие решений, планирование, а слово динамическое указывает на существенную роль времени и порядка выполнения операций в рассматриваемых процессах и методах.

Методы Д. п. являются составной частью методов, используемых в исследовании операций, и применяются в задачах оптимального планирования (напр., в задачах об оптимальных распределениях ресурсов, в теории управления запасами, в задачах замены оборудования и т. д.) и при решении многих технических проблем (напр., в задачах управления последовательными химическими процессами, в задачах оптимального проектирования прокладки дорог и др.).

Проиллюстрируем основную идею. Пусть процесс управления нек-рой системой Xсостоит из тшагов (этапов); на i-м шаге управление yi переводит систему из состояния xi-1, достигнутого в результате (i-1)-го шага, в новое состояние ж,-. Этот процесс перехода осуществляет заданная функция fi(x, у), и новое состояние определяется значениями xi-1, yi :

Таким образом, управления у 1, у 2,... , у т переводят систему из начального состояния в конечное - где Х 0 и Х т- совокупности допустимых начальных и конечных состояний системы X. Опишем одну из возможных постановок экстремальной задачи. Начальное состояние х 0 задано. Требуется выбрать управления у 1, у 2, ..., у т таким образом, чтобы система Xперешла в допустимое конечное состояние и при этом заданная целевая функция F(x0, у1,x1, у 2, ... , у т, х т )достигла максимального значения F*, т. е.

Важной особенностью метода Д. п. является то, что он применим лишь для аддитивной целевой функции.. В рассмотренном примере это означает, что

Кроме того, в методе Д. п. требуется, чтобы задача характеризовалась отсутствием "последействия": решения (управления), принимаемые на шаге, оказывают влияние только на состояние х i системы в момент i. Другими словами, процессы, описываемые функциями вида не рассматриваются. Оба упомянутых ограничительных условия можно ослабить, но только за счет существенного усложнения метода.

Для решения задач Д. п. обычные методы математического анализа либо вообще неприменимы, либо приводят к огромному числу вычислений. В основе метода Д. п. лежит принцип оптимальности, сформулированный Р. Беллманом (R. Bellman): предположим, что осуществляя управление дискретной системой X, мы уже выбрали некоторые управления дискретной системой у 1, у 2, ... , у k тем самым траекторию состояний х 0, х 1, . . . , xk, и хотим завершить процесс, т. е. выбрать yk+ 1, yk+2,... , у т (а значит и xk+ 1,xk+ 2, ...,xm);тогда, если завершающая часть процесса не будет оптимальной в смысле достижения максимума функции

то и весь процесс не будет оптимальным.

Пользуясь принципом оптимальности, легко получить основное функциональное соотношение. Определим последовательность функций переменной х:

k=1,2, ... , т. Здесь максимум берется по всем управлениям, допустимым на шаге к. Соотношение, определяющее зависимость wk-1 от wk, принято называть Беллмана уравнением. Смысл функций wk-1 (х). нагляден: если система на шаге k-1 оказалась в состоянии х, то wk-1(x) есть максимально возможное значение функции F. Одновременно с построением функций wk-1 (х). находятся условные оптимальные управления yk (х)на каждом шаге (т. е. значения оптимального управления при всевозможных предположениях о состоянии хсистемы на шаге k-1). Окончательно оптимальные управления находятся последовательным вычислением величин

Из сказанного очевидна следующая особенность метода Д. п.- с его помощью решается не одна конкретная задача при определенном х 0, а сразу все подобные однотипные задачи при любом начальном состоянии. Поскольку численная реализация метода Д. п. весьма сложна, т. к. требует большого объема памяти ЭВМ, то его целесообразно применять в тех случаях, когда необходимо многократно решать типовые задачи (скажем, определение оптимального режима полета самолета при меняющихся погодных условиях). Несмотря на то, что задача Д. п. формулируется для дискретных процессов, в ряде случаев метод Д. п. с успехом применяется для решения динамических задач с непрерывными параметрами.

Д. п. дало новый подход ко многим задачам вариационного исчисления..

Важным разделом Д. п. являются стохастические задачи Д. п.- задачи, в к-рых на состояние системы и на целевую функцию влияют случайные факторы. К таким задачам относятся, напр., задачи оптимального регулирования запасов с учетом возможностей случайного пополнения запасов. Здесь наиболее естественной областью применения Д. п. являются управляемые марковские процессы.

Метод Д. п. был предложен Р. Беллманом. Строгое обоснование метода Д. п. было получено в результате работ Л. С. Понтрягина и его учеников по математической теории управляемых процессов (см. Оптимального управления математическая теория).

Хотя метод Д. п. существенно упрощает исходные задачи, однако явное его применение, как правило, весьма громоздко. Для преодоления этих трудностей разрабатываются приближенные методы Д. п.

Лит.:[1] Беллман Р., Динамическое программирование, пер. с англ., М., 1960; [2] Болтянский В. Г., Математические методы оптимального управления, М., 1966; [3] Xедли Д т.. Нелинейное и динамическое программирование, пер. с англ., М., 1967; [4] Xедли Д ж., Уайтин Т., Анализ систем управления запасами, пер. с англ., М., 1969; [5] Xовард Р. А., Динамическое программирование и марковские процессы, пер. с англ., М., 1964.

С. А. Ашманов, В. Г. Карманов.


Математическая энциклопедия. — М.: Советская энциклопедия. . 1977—1985.

Смотреть что такое "ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ" в других словарях:

  • Динамическое программирование — в теории управления и теории вычислительных систем  способ решения сложных задач путём разбиения их на более простые подзадачи. Он применим к задачам с оптимальной подструктурой (англ.), выглядящим как набор перекрывающихся подзадач,… …   Википедия

  • динамическое программирование — — [Е.С.Алексеев, А.А.Мячев. Англо русский толковый словарь по системотехнике ЭВМ. Москва 1993] динамическое программирование Раздел математического программирования, совокупность приемов, позволяющих находить оптимальные решения, основанные …   Справочник технического переводчика

  • Динамическое программирование — [dynamic program­ming] раздел математического программирования, совокупность приемов, позволяющих находить оптимальные решения, основанные на вычислении последствий каждого решения и выработке оптимальной стратегии для последующих решений.… …   Экономико-математический словарь

  • Динамическое программирование —         раздел математики, посвящённый теории и методам решения многошаговых задач оптимального управления (См. Оптимальное управление).          В Д. п. для управляемых процессов среди всех возможных управлений ищется то, которое доставляет… …   Большая советская энциклопедия

  • динамическое программирование — dinaminis programavimas statusas T sritis automatika atitikmenys: angl. dynamic programming vok. dynamische Programmierung, f rus. динамическое программирование, n pranc. programmation dynamique, f …   Automatikos terminų žodynas

  • ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ — раздел математич. программирования, изучающий многошаговые процессы поиска оптим. решения сложных задач. Применяется при составлении программ решения таких задач оптимизации, для к рых процесс поиска решения можно представить в виде нек рой… …   Большой энциклопедический политехнический словарь

  • динамическое программирование — планирование, построение и объединение динамических объектов, создаваемых с помощью обращений к процедуре распределения памяти …   Толковый переводоведческий словарь

  • Программирование математическое — Математическое программирование  математическая дисциплина, изучающая теорию и методы решения задач о нахождении экстремумов функций на множествах конечномерного векторного пространства, определяемых линейными и нелинейными ограничениями… …   Википедия

  • ПРОГРАММИРОВАНИЕ ДИНАМИЧЕСКОЕ — англ. programming, dynamic; нем. dinamische Programmierung. Математические модели, применяемые при принятии решений. Antinazi. Энциклопедия социологии, 2009 …   Энциклопедия социологии

  • Динамическое распределение памяти — Динамическое распределение памяти  способ выделения оперативной памяти компьютера для объектов в программе, при котором выделение памяти под объект осуществляется во время выполнения программы. При динамическом распределении памяти объекты… …   Википедия

Книги

Другие книги по запросу «ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ» >>


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»