Методы динамического программирования

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

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

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

Задачи, решаемые методом динамического программирования, формулируются следующим образом: имеется управляемый процесс, задано его начальное и конечное состояния, требуется определить значения факторов его состояния, обеспечивающих получение оптимума функции процесса в целом. К наиболее типичным задачам динамического программирования относятся: распределение ресурсов и капитальных вложений между возможными направлениями их использования (по объему и времени); задача о замене оборудования; составление календарных планов текущего и капитального ремонтов сложного оборудования; определение кратчайших расстояний на заданной транспортной сети и др.

Задачи динамического программирования имеют отличительные свойства. Отметим основные из них.

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

2. Независимость оптимального плана от предыстории. Оптимальный план зависит от состояния изучаемого процесса в исходный момент времени, а не от того, как было достигнуто исходное состояние.

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

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

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

Из принципа оптимальности есть исключение. На последнем этапе можно действовать без оценки будущего этапа, поскольку его нет. На последнем этапе управление следует выбирать так, чтобы оно дало наибольший эффект и было на этом этапе наилучшим. Поэтому процесс динамического планирования проводится в обратном во времени направлении, т. е. сначала планируется последний этап. При этом необходимо сделать разные предположения о том, чем закончился предпоследний этап, и для каждого из этих направлений выбрать управление на последнем этапе. Естественно, это будет условно оптимальное управление, поскольку оно основано на предположении, что предыдущий этап окончился так-то. На I этапе не надо делать никаких гипотез о состоянии системы, так как начальное состояние задано условиями задачи. Поэтому с учетом найденных условно оптимальных управлений на последующих этапах мы можем найти, безусловно, оптимальное управление на I этапе, которое и является оптимальным управлением для всего процесса. Следовательно, задача динамического программирования решается в два этапа: на I этапе, который выполняется от конца процесса к началу, находят условные оптимальные решения; на II этапе, который выполняется от начала процесса к концу, находят безусловно оптимальное решение.

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

1. Исследуемый экономический процесс разбивается на составные элементы – этапы. Некоторые операции расчленяются на этапы естественно: например, при планировании производства на предприятии естественным этапом является год. Для других операций разделение на этапы приходится вводить искусственно.

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

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

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

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

7.2. Методика оптимального решения задачи

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

Пример 7.1. На рис. 7.1 показана модель участка транспортной сети и дороги, соединяющие начальный пункт 1 с конечным пунктом 12. Указаны

также расстояния между пунктами в километрах. Условно пункты транспортной сети разбиты на 6 этапов.

Требуется выбрать маршруты движения от пункта 1 до пункта 12 наименьшей протяженности.

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

Для рассматриваемой задачи аналитическая модель (функциональное уравнение) имеет следующий вид:

,

где - расстояние между пунктами i и j; f_j – минимальное расстояние передвижения от пункта j к конечному пункту 12 по допустимым маршрутам при использовании оптимальной стратегии.

Критерием оптимальности является минимальное расстояние в км при движении между пунктами 1 и 12.