На этом шаге мы рассмотрим введение в динамическое программирование.
Динамическое программирование (ДП) определяет оптимальное решение n-мерной задачи путем ее декомпозиции на n этапов, каждый из которых представляет собой подзадачу относительно одной переменной. Вычислительное преимущество такого подхода состоит в том, что мы занимаемся решением одномерных оптимизационных задач подзадач вместо большой n-мерной задачи.
Фундаментальным принципом ДП, составляющим основу декомпозиции задачи на этапы, является оптимальность (на каждом этапе оптимальная стратегия определяется независимо от стратегий, использованных на предыдущих этапах). Так как природа каждого этапа решения зависит от конкретной оптимизационной задачи, ДП не предлагает вычислительных алгоритмов непосредственно для каждого этапа. Вычислительные аспекты решения оптимизационных подзадач на каждом этапе проектируются и реализуются по отдельности (но это не исключает того, что может быть применен единый алгоритм для всех этапов).
Вычисления в ДП выполняются рекуррентно в том смысле, что оптимальные решения одной подзадачи используются в качестве исходных данных для следующей подзадачи. Способ выполнения рекуррентных вычислений зависит от того, как выполняются декомпозиции исходной задачи. В данной ситуации возможны несколько вариантов. Первый из них это проводить вычисления последовательно от первого до последнего этапа, такая последовательность известна как алгоритм прямой прогонки (шаг 106). Задача может быть решена с помощью алгоритма обратной прогонки (шаг 107), в соответствии с которым вычисления проводятся от последнего этапа до первого. Очевидно, что алгоритмы прямой и обратной прогонки приводят к одному и тому же решению. Обычно более логичным представляется использовать алгоритм прямой прогонки, но в общем случае алгоритм обратной прогонки может быть более эффективным с вычислительной точки зрения. Продемонстрируем ДП на решение конкретных задач. В последующих шагах будут рассмотрены следующие задачи:
- Задача о загрузке;
- Задача планирования рабочей силы;
- Задача замены оборудования;
- Задача инвестирования;
При рассмотрении каждого примера особое внимание обратите на три основных элемента моделей динамического программирования.
- Определение этапов.
- Определение на каждом этапе вариантов решения (альтернатив).
- Определение состояний на каждом этапе.
Со следующего шага мы начнем рассматривать рекуррентный алгоритм прямой прогонки.
