Общая характеристика методов динамического программирования

Динамическое программирование — один из разделов опти­мального программирования. Для него характерны специфиче­ские методы и приемы, обусловливающие возможность примене­ния динамического программирования для решения определен­ного круга задач. Например, использование принципа оптималь­ности, который выражает оптимальное поведение, т. е. обладает тем свойством, что, каково бы ни было оптимальное первона­чальное решение, последующие решения должны быть по отношению к нему также оптимальными. Принцип оптимально­сти позволяет установить соотношение между экстремальными значениями целевой функции в задачах, характеризующихся различной продолжительностью процесса и различными началь­ными состояниями. При этом необходимо учитывать последствия реализации найденного оптимального решения и для последую­щих решений. Такой подход обусловливает выработку оптималь­ной стратегии. Процесс принятия решения в этом случае являет­ся многошаговым. Получаемые на каждом этапе соотношения последовательно связаны между собой: полученные на &-м шаге результаты вводятся в уравнения (k—1)-го или (&+1)-го шагов. Таким образом, при решении вариантных оптимизационных за­дач методами динамического программирования последние раз­биваются на отдельные этапы, каждый из которых решается самостоятельно. Тем самым сложная задача со многими пере­менными сводится ко многим задачам с малым числом или даже одной переменной. Это значительно сокращает объем вычисле­ний и ускоряет процесс получения управленческого решения.

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

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

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

Для процессов с непрерывным временем динамическое про­граммирование рассматривается как предельный вариант дис­кретной схемы. Получаемые при этом результаты практически совпадают с теми, которые получаются методами, построенными на теории Л. С. Понтрягина [18].

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

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

Эффективно также применение марковских и полумарковских процессов решения при определении оптимальной стратегии слу­чайного процесса. Случайный процесс — это стохастический, вероятностный процесс. Его протекание может быть различным в зависимости от случая, но вероятность каждого течения опре­делена. Случайный процесс может быть непрерывным или дис­кретным. В рассматриваемом процессе независимой переменной является время, функция от независимой переменной — случай­на. Случайный" процесс характеризуется множеством значений его состояний. В зависимости от того, непрерывны или дискрет­ны эти значения, случайный процесс будет непрерывным или дискретным. Методы, основанные на применении марковских или полумарковских процессов решения, применяются в задачах поиска неисправностей в оборудовании, построения графика ре­монта, обслуживания и замены оборудования.

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

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

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

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