Динамическая задача распределения ресурсов

Преимущества метода динамического программирования наглядно проявляются при решении динамических задач распределения ресурсов, к которым относятся задачи планирования и распределения ресурсов между несколькими объектами управления за ряд лет. Причем, эффективность использования ресурсов на объектах различна и в общем случае меняется во времени. В процессе работы ресурсы частично уменьшаются (тратятся, амортизируются). Функции изменения количества ресурсов при их использовании на различных объектах известны. На начало каждого нового планового периода оставшиеся ресурсы могут перераспределяться между объектами. Задача заключается в определении количества ресурсов, выделяемых каждому объекту в различные периоды времени, чтобы общая (за ряд лет по всем объектам) эффективность использования ресурсов была максимальной.

Рассмотрим простейшую динамическую задачу распределения ресурсов между двумя объектами управления.

Необходимо втечение Т периодов времени (t=l,2,..., Т)распределить между двумя объединениями ресурсы в количестве A₀.Ресурсы, вложенные в определенное объединение, к концу периода приносят прибыль, равную в первом объединении аво втором .Здесь и далее и - управляемые переменные задачи, обозначающие соответственно количество ресурсов, выделенное первому и второму объединениям в период t. В результате использования количество ресурсов постоянно уменьшается, в первом объединении до величины ,а во втором . По истечении каждого периода оставшееся количество ресурсов может быть вновь перераспределено между объединениями. Требуется распределить ресурсы между объединениями по периодам времени, т.e. найти количество ресурсов, выделяемое ежегодно (если плановый период - год) каждому объединению (объекту управления), чтобы суммарная прибыль была максимальна.

Оптимизируемая система в данном случае включает два объединения. Состояние системы характеризуется количеством ресурсов, выделенных каждому объединению и .

Управление U_t на t-мэтапе состоит в определении количества ресурсов и , выделяемых первому и второму объединениям. Управление всей операцией включает совокупность поэтапных значений управления

(87)

Требуется найти оптимальное управление ,максимизирующее суммарную прибыль,

(88)

Состояние системы перед t-мэтапом характеризуется суммарным количеством ресурсов A_t, сохранившихся после предшествующих (t - 1) этапов.

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

Например, = A_t - .

Прибыль на t-мэтапе зависит от суммарного количества и распределения ресурсов и равна

(89)

Остаток ресурсов после завершения t-гoэтапа составляет

(90)

Зная зависимости для расчета прибыли на каждом этапе и суммарной прибыли, а также для определения остатка ресурсов, получаем основное функциональное уравнение задачи

(91)

Условно-оптимальное управление на каждом этапе при определенной величине A_t должно обращать в максимум условно-оптимальный выигрыш

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

Условно-оптимальный выигрыш на последнем этапе Т при различных значениях А_Т составит

(92)

Определяя и пользуясь приведенным выше основным функциональным уравнением, последовательно находим условно-оптимальную прибыль на Т-1, T-2,..., t, ...,2, 1 этапах и соответствующие ей значения условно-оптимального управления

(93)

Зная начальное количество ресурсов А₀, определяем максимальную прибыль ,оптимальное управление на первом этапе и .

Получив распределение ресурсов по объектам на первом этапе, рассчитаем остаток ресурса на начало второго этапа

(94)

Зная состояние системы перед началом второго этапа, характеризуемое величиной A₂,определяем оптимальное управление на этом этапе

(95)

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

(96)

Совокупность ресурсов , выделенных по периодам первому объединению, и совокупность ресурсов ,выделенных по периодам второму объединению, представляют оптимальное распределение ресурсов.