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

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

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

Сущность метода динамического программирования заключается в замене одной задачи со многими переменными рядом последовательно решаемых задач с существенно меньшим числом переменных.

Оптимизация этого многошагового процесса проводится на основе сформулированного Беллманом [10, 12] принципа оптимальности: оптимальное поведение обладает тем свойством, что, каковы бы ни были первоначальное состояние и первоначальное решение, последующее решение должно определять оптимальное поведение относительно состояния, полученного в результате первоначального решения. Смысл этого принципа состоит в том, что поэтапное планирование многошагового процесса должно проводиться таким образом, чтобы при планировании каждого шага учитывалась не выгода, получаемая только на данном шаге, а общая выгода, получаемая по окончании всего процесса, и именно относительно общей выгоды производится оптимальное планирование.

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

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

дебетовые карты