5

УТВЕРЖДАЮ»

________________

Зав. кафедрой КЭЭМ

д. ф.-м. н. Дивизинюк М.М.

«____» ____________ 200__ г.

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

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

Литература:

1. Вентцель Е.С. Исследование операций: задачи, принципы, методология. – М.: Наука. Гл. ред. физ. мат. лит., 1988. – 208с.

2. Лаговський В.В. Сторожук Є.А. Семко М.М. Математичне програмування у вправах і задачах. – К.: Ін-т математики НАН України, 2001ю – 96 с.

3. Красс М.С., Чупрынов Б.П. Математические методы и модели для магистрантов экономики: Учебное пособие. - СПб: Питер, 2006. – 496 с.

4. Монахов А.В. Математические методы анализа экономики. Учебное пособие. – СПб: Питер, 2002. – 176 с.

5. Конюховский П. Математические методы исследования операций в экономике. СПб: Питер, 2002. –

Изучаемые вопросы:

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

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

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

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

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

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

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

. (1)

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

. (2)

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

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

Найти

(3)

при ограничениях

> 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-го шага рассматриваемого процесса.