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

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

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

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

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

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

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

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

Date: 2015-09-24; view: 626; Нарушение авторских прав