Функциональное уравнение ДП

Пронумеруем шаги в порядке проведения условной оптимизации с конца к началу. Эффективность i -го шага описывается функцией Z_i ( S_i, U_i ), где S_i - состояние к i -му шагу (точнее - вектор параметров состояния), U_i - управление на i -м шаге (точнее - вектор управляемых переменных или решение).

Модель задачи ДП включает целевую функцию , (1)

описание допустимой области управлений D, а также уравнение состояния , связывающее между собой два последовательных состояния.

Формализация вычислительной процедуры метода ДП базируется на принципе оптимальности: последующие решения должны быть оптимальными относительно состояния, сложившегося в результате предшествующих, пусть и не оптимальных, решений. Для описания этого свойства введем последовательность функций { f_k ( S_k )}, так, что каждая из них есть зависимость экстремального значения критерия за k оставшихся шагов от состояния на начало k -го шага: . (2)

Функции (2) зависят только от состояния и не могут зависеть от искомых переменных (управлений), так как по ним ищется экстремум.

=> Состояние - это то, от чего зависит экстремум критерия.

Предположим, что осталось k шагов (k і2)

S_k - > U_k - > z_k(S_k, U_k) принимаем произвольное решение

k-1, S_k-1 - > (в соответствии с принципом оптимальности) f_k-1(S_k-1)

.(3)

Она не является экстремальной для k шагов, так как U_k взято произвольно. Если воспользоваться уравнением состояния, то (3) примет вид

, (4)

Но экстремальное значение за k шагов по определению (2) есть f_k (S_k). Таким образом, окончательно получаем

(5)

основное функциональное уравнение ДП (рекуррентное соотношение).

Для k =1: . (6)

Процедура динамического программирования:

1. Имея описание и модель задачи, выделяем шаги и производим их нумерацию с конца.

2. Определяем параметры состояния и вводим последовательность функций { f_k (S_k)}, , в которой каждая функция f_k (S_k) есть наилучшее значение критерия за k оставшихся шагов относительно состояния S_k.

3. На основе принципа оптимальности составляем функциональное уравнение ДП и отдельно выражение для f ₁.

4. Проводим условную оптимизацию, последовательно вычисляя f ₁, f ₂,..., f_N. При этом на каждом шаге для всех возможных значений состояния S_k запоминаются значения U_k ^* и f_k (в таблице или файле).

5.Исходя из заданного состояния S_N ^{^}, проводим безусловную оптимизацию по схеме:

S_N ^{^}®табл. N ® U_N ^*®у.с.® S_{N -1}^{^}®табл. N -1® U_{N -1}^*®у.с.®...® S ₁^{^}®табл.1® U ₁^*,

где у.с. - уравнение состояния. Значение f_N (S_N) из N -й таблицы есть оптимальное значение критерия задачи.

Достоинства метода ДП:

1. Задача содержит N переменных, которые могут принимать m значений. Поэтому порядок числа вариантов распределения определяется величиной m^N. При расчете по рекуррентной формуле максимум ищется для m значений состояния, а поиск максимума путем просмотра всего диапазона переменной требует перебора от двух до m +1 вариантов, то есть в среднем ~ m /2. Значит, один шаг включает расчет m ²/2 вариантов, а вся задача в ДП - Nm ²/2. Очевидно, что Nm ²/2< < m^N.

2. В случае изменения, например, количества распределяемого ресурса метод полного перебора и другие регулярные численные методы требуют решать задачу заново. В динамическом программировании, если новое значение не больше X, достаточно провести безусловную оптимизацию, взяв за исходное состояние новое значение ресурса.

3. При использовании любого метода оптимизации, кроме ДП, исключение одного из предприятий из системы распределения приведет к необходимости решать изменившуюся задачу как новую. В динамическом программировании, если этому предприятию был присвоен номер N, то есть оно было последним по ходу условной оптимизации, решение измененной задачи находится сразу: по заданному количеству распределяемого ресурса входим не в N -ю, а в (N -1)-ю таблицу и далее действуем в соответствии со схемой безусловной оптимизации.

Метод ДП дает весь ансамбль оптимальных решений, свойственных задаче.

4. Метод ДП не накладывает каких-либо специальных требований на вид и форму представления функций, составляющих критерий.

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

6. Наложение специфических условий на переменные не «утяжеляет» решение задачи методом.

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