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

 

Таким образом, последний шаг спланирован, поскольку  найдены условно оптимальные  управления для предполагаемых состояний  системы на (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 рисунок и была написана с использованием двух источников литературы.

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