Глава 7. Динамическое программирование §1. Примеры задач динамического программирования
В рассмотренных ранее задачах оптимизации решение находилось как бы за один шаг. Однако процедуру принятия решений во многих задачах планирования и управления можно представить как многошаговый процесс, т.е. состоящий из нескольких шагов.
Динамическое программирование — это математический метод оптимизации многошаговых процессов, разработанный в начале 50-х годов американским ученым Р. Беллманом. Его использование позволяет свести решение сложной задачи к последовательному решению серии более простых «подзадач». Название метода связано с тем, что первоначально с его помощью проводилась оптимизация динамических систем, т.е. систем, изменяющихся во времени. Однако затем он стал применяться и для решения задач, в которых временной фактор отсутствует, в частности для задач целочисленного программирования.
В настоящее время динамическое программирование является одним из наиболее распространенных оптимизационных методов, пригодным для решения различных прикладных задач: распределения ресурсов, управления запасами, замены оборудования, и т.п. Типичным примером задачи, для решения которой можно применить этот метод, является следующая задача перспективного планирования.
Пример 1.1. Планируется производственная деятельность фирмы на период времени в n лет. Для ее развития выделены капиталовложения в объеме K, которые нужно распределить по годам планового периода. Известно, что годовой доход фирмы зависит от объема средств, вложенных в начале года. Нужно определить, сколько капиталовложений следует выделить фирме в начале каждого года, чтобы общий доход за n лет был максимальным.
Это типичная задача динамического программирования. Распределение капиталовложений можно представить в виде многошагового процесса, где шагом является выделение средств фирме в начале каждого года планового периода.
Управление uk
на k-м шаге (k =
)
этого процесса — величина капиталовложений,
полученных фирмой в начале k-го года.
Управление u в целом
представляет собой совокупность всех
пошаговых управлений:
u = (u1, u2,…, un).
Обозначим xk — величину средств, доступных для выделения фирме после k-го года (остаток капиталовложений). Переменная xk характеризует состояние управляемого процесса после k-го шага. Ясно, что
x1 = K – u1,
x2 = x1 – u2,
…
xn = xn-1 – un.
Из этих соотношений видно, что состояние системы в конце любого шага зависит только от предшествующего состояния и управления на этом шаге. Очевидно, что объем средств, выделяемых фирме в текущем году, не может быть больше, чем остаток капиталовложений после предыдущего года. Поэтому управление k-го шага должно удовлетворять неравенству:
0 ≤ uk ≤ xk-1 , k = .
Управление u = (u1, u2,…, un), для которого эти условия выполнены, будем называть допустимым.
Обозначим fk(uk) — доход, который получит фирма в k-м году, если ей выделить в начале этого года средства в объеме uk. Функция fk характеризует эффективность управления на k-м шаге.
Общая эффективность управления u оценивается при помощи показателя Z — суммарного дохода фирмы за весь плановый период. Этот показатель равен сумме пошаговых показателей эффективностей (годовых доходов):
Z = f1(u1).+ … + fn(un).
Таким образом, задача состоит в выборе
таких допустимых управлений
,
т.е. распределения капиталовложений,
при котором функция Z
достигнет максимума.
В этом примере многошаговый характер процесса управления, по сути, был задан его условиями, согласно которым средства выделяются в начале каждого года. Однако иногда, чтобы использовать метод динамического программирования, «многошаговость» управления приходится вводить искусственно.
Пример 1.2. Имеется груз, состоящий из неделимых предметов n видов, который нужно погрузить на баржу грузоподъемностью Р. Известны стоимость ck и вес pk каждого предмета k-го вида (k = ). Нужно определить, сколько предметов каждого вида следует погрузить на баржу, чтобы суммарная стоимость груза была максимальной, а его общий вес не превышал грузоподъемности баржи.
Обозначим uk — количество предметов k-го вида, загружаемых на баржу. Тогда математическая модель этой задачи выглядит так:
Z = c1u1 + c2u2 + … + cnun → max,
p1u1 + p2u2 + … + pnun ≤ P,
u1 ≥ 0, u2 ≥ 0,…, un ≥ 0,
uk — целые числа для всех k = .
Это задача линейного целочисленного программирования, но для нахождения ее оптимального решения можно использовать динамическое программирование. Для этого процесс загрузки следует представить в виде многошагового управляемого процесса, состоящего из n шагов, причем на каждом шаге баржа загружается предметами одного вида.
Будем считать, что на первом шаге баржа загружается предметами первого вида, на втором шаге — второго вида и т.д. Управление uk на k-м шаге (k = ) — это количество предметов k-го вида, загружаемых на баржу. Параметры состояния xk на k-м шаге — это количество груза, которое еще можно погрузить на баржу после того как на нее погрузили предметы первых k видов. Ясно, что
,
k =
.
Так как на каждом шаге должны выполняться неравенства xk ≥ 0, то управления на каждом шаге должны удовлетворять неравенствам:
,
k =
.
Управление u = (u1, u2,…, un), для которого эти условия выполнены, назовем допустимым.
Эффективность управления на k-м шаге определяется стоимостью всех предметов, загруженных на этом шаге, т.е. она равна ckuk. Эффективность всего процесса управления Z равна сумме эффективностей всех шагов, т.е. суммарной стоимостью загруженных предметов:
Z = c1u1 + c2u2 + … + cnun.
Оптимальное управление доставляет максимальное значение этой функции на множестве всех допустимых управлений.
Пример 1.3. Решается задача оптимального распределения дефицитного ресурса (сырье, оборудование, инвестиции) между n объектами, причем общий объем ресурса равен S. Для каждого объекта считается известной зависимость между размером ресурса и величиной прибыли, полученной в результате выделения ресурса данному объекту. Эта зависимость, вообще говоря, имеет нелинейный характер. Нужно найти распределение ресурса, дающее максимальную общую прибыль.
Обозначим fk(uk) (k = ) — величину прибыли, получаемую от k-го объекта при выделении ему ресурса в объеме uk. единиц. Математическая модель этой задачи имеет следующий вид:
Z = f1(u1) + … + fn(un) → max,
u1 + … + un = S,
uk ≥ 0, k = .
Это задача нелинейного программирования. Если все функции fk вогнутые, то она является задачей выпуклого программирования, и ее оптимальное решение можно найти при помощи какого-либо метода решения задач этого класса, например, при помощи метода множителей Лагранжа. Если же хотя бы одна из функций прибыли не является вогнутой, то использование методов нелинейного программирования может не привести к нужному результату, так как в этом случае найденный локальный максимум может не быть глобальным (см. п.6 §2 главы 5).
В такой ситуации для нахождения оптимального решения целесообразно использовать аппарат динамического программирования. Для этого нужно, представить распределение ресурса как многошаговый процесс, состоящий из n шагов, причем на каждом шаге ресурс выделяется одному из объектов. Будем считать, что на первом шаге ресурс выделяется первому объекту, на втором шаге — второму и т.д.
Управление uk на k-м шаге (k = ) — это количество ресурса, выделяемого k-му объекту, а параметры состояния xk — это остатки ресурса после его выделения первым k объектам, задаваемые формулами:
x1 = S – u1,
x2 = x1 – u2,
…
xn = xn-1 – un.
Управление uk на каждом шаге должно удовлетворять условию:
0 ≤ uk ≤ xk-1 , k = .
Управление u = (u1, u2,…, un), для которого эти условия выполнены, будем называть допустимым.
Эффективность управления uk на k-м шаге определяется величиной прибыли, получаемой от k-го объекта, т.е. она равна fk(uk). Эффективность всего процесса управления Z равна сумме эффективностей всех шагов:
Z = f1(u1).+ … + fn(un).
Оптимальное управление доставляет максимальное значение этой функции на множестве всех допустимых управлений.