Динамическое программирование
Задачи динамического программирования: задача распределения инвестиций, задача замены оборудования, задача Джонсона
xf1(x)f2(x)f3(x)
16.345
25.267
34.34.67.8
4563
5*76.38.2
Решить онлайн
Примеры решений Задача Джонсона Симплекс метод Метод прогонки Задача замены оборудования Задача распределения инвестиций Параметры сетевой модели Задача коммивояжера Многоканальные СМО

Динамическое программирование. Пример решения задачи

Найти оптимальное распределение средств между 6 предприятиями при условии, что прибыль f(x), полученная от каждого предприятия, является функцией от вложенных в него средств х. Выписать все оптимальные управления.
N f 1(x ) f 2 (x) f 3 (x) f 4 (x) f 5 (x)
0 0 0 0 0 0
1 6 5 3 4 2
2 8 12 13 10 11
3 10 15 16 15 14
4 14 20 21 22 18
5 18 22 26 25 21
6 22 26 29 31 30
Решение получаем через сервис распределение средств между предприятиями.
I этап. Условная оптимизация.
Первый шаг. k = 5.
e4 u5 e5 = e4 - u5 f5(u5) F*5(e5) u5(e5)
1 0 1 0
1 0 2 2 1
2 0 2 0
1 1 2
2 0 11 11 2
3 0 3 0
1 2 2
2 1 11
3 0 14 14 3
4 0 4 0
1 3 2
2 2 11
3 1 14
4 0 18 18 4
5 0 5 0
1 4 2
2 3 11
3 2 14
4 1 18
5 0 21 21 5
6 0 6 0
1 5 2
2 4 11
3 3 14
4 2 18
5 1 21
6 0 30 30 6

Второй шаг. k = 4.
e3 u4 e4 = e3 - u4 f4(u4) F*4(e3) F3(u4,e3) F*4(e4) u4(e4)
1 0 1 0 2 2
1 0 4 0 4 4 1
2 0 2 0 11 11 11 0
1 1 4 2 6
2 0 10 0 10
3 0 3 0 14 14
1 2 4 11 15 15 1
2 1 10 2 12
3 0 15 0 15
4 0 4 0 18 18
1 3 4 14 18
2 2 10 11 21
3 1 15 2 17
4 0 22 0 22 22 4
5 0 5 0 21 21
1 4 4 18 22
2 3 10 14 24
3 2 15 11 26 26 3
4 1 22 2 24
5 0 25 0 25
6 0 6 0 30 30
1 5 4 21 25
2 4 10 18 28
3 3 15 14 29
4 2 22 11 33 33 4
5 1 25 2 27
6 0 31 0 31

Третий шаг. k = 3.
e2 u3 e3 = e2 - u3 f3(u3) F*3(e2) F2(u3,e2) F*3(e3) u3(e3)
1 0 1 0 4 4 4 0
1 0 3 0 3
2 0 2 0 11 11
1 1 3 4 7
2 0 13 0 13 13 2
3 0 3 0 15 15
1 2 3 11 14
2 1 13 4 17 17 2
3 0 16 0 16
4 0 4 0 22 22
1 3 3 15 18
2 2 13 11 24 24 2
3 1 16 4 20
4 0 21 0 21
5 0 5 0 26 26
1 4 3 22 25
2 3 13 15 28 28 2
3 2 16 11 27
4 1 21 4 25
5 0 26 0 26
6 0 6 0 33 33
1 5 3 26 29
2 4 13 22 35 35 2
3 3 16 15 31
4 2 21 11 32
5 1 26 4 30
6 0 29 0 29

