Динамическое программирование. Задача о распределении ресурсов.

Задача распределения ресурсов. Имеется С единиц некоторого ресурса и n производственных процессов. При использовании в i-ом производственном процессе x единиц ресурса, прибыль составляет . Необходимо найти оптимальное распределение ресурсов по производственным процессам, дающее максимальную прибыль.

– целые

Решаем методом динамич. Прог-я:

Рассмотрим семейство задач – задача об оптимальном распределении Y.

Пусть – оптимальная прибыль в задаче – оптимальное распределение ресурсов. Тогда:
-мерный вектор.

Уравнение Беллмана. Рассмотрим задачу считая, что решение задачи вида мы уже знаем. Распределим ресурсы между процессами, выделим отдельно z ресурсов на первые k и оставшиеся Y-z на последний k+1 – ый.

– уравнение Беллмана; если - максимально, то

Решение семейства задач.
1. Решаем самую простую задачу, которая связана только с первым процессом

2. Зная решение задачи при всех мы по уравнению Беллмана находим решение задачи для всех Y.

Динамическое программирование – метод решения задач оптимизации, характеризующиеся следующими этапами:

0. Задача состоит в оптимизации функции f на множество M.

1. Инвариантное погружение (составление семейства задач). Подбираем семейство задач: , каждая из которых состоит в поиске оптимального элемента с учетом ограничений:

2. Вывод уравнения Беллмана. – решение задачи оптимизации , т.е. то значение x, при котором целевая функция принимает значение – функция Беллмана. А уравнением Беллмана называется уравнение, в которое входит функция Беллмана и значение – оптимальное значение.

3. Решение семейства задач.

3.1. Находим более простые задачи и решаем их.

3.2 Находим значение функции Беллмана B(t) и , найденные на предыдущем этапе и подставляем в уравнение Беллмана. Получаем новое решение.

Пункт 3.2 повторяем до тех пор, пока не найдем решение нашей задачи.