Задача. Для двух предприятий выделено 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

2-ый шаг. k = 2.

e1

u2

e2 = e1 - u2

f2(u2)

F*2(e1)

F1(u2,e1)

F*2(e2)

u2(e2)

2

1

1

9

12

21

21

1

2

0

11

0

11

 

 

3

1

2

9

15

24

 

 

2

1

11

12

23

 

 

3

0

13

0

13

 

 

4

1

3

9

17

26

 

 

2

2

11

15

26

 

 

3

1

13

12

25

 

 

4

0

15

0

15

 

 

5

1

4

9

18

27

 

 

2

3

11

17

28

28

2

3

2

13

15

28

 

 

4

1

15

12

27

 

 

5

0

18

0

18

 

 

6

1

5

9

20

29

 

 

2

4

11

18

29

 

 

3

3

13

17

30

30

3

4

2

15

15

30

 

 

5

1

18

12

30

 

 

6

0

21

0

21

 

 

7

1

6

9

23

32

 

 

2

5

11

20

31

 

 

3

4

13

18

31

 

 

4

3

15

17

32

 

 

5

2

18

15

33

33

5

6

1

21

12

33

 

 

7

0

23

0

23

 

 

8

1

7

9

24

33

 

 

2

6

11

23

34

 

 

3

5

13

20

33

 

 

4

4

15

18

33

 

 

5

3

18

17

35

 

 

6

2

21

15

36

36

6

7

1

23

12

35

 

 

8

0

24

0

24

 

 

9

1

8

9

27

36

 

 

2

7

11

24

35

 

 

3

6

13

23

36

 

 

4

5

15

20

35

 

 

5

4

18

18

36

 

 

6

3

21

17

38

38

6

7

2

23

15

38

 

 

8

1

24

12

36

 

 

9

0

27

0

27

 

 

3-ый шаг. k = 1.

e0

u1

e1 = e0 - u1

f1(u1)

F*1(e0)

F0(u1,e0)

F*1(e1)

u1(e1)

2

1

1

7

21

28

28

1

2

0

11

0

11

 

 

3

1

2

7

21

28

 

 

2

1

11

21

32

32

2

3

0

14

0

14

 

 

4

1

3

7

21

28

 

 

2

2

11

21

32

 

 

3

1

14

21

35

35

3

4

0

16

0

16

 

 

5

1

4

7

28

35

 

 

2

3

11

21

32

 

 

3

2

14

21

35

 

 

4

1

16

21

37

37

4

5

0

17

0

17

 

 

6

1

5

7

30

37

 

 

2

4

11

28

39

39

2

3

3

14

21

35

 

 

4

2

16

21

37

 

 

5

1

17

21

38

 

 

6

0

20

0

20

 

 

7

1

6

7

33

40

 

 

2

5

11

30

41

 

 

3

4

14

28

42

42

3

4

3

16

21

37

 

 

5

2

17

21

38

 

 

6

1

20

21

41

 

 

7

0

22

0

22

 

 

8

1

7

7

36

43

 

 

2

6

11

33

44

44

2

3

5

14

30

44

 

 

4

4

16

28

44

 

 

5

3

17

21

38

 

 

6

2

20

21

41

 

 

7

1

22

21

43

 

 

8

0

26

0

26

 

 

9

1

8

7

38

45

 

 

2

7

11

36

47

47

2

3

6

14

33

47

 

 

4

5

16

30

46

 

 

5

4

17

28

45

 

 

6

3

20

21

41

 

 

7

2

22

21

43

 

 

8

1

26

21

47

 

 

9

0

29

0

29

 

 

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