Четвертый шаг. k = 2.
e1 u2 e2 = e1 - u2 f2(u2) F*2(e1) F1(u2,e1) F*2(e2) u2(e2)
1 0 1 0 4 4
1 0 5 0 5 5 1
2 0 2 0 13 13 13 0
1 1 5 4 9
2 0 12 0 12
3 0 3 0 17 17
1 2 5 13 18 18 1
2 1 12 4 16
3 0 15 0 15
4 0 4 0 24 24
1 3 5 17 22
2 2 12 13 25 25 2
3 1 15 4 19
4 0 20 0 20
5 0 5 0 28 28
1 4 5 24 29 29 1
2 3 12 17 29
3 2 15 13 28
4 1 20 4 24
5 0 22 0 22
6 0 6 0 35 35
1 5 5 28 33
2 4 12 24 36 36 2
3 3 15 17 32
4 2 20 13 33
5 1 22 4 26
6 0 26 0 26

Пятый шаг. k = 1.
e0 u1 e1 = e0 - u1 f1(u1) F*1(e0) F0(u1,e0) F*1(e1) u1(e1)
1 0 1 0 5 5
1 0 6 0 6 6 1
2 0 2 0 13 13 13 0
1 1 6 5 11
2 0 8 0 8
3 0 3 0 18 18
1 2 6 13 19 19 1
2 1 8 5 13
3 0 10 0 10
4 0 4 0 25 25 25 0
1 3 6 18 24
2 2 8 13 21
3 1 10 5 15
4 0 14 0 14
5 0 5 0 29 29
1 4 6 25 31 31 1
2 3 8 18 26
3 2 10 13 23
4 1 14 5 19
5 0 18 0 18
6 0 6 0 36 36 36 0
1 5 6 29 35
2 4 8 25 33
3 3 10 18 28
4 2 14 13 27
5 1 18 5 23
6 0 22 0 22

Поясним построение таблиц и последовательность проведения расчетов.
Столбцы 1, 2 и 3 для всех трех таблиц одинаковы, поэтому их можно было бы сделать общими. Столбец 4 заполняется на основе исходных данных о функциях дохода, значения в столбце 5 берутся из столбца 7 предыдущей таблицы, столбец 6 заполняется суммой значений столбцов 4 и 5 (в таблице 5-го шага столбцы 5 и 6 отсутствуют).
В столбце 7 записывается максимальное значение предыдущего столбца для фиксированного начального состояния, и в 8 столбце записывается управление из 2 столбца, на котором достигается максимум в 7.

Этап II. Безусловная оптимизация.
Управлением в многошаговом процессе называется совокупность решений (управляющих переменных) uk = (uk1, ..., ukr), принимаемых на каждом шаге k и переводящих систему из состояния εk-1 = (εk-11, …, εk-1s) в состояние εk = (εk1, …, εks).
Из таблицы 1-го шага имеем F*5(e0 = 6) = 36. То есть максимальный доход всей системы при количестве средств e0 = 6 равен 36
Из этой же таблицы получаем, что 1-му предприятию следует выделить u*1(e0 = 6) = 0.
При этом остаток средств составит:
e1 = e0 - u1
e1 = 6 - 0 = 6
Из таблицы 2-го шага имеем F*4(e1 = 6) = 36. То есть максимальный доход всей системы при количестве средств e1 = 6 равен 36.
Из этой же таблицы получаем, что 2-му предприятию следует выделить u*2(e1 = 6) = 2.
При этом остаток средств составит:
e2 = e1 - u2
e2 = 6 - 2 = 4
Из таблицы 3-го шага имеем F*3(e2 = 4) = 24. То есть максимальный доход всей системы при количестве средств e2= 4 равен 24
Из этой же таблицы получаем, что 3-му предприятию следует выделить u*3(e2 = 4) = 2.
При этом остаток средств составит:
e3 = e2 - u3
e3 = 4 - 2 = 2
Из таблицы 4-го шага имеем F*2(e3 = 2) = 11. То есть максимальный доход всей системы при количестве средств e3 = 2 равен 11.
Из этой же таблицы получаем, что 4-му предприятию следует выделить u*4(e3 = 2) = 0.
При этом остаток средств составит:
e4 = e3 - u4
e4 = 2 - 0 = 2
Последнему предприятию достается 2.
Итак, инвестиции в размере 6 необходимо распределить следующим образом:
1-му предприятию выделить 0;
2-му предприятию выделить 2;
3-му предприятию выделить 2;
4-му предприятию выделить 0;
5-му предприятию выделить 2;
Что обеспечит максимальный доход, равный 36.

