11.1. Общие понятия о динамическом программировании
Задачи оптимального планирования (управления) обычно состоят в следующем.
Рассматривается некоторая система S, состояние которой со временем меняется. Процесс изменения состояний системы — управляемый, т. е. можно влиять на его ход посредством выбора управляющих факторов Uv С процессом связан некоторый критерий W, характеризующий качество управления и зависящий от него. Оптимальность планирования означает выбор наилучшего управления для достижения поставленной цели, т.е. выбор такого U, чтобы W(U) было оптимальным.Задачи динамического программирования имеют ряд особенностей.
В них рассматривается процесс поведения системы во времени.
Состояние системы в каждый момент времени однозначно определяется численными значениями небольшого набора параметров.
Операция выбора решения состоит в преобразовании этого набора параметров в такой же набор с другими числовыми значениями.
Если система в рассматриваемый момент времени находится в некотором состоянии, то ее поведение в дальнейшем определяется этим состоянием и выбираемым управлением, но не зависит от предыстории (т. е. от того, в каких состояниях находилась система до этого момента).
Пусть имеется система S, состояние которой характеризуется вектором X = (*!, х2, ..., хп).
Численное значение набора параметров в момент времени і обозначим через хг
Пусть в момент і на систему S воздействует управляющий фактор U\ в результате которого в следующий момент і + 1 она пере- ходит в новое состояние. Символически такой переход можно представить в виде
?(х/Г+Ч
Пример 11.1. Пусть имеется сеть дорог, соединяющих населенные пункты.
Рассмотрим в качестве системы человека, передвигающегося из одного пункта в другой.Процесс движения естественно рассматривать как многоэтапный. Каждый этап состоит в переходе из одного пункта в соседний и совершается (условно) за единицу времени. Человек, находящийся в момент і в каком-то пункте Kv вообще говоря, может из него попасть в различные соседние пункты. Управление U\ принимаемое системой — человеком, и будет определять выбор конкретного соседнего пункта Кі+Ь в который человек будет двигаться из Kv Очевидно, ЧТО следующие СОСТОЯНИЯ человека (пункт Ki+ j), в котором он окажется через единицу времени, однозначно определяется его предыдущим состоянием Kt (пунктом, где он был) и принятым управлением (I — решением куда двигаться.
Если в нашем примере человек поставил цель попасть из пункта А в пункт В, то естественно возникает задача выбрать управление так, чтобы движение из А в В проходило по кратчайшему пути. Оптимальное управление - это последовательность решений о том, через какие пункты надо двигаться, чтобы пройденный путь из А в В был самым коротким из всех возможных.
Специфика метода динамического программирования состоит в том, что для отыскания оптимального управления изучаемый процесс расчленен на этапы. Он представляется как развивающийся по этапам, причем каждый раз оптимизируется управлением только на одном этапе.
Динамическое программирование (планирование) — это планирование дальновидное, с учетом будущего, а не близорукое, когда руководствуются принципом «лишь бы хорошо сейчас, а там — что будет».
Как же находить оптимальное управление в многошаговом процессе? Общее правило состоит в том, что управление на каждом шаге надо выбирать с учетом будущего. Из этого правила есть исключение это последний шаг, где можно действовать без оглядки на будущее: его на последнем шаге нет.
Управление на последнем шаге надо выбирать так, чтобы получить наибольший эффект без учета будущего (так как его нет). Поэтому процесс динамического планирования естественно разворачивается с конца, сначала планируется последний шаг.
Как же это планировать, если неизвестно, чем кончился предпоследний шаг.Очевидно, надо сделать различные предположения о том, чем кончился предпоследний шаг, и для каждого из них выбрать управление на последнем. Таким образом, приходим к понятию условно оптимального управления — оптимального управления, найденного в предположении, что предыдущий шаг окончился так-то.
Динамическое программирование основывается на принципе нахождения на каждом шаге условно оптимального управления для каждого возможного исхода предшествующего шага.
Руководствуясь этим принципом, мы разворачиваем процесс нахождения оптимального управления с конца, находя сначала условно оптимальное управление для каждого возможного исхода предпоследнего шага, а затем на основе его условно оптимальное управление на предпоследнем шаге и т. д., пока не дойдем до первого шага. На первом шаге нам надо делать гипотезы о состоянии системы — мы знаем, с чего начинается процесс, и можем с учетом найденных условно оптимальных управлений на последующих шагах найти безусловно оптимальное управление на первом шаге, т. е. такое управление, которое с учетом всех условно оптимальных управлений на последующих шагах дает оптимальное управление для всего процесса.
Итак, методология динамического программирования состоит в расчленении задачи на этапы и поэтапном построении оптимального управления на каждом шаге.