В этом репозитории предложены алгоритмы решения трех задач динамического программирования.
Планируется распределение начальной суммы средств x между N предприятиями. Выделенные средства xi приносят доход gi(xi) i-предприятию в начале планового периода. Определить, какое количество средств нужно, чтобы суммарный доход был максимальным.
Пример использования. Планируется распределение начальной суммы средств 16 млн.руб. между 6 предприятиями. Средства выделяются только в размерах, кратных 2 млн.руб. Функции дохода на каждом из четырех предприятий заданы таблично. Определить, какое количество средств нужно, чтобы суммарный доход был максимальным.
| x | g1(x) | g2(x) | g3(x) | g4(x) | g5(x) | g6(x) |
|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 2 | 6 | 7 | 5 | 5 | 6 | 6 |
| 4 | 8 | 10 | 8 | 9 | 10 | 11 |
| 6 | 12 | 13 | 11 | 14 | 11 | 14 |
| 8 | 14 | 15 | 16 | 15 | 13 | 15 |
| 10 | 16 | 19 | 17 | 19 | 17 | 16 |
| 12 | 18 | 22 | 20 | 22 | 20 | 18 |
| 14 | 20 | 23 | 23 | 24 | 23 | 22 |
| 16 | 22 | 26 | 26 | 25 | 25 | 24 |
import numpy as np
from std_dynprog_task import optimal_res
inc = 2
income_matrix = np.array([[ 0, 0, 0, 0, 0, 0],
[ 6, 7, 5, 5, 6, 6],
[ 8,10, 8, 9,10,11],
[12,13,11,14,11,14],
[14,15,16,15,13,15],
[16,19,17,19,17,16],
[18,22,20,22,20,18],
[20,23,23,24,23,22],
[22,26,26,25,25,24]])
optimal_res(income_matrix, inc)Вывод
---matrix of objective functions---
[[ 0 0 0 0 0 0]
[ 6 6 6 6 7 7]
[11 12 12 12 13 13]
[14 17 17 17 19 19]
[15 21 22 22 24 25]
[16 24 26 27 29 30]
[18 25 31 31 34 35]
[22 28 35 36 38 40]
[24 31 38 40 43 44]]
-----------state matrix------------
[[ 0. 0. 0. 0. 0. 0.]
[ 1. 10. 0. 0. 1. 0.]
[ 2. 1. 0. 0. 1. 10.]
[ 3. 1. 10. 10. 1. 10.]
[ 4. 2. 1. 10. 1. 1.]
[ 5. 2. 321. 1. 1. 1.]
[ 6. 32. 3. 10. 1. 1.]
[ 7. 5. 3. 1. 1. 1.]
[ 8. 65. 3. 1. 1. 1.]]
-----optimal options to invest-----
[2, 2, 0, 6, 2, 4]
[2, 2, 2, 2, 4, 4]
[2, 2, 2, 4, 2, 4]
[2, 2, 2, 6, 2, 2]
-----------------------------------Следовательно, всего есть 4 способа вложения средств в 6 предприятий при наличии начальных средств в размере 16 млн. руб. при которых получается максимальный доход в размере 44 млн. руб.
Задача 1. Планируется деятельность двух предприятий в течение n лет. Начальные средства составляют S0. Средства x, вложенные в предприятие 1 приносят доход g1(x) и возвращаются в размере 𝜑1(x) < x. Предприятие 2 при вложении средств x приносит доход g1(x) и возвращаются в размере 𝜑2(x) < x. Ежегодно распределяются все наличные средства, получаемые из возвращенных средств.
Пример использования. Найти максимальный доход и оптимальный план от ежегодного распределения средств между двумя предприятиями в течение 3-х планового периода. Начальная сумма составляет 60 млн. руб. Вложенные средства в размере x приносят на предприятии 1 доход g1(x) и возвращается в размере 40% от x, а на предприятии 2 – соответственно g2(x) и 30%. Функции доходы от предприятий g1(x) и g2(x) заданы в таблице.
| x | 20 | 40 | 60 |
|---|---|---|---|
| g1(x) | 22 | 50 | 90 |
| g2(x) | 24 | 70 | 80 |
import numpy as np
from multi_dynprog_v1 import optimal_res
inc = 20
period = 3
per_1 = 0.4
per_2 = 0.3
income_matrix = np.array([[ 0, 0],
[22,24],
[50,70],
[90,80]])
optimal_res(income_matrix, inc, per_1, per_2, period)Вывод
---matrix of objective functions---
[[ 0. 0. 0. 0. ]
[ 0. 24. 31.6 34.64]
[ 0. 70. 84.4 88.96]
[ 0. 92. 123.2 132.16]]
-----------state matrix------------
[[0. 0. 0.]
[0. 1. 1.]
[0. 0. 0.]
[1. 3. 3.]]
-----optimal options to invest-----
[(60.0, 0.0), (20.0, 4.0), (0.0, 9.2)]
-----------------------------------Следовательно, максимальный доход при распределении начальных средств в размере 60 млн. руб. в течение 3-х лет в два предприятия составляет 132.16 млн. руб.
В этой задаче используется линейная интерполяция для вычисления оставшихся средств после ежегодного распределения, поэтому оптимальный план находится приблеженно.
Задача 2. Двум корпорациям, в состав правлений которых входят одни и те же лица, на основании законов о трестах запрещено помещать деньги в одни и те же предприятия. Первая корпорация намерена поместить капитал x, а вторая – капитал y. gi(z) – доходы от помещения капитал z в i-е предприятие из N различных предприятий. Руководители хотят максимизировать доход по двум корпорациям.
Пример использования. Пусть первая корпорация намерена поместить капитал в 4 предприятия в размере 3 млн. руб., а вторая – в размере 4 млн. руб. Доходы от вложения средств в каждое из 4-х предприятий представлены в таблице.
| z | g1(z) | g2(z) | g3(z) | g4(z) |
|---|---|---|---|---|
| 1 | 2 | 3 | 2 | 4 |
| 2 | 4 | 5 | 4 | 6 |
| 3 | 6 | 6 | 5 | 7 |
| 4 | 7 | 7 | 8 | 7 |
import numpy as np
from multi_dynprog_v2 import optimal_res
inc = 1
x = 3
y = 4
income_matrix = np.array([[0,0,0,0],
[2,3,2,4],
[4,5,4,6],
[6,6,5,7],
[7,7,8,7]])
optimal_res(income_matrix, inc, x, y)Вывод
---matrix of objective functions---
[[ 0. 4. 7. 9. 11.]
[ 4. 7. 9. 11. 13.]
[ 7. 9. 11. 13. 15.]
[ 9. 11. 13. 15. 17.]]
-----------state matrix y------------
[array([[ 0., 1., 21., 21., 21.],
[inf, 1., 2., inf, inf],
[inf, 1., 2., inf, inf],
[inf, 1., 2., 3., 4.]]),
array([[ 0., 0., 10., 210., 210.],
[ 0., 10., 210., 210., 421.],
[ 0., 10., 210., 210., 421.],
[ 0., 10., 210., 21., 42.]]),
array([[ 0., 1., 1., 21., 21.],
[inf, 1., 21., 21., 21.],
[inf, 1., 21., 21., 21.],
[inf, 1., 21., 21., 21.]])]
-----------state matrix x------------
[array([[ 0., inf, inf, inf, inf],
[ 1., 1., 1., 1., 1.],
[21., 2., 2., 2., 2.],
[21., inf, inf, 3., 3.]]),
array([[ 0., 0., 0., 0., 0.],
[ 0., 10., 10., 10., 1.],
[ 10., 210., 210., 210., 2.],
[210., 210., 210., 21., inf]]),
array([[ 0., inf, inf, inf, inf],
[ 1., 1., 1., 1., 1.],
[ 1., 21., 21., 21., 21.],
[21., 21., 21., 21., 21.]])]
-----optimal options to invest-----
[(3, 0), (0, 2), (0, 1), (0, 1)]
[(3, 0), (0, 1), (0, 2), (0, 1)]
[(0, 3), (2, 0), (0, 1), (0, 1)]
[(0, 3), (1, 0), (2, 0), (0, 1)]
[(3, 0), (0, 2), (0, 0), (0, 2)]
[(3, 0), (0, 1), (0, 1), (0, 2)]
[(2, 0), (0, 1), (0, 2), (0, 2)]
[(1, 0), (2, 0), (0, 2), (0, 2)]
[(3, 0), (0, 2), (0, 0), (0, 2)]
[(0, 2), (2, 0), (0, 1), (0, 2)]
[(0, 2), (1, 0), (2, 0), (0, 2)]
[(0, 3), (2, 0), (0, 1), (0, 1)]
[(0, 2), (2, 0), (0, 2), (0, 1)]
[(1, 0), (0, 1), (0, 4), (0, 1)]
[(0, 0), (2, 0), (0, 4), (0, 1)]
[(0, 3), (0, 1), (2, 0), (0, 1)]
[(0, 2), (0, 2), (2, 0), (0, 1)]
[(0, 3), (1, 0), (0, 1), (2, 0)]
[(0, 2), (1, 0), (0, 2), (2, 0)]
[(0, 0), (1, 0), (0, 4), (2, 0)]
[(0, 3), (0, 1), (1, 0), (2, 0)]
[(0, 2), (0, 2), (1, 0), (2, 0)]В этом примере получилось 22 оптимальных варианта распределения средств в 6 предприятий при наличии начальных средств в размере 3 млн. руб. от первой корпорации и 4 млн. руб. от второй корпорации, при которых получается максимальный доход в размере 17 млн. руб.