Пример №2. Для двух предприятий выделено A единиц средств. Как распределить все средства в течение 4 лет, чтобы доход был наибольшим, если известно, что доход от x единиц средств, вложенных в первое предприятие, равен f1(х), а доход от y единиц средств, вложенных во второе предприятие, равен f2(y). Остаток средств к концу года составляет g1(x) для первого предприятия и g2(y) для второго предприятия. Задачу решить методом динамического программирования.

Решение находим через сервис распределение средств между предприятиями.

I этап. Условная оптимизация.
1-ый шаг. k = 3.


e2

u3

e3= e2- u3

f3(u3)

F*3(e3)

u3(e3)

2

1

1

8



2

0

12

12

2

3

1

2

8



2

1

12



3

0

15

15

3

4

1

3

8



2

2

12



3

1

15



4

0

17

17

4

5

1

4

8



2

3

12



3

2

15



4

1

17



5

0

18

18

5

6

1

5

8



2

4

12



3

3

15



4

2

17



5

1

18



6

0

20

20

6

7

1

6

8



2

5

12



3

4

15



4

3

17



5

2

18



6

1

20



7

0

23

23

7

8

1

7

8



2

6

12



3

5

15



4

4

17



5

3

18



6

2

20



7

1

23



8

0

24

24

8

9

1

8

8



2

7

12



3

6

15



4

5

17



5

4

18



6

3

20



7

2

23



8

1

24



9

0

27

27

9

Посмотреть все итерации
Этап II. Безусловная оптимизация.
Из таблица 1-го шага имеем F*3(e0= 9) = 47. То есть максимальный доход всей системы при количестве средств e0= 9 равен 47
Из этой же таблицы получаем, что 1-му предприятию следует выделить u*1(e0= 9) = 2
При этом остаток средств составит:
e1= e0- u1
e1= 9 - 2 = 7
Из таблица 2-го шага имеем F*2(e1= 7) = 33. То есть максимальный доход всей системы при количестве средств e1= 7 равен 33
Из этой же таблицы получаем, что 2-му предприятию следует выделить u*2(e1= 7) = 5
При этом остаток средств составит:
e2= e1- u2
e2= 7 - 5 = 2
Последнему предприятию достается 2
Итак, выделенные инвестиции в размере 9 будут распределены так:
1-му предприятию выделить 2
2-му предприятию выделить 5
3-му предприятию выделить 2
Что обеспечит максимальный доход, равный 47

Пример №3. Планируется распределение начальной суммы средств S0 = 200 млн. руб. между четырьмя предприятиям П1, П2, П3 и П4. Предполагается, что выделенные в начале планового периода средства xk приносят доход Fk(xk) (k=1,..,4). Будем считать, что
1) доход, полученный от разных предприятий, выражается в одинаковых единицах;
2) доход, полученный от вложения средств в предприятие, не зависит от вложения средств в другие предприятия;
3) общий доход равен сумме доходов, полученных от всех средств, вложенных во все предприятия.
4) средства выделяются только в размерах кратных 50 млн. руб.
Определить какое количество средств нужно выделить каждому предприятию, чтобы суммарных доход был максимальным, если функция дохода на каждом из четырех предприятий заданы в таблице.

I этап. Условная оптимизация.
1-ый шаг. k = 4.


e3

u4

e4= e3- u4

f4(u4)

F*4(e4)

u4(e4)

40

20

20

12



40

0

30

30

40

60

20

40

12



40

20

30



60

0

44

44

60

80

20

60

12



40

40

30



60

20

44



80

0

51

51

80

100

20

80

12



40

60

30



60

40

44



80

20

51



100

0

62

62

100

