 |
 |
 |
 |
|
 |
 |
92
операций, что при больших n и b существенно меньше, чем в первом случае. Например, если п = 6 и b =
30, то непосредственный перебор потребует выполнения 324 632 операций, а метод динамического
программирования — только 2511.
5.1.3. Принцип оптимальности Беллмана. Еще раз подчеркнем, что смысл подхода, реализуемого в
динамическом программировании, заключен в замене решения исходной многомерной задачи
последовательностью задач меньшей размерности.
Перечислим основные требования к задачам, выполнение которых позволяет применить данный
подход:
объектом исследования должна служить управляемая система (объект) с заданными
допустимыми состояниями и допустимыми управлениями;
задача должна позволять интерпретацию как многошаговый процесс, каждый шаг которого
состоит из принятия решения о выборе одного из допустимых управлений, приводящих к
изменению состояния системы;
задача не должна зависеть от количества шагов и быть определенной на каждом из них;
состояние системы на каждом шаге должно описываться одинаковым (по составу) набором
параметров;
последующее состояние, в котором оказывается система после выбора решения на k-м. шаге,
зависит только от данного решения и исходного состояния к началу k-го шага. Данное свойство
является основным с точки зрения идеологии динамического программирования и называется
отсутствием последействия.
Рассмотрим вопросы применения модели динамического программирования в обобщенном виде.
Пусть стоит задача управления некоторым абстрактным объектом, который может пребывать в
различных состояниях. Текущее состояние объекта отождествляется с некоторым набором параметров,
обозначаемым в дальнейшем ? и именуемый вектором состояния. Предполагается, что задано
множество ? всех возможных состояний. Для объекта определено также множество допустимых
управлений (управляющих воздействий) X, которое, не умаляя общности, можно считать числовым
множеством. Управляющие воздействия могут осуществляться в дискретные моменты времени
k(k?1:n), причем управленческое решение заключается в выборе одного из управлений x
k
?Х. Планом
задачи или стратегией управления называется вектор х = (х1, х2, .., x
n-1
), компонентами которого служат
управления, выбранные на каждом шаге процесса. Ввиду предполагаемого отсутствия последействия
между каждыми двумя последовательными состояниями объекта
?
k
и
?
k+1
существует известная
функциональная зависимость, включающая также выбранное управление: ?
k+1
= ?
k
(x
k
, ?
k
), k?1:п-1. Тем
самым задание начального состояния объекта
?
1
?? и выбор плана х однозначно определяют
траекторию поведения объекта, как это показано на рис. 5.1.
Эффективность управления на каждом шаге k зависит от текущего состояния
?
k
, выбранного
управления x
k
и количественно оценивается с помощью функций f
k
(х
k
, ?
k
), являющихся слагаемыми
аддитивной целевой функции, характеризующей общую эффективность управления объектом.
(Отметим, что в определение функции f
k
(х
k
, ?
k
) включается область допустимых значений х
k
, и эта
область, как правило, зависит от текущего состояния
?
k
.) Оптимальное управление, при заданном
начальном состоянии
?
1
, сводится к выбору такого оптимального плана х*, при котором достигается
максимум суммы значений f
k
на соответствующей траектории.
Основной принцип динамического программирования заключается в том, что на каждом шаге
следует стремиться не к изолированной оптимизации функции f
k
(х
k
, ?
k
), а выбирать