Распределение капиталовложений методом динамического программирования

Содержание

 

Введение …………………………………………………………………………..5

1 Динамическое программирование …………………………………………….6

1. Понятие динамического программирования………………………..6
2. Принцип Беллмана ……………………………………………………7

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

      1.4 Принцип поэтапного построения оптимального управления……..8

      1.5 Задача о минимизации расхода горючего самолетом при наборе  высоты и скорости………………………………………………………….9

2 Задача распределения капиталовложений (теоретическая часть)………..14

3 Задача распределения капиталовложений (практическая часть)………16

Заключение ………………………………………………………………………19

Список литературы……………………………………………………………...20

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Введение

 

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

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

Более подробно рассмотрена задача распределения капиталовложений, процесс решения которой существенно облегчен при помощи динамического программирования

 

 

 

 

 

 

 

 

 

 

 

1. Динамическое программирование

 

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

 

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

В задачах  динамического программирования экономический процесс зависит от времени [от нескольких периодов (этапов) времени], поэтому находится ряд оптимальных решений (последовательно для каждого этапа), обеспечивающих оптимальное развитие всего процесса в целом. Задачи динамического программирования называются многоэтапными или многошаговыми. Динамическое программирование представляет собой математический аппарат, позволяющий осуществлять оптимальное планирование многошаговых управляемых процессов и процессов, зависящих от времени, экономический процесс называется управляемым, если можно влиять на ход его развития. Управлением называется совокупность решений, принимаемых на каждом этапе с целью влияния на ход процесса. В экономических процессах управление заключается в распределении и перераспределении средств на каждом этапе.

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

 

 

1.2 Принцип Беллмана

 

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

Будем считать, что состояние системы S на k-ом шаге (k =) определяется совокупностью чисел , которые получены в результате управления U_k, обеспечивающего переход системы S из состояния X^(k-1) в состояние X^k. При этом будем предполагать, что состояние X^k, в которое перешла система S, зависит от данного состояния X^(k-1) и выбранного управления U_k и не зависит от того, каким образом система пришла в состояние X^(k-1).

Будем считать, что если в результате k-го шага обеспечен определенный доход или выигрыш, также зависящий от исходного состояния системы X^(k-1) и выбранного управления U_k и равный W_k(X^(k-1),U_k), то общий доход или выигрыш за n шагов составляет

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

Определение: под оптимальной стратегией будем понимать совокупность управлений U^*= ( ), в результате реализации которых система S за n шагов переходит из начального состояния X(0) в конечное состояние X(n) и при этом функция  
                                                 

принимает наибольшее значение.

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

Для этого  нужно сделать различные предположения  о том, как мог окончиться предпоследний  шаг, и с учетом этого выбрать  управление , обеспечивающее максимальное значение функции W_n(X^(n-1),U_n). Такое управление, выбранное при определенных предположениях о том, как окончился предыдущий шаг, называется условно оптимальным управлением. Следовательно, принцип оптимальности требует находить на каждом шаге условно оптимальное управление для любого из возможных исходов предыдущего шага.

F_n(X⁰) - максимальный доход, получаемый за n шагов при переходе системы S из начального состояния X⁰ в конечное состояние при реализации оптимальной стратегии управления U^*=( ), а через    F_n-k(X^k) – максимальный доход, получаемый при переходе из любого состояния X^k в конечное состояние Xⁿ при оптимальной стратегии управления на оставшихся n-k шагах. Тогда

,

 

 

 

 

 

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

 

Пусть некоторая физическая управляемая  система S находится в первоначальном состоянии S₀ Ŝ₀ .С течение времени ее состояние меняется и система приходит в конечное состояние S_k Ŝ_k. С процессом изменения состояния системы связан некоторый численный критерий W. Необходимо так организовать процесс, чтобы критерий достиг оптимального значения.  Обозначим множество возможных управлений через U. Тогда задача состоит в том, чтобы из множества возможных управлений найти такое управление U^*, которое позволит перевести систему S из начального состояния S₀ Ŝ₀ в конечное S_k Ŝ_k так, что критерий W(U) принимает оптимальное значение W^*.

 

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

 

