2017-11-30
544
В качестве примера применения подхода динамического программирования к многошаговым задачам оптимизации, в которых требуется найти набор из неотрицательных чисел 
максимизируем сепарабельную функцию (функция называется сепарабельной, если она представляет собой сумму функций, каждая из которых зависит только от одной переменной), при условии, что сумма этих чисел равна фиксированном числу 
.
Постановка задачи.
Найти 
,
при ограничениях 
Решение:
Будем решать данную задачу методом динамического программирования. В данной задаче можно интерпретировать постоянную 
как общий уровень имеющихся ресурсов и рассматривать ее в качестве параметра задачи. Обозначим через 
– функцию оптимального поведения для процесса развертывания в момент времени 
с общим запасам ресурсов .
Для процесса на временном промежутке протяженностью равной нулю и заканчивающегося для 
будет
.
Для одношагового процесса заканчивающегося в , при этом надо распределять ресурсы между 
огласно принципу оптимальности
|
|
|
Общее рекуррентное соотношение имеет вид
Решение задачи отыскивается с помощью общего рекуррентного соотношения, последовательно начиная с граничного условия 
, вплоть до шага (длина шага ) 
(C).
