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

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

Основные понятия

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

\[ J = \sum_{t=0}^{T-1} L(x_t, u_t, t) + \Phi(x_T) \]

где \( x_t \) — состояние системы в момент времени \( t \), \( u_t \) — управление, \( L \) — мгновенная стоимость (или выгода), \( \Phi \) — терминальная стоимость, \( T \) — горизонт планирования. Переход между состояниями задаётся уравнением:

\[ x_{t+1} = f(x_t, u_t, t) \]

Для непрерывного времени используется аналогичная формулировка с интегралом вместо суммы.

Классификация

По типу времени

• Дискретное время: шаги фиксированы, состояния и управления определены в моменты \( t = 0, 1, \dots, T \). Применяется в задачах с конечным числом периодов (например, управление запасами, планирование производства).
• Непрерывное время: время непрерывно, управление может меняться в любой момент. Решается с помощью уравнения Гамильтона — Якоби — Беллмана (ГЯБ). Используется в задачах оптимального управления ракетами, экономического роста.

По горизонту планирования

• Конечный горизонт: \( T \) фиксировано. Решение зависит от оставшегося времени.
• Бесконечный горизонт: \( T = \infty \). Решение стационарно (не зависит от абсолютного времени), если задача автономна. Часто решается методом итерации по стоимости или политике.

По детерминированности

• Детерминированные: переходы состояний известны точно.
• Стохастические: переходы случайны, известны только вероятности. В этом случае используется принцип оптимальности в среднем или ожидаемом значении.

Уравнение Беллмана

Центральным инструментом является уравнение Беллмана. Для дискретного времени с конечным горизонтом оно записывается как:

\[ V_t(x) = \min_{u} \left[ L(x, u, t) + V_{t+1}(f(x, u, t)) \right] \]

где \( V_t(x) \) — оптимальная стоимость (функция ценности) в момент \( t \) при состоянии \( x \). Для непрерывного времени уравнение ГЯБ имеет вид:

\[ -\frac{\partial V}{\partial t} = \min_{u} \left[ L(x, u, t) + \frac{\partial V}{\partial x} f(x, u, t) \right] \]

Решение этих уравнений даёт оптимальное управление \( u^*(x, t) \).

Применение

Экономика и финансы

• Оптимальный рост: модель Рамсея — Касса — Купманса, где потребление и накопление капитала выбираются для максимизации дисконтированной полезности.
• Ценообразование опционов: модель Блэка — Шоулза, где стоимость опциона удовлетворяет уравнению в частных производных, выводимому из принципа динамического программирования.
• Управление портфелем: выбор доли активов во времени с учётом риска и доходности.

Теория управления

• Управление роботами: планирование траектории с минимальным расходом энергии или времени.
• Авиация и космонавтика: оптимальное управление двигателями, коррекция орбиты.
• Автоматическое управление: синтез регуляторов, например, линейно-квадратичный регулятор (LQR) является частным случаем динамического программирования по времени.

Исследование операций

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

Компьютерные науки

• Алгоритмы с временными ограничениями: например, задача о рюкзаке с временными окнами.
• Обработка сигналов: фильтрация Калмана, которая является рекурсивным байесовским фильтром, основанным на принципах динамического программирования.
• Искусственный интеллект: обучение с подкреплением, где агент учится оптимальной политике через взаимодействие со средой, используя уравнение Беллмана.

Примеры задач

Задача о кратчайшем пути с временными окнами

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

Управление запасом с учётом сезонности

Компания должна закупать товар каждый месяц, чтобы удовлетворить случайный спрос. Стоимость хранения и заказа известны. Спрос меняется по месяцам. Задача решается методом динамического программирования по времени: состояние — уровень запаса на начало месяца, управление — объём заказа, горизонт — 12 месяцев. Уравнение Беллмана учитывает ожидаемые будущие затраты.

Связь с другими методами

• Линейное программирование: некоторые задачи динамического программирования по времени могут быть сведены к задачам линейного программирования большой размерности.
• Метод Монте-Карло: используется для оценки функции ценности в стохастических задачах с большим пространством состояний.
• Нейронные сети: в глубоком обучении с подкреплением (Deep Q-Networks) аппроксимируют функцию ценности для непрерывных состояний и времени.

Ограничения

• Проклятие размерности: число состояний растёт экспоненциально с числом переменных, что делает точное решение невозможным для больших задач.
• Необходимость дискретизации: для непрерывных задач требуется дискретизация времени и состояний, что может приводить к потере точности.
• Предположение о марковости: состояние должно содержать всю информацию, необходимую для принятия решения. Если это не так, требуется расширение до частично наблюдаемых марковских процессов принятия решений (POMDP).

История

Основы динамического программирования были заложены Ричардом Беллманом в 1950-х годах. Он сформулировал принцип оптимальности и разработал уравнения для дискретных и непрерывных задач. В 1957 году вышла его книга «Dynamic Programming», где были приведены первые примеры применения к задачам управления запасами и планирования. В 1960-х годах Лев Понтрягин разработал принцип максимума, который является альтернативным подходом к задачам оптимального управления с непрерывным временем. В 1970-х годах динамическое программирование по времени стало активно применяться в экономике (модели оптимального роста, теория реальных опционов). В 1980-х годах с развитием вычислительной техники появились численные методы решения (итерация по стоимости, итерация по политике). В 1990-х годах возникло обучение с подкреплением, которое объединило динамическое программирование с методами машинного обучения.

Источники

• Беллман Р. «Динамическое программирование». — М.: Издательство иностранной литературы, 1960.
• Берцекас Д. «Динамическое программирование и оптимальное управление». — М.: Мир, 1977.
• Понтрягин Л. С. и др. «Математическая теория оптимальных процессов». — М.: Наука, 1969.
• Сарджент Т. Дж. «Динамическое макроэкономическое моделирование». — М.: Издательский дом ГУ ВШЭ, 2007.
• Sutton R. S., Barto A. G. «Reinforcement Learning: An Introduction». — MIT Press, 2018.