4.2.4. Примеры задач динамического программирования
Задача о рюкзаке.
Задано конечное множество предметов, которые имеют вес и стоимость
i
-й предмет
: вес -
стоимость
-
Надо выбрать такую совокупность предметов, чтобы суммарный вес был не более наперед заданного значения, а стоимость максимальна.
maxcixi
при
y,где
y
- грузоподъемность (максимально
возможный вес)
Чтобы решить эту задачу с помощью динамического программирования, надо представить ее решение в виде процесса:
Z
(y)
=
(
+Z(y
))
где
=
{i
:
y}
-уравнение
Беллмана для задачи о рюкзаке.
Зная значения Z для малых аргументов, можно вычислить его для любого аргумента.
Процесс построения функции Беллмана не формализуется. Это творческий процесс, т.е. динамическое программирование, это идея, которая в каждой предметной области реализуется по-своему.
2. Задача оптимального распределения ресурсов.
Существует
n
предприятий, между ними надо распределить
средств.
Известно, что выдачаi
-му предприятию
средств дает доход
(
).
Требуется распределить средства так, чтобы суммарный доход был максимальным:
S
=
max
0,
i
=
,
=
Эту задачу удобно решать методом динамического программирования.
Пусть
все
кратны
(
-некоторая
константа),
например:
40
80 120 ...(
=
40)
Представим процесс решения задачи как n -шаговый.
На первом шаге выдадим средства первому предприятию
:
=
- оставшиеся средства (первому
предприятию выдано
средств)
:
=
:
:
n)
:
=
0 (все
средства распределены)
Введем
функцию Беллмана
- максимальный доход, который может быть
получен при распределении средств
между предприятиямиk+1,
... , n.
=
{
(
)
+
(
-
)}
Замечание:
Если разбиение задачи размера n сводит ее к n задачам размера n1 , то рекурсивный алгоритм имеет экспоненциальную сложность. В этом случае часто можно получить более эффективный алгоритм с помощью табличной техники, называемой динамическим программированием.
Динамическое программирование, в сущности, вычислительное решение для всех подзадач. Вычисление идет от малых подзадач к большим, и ответы записываются в таблице. Преимущество этого метода состоит в том, что раз уж подзадача решена, ее ответ где-то хранится и никогда не вычисляется заново.
Задачи динамического программирования называются многоэтапными или многошаговыми.
Недостатки динамического программирования.
В отличие от линейного программирования, в котором симплекс-метод является универсальным, в динамическом программировании такого метода не существует. Каждая задача имеет свои трудности, и в каждом случае необходимо найти наиболее подходящую методику решения.
Трудоемкость решения многомерных задач. При очень большом числе переменных решение задачи ограничивается памятью и быстродействием ЭВМ.
5. Вариационное исчисление (ви)
Вариационное исчисление занимается оптимизацией функционалов, аргументами которых являются функции:
J
(y(x))
=
Будем искать необходимые условия экстремума функционала. Рассмотрим функции с фиксированными концами. Норма:
=
{
+
}
Пусть y*(x) доставляет минимум функционалу J (y(x))
Рассмотрим вариацию :
(y(x))
=
(x)
+ (x)
, где (a)
= (b)
= 0
(x) - вариация
- гладкая, то есть непрерывная вместе со своей производной.
Иллюстрация:
Пусть
=
+
,
тогда:
(т.к.
это min
функционала)
Из этого неравенства можно получить необходимые условия экстремума.