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

Динамическое программирование представляет собой мате­матический аппарат, который подходит к решению некоторого класса задач путем их разложения на части, небольшие и менее сложные задачи. При этом отличительной особенностью явля­ется решение задач по этапам, через фиксированные интерва­лы, промежутки времени, что и определило появление термина «динамическое программирование». Следует заметить, что мето­ды динамического программирования успешно применяются и при решении задач, в которых фактор времени не учитывается. В целом математический аппарат можно представить как поша­говое или поэтапное программирование. Решение задач метода­ми динамического программирования проводится на основе сформулированного Р. Э. Беллманом принципа оптимальности: оптимальное поведение обладает тем свойством, что каким бы ни было первоначальное состояние системы и первоначальное решение, последующее решение должно определять оптималь­ное поведение относительно состояния, полученного в резуль­тате первоначального решения.

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

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

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

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

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

Для процессов с непрерывным временем ДП рассматривает­ся как предельный вариант дискретной схемы решения. Получа­емые при этом результаты практически совпадают с теми, кото­рые получаются методами максимума Л. С. Понтрягина или Га­мильтона — Якоби — Беллмана.

ДП применяется для решения задач, в которых поиск опти­мума возможен при поэтапном подходе, например:

 распределе­ние дефицитных капитальных вложений между новыми направ­лениями их использования;

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

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

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

 поиск кратчайших расстояний на транспортной сети;

 при распределении инвестиций по направлениям использования;

разработки долгосрочных программ функционирования хозяйствующих субъектов;

 формирование последовательности раз­вития коммерческой операции и т. д.

< Предыдущая		Следующая >