3. Экономические задачи, решаемые с помощью методов динамического программирования.
Первыми к появлению динамического программирования привели динамические задачи управления запасами (ЗУЗ). Они составляют один из наиболее многочисленных классов экономических задач. Правильное и своевременное определение оптимальной стратегии управления запасами, а также их нормативного уровня позволяет высвободить значительные оборотные средства, замороженные в виде запасов, что в конечном итоге повышает эффективность используемых ресурсов.
Также одним из важнейших классов задач, в которых применение методов динамического программирования оказывается плодотворным, являются задачи последовательного принятия решений. Их особенностью является то, что искомые переменные ,… должны определяться в строгой временной последовательности и не должны меняться местами. К таким задачам относятся задачи «о найме работников».
Одна из типичных задач динамического программирования — распределение капитальных вложений, когда на каждом этапе (например, ежегодно) решается задача распределения. Требуется установить такое распределение капитальных ресурсов на каждом этапе, при котором суммарная прибыль за все этапы будет максимальной
Пример. Пусть x — количество капитальных вложений, которые необходимо распределить между двумя отраслями. Количество капитальных средств у, вложенное в первую отрасль, за год приносит прибыль g(y) = 0,8y . Доля капитальных средств x – y вложенных во вторую отрасль, приносит за год доход h(x – y) = 0,5(x — y). К концу года средства, вложенные в первую отрасль, составят a(y) = 0,3y, во вторую – b(x –y) = 0,6(x –y). . По истечении каждого года оставшиеся капитальные вложения заново распределяются по отраслям. Необходимо установить распределение так, чтобы суммарная прибыль за три года была максимальной.
Итак, сначала ищем величину y2 — количество средств, вложенных в течение третьего года, затем y1 и y0 (соответственно второго и первого годов). В соответствии с принципом оптимальности, зная зависимость от величин y1 и y0, а также x2 — количество ресурсов, полученных к началу третьего года, необходимо наилучшим образом использовать доступное количество ресурсов, т. е. решить задачу
f 1(x2) = g(y2) + b(x2)
f 1(x2) = 0,8y2 + 0,5(x2 – y2) = 0,5x2 + 0,3y2
Очевидно, максимум возможен при x2=y2.
Следовательно, все ресурсы на последнем этапе нужно направить в первую отрасль. При этом будет получена прибыль f1(x2) = 0,8x2 . Теперь найдем y1. Рассмотрим двухшаговый процесс — последний и предпоследний этапы. Необходимо наилучшим образом использовать ресурсы x1, не интересуясь предыдущим решением. Максимальный суммарный доход на последних двух этапах
где g(y2) + h(x1 – y1) — прибыль на предпоследнем этапе при y1.
f1 — максимальная прибыль на последнем этапе. Необходимо выбрать y1 такое, чтобы f2(x2) была максимальной.
П о известному f1 получаем
= 0,5x1 + 0,3y1 + 0,8 =
= 0,98x1 + 0,6y1
Значит на предпоследнем этапе все капитальные вложения также
должны быть направлены в первую отрасль.
Аналогично для первого этапа
f 3(x2) = g(y) + h(x – y) + f2 =
= 0,8y1 + 0,5(x – y) + 1,04
= 1,124x – 0,012y
Здесь максимум достигается при у = 0. Следовательно, наибольший суммарный доход на всех этапах f3(x) = 1,24x. На первом этапе все ресурсы необходимо направить во вторую отрасль: y = 0. Таким образом, получена оптимальная стратегия y = 0; y1 = x1; y2 = x2.
Первый этап: все ресурсы — во вторую отрасль; прибыль составит h(x) = 0,5x. К концу года останется b(x) = 0,6x капитальных вложений, которые будут направлены в первую отрасль и дадут прибыль g(0,6x) = 0,8 · 0,6x = 0,48x.Остаток ресурсов при этом a(0,6x) = 0,3 . 0,6x = 0,18x
Прибыль на третьем этапе g(0,18x) = 0,8 · 0,18x = 0,144x; тогда суммарная прибыль составит 0,5x + 0,48x + 0,144x = 1,124x.
Контрольные вопросы по теме:
1. Представьте математическую модель задачи динамического программирования.
2. Сформулируйте основной принцип подхода, реализуемого в динамическом программировании.
3. Перечислите основные требования к задачам, выполнение которых позволяет решить их методами динамического программирования.
4. В чем заключается Принцип оптимальности Беллмана?
5. Основные идеи вычислительного метода динамического программирования (алгоритм).
6.Назовите виды экономических задач, решаемых с помощью методов динамического программирования.
Лекция № 14 Тема: Динамическое программирование.
Учебные цель: дать студентам представление о методах решения задач динамического программирования.
- Вентцель Е.С. Исследование операций: задачи, принципы, методология. – М.: Наука. Гл. ред. физ. мат. лит., 1988. – 208с.
- Лаговський В.В. Сторожук Є.А. Семко М.М. Математичне програмування у вправах і задачах. – К.: Ін-т математики НАН України, 2001ю – 96 с.
- Красс М.С., Чупрынов Б.П. Математические методы и модели для магистрантов экономики: Учебное пособие. — СПб: Питер, 2006. – 496 с.
- Монахов А.В. Математические методы анализа экономики. Учебное пособие. – СПб: Питер, 2002. – 176 с.
- Конюховский П. Математические методы исследования операций в экономике. СПб: Питер, 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-го шага рассматриваемого процесса.