Билет 58. Применение методов динамического программирования

Динамическое программирование в математике и теории вычислительных систем — метод решения задач с оптимальной подструктурой и перекрывающимися подзадачами, который намного эффективнее, чем решение «в лоб»

Модели динамического программирования могут применяться, например, при разработке правил управления запасами, устанавливающими момент пополнения запасов и размер пополняющего заказа; при разработке принципов календарного планирования производства и выравнивания занятости в условиях колеблющегося спроса на продукцию; при распределении дефицитных капиталовложений между возможными новыми направлениями их использования; при составлении календарных планов текущего и капитального ремонта сложного оборудования и его замены; при разработке долгосрочных правил замены выбывающих из эксплуатации основных фондов и т.д.

Динамическое программирование — раздел математического программирования, совокупность приемов, позволяющих находить оптимальные решения, основанные на вычислении последствий каждого решения и выработке оптимальной стратегии для последующих решений. Метод его заключается в том, что для отыскания решения поставленной задачи решается похожая (или похожие), но более простая. При этом осуществляется переход к еще более простым и так далее, пока не доходят до тривиальной.

Процессы принятия решений, которые строятся по такому принципу, называются многошаговыми процессами. Математически оптимизационная задача строится с помощью таких соотношений, которые последовательно связаны между собой: например, полученный результат для одного года вводится в уравнение для следующего (или, наоборот, для предыдущего) и т. д. Таким образом, можно получить на вычислительной машине результаты решения задачи для любого избранного момента времени и «следовать» дальше. Динамическое программирование применяется не обязательно для задач, связанных с течением времени. Многошаговым может быть и процесс решения вполне статической задачи. Таковы, например, некоторые задачи распределения ресурсов.

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

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

Особенно эффективно применяется динамическое программирование тогда, когда по самому существу задачи приходится принимать решения по этапам. Покажем это на простом примере задачи ремонта и замены оборудования. На литейной машине шинного завода изготавливаются одновременно две шины — в двух формах. Если одна форма выходит из строя, машину приходится разбирать. При этом может оказаться выгодным заменить также и вторую форму, чтобы лишний раз не разбирать машину, если и эта форма выйдет из строя на следующем этапе. Более того, бывает, что есть смысл заменить обе формы до того, как одна из них выйдет из строя. Методом динамического программирования (с помощью дерева решений) определяется наилучшая стратегия в вопросе о замене форм с учетом всех факторов: выгоды от продолжения эксплуатации формы, потерь от простоя машины, стоимости забракованных шин и т. д.