Посмотреть все итерации
Этап II. Безусловная оптимизация.
Из таблица 1-го шага имеем F*4(e0 = 100) = 75. То есть максимальный доход всей системы при количестве средств e0 = 100 равен 75
Из этой же таблицы получаем, что 1-му предприятию следует выделить u*1(e0 = 100) = 20
При этом остаток средств составит:
e1 = e0 - u1
e1 = 100 - 20 = 80
Из таблица 2-го шага имеем F*3(e1 = 80) = 56. То есть максимальный доход всей системы при количестве средств e1 = 80 равен 56
Из этой же таблицы получаем, что 2-му предприятию следует выделить u*2(e1 = 80) = 20
При этом остаток средств составит:
e2 = e1 - u2
e2 = 80 - 20 = 60
Из таблица 3-го шага имеем F*2(e2 = 60) = 62. То есть максимальный доход всей системы при количестве средств e2 = 60 равен 62
Из этой же таблицы получаем, что 3-му предприятию следует выделить u*3(e2 = 60) = 40
При этом остаток средств составит:
e3 = e2 - u3
e3 = 60 - 40 = 20
Последнему предприятию достается 20
Итак, инвестиции в размере 100 надо распределить:
1-му предприятию выделить 20
2-му предприятию выделить 20
3-му предприятию выделить 40
4-му предприятию выделить 20
Что обеспечит максимальный доход, равный 75

Перейти к онлайн решению своей задачи

Пример №4. Распределить 5 однородных партий товара между тремя рынками так, чтобы получить максимальный доход от их продажи. Доход от продажи на каждом рынке G(X)зависит от количества реализованных партий товара Х и представлен в таблице.

Объем товара Х (в партиях) Доход G(X)
1 2 3
0 0 0 0
1 28 30 32
2 41 42 45
3 50 55 48
4 62 64 60
5 76 76 72

Решение:
Исходные данные.

f1 f2 f3 xi
0 0 0 0
28 30 32 1
41 42 45 2
50 55 48 3
62 64 60 4
76 76 72 5

I этап. Условная оптимизация.
1-ый шаг. k = 3.
e2u3e3 = e2 - u3f3(u3) F*3(e3) u3(e3)
1 0 1 0
1 0 32 32 1
2 0 2 0
1 1 32
2 0 45 45 2
3 0 3 0
1 2 32
2 1 45
3 0 48 48 3
4 0 4 0
1 3 32
2 2 45
3 1 48
4 0 60 60 4
5 0 5 0
1 4 32
2 3 45
3 2 48
4 1 60
5 0 72 72 5
2-ой шаг. k = 2.
e1u2e2 = e1 - u2f2(u2) F*2(e1) F1(u2,e1) F*2(e2) u2(e2)
1 0 1 0 32 32 32 0
1 0 30 0 30
2 0 2 0 45 45
1 1 30 32 62 62 1
2 0 42 0 42
3 0 3 0 48 48
1 2 30 45 75 75 1
2 1 42 32 74
3 0 55 0 55
4 0 4 0 60 60
1 3 30 48 78
2 2 42 45 87 87 2
3 1 55 32 87
4 0 64 0 64
5 0 5 0 72 72
1 4 30 60 90
2 3 42 48 90
3 2 55 45 100 100 3
4 1 64 32 96
5 0 76 0 76
3-ий шаг. k = 1.
e0u1e1 = e0 - u1f1(u1) F*1(e0) F0(u1,e0) F*1(e1) u1(e1)
1 0 1 0 32 32 32 0
1 0 28 0 28
2 0 2 0 62 62 62 0
1 1 28 32 60
2 0 41 0 41
3 0 3 0 75 75
1 2 28 62 90 90 1
2 1 41 32 73
3 0 50 0 50
4 0 4 0 87 87
1 3 28 75 103 103 1
2 2 41 62 103
3 1 50 32 82
4 0 62 0 62
5 0 5 0 100 100
1 4 28 87 115
2 3 41 75 116 116 2
3 2 50 62 112
4 1 62 32 94
5 0 76 0 76

