Общая методика решения задачи методом динамического программирования

Оптимальное решение задачи методом динамического программирования находится на основе функционального уравнения (26). Используя его, запишем алгоритм метода динамического программирования.

Этап 1. Записать функциональное уравнение для последнего состояния процесса (ему соответствует l=n-1):

.

Этап 2. Найти R_n(S_n-1,X_n) из дискретного набора его значений при некоторых фиксированных S_n-1 и X_n из соответствующих допустимых областей. Так как f₀(S_n)=0, то

.

В результате после первого шага известно решение X_n и соответствующее значение функции f₁(S_n-1).

Этап 3. Уменьшить значение l на единицу и записать соответствующее функциональное уравнение. При l=n-k (k= ) оно имеет вид

. (27)

Этап 4. Найти условно-оптимальное решение на основе выражения (27).

Этап 5. Проверить, чему равно значение l. Если l=0, расчет условно-оптимальных решений закончен, при этом найдено оптимальное решение задачи для первого состояния процесса. Если l>0, перейти к выполнению этапа 3.

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

Методика решения задачи оптимального распределения средств на расширение производства методом динамического программирования

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

Пусть группе предприятий выделяются дополнительные средства на реконструкцию и модернизацию производства. По каждому из n предприятий известен возможный прирост g_i(x) ( ) выпуска продукции в зависимости от выделенной ему суммы x. Требуется так распределить между предприятиями средства c, чтобы общий прирост f_n(c) выпуска продукции был максимальный.

В соответствии с вычислительной схемой динамического программирования рассмотрим сначала случай n=1, т.е. предположим, что все имеющиеся средства выделяются на реконструкцию и модернизацию одного предприятия. Обозначим через f₁(x) максимально возможный прирост выпуска продукции на этом предприятии, соответствующий выделенной сумме x. Каждому значению x отвечает вполне определенное значение g₁(x) выпуска, поэтому можно записать, что

f₁(x) = max[g₁(x)] = g₁(x). (28)

Пусть теперь n=2, т.е. средства распределяются между двумя предприятиями. Если второму предприятию выделена сумма x, то прирост продукции на нем составит g₂(x). Оставшиеся другому предприятию средства (c-x) в зависимости от величин x позволят увеличить прирост выпуска продукции на двух предприятиях:

g₂(x)+f₁(c-x). (29)

Оптимальному значению f₂(c) прироста продукции при распределении суммы с между двумя предприятиями соответствует такое x, при котором сумма (29) максимальна. Это можно выразить записью:

.

Значение f₃(c) можно вычислить, если известны значения f₂(с) и т.д.

Функциональное уравнение Беллмана для рассматриваемой задачи запишется в следующем виде:

. (30)

Итак, максимальный прирост выпуска продукции на n предприятиях определяется как максимум суммы прироста выпуска на n-м предприятии и прироста выпуска на остальных n-1 предприятиях при условии, что оставшиеся после n-го предприятия средства распределяются между остальными предприятиями оптимально.

Имея функциональные уравнения (28), (30), мы можем последовательно найти сначала f₁, затем f₂,..,f_n для различных значений распределяемой суммы средств.

Для отыскания оптимального распределения средств прежде всего находим величину x (c) ассигнований n-у предприятию, которая позволяет достичь полученного нами максимального значения f_n прироста продукции. По величине оставшихся средств c-x и уже известному нам значению f_n-1 устанавливаем x (c) – величину ассигнований (n-1)-у предприятию и т.д. и, наконец, находим x (с) и x (с).