Лекция: Задачи динамического программирования
Условность задач линейного программирования применительно к управлению состоит в оптимизации только для какой–то стационарной ситуации. В действительности задачи управления динамичны, поэтому точнее определять оптимум не для одного момента времени, а последовательно на протяжении длительного периода.
Например, недостаточно определить оптимальный план производства на месяц, вполне вероятно, что в последующие месяцы производство может быть неоптимальным, так как возможности дальнейшего развития не учитывались. Составление ежемесячных оптимальных планов более эффективно с учетом предшествующих периодов, так как годовой оптимальный план будет результатом оптимальных решений, принятых для каждого месяца; причем план каждого последующего месяца должен учитывать решения, принятые в предыдущих.
Динамическое программирование дает возможность принять ряд последовательных решений (многошаговый процесс), обеспечивающих оптимальность развития процесса в целом.
Предположим, что есть некоторые ресурсы x, которые распределяются на два предприятия: на первое y, на второе x–y. Пусть в течение определенного периода (например, года) количество y приносит доход (прибыль) g(y), а количество x–y доход h(x–y). Общий доход от вложенных ресурсов составит
R1(x, y) = g(y) + h(x–y).
Обозначим через F1(x) наибольший доход, который могут принести ресурсы x при оптимальном распределении их между предприятиями.
Тогда
Теперь рассмотрим двухшаговый процесс, состоящий из двух периодов (этапов). Так как доход получается вследствие выпуска и реализации продукции, что связано с определенными издержками (затратами ресурсов), то к началу второго периода первоначальная сумма y уменьшится до величины a.y (0£a£1), а сумма x–y до величины b.(x–y) (0£b£1). Наибольший доход, который можно получить от суммарного остатка a.y + b.(x–y) в течение второго этапа, равен F1[a.y + b.(x–y)].
Обозначим через F2(x) наибольший доход, который может быть получен от суммы x за оба периода. Этот доход равен максимальному значению суммы доходов первого и второго периодов при условии, что начальные для каждого периода ресурсы распределялись наилучшим образом. Иначе
Равенство (2) устанавливает связь между функциями F1(x) и F2(x).
Рассматривая n–шаговый процесс, приходим косновному функциональному уравнению Беллмана, устанавливающему связь между Fn(x) и Fn–1(x):
Определив по равенству (1) F1(x), пользуясь (2), вычисляем F2(x), затем F3(x) и т.д. Значение Fn(x) является доходом, полученным за n шагов.
Основное функциональное уравнение Беллмана является математической формулировкой принципа оптимального динамического программирования.
n Оптимальное поведение (управление) обладает свойством – каковы бы ни были первоначальное состояние и решение в начальный момент, последующие решения должны составлять оптимальное поведение относительно состояния, полученного в результате предыдущего решения.
Это означает, как следует из уравнения Беллмана, что максимальный доход от n–шагового процесса равен сумме доходов от 1-го и (n–1) последующих шагов при условии наилучшего распределения в последующих шагах оставшихся после 1-го шага ресурсов.