5.3 Метод динамического программирования
Динамическое программирование – это метод оптимизации, приспособленный к поэтапным операциям нахождения решения. Задача разбивается на ряд последовательных шагов или этапов.
Условием применимости метода является аддитивность целевой функции, т.е. возможность представления функции от переменных в виде суммы функции, каждая из которых зависит только от одной переменной:
.
К числу задач динамического программирования относятся задачи: о замене и загрузке оборудования; оптимального распределения ресурсов по этапам планирования; оптимального управления запасами; оптимального распределения капиталовложений и многие другие.
Рассмотрим модель нелинейного программирования
При использовании метода динамического программирования задача разбивается на количество шагов по числу неизвестных. На каждом шаге решается задача оптимизации только по одной переменной. Таким образом, процесс нахождения оптимального плана многомерной задачи распадается на ряд более простых одномерных задач оптимизации.
Принимая решение нашаге надо учитывать его влияние на будущее, т.е. учитывать влияние принимаемого решения на эффективность последующих шагов. Имеется единственный шаг в решении задачи в котором можно планировать без учета влияния решения на последующие шаги – это последний шаг. Его можно планировать так, чтобы он изолированно принес наибольшую выгоду. Поэтому процесс поиска оптимального решения начинается от конца к началу.
Чтобы планировать последний шаг, надо знать чем окончился предыдущий, а это неизвестно. В этом случае находят (предполагают) варианты условий начала последнего -го шага, т.е. варианты окончания-го шага. Для каждого варианта находят такие решения, при которых выигрыш на последнем шаге будет максимальным. Этот выигрыш определяется по функциональному уравнению Беллмана для последнего шага:
,
где – варианты условий начала-го шага.
Аналогично оптимизируется решение на предпоследнем -м шаге применительно к вариантам условий начала этого шага, но с учетом решений, найденных на-м шаге и т. д.
Уравнение Беллмана для шагов, начиная с предпоследнего до начала процесса, имеет вид:
,
где – варианты условий начала-го шага;
–функция Беллмана, найденная на предыдущем шаге.
При динамическом программировании многошаговый процесс проходят два раза:
1) от конца к началу – находят условные оптимальные решения на каждом шаге с учетом выигрыша на всех шагах, начиная с данного до конца;
2) от начала к концу – находят оптимальные шаговые решения на всех шагах.
- Экономико-математические методы
- 1 Общая задача математического
- 1.1 Модель математического программирования
- 1.2 Математическая формулировка задач линейного
- 1.3 Примеры построения простейших моделей математического
- 1.4 Геометрическая интерпретация задач линейного
- 1.4.1 Графический метод решения
- 1.4.2 Схема решения задачи графическим методом
- 1.4.3 Особые случаи решения задач линейного
- 1.5 Контрольные вопросы к разделу 1
- 2 Симплекс-метод решения задач линейного
- 2.1 Симметричный симплекс-метод
- 2.2 Экономический анализ оптимального плана по последней
- 2.3 Симплекс-метод с искусственным базисом
- 2.4. Схема решения задач линейного программирования
- 2.5. Особые случаи при решении задач симплекс-методом
- 2.6 Контрольные вопросы к разделу 2
- 3 Двойственные задачи линейного
- 3.1 Понятие о двойственных задачах
- 3.2 Теоремы двойственности в линейном программировании
- 3.3 Экономическая интерпретация двойственных задач
- 3.4. Примеры построения двойственных задач
- 3.5 Контрольные вопросы к разделу 3
- 4 Транспортная задача линейного
- 4.1 Математическая постановка транспортной задачи
- 4.2 Метод потенциалов решения транспортной задачи
- Числаui являются потенциалами строк, аvj – потенциалами столбцов. Из теоремы следует, что для того, чтобы план был оптимальным, необходимо выполнение следующих условий:
- Если хотя бы одна незанятая клетка не удовлетворяет условию (б), то план не оптимален.
- 4.3 Схема решения транспортной задачи
- 4.4 Контрольные вопросы к разделу 4
- 5 Методы решения задач нелинейного
- 5.1 Классификация задач математического программирования
- 5.2 Метод Лагранжа
- 5.3 Метод динамического программирования
- 5.4 Применение динамического программирования для решения задач о замене оборудования и эффективного использования
- 5.5 Контрольные вопросы к разделу 5
- 6 Наиболее распространенные модели
- Содержание
- Литература
- Экономико-математические методы Учебное пособие