Классификация математических моделей, используемых в экономике и менеджменте (стр. 4 из 11)
Равенства (1.1) получили название уравнений состояний. Функции
полагаем заданными.Варьируя управления U, получим различную «эффективность» процесса, которую будем оценивать количественно целевой функцией Z, зависящей от начального состояния системы
и от выбранного управления U:
(1.2)Показатель эффективности k-го шага процесса управления, который зависит от состояния
вначале этого шага и управления 
, выбранного на этом шаге, обозначим через 
(рис. 1). В рассматриваемой задаче пошаговой оптимизации целевая функция (1.2) должна быть аддитивной, т.е. 
(1.3)Обычно условиями процесса на управление на каждом шаге
накладываются некоторые ограничения. Управления, удовлетворяющие этим ограничениям, называются допустимыми.Задачу пошаговой оптимизации можно сформулировать так: определить совокупность допустимых управлений
, переводящих систему из начального состояния в конечное состояние 
и максимизирующих (минимизирующих) показатель эффективности (1.3).Для единообразия формулировок (но не вычислительных процедур!) в дальнейшем будем говорить только о задаче максимизации, имея в виду, что если необходимо минимизировать Z, то заменив Z на Z’=-Z перейдем к максимизации Z’.
Начальное состояние
и конечное состояние могут быть заданы однозначно или могут быть указаны множество 
начальных состояний и множество 
конечных состояний так, что 
. В последнем случае в задаче пошаговой оптимизации требуется определить совокупность допустимых управлений, переводящих систему из начального состояния 
в конечное 
и максимизирующих целевую функцию (1.3). Управление, при котором достигается максимум целевой функции (1.3) называется оптимальным управлением и обозначается через U*= 
.Если переменные управления
принимают дискретные значения, то модель ДП называется дискретной. Если же указанные переменные изменяются непрерывно, то модель ДП называется непрерывной. В зависимости от числа параметров состояний (s) и числа управляющих переменных на каждом шаге (r) различают одномерные и многомерные модели ДП. Число шагов в задаче может быть либо конечным, либо бесконечным.ДП применяется при оптимизации как детерминированных, так и стохастических процессов.
В некоторых задачах, решаемых методом ДП, процесс управления естественно разбивается на шаги. Например, при распределении на несколько лет ресурсов деятельности предприятия шагом естественно считать временной период; при распределении средств между n предприятиями номером шага естественно шага номер очередного предприятия. В других задачах разбиение на шаги вводится искусственно. Например, непрерывный управляемый процесс можно рассматривать как дискретный, условно разбив его на некоторые временные отрезки – шаги. Исходя из условий каждой конкретной задачи, длину шага выбирают таким образом, чтобы на каждом шаге получить простую задачу оптимизации и обеспечить требуемую точность вычислений.
2.2.2 Принцип оптимальности и уравнение Беллмана
Метод динамического программирования состоит в том, что оптимальное управление строится постепенно, шаг за шагом. На каждом шаге оптимизируется управление только этого шага. Вместе с тем на каждом шаге управление выбирается с учетом последствий, так как управление, оптимизирующее целевую функцию только для данного шага, может привести к неоптимальному эффекту всего процесса. Управление на каждом шаге должно быть оптимальным с точки зрения процесса в целом.
Иллюстрацией к сказанному выше может служить задача о выборе кратчайшего пути для перехода их точки A в точку В, если маршрут должен пройти через некоторые пункты. На рис. 2 эти пункты обозначены кружками, а соединяющие их дороги – отрезками, рядом с которыми проставлены соответствующие расстояния.
С точки зрения интересов оптимизации только каждого ближайшего шага – выбора кратчайшего пути из данной точки в соседнюю – следует двигаться по маршруту, проходящему через точки А, А1, А3, А2, А4, В. Длина этого маршрута равна 34. Такой путь из А в В не является кратчайшим. Например, маршрут, проходящий через точки А, А3, А4, В имеет меньшую длину, равную 25. Решив эту задачу, мы убедимся, что второй путь также не является оптимальным.
Приведенный пример многошаговой операции показывает, что управление в каждом шаге надо выбирать с учетом его последствий на предстоящих шагах. Это основное правило ДП, сформулированное Р. Беллманом называется принципом оптимальности.
Оптимальное управление обладает таким свойством, что каково бы ни было начальное состояние на любом шаге и управление, выбранное на этом шаге, последующие управления должны выбираться оптимальными относительно состояния, к которому придет система в конце данного шага.
Использование этого принципа гарантирует, что управление, выбранное на любом шаге, является не локально лучшим, а лучшим с точки зрения процесса в целом.
Так, если система в начале k-го шага находится в состоянии
и мы выбираем произвольное управление , то система придет в новое состояние 
, и дальнейшие управления 
должны выбираться оптимальными относительно состояния 
. Последнее означает, что при этих управлениях максимизируется показатель эффективности на последующих до конца процесса шагах k+1,…,n, т.е. величина 
Показатель, характеризующий суммарную эффективность от данного k-го до последнего n-го шага, будем обозначать через Zk, т.е. 
Задача оптимизации процесса, начиная с k-го до последнего n-го шага (рис.3), похожа на исходную при начальном состоянии системы , управлении 
и показателе эффективности 
(аналогично (2)). Выбрав оптимальное управление Uk* на оставшихся n-k+1 шагах, получим величину 
, которая зависит только от , т.е. 
(2.1)Назовем величину
условным максимумом. Если теперь мы выберем на k-м шаге некоторое произвольное управление 
, то система придет в состояние . Согласно принципу оптимальности, какое бы мы не выбрали, на последующих шагах управление 
должно выбрать так, чтобы показатель эффективности Zk+1 достигал максимального значения, равного 
. Остается выбрать управление . Его нельзя выбирать из условия локальной максимизации показателя эффективности на данном k-м шаге, лишь бы получить 
. Такой подход был бы недальновидным, поскольку от выбора зависит новое состояние , а от последнего – максимально возможная эффективность, которая может быть достигнута в дальнейшем, т.е. величина . Поэтому необходимо выбирать управление так, чтобы оно в совокупности с оптимальным управлением на последующих шагах (начиная с (k+1) – го) приводило бы к общему максимуму показателя эффективности на n-k+1 шагах, начиная с k-го до конца. Это положение в аналитической форме можно записать в виде следующего соотношения: