Добавил:
Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
Скачиваний:
128
Добавлен:
10.12.2013
Размер:
1.25 Mб
Скачать

Динамическое программирование

Глава 9. Динамическое программирование

Динамическое программирование - один из мощных методов решения задач математического программирования, разработанный американским математиком Р. Беллманом в конце 50-х годов. Он изначально ориентирован на оптимизацию так называемых многошаговых (многостадийных, многоэтапных) процессов и использование ЭВМ.

Концепция метода проистекает из следующего свойства оптимального решения. Пусть оптимальный путь из точки A в точку E проходит через точки B, С и D (рис. 9.1). Тогда любая часть этого пути является оптимальным путем. Действительно, если бы, например, оптимальный путь из C в E не проходил через D, то и полный путь A,B,C,D,E не был бы оптимальным (его можно было бы улучшить за счет изменения перехода из C в E), что противоречит исходной посылке.

Рис. 9.1

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

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

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

f=(<оператор> <f1, f2,...,fm>).

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

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

При разбиении задачи на шаги состояние служит связующим звеном между смежными шагами. Состояние зависит от предшествующих решений, но зная его, можно принимать решения на последующих шагах без учета решений, предшествовавших данному состоянию. Обратим внимание на важный момент: чтобы принять очередное решение, достаточно знать состояние, а не решения, приведшие к этому состоянию. Так, например, при корректировке траектории некоторого летательного аппарата (в однородной среде) достаточно знать его координаты на момент принятия решения, и не нужны решения, приведшие его в данную точку пространства. Значит, координаты и определяют состояние системы. Если же выбор решения зависит также от количества топлива на борту аппарата, то состояние системы будет определяться как координатами, так и весом оставшегося топлива. Итак, состояние описывается теми переменными системы, которые зависят от решения на предшествующем шаге и знание которых достаточно для принятия решения на очередном шаге. Чтобы отличать переменные состояния от искомых переменных (управлений), в дальнейшем будем называть их параметрами состояния.

Соседние файлы в папке Лекции по Гольду