11. Основы динамического программирования. Достоинства и недостатки метода.

Изначально ориентирован на оптимизацию так называемых многошаговых (многостадийных, многоэтапных) процессов и использование ЭВМ.

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

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

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

Очень важным понятием в ДП является состояние системы. Оно фигурирует в принципе оптимальности и на нем базируются вычислительные процедуры ДП.

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

Работа метода дп

Основные черты метода ДП:

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

2. Решение каждой из этих задач опирается на результаты решения предшествующей (в смысле порядка расчета) задачи. Связь задач осуществляется через состояние, которое есть, с одной стороны, результат выбора конкретного перехода на данном шаге, с другой - исходная информация для извлечения результата решения непосредственно предшествующей задачи. Из такого смысла состояния следует, что каждая задача должна решаться для всех состояний, с которых может начаться рассматриваемый шаг. Такую схему расчета называют условной оптимизацией. Это название подчеркивает, что на каждом шаге при выборе оптимального решения оговаривается условие, а именно, состояние, относительно которого ищется решение.

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

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