 |
 |
 |
 |
|
 |
 |
88
результате вопрос о глобальной оптимизации некоторой функции сводится к поэтапной оптимизации
некоторых промежуточных целевых функций. В динамическом программировании* рассматриваются
методы, позволяющие путем поэтапной (многошаговой) оптимизации получить общий
(результирующий) оптимум.
* Динамическое программирование как научное направление возникло и сформировалось в 1951-1953 гг. благодаря
работам Р. Беллмана и его сотрудников.
Обычно методами динамического программирования оптимизируют работу некоторых управляемых
систем, эффект которой оценивается аддитивной, или мультипликативной, целевой функцией.
Аддитивной называется такая функция нескольких переменных f(х1, x2, ...,х
n
), значение которой вычис-
ляется как сумма некоторых функций f
j
, зависящих только от одной переменной х
j
:
Слагаемые аддитивной целевой функции соответствуют эффекту решений, принимаемых на
отдельных этапах управляемого процесса. По аналогии, мультипликативная функция распадается на
произведение положительных функций различных переменных:
Поскольку логарифм функции типа (5.2) является аддитивной функцией, достаточно ограничиться
рассмотрением функций вида (5.1).
Изложим сущность вычислительного метода динамического программирования на примере задачи
оптимизации
при ограниченияx
Отметим, что в отличие от задач, рассмотренных в предыдущих главах, о линейности и
дифференцируемости функций f
j
(x
j
) не делается никаких предположений, поэтому применение
классических методов оптимизации (например, метода Лагранжа) для решения задачи (5.3)-(5.4) либо
проблематично, либо просто невозможно.
Содержательно задача (5.3)-(5.4) может быть интерпретирована как проблема оптимального
вложения некоторых ресурсов j, приводимых к единой размерности (например, денег) с помощью
коэффициентов a
j
, в различные активы (инвестиционные проекты, предприятия и т. п.),
характеризующиеся функциями прибыли
f
j
, т. е. такого распределения ограниченного объема ресурса
(b), которое максимизирует суммарную прибыль. Представим ситуацию, когда она решается последова-
тельно для каждого актива. Если на первом шаге принято решение о вложении в n-й актив x
n
единиц, то
на остальных шагах мы сможем распределить b-a
n
x
n
единиц ресурса. Абстрагируясь от соображений, на
основе которых принималось решение на первом шаге (допустим, мы по каким-либо причинам не
могли на него повлиять), будет вполне естественным поступить так, чтобы на оставшихся
шагах
распределение текущего объема ресурса произошло оптимально, что равнозначно решению задачи
при ограничениях