Модель динамического программирования

Модель динамического программирования

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

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

В основе метода динамического программирования лежит принцип оптимальности, сформулированный Беллманом. Этот принцип и идея включения конкретной задачи оптимизации в семейство аналогичных многошаговых задач приводят к рекуррентным соотношениям – функциональным уравнениям – относительно оптимального значения целевой функции. Их решение позволяет последовательно получить оптимальное управление для исходной задачи оптимизации.

Дадим общее описание модели динамического программирования.

Рассматривается управляемая система, которая под влиянием управления переходит из начального состояния в конечное состояние . Предположим, что процесс управления системой можно разбить на n шагов. Пусть - состояние системы после первого, второго, … , n-го шага. Схематически это показано на рис. 1.

Состояние системы после -го шага ( =1, 2, … , n) характеризуется параметрами , которые называются фазовыми координатами. Состояние можно изобразить точкой s-мерного пространства, называемого фазовым пространством. Последовательное преобразование системы (по шагам) достигается с помощью некоторых мероприятий которые составляют управление системой

Где - управление на -м шаге, переводящее систему из состояния - в состояние (рис. 1) Управление на -м шаге заключается в выборе значений определенных управляющих переменных * .

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

Равенство (1.1) получили название уравнений состояний. Функции полагаем заданными.

Варьируя управления U, получим различную «эффективность» процесса **, которую будем оценивать количественно целевой функцией Z,  зависящей от начального состояния системы и от выбранного управления U:

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

Если свойство аддитивности целевой функции Z не выполняется, то этого иногда можно добиться некоторыми преобразованиями функции. Например, если Z – мультипликативная функция, заданная в виде

то можно рассмотреть функцию Z’=Log Z, которая является аддитивной.

Обычно условиями процесса на управление на каждом шаге накладываются некоторые ограничения. Управления, удовлетворяющие этим ограничениям, называются допустимыми.

Задачу пошаговой оптимизации можно сформулировать так: определить совокупность допустимых управлений переводящих систему из начального состояния в конечное состояние и максимизирующих или минимизирующих показателей эффективности (1.3).

Для единообразия формулировок (но не вычислительных процедур!) в дальнейшем мы будем говорить только о задаче максимизации, имея в виду, что если необходимо минимизировать Z, то, заменив Z наZ’=- Z, перейдем к максимизации Z’.

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

Если переменные управления принимают дискретные значения, то модель ДП называется дискретной. Если же указанные переменные изменяются непрерывно, то модель ДП называется непрерывной. В   зависимости от числа параметров состояний (s) и числа управляющих переменных на каждом шаге (r) различают одномерные и многомерные модели ДП *. Число шагов в задаче может быть либо конечным, либо бесконечным.

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

В некоторых задачах, решаемых методом ДП, процесс управления естественно разбивается на шаги. Например, при распределении на несколько лет ресурсов деятельности предприятия шагом естественно считать временной период; при распределении между n предприятиями номером шага естественно считать номер очередного предприятия. В других задачах разбиение на шаги вводится искусственно. Например, непрерывный управляемый процесс можно рассматривать как дискретный, условно разбив его на некоторые временные отрезки – шаги. Исходя из условий каждой конкретной задачи, длину шага выбирают таким образом, чтобы на каждом шаге получить простую задачу оптимизации и обеспечить требуемую точность вычислений.