Модели динамичного программирования.

Общая постановка задачи.

 

До сих пор рассматривались такие задачи оптимизации, в которых принятие решения осуществлялось в один этап. Зависимость рассматриваемого этапа от прошлого и его влияние на будущее не учитывалось.

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

· распределение ресурсов, например, ограниченного объема капиталовложений между возможными новыми направлениями их использования по объему и времени;

· разработка правил управления запасами, устанавливающих момент пополнения и размер пополняемого запаса;

· выбор транспортных маршрутов или технологических способов изготовления изделий;

· разработка принциповкалендарного планирования производства и выравнивания занятости в условиях колеблющегося спроса на продукцию;

· составление календарных планов текущего и капитального ремонта сложного оборудования и его замены;

· разработка долгосрочных правил замены выбывающих из эксплуатации основных фондов и т.д.

Экономический процесс является управляемым, если можно влиять на ход его развития. Под управлением понимается совокупность решений, принимаемых на каждом этапе для влияния на ход развития процесса.

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

Словосочетание «динамическое программирование» впервые было использовано в 1940-х годах Р. Беллманом[60] для описания процесса нахождения решения задачи, где ответ на одну задачу может быть получен только после решения задачи, «предшествующей» ей. В 1953 г. он уточнил это определение до современного. Первоначально эта область была основана, как системный анализ и инжиниринг. Вклад Беллмана в динамическое программирование был увековечен в названии уравнения Беллмана, центрального результата теории динамического программирования.

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

Термин " динамическое " в названии метода возник, видимо, потому что этапы предполагаются разделенными во времени. Однако этапами могут быть элементы операции, никак не связанные друг с другом показателем времени.

При распределении на несколько лет ресурсов деятельности предприятия шагом целесообразно считать временной период; при распределении средств между предприятиями - номер очередного предприятия.

В других задачах разбиение на шаги вводится искусственно. Например, непрерывный управляемый процесс можно рассматривать как дискретный, условно разбив его на временные отрезки (шаги). Исходя из условий каждой конкретной задачи, длину шага выбирают таким образом, чтобы на каждом шаге получить простую задачу оптимизации и обеспечить требуемую точность вычислений.

Тем не менее, метод решения подобных многоэтапных задач применяется один и тот же, и его название стало общепринятым, хотя в некоторых источниках его называют многоэтапным программированием.

Для определения сущности динамического программирования рассмотрим задачу.

Представим себе некоторую операцию О, состоящую из ряда последовательных "шагов" или этапов, например, деятельность отрасли промышленности в течение ряда хозяйственных лет. Пусть число шагов равно m. Выигрыш (эффективность операции) Z за всю операцию складывается из выигрышей на отдельных шагах:

(14)

где Z_i – выигрыш на i-ом шаге.

Если Z обладает таким свойством, то его называют аддитивным критерием.

Операция О является управляемым процессом, то есть мы можем выбирать какие-то параметры, которые влияют на его ход и исход, причем на каждом шаге выбирается решение, от которого зависит выигрыш и на данном шаге, и выигрыш за операцию в целом. Эти решения называются шаговыми.

Совокупность всех шаговых управлений является управлением операцией в целом. Обозначим его буквой х, а шаговые управления - буквами х₁, х₂,..., х_m:

х=х(х₁, х₂,..., х_m).

Требуется найти такое управление х, при котором выигрыш Z обращается в максимум:

, (15)

где Х – множество допустимых (возможных) управлений.

Управление х*, при котором этот максимум достигается, называется оптимальным управлением. Оно состоит из совокупности оптимальных шаговых управлений: х*=х*(х₁*, х₂*,..., х_m*).

Самый простой способ решения задачи - полный перебор всех вариантов. Когда количество вариантов невелико, этот способ вполне приемлем. Однако на практике задачи с небольшим числом вариантов встречаются весьма редко, поэтому полный перебор, как правило, неприемлем из-за чрезмерных затрат вычислительных ресурсов. Поэтому в таких случаях на помощь приходит динамическое программирование.

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

В этой идее есть принципиальная тонкость: каждый шаг оптимизируется не сам по себе, а с "оглядкой на будущее", на последствия принимаемого "шагового" решения. Оно должно обеспечить максимальный выигрыш не на данном конкретном шаге, а на всей совокупности шагов, входящих в операцию.

В основе решения всех задач динамического программирования лежит "принцип оптимальности" Беллмана, который выглядит следующим образом:

Каково бы ни было состояние системы S в результате какого-либо числа шагов, на ближайшем шаге нужно выбирать управление так, чтобы оно в совокупности с оптимальным управлением на всех последующих шагах приводило к оптимальному выигрышу на всех оставшихся шагах, включая данный.

Основное требование - процесс управления должен быть без обратной связи, т.е. управление на данном шаге не должно оказывать влияния на предшествующие шаги.

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