Динамическое программирование

Это метод оптимизации решений, который специально приспособлен к многоэтапным операциям. Выделение этапов может быть произведено двумя способами:

1)искусственный (по видам выполненных работ).

2)естественный (по месяцам, годам).

Суммарный выигрыш W=,

Где w_i - это выигрыш в результате операции на любом из этапов.

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

Подобные решения, принимаемы нами, называются шаговым управлением, то есть управлением на i-ом шаге. Последовательность шаговых управлений дает нам управление операцией в целом.

Х= (х₁,х₂,…,х_n) - шаговое упраление

Х*= (x₁*, x₂*…. x_n*) – оптимальное управление всей операции

W*=W(X*).

Алгоритм.

Планируется деятельность группы промышленных предприятий m на каждые n хозяйственных лет. М – количество средств, распределенных между предприятиями. В процессе работы предприятия средства могут быть частично израсходованы, а частично сохранены и пущены на перераспределение. Каждое предприятие приносит прибыль каждый год в зависимости от вложенных средств. В начале каждого года происходит перераспределение средств. Какое количество средств в начале каждого года нужно выделить предприятию, чтобы суммарный доход за n лет был максимальным?

X_ik – упр-ие шага на любом из этапов

i – номер шага

k – номер предприятия

X_i = (x_i1, x_i2, …, x_im) X = (x₁, x₂, …, x_n)

При каком x значение ω будет стремиться в max (и min)?

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

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

Исходя из этого предположения, выбирается условное оптимальное упр-ие. В частности с помощью него мы можем получить условный оптимальный выигрыш на n-1 этапе. Далее действуем аналогично до 1-го этапа. На основе полученных n целочисленных данных делается вывод об оптимальных упр-ях X^* и оптимальном выигрыше ω^*.

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

Принцип оптимальности.

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

Динамическое программирование не сводит задачи к стандартной вычислительной процедуре. Здесь необходимо до вычислений ____систему и выделить шаги.

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

Дата добавления: 2014-01-14