4.2.4. Примеры задач динамического программирования

1. Задача о рюкзаке.

Задано конечное множество предметов, которые имеют вес и стоимость

i -й предмет : вес -

стоимость -

Надо выбрать такую совокупность предметов, чтобы суммарный вес был не более наперед заданного значения, а стоимость максимальна.

maxc_ix_i при y,где y - грузоподъемность (максимально возможный вес)

Чтобы решить эту задачу с помощью динамического программирования, надо представить ее решение в виде процесса:

Z (y) = (+Z(y  ))

где = {i :  y} -уравнение Беллмана для задачи о рюкзаке.

Зная значения Z для малых аргументов, можно вычислить его для любого аргумента.

Процесс построения функции Беллмана не формализуется. Это творческий процесс, т.е. динамическое программирование, это идея, которая в каждой предметной области реализуется по-своему.

2. Задача оптимального распределения ресурсов.

Существует n предприятий, между ними надо распределить средств. Известно, что выдачаi -му предприятию средств дает доход().

Требуется распределить средства так, чтобы суммарный доход был максимальным:

S = max

0, i =,

=

Эту задачу удобно решать методом динамического программирования.

Пусть все кратны(-некоторая константа), например:

40 80 120 ...( = 40)

Представим процесс решения задачи как n -шаговый.

На первом шаге выдадим средства первому предприятию

1. : =- оставшиеся средства (первому предприятию выдано средств)

2. : =

:

:

n) : = 0 (все средства распределены)

Введем функцию Беллмана - максимальный доход, который может быть получен при распределении средствмежду предприятиямиk+1, ... , n.

={() +(-)}

Замечание:

Если разбиение задачи размера n сводит ее к n задачам размера n1 , то рекурсивный алгоритм имеет экспоненциальную сложность. В этом случае часто можно получить более эффективный алгоритм с помощью табличной техники, называемой динамическим программированием.

Динамическое программирование, в сущности, вычислительное решение для всех подзадач. Вычисление идет от малых подзадач к большим, и ответы записываются в таблице. Преимущество этого метода состоит в том, что раз уж подзадача решена, ее ответ где-то хранится и никогда не вычисляется заново.

Задачи динамического программирования называются многоэтапными или многошаговыми.

Недостатки динамического программирования.

1. В отличие от линейного программирования, в котором симплекс-метод является универсальным, в динамическом программировании такого метода не существует. Каждая задача имеет свои трудности, и в каждом случае необходимо найти наиболее подходящую методику решения.

2. Трудоемкость решения многомерных задач. При очень большом числе переменных решение задачи ограничивается памятью и быстродействием ЭВМ.

5. Вариационное исчисление (ви)

Вариационное исчисление занимается оптимизацией функционалов, аргументами которых являются функции:

J (y(x)) =

Будем искать необходимые условия экстремума функционала. Рассмотрим функции с фиксированными концами. Норма:

={+}

Пусть y^*(x) доставляет минимум функционалу J (y(x))

Рассмотрим вариацию :

(y(x)) =(x) + (x) , где (a) = (b) = 0

(x) - вариация

 - гладкая, то есть непрерывная вместе со своей производной.

Иллюстрация:

Пусть =+, тогда:

(т.к. это min функционала)

Из этого неравенства можно получить необходимые условия экстремума.