то ли сумму набирать, то ли вначале несколько слов про ДП (дин. прогр.) сказать
все слова забыла
щас в одном месте подсмотрю
Беллман Р., Калаба Р. Динамическое программирование и современная теория управления // М.: Наука, 1969, 118 стр.Многошаговые процессы принятия решения. Принцип оптимальности Беллмана. Основное функциональное уравнение Беллмана. В качестве примера общей модели управляемого процесса, т.е. процесса, для которого имеется возможность выбирать какие-то параметры, влияющие на его ход, рассмотрим многошаговый процесс принятия решений, предложенный американским математиком Ричардом Беллманом, основоположником теории динамического программирования (динамической оптимизации).
Пусть
– пространство состояний системы (у физиков - фазовое пространство), функция
– преобразование, переводящее систему из состояния
в состояние
где
Определение 1. Бесконечная последовательность состояний системы
$$\[p_0, \ p_1, \dots, \ p_n, \dots \] \ ãäå \ p_0 = p \ è \ p_{n+1} = T(p_n), \ n = 0, \ 1, \ 2, \dots $$ есть история системы, наблюдаемая в дискретные моменты времени, или
многошаговый процесс.
Расширим понятие многошагового процесса, предположив, что на каждом шаге мы можем управлять переходами системы из состояния
в состояние
с помощью вектора
, где значения вектора
выбираются из набора допустимых векторов
. Вектор
называется
вектором решения, и выбор вектора
называется решением или
шаговым управлением.
Простейший
- шаговый процесс принятия решений есть последовательность векторов состояния и векторов управления
, где
для всех
.
Пусть, помимо функции
переходов системы из состояния в состояние, у нас также задана
скалярная функция критерия или
функция дохода, которая зависит от всех состояний процесса
и всех выбранных пошаговых управлений
.
Определение 2. Назовем последовательность пошаговых управлений
стратегией. Стратегия, максимизирующая функцию дохода, называется
оптимальной стратегией или
оптимальным управлением.
1. Будем рассматривать только системы, которые обладают свойством
отсутствия последействия, т.е. состояние, в котором оказывается система после выбора решения (управления) на
-м шаге, зависит только от исходного состояния к началу
-го шага и выбранного управления.
2. Предположим, что структура функции дохода такова, что оптимальное управление на каждом шаге зависит только от текущего состояния системы.
Принцип оптимальности Беллмана.Оптимальная стратегия обладает тем свойством, что, каковы бы ни были первоначальное состояние и первоначальное решение (управление), последующее решение должно определять оптимальную стратегию относительно состояния, полученного в результате первоначального решения.разъясняем
начальное состояние
и начальное управление
- любые, они перевели систему в новое состояние
. Забываем историю процесса, раз наше текущее состояние
, значит, выстраиваем оптимальную стратегию относительно начального состояния
надеюсь, теперь понятно
Если
в качестве функции дохода использовать аддитивную функцию, где общий выигрыш складывается из суммы выигрышей по всем шагам, то принцип выбора оптимальных пошаговых управлений формулируется так:
«Каково бы ни было состояние системы перед очередным шагом, надо выбрать управление на этом шаге так, чтобы выигрыш на данном шаге плюс оптимальный выигрыш на всех последующих шагах был максимальным».Используя это соображение, можно записать основное рекуррентное соотношение динамического программирования (функциональное уравнение Беллмана), позволяющее получить как аналитически, так и численно оптимальную стратегию и максимальный доход.
Перечислим еще раз
требования к задаче, позволяющие применить метод динамического программирования.1. Объектом исследования должна служить управляемая система с заданными допустимыми состояниями и допустимыми управлениями.
2. Задача должна позволять интерпретацию как многошаговый процесс, каждый шаг которого состоит из принятия решения о выборе одного из допустимых управлений, приводящих к изменению состояния системы.
3. Состояния системы на каждом шаге должны описываться одинаковым набором параметров.
4. Задача не должна зависеть от количества шагов.
5. Состояние, в котором оказывается система после выбора решения (управления) на
-м шаге, зависит только от данного управления и состояния системы перед
-м шагом (отсутствие последействия, будущее зависит только от настоящего и не зависит от прошлого).
6. Для каждых двух последовательных состояний системы
и
существует известная функциональная зависимость, зависящая от выбранного управления
:
.