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

Содержание

 

Введение …………………………………………………………………………..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 - Условия задачи минимизации расходов горючего самолёта