В каждом процессе имеется последний k-й шаг, принятие решения на котором не зависит от будущего. Поэтому на этом шаге выбирают управление, позволяющее получить наибольший эффект. Спланировав этот шаг, к нему можно присоединить предпоследний (k – 1)-й шаг, к которому, в свою очередь, (k – 2)-й и т. д. В конечном итоге приходят в начальное состояние системы S₀. Процесс динамического программирования как бы «разворачивается» от конца к началу.

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

Пусть планируется k-шаговый процесс. Сделаем ряд предположений о возможных состояниях системы на (k – 1)-м шаге. Обозначим эти состояния через S_k-1,1, S_k-1,2,…, S_k-1,r. На последнем шаге найдем для каждого из них условно оптимальное управление , ,…, . Таким образом, k-й шаг спланирован. Действительно, какое бы состояние ни имела система на предпоследнем шаге, уже известно, какое управление следует применить на последнем шаге. Аналогично поступаем на (k – 1)-м шаге, только условно оптимальные управления необходимо выбирать, учитывая уже выбранные условно оптимальные управления на k-м шаге, и т. д. В итоге приходим к первоначальному состоянию S₀ S₀ системы.

Для первого  шага (в отличие от всех остальных) предположений о возможном состоянии  системы не делаем, так как состояние S₀ известно, а находим оптимальное управление, учитывая все условно оптимальные управления, найденные для второго шага. Проходя от S₀ к S_k, получаем искомое оптимальное управление для всего процесса.

  

1.5 Задача о минимизации расхода горючего самолетом при наборе

высоты и  скорости

 

Пусть самолет, находящийся на высоте Н₀ и имеющий скорость v₀, должен подняться на высоту Н_k и иметь скорость V_k .Известен расход горючего при подъеме самолета с любой высоты Н₁ любую высоту Н₂> Н₁ при постоянной скорости, а также расход горючего при увеличении скорости от любого значения V₁ до любого значения V₂ > V₁ при неизменной высоте.  Найти оптимальное управление набором высоты и скорости, при котором общий расход горючего минимален.

Решение: Из условия следует, что состояние  физической системы S (самолета) характеризуется двумя параметрами: скоростью V и высотой Н.

Поэтому решение  будем искать на плоскости VOH, а точнее на ограниченном прямыми V = V₀, V = V_k и H = Н₀ , Н = Н_k прямоугольнике, который и является областью допустимых состояний. Начальное S₀ (V₀, H₀) и конечное S_k (V_k, H_k) состояния вполне определены, как две точки S₀ и S_k на плоскости.

Чтобы построить  решение методом динамического  программирования, разобьем отрезок  (Н_k – Н₀) на n₁ а отрезок (V_k – V₀) – на п₂ равных частей

(этапов) и условимся считать, что за  один этап (шаг) самолет может  увеличить либо высоту на величину = (Н_k – Н₀)/п₁, либо скорость на величину = (V_k – V₀)/n₂ .Очевидно, существует множество траекторий (управлений), представляющих собой ломаные линии, по которым точка S может переместиться из S₀ в S_k. Решение задачи состоит в том, чтобы из множества управлений выбрать такое, которое позволит минимизировать расход горючего W, равный сумме расходов горючего на каждом этапе соответствующей ломаной линии. Можно рассмотреть все возможные траектории от S₀ к S_k, определить расход горючего для каждой из них и выбрать наилучшую. Но если п₁ и п₂ велики, то непосредственный перебор всех вариантов требует значительных затрат времени даже при использовании ЭВМ. Гораздо проще и быстрее задача решается методом динамического программирования. Рассмотрим решение задачи, условия которой приведены на рис.1.

