ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ

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

Общая постановка задачи ДП: рассматривается управляемый процесс (например, экономический). В результате управлений Х₁, …, Х_n система (объект управления) S переводится из начального состояния s₀ в состояние s_n.

Х₁ Х₂ Х₃ Х_n

s₀ s₁ s₂ … s_n

Состояние системы в конце k – го шага зависит только от предшествующего состояния и управления на k –м шаге. Данное положение записывается в виде уравнений состояний: . Целевая функция равна сумме целевых функций каждого шага: . Принцип оптимальности Беллмана: каково бы ни было состояние s системы в результате какого-либо числа шагов, на ближайшем шаге нужно выбирать управление так, чтобы оно в совокупности с оптимальным управлением на всех последующих шагах приводило к оптимальному выигрышу на всех оставшихся шагах, включая данный. Решать задачу ДП следует с последнего шага (условная оптимизация). Для этого необходимо предварительно составить два уравнения Беллмана: для n-го шага и для произвольного k-го шага.

;

.

Общая схема применения метода ДП:

1) выбирается способ деления процесса управления на шаги;

2) определяются параметры состояния s_k и переменные управления Х_к на каждом шаге;

3) записываются уравнения состояний;

4) вводятся целевая функция k –го шага и суммарная целевая функция;

5) записываются уравнения Беллмана;

6) проводится условная оптимизация (решаются уравнения Беллмана);

7) после выполнения условной оптимизации получают оптимальное решение для конкретного начального состояния s₀:

а)

б) по цепочке .