Задачи динамического программирования

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

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

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

Предположим, что есть некоторые ресурсы x, которые распределяются на два предприятия: на первое y, на второе x – y. Пусть в течение определенного периода (например, года) количество y приносит доход (прибыль) g (y), а количество x – y доход h (x – y). Общий доход от вложенных ресурсов составит

R ₁(x, y) = g (y) + h (x – y).

Обозначим через F ₁(x) наибольший доход, который могут принести ресурсы x при оптимальном распределении их между предприятиями.

Тогда

Теперь рассмотрим двухшаговый процесс, состоящий из двух периодов (этапов). Так как доход получается вследствие выпуска и реализации продукции, что связано с определенными издержками (затратами ресурсов), то к началу второго периода первоначальная сумма y уменьшится до величины a ^. y (0£ a £1), а сумма x – y до величины b ^.(x – y) (0£ b £1). Наибольший доход, который можно получить от суммарного остатка a ^. y + b ^.(x – y) в течение второго этапа, равен F ₁[ a ^. y + b ^.(x – y)].

Обозначим через F ₂(x) наибольший доход, который может быть получен от суммы x за оба периода. Этот доход равен максимальному значению суммы доходов первого и второго периодов при условии, что начальные для каждого периода ресурсы распределялись наилучшим образом. Иначе

Равенство (2) устанавливает связь между функциями F ₁(x) и F ₂(x).

Рассматривая n –шаговый процесс, приходим к основному функциональному уравнению Беллмана, устанавливающему связь между F_n (x) и F_{n –1}(x):

Определив по равенству (1) F ₁(x), пользуясь (2), вычисляем F ₂(x), затем F ₃(x) и т.д. Значение F_n (x) является доходом, полученным за n шагов.

Основное функциональное уравнение Беллмана является математической формулировкой принципа оптимального динамического программирования.

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

Это означает, как следует из уравнения Беллмана, что максимальный доход от n –шагового процесса равен сумме доходов от 1-го и (n –1) последующих шагов при условии наилучшего распределения в последующих шагах оставшихся после 1-го шага ресурсов.