Динамическое программирование — раздел математического программирования, представляет собой совокупность приемов, позволяющих находить оптимальные решения, основанные на вычислении последствий каждого решения и выработке оптимальной стратегии для последующих решений.
Ключевая идея в динамическом программировании достаточно проста. Как правило, чтобы решить поставленную задачу, требуется решить отдельные части задачи (подзадачи), после чего объединить решения подзадач в одно общее решение. Часто многие из этих подзадач одинаковы. Подход динамического программирования состоит в том, чтобы решить каждую подзадачу только один раз, сократив тем самым количество вычислений. Это особенно полезно в случаях, когда число повторяющихся подзадач экспоненциально велико.
Метод динамического программирования сверху — это простое запоминание результатов решения тех подзадач, которые могут повторно встретиться в дальнейшем.
Динамическое программирование снизу включает в себя переформулирование сложной задачи в виде рекурсивной последовательности более простых подзадач.
Процессы принятия решений, которые строятся по такому принципу, называются многошаговыми процессами. Математически оптимизационная задача строится с помощью таких соотношений, которые последовательно связаны между собой: например, полученный результат для одного года вводится в уравнение для следующего (или, наоборот, для предыдущего) и т. д. Таким образом, можно получить на компьютере результаты решения задачи для любого избранного момента времени и «следовать» дальше. Динамическое программирование применяется не обязательно для задач, связанных с течением времени. Многошаговым может быть и процесс решения вполне статической задачи. Таковы, например, некоторые задачи распределения ресурсов.
Общим для задач динамического программирования является то, что переменные рассматриваются не вместе, а последовательно, одна за другой. Сущность состоит в том, что строится такая вычислительная схема, когда вместо одной задачи со многими переменными строится много задач с малым числом переменных (обычно даже одной) в каждой. Это значительно сокращает объем вычислений.
Однако такое преимущество достигается лишь при двух условиях:
- когда критерий оптимальности аддитивен, т. е. общее оптимальное решение является суммой оптимальных решений каждого шага,
- и когда будущие результаты не зависят от предыстории того состояния системы, при котором принимается решение.
Это вытекает из принципа оптимальности Беллмана, лежащего в основе теории динамического программирования. Из него же вытекает основной прием — нахождение правил доминирования, на основе которого на каждом шаге производится сравнение вариантов будущего развития и заблаговременное отсеивание заведомо бесперспективных вариантов. Когда эти правила обращаются в формулы, однозначно определяющие элементы последовательности один из других, их называют разрешающими правилами. Несмотря на выигрыш в сокращении вычислений, их объем остается очень большим.
Можно выделить два наиболее общих класса задач, к которым в принципе мог бы быть применим этот метод, если бы не «проклятие размерности» (на самом деле на таких задачах, взятых в крайне упрощенном виде, пока удается только демонстрировать общие основы метода и анализировать экономико-математические модели).
Первый — задача планирования деятельности экономического объекта (предприятия, отрасли и т. п.) с учетом изменения потребности в производимой продукции во времени. Второй класс задач — оптимальное распределение ресурсов между различными направлениями во времени. Сюда можно отнести, в частности, такую задачу: как распределить урожай зерна каждого года на питание и на семена, чтобы за ряд лет получить наибольшее количество хлеба?
Особенно эффективно применяется динамическое программирование тогда, когда по самому существу задачи приходится принимать решения по этапам. Покажем это на простом примере задачи ремонта и замены оборудования.
Пример. На литейной машине шинного завода изготавливаются одновременно две шины — в двух формах. Если одна форма выходит из строя, машину приходится разбирать. При этом может оказаться выгодным заменить также и вторую форму, чтобы лишний раз не разбирать машину, если и эта форма выйдет из строя на следующем этапе. Более того, бывает, что есть смысл заменить обе формы до того, как одна из них выйдет из строя. Методом динамического программирования (с помощью дерева решений) определяется наилучшая стратегия в вопросе о замене форм с учетом всех факторов: выгоды от продолжения эксплуатации формы, потерь от простоя машины, стоимости забракованных шин и т. д.
Метод динамического программирования позволяет с успехом решать многие задачи экономического планирования.
