§1. Динамическое программирование как метод оптимизации.
Общая характеристика.
Динамическое программирование (ДП) – это метод оптимизации многошаговых процессов принятия решений, позволяющий указать пути исследования целого класса экстремальных задач. Этот метод оказывается эффективным для задач с сепарабельной целевой функцией (функция нескольких переменных, которая представляет собой сумму функций одной переменной). К таким задачам, в частности, относятся задачи линейного программирования.
Многие экономические задачи расчленяются на шаги естественным образом. К ним относятся задачи планирования и управления, в которых естественным шагом является год, квартал, месяц, неделя, день и т.д. Кроме этого метод ДП может использоваться при решении задач, в которых время вообще не фигурирует. Необходимость принятия решений возникает тогда, когда производятся те или иные целенаправленные действия; например, некоторая физическая система переводится из одного состояния в другое посредством приложения управляющих воздействий. Если подобные ситуации повторяются периодически, то организуется процесс принятия решений. К таким задачам относятся задачи оптимального управления.
Итак, рассмотрим некоторый многошаговый процесс. Его нужно организовать так, чтобы получить наилучший результат с точки зрения принятого критерия Z оптимальности. Если этот критерий имеет числовое значение, то критерий оптимальности нужно минимизировать или максимизировать.
Пусть процесс принятия решения разбивается на n шагов. Действия, совершаемые на j-ом шаге, характеризуются совокупностью показателей . Состояние процесса к началу этого шага характеризуется совокупностью параметров = . Очевидно, что вектор управления является функцией состояния системы: = (). Начальное состояние системы задано. Результирующее значение критерия Z определяется теми , j =1, которые были приняты ранее: Z=Z(, , …, ).
Возникает вопрос: как выбрать , , …, , чтобы величина Z приняла экстремальное значение? Можно рассматривать Z как функцию переменных , используя для нахождения экстремума один из известных способов оптимизации. Однако этот путь не всегда прост. Появилась идея провести оптимизацию поэтапно, анализируя последовательно каждый шаг процесса в поисках варианта его наилучшего продолжения. Эта идея лежит в основе метода динамического программирования.
Итак, важным условием применимости метода динамического программирования является возможность разбиения процесса принятия решений на ряд однотипных шагов, каждый из которых планируется отдельно, но с учетом результатов, полученных на предыдущих шагах.
Динамическое программирование основывается на двух важных принципах: принцип оптимальности и принцип вложения (или погружения).
Принцип оптимальности: необходимо всегда обеспечивать оптимальное (в смысле принятого критерия) продолжение процесса относительно уже достигнутого состояния. Другими словами, на каждом шаге решение должно приниматься оптимальное и должно учитывать результат, полученный на предыдущих шагах. С точки зрения математики это реализуется в составлении неких рекуррентных соотношений.
Принцип вложения (погружения). Природа задачи, для которой используется метод ДП, не меняется при изменении числа шагов, поэтому задача погружается в семейство подобных задач, являясь одной из них.
Реализация названных принципов дает гарантию, что 1) решение, принимаемое на очередном шаге, окажется лучшим с точки зрения всего процесса; 2) последовательность решений одношаговой, двухшаговой и т.д. задач приведет к решению исходной n-шаговой задачи.
Схема динамического программирования чаще всего (но не всегда) строится так, что первым исследуется последний (конечный) шаг задачи. Этот завершающий этап может быть спланирован наилучшим образом с точки зрения критерия Z сам по себе. Но (!) с учетом ожидаемых исходов предыдущего этапа, еще не исследованного. Поэтому получаем набор условно оптимальных решений.
Завершив исследование последнего этапа, применяют те же рассуждения для предпоследнего этапа, но теперь цель – достигнуть экстремального значения Z не на одном (предпоследнем) этапе, а на двух последних вместе. Тем самым будет найден второй набор условно оптимальных решений. Повторяем подобные операции для третьего, четвертого и т.д. этапов, в результате получаем решение задачи.
Отметим преимущества метода динамического программирования:
Дает возможность решать задачи, которые ранее не исследовались из-за отсутствия математического аппарата, например, конечномерные задачи с дискретной структурой.
Позволяет упростить поиск оптимальных решений в ряде случаев за счет резкого сокращения объемов вычислений, например, в комбинаторных задачах.
Отметим недостатки метода динамического программирования:
Отсутствие универсального алгоритма, пригодного для решения всех задач (есть общая идея, а алгоритм формируется для каждой конкретной задачи отдельно). Поэтому результат во многом зависит от опыта математика-исследователя.
Трудности при анализе задач большой размерности (для решения конкретных задач нужны ЭВМ с большой оперативной памятью, поскольку размер таблиц от этапа к этапу может расти экспоненциально). Этот недостаток даже получил специальное название – «проклятие размерности».