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

 Стохастическое динамическое программирование

• Отличие: Функция перехода T(s, x) или немедленный выигрыш r(s, x) являются случайными величинами.

• Подход: Оптимизация ожидаемого значения целевой функции.

• Рекуррентное соотношение:
  f_k(s) = opt_{x ∈ X} E[ r(s, x, ω) + f_{k+1}( T(s, x, ω) ) ]

  • ω — случайное событие (реализация неопределенности).

• Пример: Управление запасами при случайном спросе.

ДП и сетевое представление

• Задача о кратчайшем пути — канонический пример ДП.

• Этапы: Шаг k — переход на k-ю дугу.

• Состояние: s — текущий узел в сети.

• Решение: Выбор следующей дуги.

• Уравнение Беллмана:
  d(j) = min_{i} [ d(i) + c_{ij} ] для всех узлов j,
  где d(j) — длина кратчайшего пути до узла j.

 Проклятие размерности (Curse of Dimensionality)

• Проблема: Количество состояний s растет экспоненциально с увеличением числа параметров, его описывающих.

• Пример: Если состояние описывается 5-ю переменными, каждая из которых может принимать 10 значений, число состояний = 10^5 = 100,000.

• Следствие: Вычислительная сложность делает решение многих практических задач методом ДП невозможным.

• Пути смягчения: Аппроксимационное ДП, агрегация состояний, методы Монте-Карло.

Сравнение с другими методами ИО

• ДП vs Линейное программирование (ЛП):

  • ДП: Для дискретных, многоэтапных задач.

  • ЛП: Для задач с непрерывными переменными и линейными ограничениями. Часто более эффективно для больших задач.

• ДП vs Жадные алгоритмы:

  • Жадные алгоритмы делают локально оптимальный выбор в надежде на глобальный оптимум.

  • ДП гарантирует глобальный оптимум, проверяя все варианты системно, но за бóльшую вычислительную цену.

Заключение: Сильные стороны ДП

• Гарантирует нахождение глобального оптимума для задач с оптимальной подструктурой.

• Универсален: Применим к детерминированным и стохастическим задачам.

• Нагляден: Процесс заполнения таблиц предоставляет ценную информацию для ЛПР.

• Точен: В отличие от эвристик, дает точный ответ.

Заключение: Слабые стороны ДП

• Проклятие размерности. Главное ограничение.

• Требует вывода рекуррентного соотношения. Для новых задач это может быть нетривиально.

• Не всегда применимо. Если задача не обладает оптимальной подструктурой или свойствами без последействия, ДП не работает.

Сфера применения ДП в ИО

• Управление запасами и цепями поставок

• Планирование инвестиций и управление портфелем

• Планирование производства и ремонтов

• Управление проектами (CPM, PERT)

• Маршрутизация и логистика

• Биоинформатика (выравнивание последовательностей)

Историческая справка

• Ричард Э. Беллман (Richard E. Bellman) — отец-основатель термина и метода (1950-е гг.).

• Термин «динамическое» был выбран для того, чтобы звучать «модно» и получить финансирование от RAND Corporation.

• Истоки метода прослеживаются в работах А. Н. Колмогорова и Дж. фон Неймана.

Ключевые выводы

1. ДП — мощный метод для многоэтапного принятия решений.

2. Основа — Принцип оптимальности Беллмана.

3. Реализуется через рекуррентные соотношения.

4. Сила — точность. Слабость — «проклятие размерности».

5. Остается краеугольным камнем теории оптимизации.

Вопросы для самоконтроля

1. Сформулируйте Принцип оптимальности Беллмана своими словами.

2. В чем разница между состоянием и этапом?

3. Почему «проклятие размерности» является фундаментальным ограничением ДП?

4. Какую задачу ИО вы бы решали с помощью ДП, а какую с помощью ЛП?