Раздел 8. Динамические задачи, марковские модели принятия решений

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

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

Рассмотрим экономическую задачу распределения ресурсов: пусть есть начальный капитал k_o . Его можно потратить на несколько предприятий P₁ ,P₂ ,...,P_n.

X_ij - количество средств вкладываемых в i - ом году, в j - ое предприятие. В результате получается эффект: W_ij = f (X_ij )

В общем случае это не линейная функция.

W = ∑ f (X_ij ) → max

∑ X_ij ≤ k₀

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

Бег на 800 метров. Каждый бегун имеет запас энергии, который он тратит на каждые 100 метров. t_i – время на i – й 100 метров. ∑ t_i (x_i) → min; ∑ x_i ≤ x₀. Оказывается, на первых 100 метров бегун будет обеспечивать минимальное время.

Принцип оптимальности Беллмана

Принцип оптимальности Беллмана ставит вопрос о том, что такое оптимальность отдельного элемента системы с точки зрения оптимальности всей системы. Принимая решение на отдельном этапе, мы должны выбирать управление на этом этапе с прицелом на будущее, т. к. нас интересует результат в целом за все шаги. Беллман предложил рассматривать величину выигрыша от i - го шага и до конца, если i - ый шаг начинается с некоторого состояния S . Такую величину называют условным оптимальным выигрышем W_i (S) .

Тогда, принимая решение на i − м шаге, мы должны выбрать X_i так, чтобы условный оптимальный выигрыш был максимальным от i − шага и до конца.

Определение: оптимальность в малом понимается через оптимальность в большом.

Любой процесс имеет где-то окончание, т. е. имеет горизонт планирования. Тогда последний этап «не имеет будущего». Вот именно его можно оптимизировать только из условий данного этапа. После этого приступают к оптимизации (m - 1) - го этапа. Выбирают такое X_m-1,чтобы при применении этого X_m-1 его внести в управление последнего шага. При этом мы задаём состояние, с которого начинается (m − 1) − ый шаг. Поэтому функцию W_i (S) называют условным оптимальным выигрышем. Таким образом, процесс оптимизации разворачивается от конца к началу, и начальное состояние становится известно. Принцип Беллмана нашёл применение в методе программно-целевого планирования (любое действие планируется некоторым проектом).

Задача о наборе высоты и скорости летательного аппарата.

Летательный аппарат находится на высоте h₀ и летит со скоростью v₀. Необходимо перевести его на высоту h₁со скоростью v₁. Причём h₁ > h₀, v₁ > v₀ . Разобьём участокот h₀ до h₁ на n частей:

Известен расход горючего при переводе системы на Δh при v = const и на Δv при h = const . Таким образом, из каждого состояния есть лишь два управления.

За каждое такое управление получим расход горючего (выигрыш и потери). Суммарные потери равны сумме всех выигрышей на всех шагах. Дойдя до конца и получив 22, мы получим минимальную величину потерь горючего.

Любая задача, сводится к поиску минимального пути в графе и решается методом динамического программирования.

Функциональное уравнение Беллмана.

Назовём состоянием системы вектор координат: S = (ξ₁, ξ₂,...,ξ_L) (кси - ξ) . В некоторых задачах состояние – одна величина. Тогда работу системы можно представить как движение в фазовом пространстве – пространстве состояний. Назовём шаговым управлением – управление на i - ом шаге. Рассмотрим процесс управления системой за m шагов. Функция W_i (S, U_i ) называется выигрышем на i- ом шаге. Здесь S - состояние перед i - ым шагом, а U_i - управление на i - ом шаге.

Величина W_i (S, U_i ) должна быть известна до начала динамического программирования. Если состояние перед i - ым шагом было S и мы приняли какое-то управление U_i , то система перейдёт в новое состояние S^' 𝜑_i (S, U_i ). Эта функция должна быть так же известна. Если эти функции не заданы, то их надо сформулировать. Введём W_i (S )- условный оптимальный выигрыш. Это выигрыш на всех этапах от i до конца, если i - ый шаг начинается с состояния S .

Рассмотрим m шагов. Начнём с (i +1)- го шага. Мы системой управляем оптимально, величина оптимального выигрыша W_i+1 (S^' ). На i - ом шаге - любое управление. W̃_i (S^' ) - неоптимальный выигрыш, т. к. на i − ом шаге мы применяем управление U_i

Это функциональное уравнение Беллмана. Для использования уравнения Беллмана начинают сконца:

1. i = m

   
   

2. i = m - 1

   

   Итак, идя от конца к началу, мы получаем последовательно:
   W_m (S), W_{m - 1} (S),...,W₁ (S)
   U_m (S), U_{m - 1} (S),...,U₁ (S)
   Придя в начальное состояние W₁ (S), мы можем подставить S = S₀ и W₁ (S₀ ) = W_max - это безусловный выигрыш.

   Теперь необходимо получить, идя от начала к концу по цепочке, безусловно оптимальное уравнение:

   

   Итак, в конце мы получаем:

   

---

Предыдущая лекция  |  Следующая лекция