Этап II. Безусловная оптимизация.
Из таблицы 1-го шага имеем F*3(e0 = 5) = 116. То есть максимальный доход всей системы при количестве товаров e0 = 5 равен 116.
Из этой же таблицы получаем, что 1-му рынку следует выделить u*1(e0 = 5) = 2 партии товаров.
При этом остаток товара (в партиях) составит:
e1 = e0 - u1
e1 = 5 - 2 = 3
Из таблицы 2-го шага имеем F*2(e1 = 3) = 75. То есть максимальный доход всей системы при количестве товаров e1 = 3 равен 75.
Из этой же таблицы получаем, что 2-му рынку следует выделить u*2(e1 = 3) = 1 партию товаров.
При этом остаток товаров составит:
e2 = e1 - u2
e2 = 3 - 1 = 2
Последнему рынку достается 2 партии товаров.
Итак, объем товара Х в размере 5 партий необходимо распределить следующим образом:
1-му рынку выделить 2 партии товаров.
2-му рынку выделить 1 партию.
3-му рынку выделить 2 партии товаров.
Что обеспечит максимальный доход, равный 116.

Решить эту задачу онлайн

Пример №5. Планируется распределение начальной суммы средств Е0 = 60 млн руб. между четырьмя предприятиями при условии, что средства выделяются только в размерах, кратных 10 млн руб., и функции дохода fi(x) для i-го предприятия заданы таблицей:


10

20

30

40

50

60

f 1

1

3

5

7

7

8

f 2

2

4

4

6

7

8

f 3

1

4

4

7

7

8

f 4

2

3

5

6

7

8
Определить, какое количество средств нужно выделить каждому предприятию, чтобы суммарная прибыль была наибольшей.
I этап. Условная оптимизация.
1-ый шаг. k = 4.
e3 u4 e4 = e3 - u4 f4(u4) F*4(e4) u4(e4)
10 0 10 0 0 0
10 0 2 2 10
20 0 20 0 0 0
10 10 2 0 0
20 0 3 3 20
30 0 30 0 0 0
10 20 2 0 0
20 10 3 0 0
30 0 5 5 30
40 0 40 0 0 0
10 30 2 0 0
20 20 3 0 0
30 10 5 0 0
40 0 6 6 40
50 0 50 0 0 0
10 40 2 0 0
20 30 3 0 0
30 20 5 0 0
40 10 6 0 0
50 0 7 7 50
60 0 60 0 0 0
10 50 2 0 0
20 40 3 0 0
30 30 5 0 0
40 20 6 0 0
50 10 7 0 0
60 0 8 8 60

Посмотреть все итерации
Таким образом, начальную сумму в размере 60 млн. руб. необходимо распределить следующим образом:
первому предприятию выделить 0 млн. руб.
Второму предприятию выделить 10 млн. руб.
Третьему предприятию выделить 20 млн. руб.
Четвертому предприятию выделить 30 млн. руб.

Данное распределение начальных средств в размере 60 млн. руб. обеспечит максимальный доход, равный 11 млн. руб.

Перейти к онлайн решению своей задачи

Пример №6. Для модернизации предприятий совет директоров инвестирует средства в объеме 25 млн. руб. с дискретностью 5 млн. руб. Прирост выпуска продукции зависит от выделенной суммы, его значения представлены предприятиями и содержатся в таблице. Найти распределение инвестиций между предприятиями, обеспечивающее фирме максимальный прирост выпуска продукции, причем на одно предприятие можно осуществить только одну инвестицию.

Выделяемые средства, млн.руб. Прирост выпуска продукции, млн.руб.
Предприятие №1Предприятие №2Предприятие №3
5 10 15 20 2511 16 23 28 3413 15 21 29 3710 17 22 28 36

I этап. Условная оптимизация. 1-ый шаг. k = 3.

e2u3e3= e2- u3f3(u3)F*3(e3)u3(e3)
5050
5010105
100100
5510
100171710
150150
51010
10517
150222215
200200
51510
101017
15522
200282820
250250
52010
101517
151022
20528
250363625

