Вычислительные алгоритмы динамического программирования

Тема 11. Метод динамического программирования

1. Общая постановка задачи динамического программирования

Определение 11.1. Динамическое программирование – это метод оптимизации, приспособленный к операциям, в которых процесс принятия решения может быть разбит на этапы (шаги). Такие операции называются многошаговыми.

Многие экономические процессы расчленяются на шаги естественным образом. Например, процессы планирования и управления, развиваемые во времени. Здесь естественный шаг: год, квартал, месяц и т.д.

Рассматриваемые ранее задачи (ЗЛП и ЗНП) относятся к задачам однократного принятия решений, ЗДП требует некоторой последовательности принятых решений и относится к многоэтапным (многошаговым) задачам.

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

В общем случае ЗДП формулируется следующим образом: имеется некоторая управляемая система S, характеризующаяся определенным набором параметров, задающих ее состояние, которая под влиянием управления переходит из начального состояния в конечное.

Состояние системы на каждом шаге определяется вектором-состояния . Дальнейшее изменение ее состояния зависит только от данного состояния и не зависит от того, каким путем система перешла в него (процесс без последействия).

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

Действие на каждом шаге связано с определенным выигрышем (доходом, прибылью) или потерей (издержками), которые зависят от состояния на начало шага и принятого решения:

– приращение целевой функции в результате i-го шага и принятого решения:

– значение целевой функции при переходе системы из начального состояния в конечное за n шагов.

На векторы-состояния и управления могут быть наложены ограничения, объединение которых составляет область допустимых решений .

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

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

2. Принцип оптимальности. Функциональные уравнения Беллмана

В основе вычислительных алгоритмов динамического программирования лежит принцип оптимальности, сформулированный Беллманом: каково бы ни было состояние системы S в результате i–1 шагов, управление на i-ом шаге должно выбираться так, чтобы оно в совокупности с управлениями на всех последующих шагах от (i+1)—го до n—го оптимизировало функцию цели.

Схема решения ЗДП состоит из двух частей:

1) обратный ход: от последнего шага к первому получают множество возможно оптимальных управлений («условно-оптимальных»);

2) прямой ход: от известного начального состояния к последнему из полученного множества «условно-оптимальных» управлений составляется искомое оптимальное управление для всего процесса в целом.

Принцип оптимальности Беллмана можно записать в математической форме следующим образом. Обозначим через – «условно-оптимальные» значения приращений целевой функции на последнем шаге, двух последних, …, на всей последовательности n шагов, соответственно. Тогда для последнего шага:

где – множество допустимых управлений на n-ом шаге, – возможные состояния системы перед n-ым шагом.

Для k последних шагов:

Полученные рекуррентные соотношения называются функциональными уравнениями Беллмана.

Безусловно-оптимальное значение целевой функции для всего n-шагового процесса ; искомое оптимальное управление .

Источник

Лекция № 14 Тема: Динамическое программирование.

Учебные цель: дать студентам представление о методах решения задач динамического программирования.

1. Вентцель Е.С. Исследование операций: задачи, принципы, методология. – М.: Наука. Гл. ред. физ. мат. лит., 1988. – 208с.
2. Лаговський В.В. Сторожук Є.А. Семко М.М. Математичне програмування у вправах і задачах. – К.: Ін-т математики НАН України, 2001ю – 96 с.
3. Красс М.С., Чупрынов Б.П. Математические методы и модели для магистрантов экономики: Учебное пособие. — СПб: Питер, 2006. – 496 с.
4. Монахов А.В. Математические методы анализа экономики. Учебное пособие. – СПб: Питер, 2002. – 176 с.
5. Конюховский П. Математические методы исследования операций в экономике. СПб: Питер, 2002. –

1. Постановка задачи динамического программирования.

2. Основные идеи вычислительного метода динамического программирования. Принцип оптимальности Беллмана.

3. Экономические задачи, решаемые с помощью методов динамического программирования.

1. Постановка задачи динамического программирования.

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

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

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

Слагаемые аддитивной целевой функции соответствуют эффекту решений, принимаемых на отдельных этапах управляемого процесса. По аналогии, мультипликативная функция распадается на произведение положительных функций различных переменных:

Поскольку логарифм функции типа (2) является аддитивной функцией, достаточно ограничиться рассмотрением функцией вида (1).

Изложим сущность вычислительного метода динамического программирования на примере задачи оптимизации:

> 0, > 0, j = 1, 2, … , n. (4)

2. Основные идеи вычислительного метода динамического программирования. Принцип оптимальности Беллмана.

Допустим, что применение классических методов оптимизации для решения задачи либо проблематично, либо просто невозможно.

Основной принцип подхода, реализуемого в динамическом программировании, заключён в замене решения исходной многомерной задачи последовательностью задач меньшей размерности.

Перечислим основные требования к задачам, выполнение которых позволяет применить данный подход:

1.Объектом исследования должна служить управляемая система (объект) с заданными допустимыми состояниями и допустимыми управлениями;

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

3. Задача не должна зависеть от количества шагов и быть определенной на каждом из них;

4. Состояние системы на каждом шаге должно описывается одинаковым (по составу) набором параметром;

5. Последующее состояние, в котором оказывается система после выбора решения на k-том шаге, зависит только от данного решения и её состояния к началу k-того шага. Данное свойство является основным с точки зрения идеологии динамического программирования и называется отсутствием последствия.

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

Применительно к дискретным условиям планирования/, которые возникают в экономических задачах, динамическое программирование – метод многошаговой оптимизации.

Алгоритм многошаговой оптимизации методом динамического программирования содержит следующие этапы.

1. Описывается процесс и выбираются параметры системы, образующие фазовое пространство или пространство состояний. Определяются управляющие воздействия на систему. Выбирается способ членения процесса на шаги. Вводятся обозначения переменных, позволяющие формализовать описание процесса.

2. Определяются функции эффекта (выигрыша) на i-том шаге в зависимости от состояния системы в начале этого шага и используются управления : .

3. Определяются функции, выражающие изменение состояния системы под влиянием управления на i-том шаге процесса: .

4. Составляется рекуррентное соотношение динамического программирования:

5. Определяется условно-оптимальный эффект (выигрыш) для последнего n-го шага рассматриваемого процесса: , а также соответствующее ему условно-оптимальное управление .

6. Определяются условные оптимальные выигрыши (эффекты) и соответствующие этим эффектам управления для предпоследнего, предпредпоследнего и т.д. до первого шагов процесса:

7. Определяется начальное состояние (если оно не задано), выбираются оптимальные эффекты и безусловные направления для первого, второго и т.д. до последнего n-го шага рассматриваемого процесса.

Источник