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

Филиал РГГУ в г. Домодедово

 

Кафедра математических и естественнонаучных дисциплин

 

 

УЧЕБНО-МЕТОДИЧЕСКОЕ ПОСОБИЕ

Для самостоятельного приобретения знаний и овладения умениями

По дисциплине

МЕТОДЫОПТИМАЛЬНЫХ РЕШЕНИЙ

(направление ЭКОНОМИКА)

(Бесконтактная форма обучения)

Практическое занятие 11

Самостоятельное занятие 5

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

Время: 4 часа

 

 

Разработал профессор СМИРНОВ В.Е.

 

 

Домодедово 2019

Тема: Принятие оптимальных инвестиционных решений методом динамического программирования

Время: 4 часа

Теоретическая часть

Задание 1. Изучить существо метода динамического программирования

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

Принцип оптимальности и уравнения Беллмана

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

Динамическое программирование (ДП) - метод оптимизации, приспособленный к операциям, в которых процесс принятия ре­шения может быть разбит на этапы (шаги). Такие операции назы­ваются многошаговыми. Начало развития динамического программирования относится к 50-м годам ХХ в. Оно связано с именем американского математика Ричарда Беллмана.

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

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

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

Рассматривается управляемый процесс, например, экономический процесс распре­деления средств между предприятиями, использования ресурсов в течение ряда лет, замены оборудования, пополнения запасов и т. п. В результате управления объект управления S пере­водится из начального состояния S ₀в конечное S_n.

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

Обозначим через X_k управление на k-м шаге (k = 1, 2,..., п). Пе­ременные X_k удовлетворяют некоторым ограничениям и в этом смысле называются допустимыми (X_k, может быть числом, точкой в n-мерном пространстве, качественным признаком и т.д.).

Пусть Х (X₁, Х₂,.,, Х_п) - управление, переводящее систему S из состояния S₀ в состояние S_i. Обозначим через S_k состояние сис­темы после k-ro шага управления. Получаем последовательность состояний S₀, S₁,,.., S_k-1, S_k,…, S_n-1, S_n=Si. Изобразим каждое состояние окружностями(рисунок 4.1).

 

 

... …

 

Рисунок 4.1 – Процесс управляемого изменения состояний системы

 

Показатель эффективности рассматриваемой управляемой операции - целевая функция - зависит от начального состояния и вектора управления:

Z = F (S₀,X). (4.1)

Сделаем несколько предположений.

1. Состояние S_k системы в конце k-ro шага зависит только от предшествующего состояния S_k-1 и управления на k-м шаге X_k (и не зависит от предшествующих состояний и управлений). Это требование называется "отсутствием последействия": Сформулированное предположение записывается в виде уравнений

(4.2.)

которые называются уравнениями состояний.

2. Целевая функция (4.1) является аддитивной от показателя эффективности каждого шага. Обозначим показатель эффек­тивности k-ro шага через

. (4.3.)

Тогда

. (4.4)

Задача пошаговой оптимизации (задача ДП) формулируется так: определить такое допустимое управление Х, переводящее сис­тему S из состояния S₀ в состояние S_i, при котором целевая функция (4.4) принимает наибольшее (наименьшее) значение.

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

1. Задача оптимизации интерпретируется как п-шаговый процесс управления.

2. Целевая функция равна сумме целевых функций каждого шага.

3. Выбор управления на k-м шаге зависит только от состояния системы к этому шагу и не влияет на предшествующие шаги (нет обратной связи).

4. Состояние S_k после k-го шага управления зависит только от предшествующего состояния S_k-1 и управления X_k (отсутствие по­следействия). 5. На каждом шаге управление X_k зависит от конечного числа управляющих переменных, а состояние S_k - от конечного числа па­раметров (смысл замечания 5 станет ясным из рассмотренных примеров).

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

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