Динамическое программирование, принцип Беллмана, схема метода.

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

ДП является инструментом приведения многомерных задач к многошаговым одномерным (меньшей размерности).

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

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

Задачи ДП:

· распределение ресурсов;

· календарное планирование;

· управление запасами;

· оптимизация маршрутов на сетях;

· замена оборудования.

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

Постановка задачи:

Имеется система S, которая переходит из начального состояния S₀ в конечное состояние S­_m под воздействием вектора управлений U. В развернутом виде это выглядит:

Или сокращенно:

Где – вектор управлений.

Все эти переходы можно представиться как траекторию в фазовом пространстве:

(Рисунок рассмотрен для случая, когда состояния системы описываются двумерным вектором).

Управление тоже может описываться вектором.

Через – будем обозначать доход на переходе , - функция перехода состояний. Интересующий нас выигрыш –

Также кроме аддитивного критерия может применяться мультипликативный, где .

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

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

Рассмотрим последовательность переходов состояний в виде следующей схемы:

Доход на i – м шаге: . – наилучшая эффективность при движении из S_i в S_m– называется Условно Оптимальным Выигрышем (УОВ). УОВ зависит только от состояния, это непосредственно вытекает из формулы для УОВ. Управление, при котором достигается УОВ называется Условно Оптимальным Управлением (УОУ) и обозначается .

Назовем конструкцию – полуоптимальным выигрышем (ПОВ). В таком случае УОВ на i-м шаге будет иметь вид (Уравнение Беллмана):

где u_i – все возможные управления на i-м шаге, S_i – получается из функции перехода состояний .

Реализация вышеописанных идей предполагает 2 этапа:

1. Обратная прогонка.

m-й шаг:

, где – множество возможных «предпоследних» состояний. - УОУ.

m-1-й шаг:

 

, где . – УОУ. УОВ – полученна предыдущем шаге.

…………………………………………………………………………..

i-йшаг:

 

, где . – УОУ.

…………………………………………………………………………..

1-йшаг:

 

, где . – УОУ.

2. Прямая прогонка.

В результате обратной прогонки получили УОВ на 1-м шаге. Нулевое состояние системы, при котором УОВ на 1-м шаге максимален и есть оптимальный выигрыш данной задачи. На каждом шаге было сформировано условно оптимальное управление. Определив начальное состояние, приводящее к оптимальному выигрышу (зачастую мощность множества начальных состояний равна единице, т.е. начальное состояние заранее известно), по УОУ на 1-м шаге определим соответствующее управление, которое уже будет безусловным. Имея управление на 1-м шаге и начальное состояние, по функции перехода состояний получим 1-е состояние, по которому определим безусловное оптимальное управление на 2-м шаге. И так далее восстановим всю цепочку оптимальных управлений. Сказанное можно записать следующим образом:

 

35. Динамическое программирование. Задача распределения капиталовложений (ресурсов).

Имеется m предприятий П₁, П₂, …, П_m. K₀ – средства, вкладываемые в развитие этих предприятий. Пусть x_i – вклад в i – е предприятие. В результате этого вклада имеем доход V_i(x_i). Задача состоит в том, чтобы распределить начальные средства K₀так, чтобы суммарный доход от всех предприятий был максимален.

Для решения задачи данной задачи необходимо:

· сформировать шаги;

· решить, что есть управление;

· сформировать оценки управлений.

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

Обратная прогонка:

m-й шаг:

с учетом требования к трате всего ресурса на последнем шаге получаем:

…………………………………………………………………………..

i-й шаг:

…………………………………………………………………………..

1-й шаг:

Прямаяпрогонка:

 

36. Динамическое программирование. Задача о замене оборудования (1-я постановка).

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

В 1-й постановке это задачи считаем, что оборудование не имеет остаточной стоимости (то есть при замене старое оборудование нельзя продать) и затраты на замену и эксплуатацию не разделяются. – затратына замену и эксплуатацию оборудования, начиная с шага, заканчивая началом шага. То есть, - это затраты на замену оборудования в начале шага и последующую эксплуатацию без замены до начала шага. Эти затраты известны по условию задачи. Нарисуем схему задачи для 4 этапов эксплуатирования оборудования:

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

Обратная прогонка:

n-й шаг:

n-1-йшаг:

…………………………………………………………………………..

i-йшаг:

…………………………………………………………………………..

1-й шаг:

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

4-й шаг:

3-й шаг: на начале 3-го шага альтернативы 2: сразу попасть в конечное состояние или сначала перейти в предпоследнее состояние:

То есть выгоднее сразу перейти в конечное состояние:

2-й шаг:

1-й шаг:

Прямая прогонка – переход по жирным дугам из начала в конец: .