Посмотреть все итерации
Итак, инвестиции в размере 25 млн. руб. необходимо распределить следующим образом:
1-му предприятию выделить 5 млн. руб.
2-му предприятию выделить 5 млн. руб.
3-му предприятию выделить 15 млн. руб.
Это обеспечит максимальный доход в размере 46 млн. руб.

Пример №7. Лизинговой компании необходимо сделать выбор объектов предполагаемых лизинговых сделок с определением оптимальных объемов финансирования на приобретение этих объектов в размерах кратных 100 млн. руб. Для инвестирования на эти цели компания располагает капиталом в объеме 700 млн. руб. В таблице 4 приводится среднегодовая прибыль компаний, ожидаемая от лизингополучателей при предоставлении им того или иного объекта на сумму от 0 до 700 млн. руб.
Таблица - Объем финансирования, млн. руб. Среднегодовая прибыль при предоставлении объектов, млн. руб.

f1f2f3xi
0000
316255100
60120104200
87174147300
112224184400
135270215500
156312240600
175350269700

Под оптимальным объемом финансирования на приобретение объектов лизинга администрация компании понимает такое распределение суммы в 700 млн. руб. при котором среднегодовая прибыль от лизингополучателей всех этих объектов оказывается максимальной.

Используя метод динамического программирования, рассчитать такие объемы инвестиций по объектам лизинга, по которым ожидается максимальная по величине среднегодовая прибыль лизингополучателя.

Итак, инвестиции в размере 700 млн. руб. необходимо распределить следующим образом:

1-му объекту выделить 0 млн. руб..

2-му объекту выделить 500 млн. руб..

3-му объекту выделить 200 млн. руб..

Что обеспечит максимальный доход, равный 374 млн. руб.

Пример №8. Инвестор выделяет средства в размере т.д. ед, которые должны быть распределены между тремя предприятиями.
Требуется, используя принцип оптимальности Беллмана, составить план распределения средств между предприятиями, обеспечивающий наибольшую общую прибыль, если каждое предприятие при инвестировании в него средств Х т.д.ед. приносит прибыль U(Х) по следующим данным:
Инвестирование средств т/р Прибыль т/р
Х U1(Х) U2(Х) U3(Х)
1 6,58 5,14 6,1
2 12,3 4,26 8,5
3 14,5 10,52 11,52
4 20,9 18,54 18,26
5 26,86 25,62 17,4


Итак, инвестиции в размере 5 необходимо распределить следующим образом:
1-му предприятию выделить 4,
2-му предприятию выделить 0,
3-му предприятию выделить 1.
Что обеспечит максимальный доход, равный 27.

Пример №9. Планируется распределение начальной суммы средств e0 = 40 млн руб., причем средства выделяются кратно 10 млн руб. между тремя предприятиями П1, П2, П3. Выделение предприятию Пk средств uk приносит доход fk(uk), который задан в табл. Определить, какое количество средств нужно выделить каждому предприятию, чтобы обеспечить максимальный суммарный доход.

x 0 10 20 30 40
f1(x) 0 4 5 7 8
f2(x) 0 3 3 4 6
f3(x) 0 4 4 5 6


Итак, максимальный доход в количестве 40 будет получен, если:
1-му предприятию выделить 20
2-му предприятию выделить 10
3-му предприятию выделить 10
Что обеспечит максимальный доход, равный 12
Учебно-методический
√ курсы переподготовки и повышения квалификации
√ вебинары
√ сертификаты на публикацию методического пособия
Подробнее
Библиотека материалов
√ Общеобразовательное учреждение
√ Дошкольное образование
√ Конкурсные работы
Все авторы, разместившие материал, могут получить свидетельство о публикации в СМИ
Подробнее
Инвестиции с JetLend

Удобный сервис для инвестора и заемщика. Инвестируйте в лучшие компании малого бизнеса по ставкам от 16,9% до 37,7% годовых.
Подробнее
Курсовые на заказ