4.2. Решение задачи распределения капитальных вложений методом динамического программирования
Динамическое программирование - это вычислительный метод для решения задач управления определённой структуры, когда задача с n переменными представляется как многошаговый процесс принятия решений. На каждом шаге (этапе) определяется экстремум функции только от одной переменной. Состояние исследуемой системы на каждом шаге характеризуется некоторой переменной величиной, которая называется параметром состояния. Эффект от принятия параметром состояния того или иного значения на данном этапе вместе с уже рассмотренными шагами характеризуется функцией состояния. Решение конкретной задачи методом динамического программирования сводится к выбору параметра состояния, составления функции состояния и рекуррентных соотношений, связывающих функции состояния для двух соседних последовательных этапов, и их применению для выбора оптимального управления.
Воспользуемся методом динамического программирования для решения полученной задачи распределения капитальных вложений. Последовательно ищется оптимальное распределение для k = 2, 3 и 4 фирм.
Пусть первым двум фирмам выделено тыс. рублей инвестиции ( - параметр состояния, который может изменяться от 0 до 700). Обозначим через F2 () максимальный прирост прибыли на первых двух предприятиях.
Если из тыс. рублей 2-ая фирма получит х2 тыс. рублей, то максимальный прирост прибыли на 2-ой фирме можно выразить как f2(x2).
На долю 1-ого предприятия останется - х2 тыс. рублей, а максимальный прирост прибыли на 1-ом предприятии составит F1 ( - х2).
Тогда максимальный прирост прибыли на двух предприятиях будет равен
F2 () = max {f2(x2) + F1 ( - х2)}
0 ≤ x2 ≤ 700
Используя исходные данные из задания, строим Таблицу № 1.1. Значения f2(x2) складываем со значениями F1 (-x2) = f1(-x2) и на каждой побочной диагонали находим наибольшее число, которое помечаем звёздочкой.
Таблица № 1.1
-х2 | 0 | 100 | 200 | 300 | 400 | 500 | 600 | 700 | |
X2 | F1(-x2) f2(x2) | 0 | 37 | 64 | 87 | 105 | 120 | 134 | 145 |
0 | 0 | 0 | 37 | 64 | 87 | 105 | 120 | 134 | 145 |
100 | 48 | 48* | 85* | 112* | 135 | 153 | 168 | 182 | --- |
200 | 75 | 75 | 112* | 139* | 162* | 180 | 195 | --- | --- |
300 | 98 | 98 | 135 | 162* | 185 | 203 | --- | --- | --- |
400 | 120 | 120 | 157 | 184 | 207* | --- | --- | --- | --- |
500 | 132 | 132 | 169 | 196 | --- | --- | --- | --- | --- |
600 | 144 | 144 | 181 | --- | --- | --- | --- | --- | --- |
700 | 156 | 156 | --- | --- | --- | --- | --- | --- | --- |
Звездочкой обозначен максимальный суммарный эффект от выделения соответствующего размера инвестиций 2-м предприятиям.
В Таблицу № 1.2. в графу F2 () заносим значения максимального прироста прибыли на первых двух предприятиях, а в графе указываем соответствующий каждому значениюF2() размер инвестиций 2-ому предприятию.
Таблица № 1.2.
| 0 | 100 | 200 | 300 | 400 | 500 | 600 | 700 |
F2() | 0 | 48 | 85 | 112 | 139 | 162 | 185 | 207 |
() | 0 | 100 | 100 | 200 | 200 | 300 | 300 | 400 |
|
|
|
| 100 |
| 200 |
|
|
Далее действуем также: находим функции F3 (), F4 (), используя на каждом k-ом шаге основное рекуррентное соотношение:
Fk (ξ)=max {fk(xk) + Fk-1(ξ - xk)}
0 ≤ xk ≤ 700
для k= 2,3,4
Заполняем Таблицу № 2.1., аналогичным способом определяя максимальный прирост прибыли от распределения капитальных вложений между тремя предприятиями (F3 ()).
Таблица № 2.1.
-х3 | 0 | 100 | 200 | 300 | 400 | 500 | 600 | 700 | |
Х3 | F2(-x3) f3(x3) | 0 | 48 | 85 | 112 | 139 | 162 | 185 | 207 |
0 | 0 | 0 | 48 | 85 | 112 | 139 | 162 | 185 | 207 |
100 | 85 | 85* | 133* | 170* | 197* | 224* | 247* | 270* | --- |
200 | 100 | 100 | 148 | 185 | 212 | 239 | 262 | --- | --- |
300 | 111 | 111 | 159 | 196 | 223 | 250 | --- | --- | --- |
400 | 118 | 118 | 166 | 203 | 230 | --- | --- | --- | --- |
500 | 124 | 124 | 172 | 209 | --- | --- | --- | --- | --- |
600 | 129 | 129 | 177 | --- | --- | --- | --- | --- | --- |
700 | 132 | 132 | --- | --- | --- | --- | --- | --- | --- |
Звездочкой обозначен максимальный суммарный эффект от выделения соответствующего размера инвестиций 3-м предприятиям.
В Таблицу № 2.2. в графу F3 () заносим значения максимального прироста прибыли на трех предприятиях, а в графе указываем соответствующий функцииF3() размер инвестиций 3-ему предприятию.
Таблица № 2.2.
| 0 | 100 | 200 | 300 | 400 | 500 | 600 | 700 |
F3() | 0 | 85 | 133 | 170 | 197 | 224 | 247 | 270 |
() | 0 | 100 | 100 | 100 | 100 | 100 | 100 | 100 |
В Таблице № 3.1., определяющей максимальный прирост прибыли от распределения капитальных вложений между четырьмя предприятиями F4(), заполняем только одну диагональ для значения = 700, поскольку данный этап является завершающим, предприятий всего четыре и между ними необходимо распределить именно 700 тыс. рублей.
Таблица № 3.1.
-х4 | 0 | 100 | 200 | 300 | 400 | 500 | 600 | 700 | |
Х4 | F(-x4) f2(x4) | 0 | 85 | 133 | 170 | 197 | 224 | 247 | 270 |
0 | 0 |
|
|
|
|
|
|
| 270 |
100 | 47 |
|
|
|
|
|
| 294* | --- |
200 | 70 |
|
|
|
|
| 294* | --- | --- |
300 | 80 |
|
|
|
| 277 | --- | --- | --- |
400 | 86 |
|
|
| 256 | --- | --- | --- | --- |
500 | 91 |
|
| 224 | --- | --- | --- | --- | --- |
600 | 94 |
| 179 | --- | --- | --- | --- | --- | --- |
700 | 98 | 98 | --- | --- | --- | --- | --- | --- | --- |
Звездочкой обозначен максимальный суммарный эффект от выделения соответствующего размера инвестиций в размере 700 тыс. рублей 4-м предприятиям.
Z max = 294 тыс. рублей,
причем 4-ому предприятию должно быть выделено
х4* = х4 (700) = 200 тыс. рублей
ЛИБО
х4** = х4 (700) = 100 тыс. рублей.
На долю остальных трех предприятий остается в 1-ом случае (х4* = 200) 500 тыс. рублей,
во 2-ом случае (х4** = 100) 600 тыс. рублей.
Из Таблицы № 2.2. видно, что 3-ему предприятию должно быть выделено
в 1-ом случае (х4* = 200): х3* = х3 (700 – х4*) = х3 (500) = 100 тыс. рублей
во 2-ом случае (х4** = 100): х3** = х3 (700 – х4**) = х3 (600) = 100 тыс. рублей.
Таким образом, х3* = 100 тыс. рублей.
Продолжая обратный процесс, находим:
в 1-ом случае (х4* = 200): х2* = х2 (700 – х4* - х3*) = х2 (400) = 200 тыс. рублей
во 2-ом случае (х4** = 100): х2** = х2 (700 – х4** - х3*) = х2 (500) = 300 тыс. рублей
ЛИБО
х2*** = х2 (500) = 200 тыс. рублей = х2*.
На долю 1-ого предприятия останется:
х1* = 700 – х4* - х3* - х2* = 200 тыс. рублей
х1** = 700 – х4** - х3** - х2*** = 300 тыс. рублей
х1*** = 700 – х4** - х3** - х2** = 200 тыс. рублей = х1*
Таким образом, одинаково оптимальными будут являться 3 варианта распределения капитальных вложений.
1-ый вариант
х1* = 200; | Z max = 294 |
х2* = 200; | |
х3* = 100; | |
х4* = 200 |
2-ой вариант
х1* = 200; | Z max = 294 |
х2** = 300; | |
х3* = 100; | |
х4** = 100 |
3-ий вариант
х1** = 300; | Z max = 294 |
х2* = 200; | |
х3* = 100; | |
х4** = 100 |
В качестве проверки правильности решения задачи можно использовать равенство:
Z max = f1(x1) + f2(x2) + f3(x3) + f4(x4)
1-ый вариант: 64 + 75 + 85 + 70 = 294 тыс. рублей
2-ой вариант: 64 + 98 + 85 + 47 = 294 тыс. рублей
3-ий вариант: 87 + 75 + 85 + 47 = 294 тыс. рублей
Следовательно, полученные решения верны.
- 1. Линейная производственная задача…………………………….3
- 1.2. Математическая модель линейной производственной задачи
- 1.3. Решение линейной производственной задачи симплексным методом.
- Выводы.
- 1.4. Проверка полученного решения
- 1.5. Графическое решение линейной производственной задачи с двумя переменными
- Двойственная задача линейного программирования,
- 2.1. Двойственная задача линейного программирования
- 2.2. Задача о «расшивке узких мест производства»
- Транспортная задача линейного программирования
- 3.1. Математическая модель транспортной задачи.
- 3.2. Решение транспортной задачи методом потенциалов.
- Динамическое программирование задача распределения капитальных вложений
- 4.1. Формулировка задачи распределения капитальных вложений
- 4.2. Решение задачи распределения капитальных вложений методом динамического программирования
- Анализ доходности и риска финансовых операций