Классификация математических моделей, используемых в экономике и менеджменте
Если
переменные
управления
принимают
дискретные
значения, то
модель ДП называется
дискретной.
Если же указанные
переменные
изменяются
непрерывно,
то модель ДП
называется
непрерывной.
В зависимости
от числа параметров
состояний (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-го до конца.
Это положение
в аналитической
форме можно
записать в виде
следующего
соотношения:
(2.2)
Получившего название основного функционального уравнения ДП, или уравнения Беллмана.
Из
уравнения (5)
может быть
получена функция
,
если известна
функция
;
аналогично
можно получить
,
если найдена
,
и т.д., пока не
будет определена
величина
,
представляющая
по определению
максимальное
значение показателя
эффективности
процесса в
целом:
![]()
Соотношения
(5) для определения
последовательности
функций
через
(k=n, n-1,…,1) получили
название основных
рекуррентных
уравнений
Беллмана.
Решая
уравнения (2.2)
для определения
условного
максимума
показателя
эффективности
за n-k+1 шагов, начиная
с k-го шага, определяем
соответствующее
оптимальное
управление
,
при котором
этот максимум
достигается.
Это управление
также зависит
от
.
Будем обозначать
такое управление
через
и называть
условным оптимальным
управлением
на k-м шаге.
Основное
значение уравнения
(2.2, в котором
реализована
идея динамического
программирования,
заключается
в том, что решение
исходной задачи
определения
максимума
функции (1.2) n переменных
сводится к
решению последовательности
n задач, задаваемых
соотношениями
(2.2), каждое из
которых является
задачей максимизации
функции одной
переменной
.
Эти задачи
оказываются
взаимосвязанными,
так как в соотношении
(2.2) при определении
учитывается
найденная при
решении предыдущей
задачи функция
.
2.2.3 Общее описание процесса моделирования и построения вычислительной схемы динамического программирования
Общая задача оптимизации, чтобы ее можно было описать моделью ДП должна удовлетворять следующим условиям :
Задача может интерпретироваться как n-шаговый процесс управления, а показатель эффективности процесса может быть представлен в аддитивной форме, т.е. как сумма показателей эффективности на каждом шаге.
Структура задачи инвариантна относительно числа шагов п, т. е. должна быть определена для любого n и не зависеть от этого числа.
На каждом шаге состояние системы определяется конечным числом s параметров состояния и управляется конечным числом r переменных управления, причем s и r не зависят от числа шагов п.
Выбор управления на k-м шаге не влияет на предшествующие шаги, а состояние в начале этого шага есть функция только предшествующего состояния и выбранного на нем управления (отсутствие последействия).
Построение модели ДП сводится к следующим основным моментам:
1) выбирают способ деления процесса на шаги;
2)
вводят параметры
состояния
и переменные
управления
на каждом шаге
процесса;
3) записывают уравнение состояния
(3.1)
4) вводят
показатели
эффективности
на k-м
шаге
и суммарный
показатель
– целевую функцию
(3.2)
5) вводят
в рассмотрение
условные максимумы
показателя
эффективности
от k-гo
шага
(включительно)
до конца процесса
и условные
оптимальныеуправления
на k-м
шаге
![]()
из ограничений задачи определяют для каждого шага множества Dk допустимых управлений на этом шаге;
записывают основные для вычислительной схемы ДП функциональные уравнения Беллмана
(3.3)
(3.4)
Несмотря на единообразие в общем построении модели ДП, приведенном выше, вычислительная схема строится в зависимости от размерности задачи, характера модели (дискретной или непрерывной), вида функций (3.1), (3.2) и других характеристик модели. При всем разнообразии вычислительных схем ДП можно отметить в них некоторые общие черты.
Решение уравнений (3.3) проводят последовательно, начиная с (3.4). Этот этап получил название условной оптимизации.
В
результате
последовательного
решения п
частных
задач на условный
максимум определяют
две последовательности
функций:
—условные
максимумы и
соответствующие
им
—условные
оптимальные
управления.
Указанные последовательности функций в дискретных задачах получают в табличной форме, а в непрерывных моделях их можно получить аналитически.
После выполнения первого этапа (условной оптимизации) приступают ко второму этапу — безусловной оптимизации.
а) Если
начальное
состояние
задано
,
то
непосредственно
определяют
максимум
целевой
функции
(3.5)
а затем — искомое безусловное оптимальное управление по цепочке
(3.6)
В
этой цепочке
переход, указанный
сплошной линией,
проводят по
последовательности
,
а пунктирной
— с помощью
уравнений
состояний.
б) Если
задано множество
начальных
состояний,
,
то дополнительно
решают еще одну
задачу на максимум:
(3.7)
откуда
находят
,
а затем, как и
в п. а), по цепочке
(3.6) —безусловное
оптимальное
управление.
Иногда на этапе условной оптимизации вычислительный процесс удобно строить в направлении, обратном описанному выше, т. е. от 1-го шага к л-му. Этот способ получил название прямого хода вычислений в отличие от вышеизложенного, который называется обратным ходом. Уравнения состояний для прямого хода удобно записывать в виде
(3.8)
Они
могут быть
получены решением
уравнений (1.1)
относительно
.
Введем в рассмотрение
условные максимумы
показателя
эффективности
за k
шагов,
от 1-го до k-го
включительно
— величины
.
Повторив
рассуждения
п. 2.2.2., придем к
следующей форме
уравнений
Беллмана:
(3.9)
(3.10)
В результате решения этих уравнений получим последовательности
(3.11)
Этап
безусловной
оптимизации
не отличается
принципиально
от аналогичного
этапа в обратном
ходе вычислений:
,
если
задано,
или
(3.12)
если
указано множество
возможных
конечных состояний.
Далее, определяем
безусловное
оптимальное
управление
по цепочке
(3.13)
2.2.4 Оптимальное распределение ресурсов
Класс задач, рассматриваемый в данной главе, имеет многочисленные практические приложения.
В общем виде эти задачи могут быть описаны следующим образом. Имеется некоторое количество ресурсов, под которыми можно понимать денежные средства, материальные ресурсы (например, сырье, полуфабрикаты, трудовые ресурсы, различные виды оборудования и т. п.). Эти ресурсы необходимо распределить между различными объектами их использования по отдельным промежуткам планового периода или по различным промежутками по различным объектам так, чтобы получить максимальную суммарную эффективность от выбранного способа распределения. Показателем эффективности может служить, например, прибыль, товарная продукция, фондоотдача (задачи максимизации) или суммарные затраты, себестоимость, время выполнения данного объема работ и т. п. (задачи минимизации).
Вообще говоря, подавляющее число задач математического программирования вписывается в общую постановку задачи оптимального распределения ресурсов. Естественно, что при рассмотрении моделей и вычислительных схем решения подобных задач методом ДП необходимо конкретизировать общую форму задачи распределения ресурсов.
В дальнейшем будем предполагать, что условия, необходимые для построения модели ДП, в задаче выполняются. Опишем типичную задачу распределения ресурсов в общем виде.
Задача
1. Имеется начальное
количество
средств
,
которое необходимо
распределить
в течение п
лет
между s
предприятиями.
Средства
(k=1,
2,…,n;
i=1,…,
s),
выделенные
в k-м
году
i-му
предприятию,
приносят доход
в размере
и
к концу года
возвращаются
в количестве
.
В
последующем
распреелении
доход может
либо участвовать
(частично или
полностью),
либо не участвовать.
Требуется определить такой способ распределения ресурсов (количество средств, выделяемых каждому предприятию в каждом плановом году), чтобы суммарный доход от s предприятий за п лет был максимальным.
Следовательно, в качестве показателя эффективности процесса распределения ресурсов за п лет принимается суммарный доход, полученный от s предприятий:
(4.1)
Количество
ресурсов в
начале k-го
года
будем характеризовать
величиной
(параметр состояния).
Управление
на k-м
шаге
состоит в выборе
переменных
обозначающих
ресурсы, выделяемые
в k-м
году
i-му
предприятию.
Если предположить, что доход в дальнейшем распределении не участвует, то уравнение состояния процесса имеет вид