Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Динамическое программирование. Задача о распределении ресурсов.
Задача распределения ресурсов. Имеется С единиц некоторого ресурса и n производственных процессов. При использовании в i-ом производственном процессе x единиц ресурса, прибыль составляет . Необходимо найти оптимальное распределение ресурсов по производственным процессам, дающее максимальную прибыль. – целые Решаем методом динамич. Прог-я: Рассмотрим семейство задач – задача об оптимальном распределении Y. Пусть – оптимальная прибыль в задаче – оптимальное распределение ресурсов. Тогда: Уравнение Беллмана. Рассмотрим задачу считая, что решение задачи вида мы уже знаем. Распределим ресурсы между процессами, выделим отдельно z ресурсов на первые k и оставшиеся Y-z на последний k+1 – ый. – уравнение Беллмана; если - максимально, то Решение семейства задач. Динамическое программирование – метод решения задач оптимизации, характеризующиеся следующими этапами: 0. Задача состоит в оптимизации функции f на множество M. 1. Инвариантное погружение (составление семейства задач). Подбираем семейство задач: , каждая из которых состоит в поиске оптимального элемента с учетом ограничений: 2. Вывод уравнения Беллмана. – решение задачи оптимизации , т.е. то значение x, при котором целевая функция принимает значение – функция Беллмана. А уравнением Беллмана называется уравнение, в которое входит функция Беллмана и значение – оптимальное значение. 3. Решение семейства задач. 3.1. Находим более простые задачи и решаем их. 3.2 Находим значение функции Беллмана B(t) и , найденные на предыдущем этапе и подставляем в уравнение Беллмана. Получаем новое решение. Пункт 3.2 повторяем до тех пор, пока не найдем решение нашей задачи.
|