Числа на вертикальных линиях означают расход горючего при наборе высоты с постоянной скоростью на данном этапе, а числа  на горизонтальных линиях — расход горючего при увеличении скорости без  изменения высоты. Как следует  из рис. 1, весь процесс разбит на k = n₁ + n₂ = 4 + 6 = 10 шагов. Точки пересечения линий разбиения изображены кружками, в которые записан расход горючего. Оптимизацию начинаем с последнего шага. Рассмотрим отдельно правый верхний угол прямоугольной сетки с конечной точкой S_к. В точку S_к можно прийти либо из точки a₁ либо из А₂, т. е. для каждой точки управление единственное. Если на предпоследнем шаге самолет перешел в состояние А₁, то, чтобы перейти в состояние S_к, самолет должен увеличивать только скорость и расходовать при этом 8 ед. горючего; если самолет перешел в состояние А₂, то набирать высоту и затрачивать 11 ед. горючего. Эти расходы горючего, являющиеся одновременно и минимальными, записываем в кружки возле точек А₁ и А₂. Условно оптимальные управления, приводящие к этому расходу, отмечаем стрелкой, выходящей из кружка и указывающей, как управлять самолетом на последнем шаге, если в результате предыдущего шага он окажется в одном из рассмотренных состояний.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Рисунок 1 - Условия задачи минимизации расходов горючего самолёта

 

Таким образом, последний шаг спланирован, поскольку  найдены условно оптимальные  управления для предполагаемых состояний  системы на (n – 2)-м шаге и известны значения функции W для каждого из этих состояний. Переходим к планированию девятого шага. Чтобы выбрать условно оптимальные управления на этом шаге, нужно рассмотреть возможные состояния, в которые может прийти система на восьмом шаге. На восьмом шаге состоянию самолета может соответствовать одна из трех точек: В₁, В_г или B₃. Найдем условно оптимальное управление для этих состояний и соответствующий этому управлению минимальный расход горючего. Для точки В₁ выбора нет. Возможное единственное управление проходит через точку A₁ при расходе горючего 17 ед., а условно оптимальное управление изображено стрелкой, выходящей из точки В₁. Из точки В₂ возможны два пути: через точки А₁ и А₂. В первом случае расход горючего составляет 18 ед., во втором — 24 ед. Выбираем управление через точку А₁. Минимальный расход горючего (18 ед.) записываем в кружок, путь отмечаем стрелкой. Для точки B₃ путь в S_k также единственный (через точку А₂). Расход горючего, составляющий 22 ед., записываем в кружок, а управление отмечаем стрелкой.

Для точек В₁ ,В₂ ,В₃ выбраны условно оптимальные управления, следовательно, девятый шаг спланирован.

Переходим к планированию восьмого шага. В  результате седьмого шага состоянию  самолета может соответствовать  одна из точек С₁ , С₃, С_4. Для точек С₁ и С₄ пути в S_k единственные и расход горючего соответственно составляет 27 и 34 ед..

 

Для точки С₂ расход горючего при движении через точки В₁ и В₂ составляет 25 ед., поэтому условно оптимальное управление показываем как через точку В₁ так и через точку В₂.

Наконец, для точки С₃ расход горючего при движении через точку В₂ составляет 28 ед., а через точку В₃ — 34 ед. Минимальный расход горючего (28 ед.) записываем в кружок.

Продолжая процесс для оставшихся шагов, приходим в точку S₀. Выбирая для этого состояния уже не условно оптимальное, а оптимальное управление, получаем оптимальное управление для всего процесса, которому соответствует минимальный расход горючего, равный 88 ед. Оптимальное управление на рис.1 изображено дополнительными стрелками. Как следует из рисунка, оптимальное управление не является единственным, так как имеют место условно оптимальные управления, приводящие к одинаковому расходу горючего.

Найденные оптимальные управления процессом  набора высоты и скорости самолета состоят в следующем: на первом шаге следует увеличить скорость до значения V₀ + ∆V; на втором — высоту до Н₀ +∆ Н; на третьем, четвертом и пятом шагах — скорость до величины V₀ + 4∆V; на шестом и седьмом шагах увеличить высоту до значения Н₀ + 3∆V . На восьмом шаге можно либо увеличить высоту до значения Н_k тогда на девятом и десятом шагах следует набирать скорость до величины V_k, либо увеличить скорость до величины V₀ + 5∆V , тогда на девятом шаге необходимо набирать высоту до значения Н_к, а на десятом — увеличить скорость до величины V_k.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

2 Задача распределения капиталовложений

 

