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

Динамическое программирование

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

Обычно методами динамического программирования оптимизируют работу некоторых управляемых систем, эффект которой оценивается аддитивной, или мультипликативной, целевой функцией. Аддитивной называется такая функция нескольких переменных , значение которой вычисляется как сумма некоторых функций f_j, зависящих только от одной переменной x_j:

(1)

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

(2)

Рассмотрим сущность вычислительного метода динамического программирования на примере задачи оптимизации:

(3)

при ограничениях

(4)

Содержательно задача (3)-(4) может быть сформулированна как проблема оптимального вложения некоторых ресурсов j, приводимых к единой размерности (например, денег) с помощью коэффициентов a_j, в различные активы (инвестиционные проекты, предприятия и т.п.), характеризующиеся функциями прибыли f_j, т.е. такого распределения ограниченного объёма ресурса (b), которое максимизирует суммарную прибыль. Пусть имеется ситуация, когда она решается последовательно для каждого актива. Если на первом шаге принять решение о вложении в n-й актив x_n единиц, то на остальных шагах можно распределить b-a_nx_n единиц ресурса. Здесь вполне естественно будет поступить так, чтобы на оставшихся шагах распределение текущего объёма ресурса произошло оптимально, что равнозначно решению задачи:

(5)

при ограничениях:

(6)

Очевидно, что максимальное значение (5) зависит от размера распределяемого остатка, и если оставшееся количество ресурса обозначить через , то величину (5) можно выразить как функцию от :

, (7)

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

(8

Если бы имелась возможность влиять на x_n, то для получения максимальной прибыли нужно было бы максимизировать , по переменной x_n, т.е. найти и фактически решить задачу:

(9)

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

, (10)

т.е. значению целевой функции при одномоментном распределении ресурса.

Если в выражении (9) заменить значения b на и n на k, то его можно рассматривать как рекуррентную формулу, позволяющую последовательно вычислять оптимальные значение целевой функции при распределении объёма ресурса за k шагов:

(11)

Значение переменной x_k, при котором достигается рассматриваемый максимум, обозначим .

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

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

Дата добавления: 2014-01-07