5.3 Метод динамического программирования

Динамическое программирование – это метод оптимизации, приспособленный к поэтапным операциям нахождения решения. Задача разбивается на ряд последовательных шагов или этапов.

Условием применимости метода является аддитивность целевой функции, т.е. возможность представления функции от переменных в виде суммы функции, каждая из которых зависит только от одной переменной:

.

К числу задач динамического программирования относятся задачи: о замене и загрузке оборудования; оптимального распределения ресурсов по этапам планирования; оптимального управления запасами; оптимального распределения капиталовложений и многие другие.

Рассмотрим модель нелинейного программирования

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

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

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

,

где – варианты условий начала-го шага.

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

Уравнение Беллмана для шагов, начиная с предпоследнего до начала процесса, имеет вид:

,

где – варианты условий начала-го шага;

–функция Беллмана, найденная на предыдущем шаге.

При динамическом программировании многошаговый процесс проходят два раза:

1) от конца к началу – находят условные оптимальные решения на каждом шаге с учетом выигрыша на всех шагах, начиная с данного до конца;

2) от начала к концу – находят оптимальные шаговые решения на всех шагах.