Главная » Справочник » Основы организации и управления транспортными системами » Идея и общий алгоритм метода динамического программирования

Идея и общий алгоритм метода динамического программирования

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

Поэтому методы динамического программирования имеют следующие принципиальные отличия от методов оптимизации статических задач:

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

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

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

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

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

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

Следовательно, задача динамического программирования решается в два этапа: на I этапе, который выполняется от конца процесса к началу, находят условные оптимальные решения; на II этапе, который выполняется от начала процесса к концу, находят безусловно оптимальное решение.

Алгоритм метода динамического программирования включает следующие действия:

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

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

Предыдущая статья Идея и алгоритм определения оптимального варианта плана формирования поездов Следующая статья Изобретение паровой машины и принцип ее работы

Статьи по теме