Планируется распределение начальной суммы  средств  между n предприятиями  П₁, П₂, …, П_k. Предполагается, что выделенные предприятию П_k в начале планового периода средства х_k приносят доход f_n(x_n), k = . Будем считать, что:

1. доход, полученный от вложения средств в предприятие П_k, не зависит от вложения средств в другие предприятия;
2. доход, полученный от разных предприятий, выражается в одинаковых единицах;
3. общий доход равен сумме доходов, полученных от всех средств, вложенных во все предприятия.

 

Математическая  модель задачи следующая:

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

x₁ + х₂ + …+ х_к  = ₀,

x_k ≥ 0, k = .

Опишем  задачу в виде модели динамического  программирования.

За номер k-го шага примем номер предприятия, которому выделяются средства x_k. Уравнениями состояния служат равенства:

_k = _k-1 – x_k, k =

Суммарный доход за п шагов составит:

Уравнения Беллмана имеют вид:

 

 

      

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

3 Практическая  часть

Задание: для двух предприятий выделено а единиц средств. Как распределить все средства в течение 4 лет, чтобы доход был наибольшим, если известно, что доход от х единиц средств, вложенных в первое предприятие, равен f₁(х), а доход от у единиц средств, вложенных во второе предприятие, равен f₂(у). Остаток средств к концу года составляет g₁(х) для первого предприятия и g₂(у) для второго предприятия. Задачу решить методом динамического программирования.

 

         Таблица 1 – Исходные данные  задачи

a	f1	g1	f2	g2
1000	3x	0,1x	2y	0,5y

 

 

Решение: процесс распределения средств разобьем на 4 этапа - по соответствующим годам.

Обозначим а_k = х_k + у_k - средства, которые распределяются на к -ом шаге как сумма средств по предприятиям.

 

Суммарный доход от обоих предприятий  на к -ом шаге:

 

z_{k =} f₁(x_k) + f₂(a_k - x_k) = 3x_k + 2(a_k - x_k) = 2a_k + 3x_k

 

Остаток средств от обоих предприятий  на к -ом шаге:

 

a_{k+1 =} g₁(x_k) + g₂(a_k - x_k) = 0,1x_k + 0,5(a_k - x_k) = 0,5a_k + 0,4x_k

 

Обозначим   (а_к) - максимальный доход, полученный от распределения средств а_k между двумя предприятиями с к -го шага до конца рассматриваемого периода. Рекуррентные соотношения Беллмана для этих функций:

 

Проведём оптимизацию, начиная с четвёртого шага

4-й шаг:

оптимальный    доход    равен:

т.к. линейная возрастающая функция достигает максимума в конце рассматриваемого промежутка, т.е. при x₄ = a₄.

 

З-й шаг:

,т.к. линейная убывающая функция достигает максимума в начале рассматриваемого промежутка, т.е. при х₃ = 0.

 

2-й шаг:

,т.к. линейная убывающая функция достигает максимума в начале рассматриваемого промежутка, т.е. при x₂ = 0 .

 

1-й шаг:

,т.к.

линейная убывающая функция достигает максимума в начале рассматриваемого промежутка, т. е. при x₁ = 0.

Результаты оптимизации:

Определим количественное распределение  средств по годам:

т.к. a₁ = a = 1000, , получаем a₂ = 0,5a₁ 0,4x₁ = 500. Далее аналогично:

 

 

 

 

Представим распределение средств в виде таблицы:

Таблица 2 – Результаты решения задачи

Предприятие	год
	1	2	3	4
1	0	0	0	125
2	1000	500	250	0

 

При таком распределении средств  за 4 года будет получен доход, равный

 

 

 

 

Список использованной литературы:

1. Акулич И.Л. Математическое программирование в примерах и задачах. М.: Высшая школа, 1986. – 319 с.
2. Кузнецов Ю.Н., Кузубов В.И., Волощенко А.Б. Математическое программирование. М.: Высшая школа, 1980. – 300 с.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Аннотация

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

Данная работа состоит из 20 листов. В неё включены 2 таблицы, 1 рисунок и была написана с использованием двух источников литературы.

Ключевые слова: динамическое программирование, принцип Беллмана, экономические  задачи, математическая модель, оптимальное управление.