<<

Динамическое программирование

1 – 4. Задачи об оптимальном распределении ресурсов между двумя отраслями на п лет

1 (30 вариантов). Планируется работа двух отраслей производства на период в три года. Средства х, вложенные в I отрасль в начале года, дают в конце года прибыль Аx и возвращаются в размере Вxlt;x; аналогично для II отрасли функция прибыли равна Сx, а возврата – Dx (Dxlt;x).

В конце года все возвращенные средства заново перераспределяются между I и II отраслями, новые средства не поступают, прибыль в производство не вкладывается.

Количество средств, выделенное на развитие двух отраслей в начале периода, составляет z1=100 единиц. Требуется распределить средства между отраслями на каждый год планируемого периода так, чтобы суммарный доход, полученный от этих отраслей за три года, был максимальным.

Коэффициенты А, В, С и D для 30 вариантов приведены ниже.

Варианты

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

А

3

4

4

3

5

2

6

1

5

3

7

8

3

2

6

В

0,5

0,7

0,3

0,3

0,7

0,8

0,2

0,2

0,7

0,8

0,4

0,3

0,8

0,7

0,1

С

4

6

8

1

7

4

4

4

6

6

4

6

5

4

2

D

0,2

0,4

0,6

0,9

0,3

0,4

0,7

0,6

0,4

0,4

0,9

0,5

0,3

0,3

0,8

Варианты

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

А

4

3

4

8

6

2

2

2

5

6

3

1

4

3

5

В

0,4

0,9

0,7

0,3

0,3

0,9

0,7

0,3

0,5

0,2

0,8

0,9

0,4

0,2

0,7

С

3

4

7

6

4

4

3

1

7

4

5

3

2

2

6

D

0,6

0,4

0,3

0,8

0,6

0,5

0,2

0,8

0,2

0,7

0,4

0,4

0,8

0,6

0,3

2.

Планируется деятельность двух отраслей производства на п лет. Начальные ресурсы s0. Средства х, вложенные в I отрасль в начале года, дают в конце года прибыль f1(x) и возвращаются в размере q1(x)lt;x; аналогично для II отрасли функция прибыли равна f2(x), а возврата – q2(x) (q2(x)lt;x). В конце года все возвращенные средства заново перераспределяются между I и II отраслями, новые средства не поступают, прибыль в производство не вкладывается.

Требуется распределить имеющиеся средства s0 между двумя отраслями производства на п лет так, чтобы суммарная прибыль от обеих отраслей за п лет оказалась максимальной.

Необходимо:

а) построить модель ДП для задачи и вычислительную схему;

б) решить задачу при : s0=100 ед., п=3, f1(x)=8х, q1(x)=0,4x, f2(x)=6x, q2(x)=0,7x.

3. s0=400 ед., п=4, f1(x)=0,4х, q1(x)=0,5x, f2(x)=0,3x, q2(x)=0,8x.

4. s0=100 ед., п=4, f1(x)=0,1х2, q1(x)=0,75x, f2(x)=0,5x, q2(x)=0,3x.

5 – 13. Задачи о нахождении оптимальных маршрутов перевозки груза из пункта 1 в конечный пункт.

5. На сети дорог, изображенной на рис. 1, а, б, указаны стоимости перевозки единицы груза между отдельными пунктами сети. Найти наиболее экономный маршрут доставки груза из пункта А в пункт Б. Чему равны суммарные затраты по доставке единицы груза оптимальным маршрутом?

Рис. 1,а

Рис. 1,б

6. На сети дорог, изображенной на рис. 2, а, б, указаны стоимости перевозки единицы груза между отдельными пунктами сети. Найти на сети маршруты, ведущие

Рис.

2,а

Рис. 2,б

в конечный пункт 12 из всех остальных пунктов, при перевозке груза по которым затраты минимизируются. Определить величину этих затрат для каждого найденного оптимального маршрута.

7. Определить экономный маршрут движения транспорта из начального пункта А

Рис. 3,а

Рис. 3,б

в конечный пункт Б на сети дорог, изображенной на рис. 3, а, б. Стоимости между промежуточными пунктами сети на рисунке указаны. Чему равна стоимость оптимального маршрута?

8. На сетевом графике комплекса работ, изображенном на рис. 4, а, б, найти

Рис. 4,а

Рис. 4,б

критический путь и определить критический срок.

9 – 12. Найти оптимальные маршрут и расстояние из пункта 1 в конечный пункт 10 (рис. 5, а, б; 6 а, б).

Рис. 5, а

Рис. 5, б

Рис. 6,а

Рис. 6,б

13 (10 вариантов).

На данной сети дорог (рис. 7) имеется несколько маршрутов, по которым можно доставить груз из пункта 1 в пункт 10. Известны стоимости cij перевозки единицы груза между пунктами сети. Найти наиболее экономный маршрут доставки груза из пункта 1 в пункт 10 и соответствующие ему затраты.
Рис. 7

Все необходимые данные для 10 вариантов приведены в таблице.

№№

с12

с13

с14

с25

с27

с35

с36

с37

с45

с46

с47

с58

с59

с68

с69

с79

с8,10

с9,10

1

7

3

5

2

7

9

3

1

8

4

5

2

6

1

9

4

3

8

2

4

8

4

6

1

5

3

5

4

8

2

7

4

9

6

1

7

2

3

9

2

5

3

7

4

6

8

1

3

5

8

7

1

4

5

9

5

4

1

6

2

5

3

6

8

4

7

2

9

5

3

6

1

4

6

1

5

5

3

8

2

5

8

1

7

5

9

1

3

5

8

4

9

2

7

6

8

1

5

9

2

6

8

4

5

2

6

1

8

3

6

2

5

9

7

3

5

4

1

6

2

7

4

6

8

3

7

2

9

2

8

1

3

8

6

2

6

7

3

9

2

8

5

2

9

4

6

7

4

6

7

6

9

1

9

3

8

7

4

9

3

7

4

8

6

3

1

8

1

9

4

10

4

6

1

3

5

7

3

6

2

5

9

1

8

2

3

5

3

8

14 – 38.

Задачи о замене оборудования.

Плановый период эксплуатации оборудования рассчитай на n лет. В конце этого периода имеющееся оборудование должно быть продано. Стоимость нового оборудования равна соst. Даны также ликвидная стоимость likv(i) и затраты zаtr(i) на содержание в течение одного года оборудования возраста i лет, i=0,1,..., n. Требуется найти оптимальную стратегию замены оборудования за указанный временной период, минимизирующий суммарные затраты.

14. n= 4, соst=8500,

15. n=4, соst=3000,

i

0

1

2

3

4

likv(i)

6000

5000

3000

1000

zаtr(i)

600

800

1100

1500

i

0

1

2

3

4

likv(i)

1200

1000

800

100

zаtr(i)

400

600

1000

1 900

16. n=4, соst=8400,

17. n=4, соst=1000,

i

0

1

2

3

4

likv(i)

7000

4000

3000

1000

zаtr(i)

200

2000

2100

2400

i

0

1

2

3

4

likv(i)

800

500

300

100

zаtr(i)

400

1000

1700

3400

18.

n=4, соst=9000,

19. n=4, соst=4000,

i

0

1

2

3

4

likv(i)

1100

700

500

200

zаtr(i)

100

1000

1600

2000

i

о

1

2

3

4

likv(i)

3400

2000

1000

900

zаtr(i)

200

600

1300

3000

20. n=5, соst=5400, 21. n=5, соst=1100,

i

0

1

2

3

4

5

likv(i)

3500

3000

2400

2000

1000

zаtr(i)

500

2000

2100

2400

2600

i

0

1

2

3

4

5

likv(i)

1000

900

450

400

100

zаtr(i)

800

1700

1900

2900

4200

22. n=5, соst=3200, 23. n=5, соst=3000,

i

0

1

2

3

4

5

likv(i)

1400

700

500

400

200

zаtr(i)

200

700

1500

3200

3700

i

0

1

2

3

4

5

likv(i)

2000

1300

900

500

200

zаtr(i)

400

800

1300

1400

2100

24. п=6, соst=3000, 25. n=6, соst=2600,

i

0

1

2

3

4

5

6

likv(i)

2100

1800

1100

800

100

20

zаtr(i)

700

900

1200

1900

2400

3100

i

0

1

2

3

4

5

6

likv(i)

2200

1300

1000

300

100

70

zаtr(i)

100

300

800

1300

2400

3100

26. п=6, соst=1500, 27. n=6, соst=4000,

i

0

1

2

3

4

5

6

likv(i)

1400

600

500

300

100

90

zаtr(i)

1200

1600

2500

3000

3800

4000

i

0

1

2

3

4

5

6

likv(i)

2000

1800

1000

500

300

100

zаtr(i)

400

1100

1700

2500

3500

4100

28. п=7 соst=5500, 29. n=7, соst=2000,

i

0

1

2

3

4

5

6

7

likv(i)

5000

4200

2300

1500

800

300

200

zаtr(i)

400

700

1200

1900

2400

3500

3700

i

0

1

2

3

4

5

6

7

likv(i)

1800

1200

900

600

500

300

200

zаtr(i)

900

1300

1500

1600

1700

2500

3100

30. п=7 соst=1100, 31. n=7, соst=3000,

i

0

1

2

3

4

5

6

7

likv(i)

900

800

600

500

300

200

20

zаtr(i)

500

900

1100

1200

1400

2500

2700

i

0

1

2

3

4

5

6

7

likv(i)

1900

1300

900

500

400

300

130

zаtr(i)

90

100

400

500

800

1000

1400

32. п=8 соst=1000, 33. n=8, соst=1300,

i

0

1

2

3

4

5

6

7

8

likv(i)

900

700

600

400

200

100

50

20

zаtr(i)

80

200

500

600

800

900

1100

1300

i

0

1

2

3

4

5

6

7

8

likv(i)

1000

900

800

600

500

400

300

200

zаtr(i)

90

200

250

300

400

550

700

900

1000

34. п=5 соst=8000, 35. 10, соst=7500, а данные в таблице необходимо умножить на 10.

i

0

1

2

3

4

5

likv(i)

6000

5000

3000

1000

500

zаtr(i)

600

800

1100

1500

2000

i

0

1

2

3

4

5

6

7

8

9

10

likv(i)

600

500

300

100

95

95

84

80

40

35

zаtr(i)

60

80

110

150

155

155

160

162

250

300

36. n=5, соst=4000, likv(i)=соst·2-i, zаtr(i)=600(i+1).

37. n=5, соst=8000, likv(i)=соst·2-i, zаtr(i)=0,1соst·(i+1).

38. n=5, соst(k)=5000+5000(k-1), k – год покупки, k=1, 2, …, 5,

likv(i)=соst(k) 2-i, zаtr(i)=0,1соst(k)·(i+1).

39 – 46. Задачи об оптимальном распределении капиталовложений между п предприятиями.

Группе из п предприятий П1, П2, .... ,Пп выделяются дополнительные средства на реконструкцию и модернизацию производства. Известна матрица f, в которой на позиции (i, k) находится величина fik, fik?0, равная приросту выпуска продукции на предприятии Пk, при выделении ему дополнительных средств в размере i ден. ед. (i=0, 1, …, m; k=1, 2, ..., n). Требуется так распределить между предприятиями общую сумму средств в m ден. ед., чтобы суммарный прирост выпуска продукции был максимальным. Вложения кратны ?.

39. fТ=, п=3, т=9, ?=1.

40. fТ=, п=4, т=5, ?=1.

41. fТ=, п=4, т=9, ?=1.

42. В условиях задачи 39 найти оптимальное распределение средств т=8.

43. В условиях задачи 40 найти оптимальное распределение средств между 2-, 3- и 4-м предприятиями.

44. fТ=, п=4, т=5, ?=1.

45. fТ=, п=8, т=10, ?=1.

46 (10 вариантов). п=4, т=250, ?=50. Значения коэффициентов матрицы f для 10 вариантов приведены в таблице (при т=0 коэффициенты f11=f12=f13=f14=0).

№№

fij

f21

f22

f23

f24

f31

f32

f33

f34

f41

f42

f43

f44

f51

f52

f53

f54

f61

f62

f63

f64

1

5

7

6

4

9

10

8

11

21

20

21

19

33

34

32

35

38

39

40

41

2

8

10

7

10

13

12

14

13

22

21

22

23

31

38

29

30

39

40

38

41

3

11

12

10

11

16

15

17

14

23

24

22

25

32

31

32

30

38

39

40

38

4

10

9

7

8

15

16

13

14

24

22

20

21

33

34

31

32

40

39

41

40

5

12

13

11

11

17

15

16

18

23

25

21

22

34

33

35

34

42

41

43

44

6

21

20

22

23

30

28

31

29

42

41

40

41

51

52

53

50

62

63

61

64

7

22

23

24

21

31

30

32

29

43

41

42

40

52

53

51

53

63

64

65

66

8

23

24

25

22

32

31

33

30

44

43

42

41

53

52

54

55

70

72

71

73

9

25

26

27

28

34

33

35

35

46

46

45

44

57

58

56

55

78

77

79

80

10

15

12

17

13

32

30

33

31

39

38

40

37

46

45

47

44

52

54

60

63

<< |
Источник: И.И. Холявин. МАТЕМАТИЧЕСКОЕ ПРОГРАММИРОВАНИЕ И ЭКОНОМИКО-МАТЕМАТИЧЕСКИЕ МЕТОДЫ. Учебное пособие для студентов экономических вузов Часть 2. Гатчина 2009. 2009

Еще по теме Динамическое программирование:

  1. Общая постановка задачи динамического программирования
  2. 16.5. Задача динамического программирования в терминах теории графов.
  3. 3.5. Нелинейное и динамическое программирование; понятие об имитационном моделировании
  4. 16.4. Решение задачи о кратчайшем пути методами динамического программирования.
  5. 9.4. Математика элементы векторной оптимизации; элементы сетевого планирования; модели управления запасами; динамическое программирование; оптимальное управление
  6. Основные этапы развития технологий программирования Программирование в кодах и ассемблер
  7. • Принцип оптимальности в планировании и управлении, общая задача оптимального программирования • Формы записи задачи линейного программирования и ее экономическая интерпретация • Математический аппарат • Геометрическая интерпретация задачи • Симплексный метод решения задачи 2.1. Принцип оптимальности в планировании и управлении, общая задача оптимального программирования
  8. Модульное программирование
  9. Язык программирования
  10. 3.3. Целочисленное программирование
  11. б.              Линейное программирование
  12. Программирование государственных финансов
  13. Визуальное программирование интерфейса
  14. Программирование, управляемое событиями
  15. Языки программирования высокого уровня
  16. Параметрическое программирование 1 (35 вариантов).
- Информатика для экономистов - Антимонопольное право - Бухгалтерский учет и контроль - Бюджетна система України - Бюджетная система России - ВЭД РФ - Господарче право України - Государственное регулирование экономики в России - Державне регулювання економіки в Україні - ЗЕД України - Инновации - Институциональная экономика - История экономических учений - Коммерческая деятельность предприятия - Контроль и ревизия в России - Контроль і ревізія в Україні - Кризисная экономика - Лизинг - Логистика - Математические методы в экономике - Микроэкономика - Мировая экономика - Муніципальне та державне управління в Україні - Налоговое право - Организация производства - Основы экономики - Политическая экономия - Региональная и национальная экономика - Страховое дело - Теория управления экономическими системами - Управление инновациями - Философия экономики - Ценообразование - Экономика и управление народным хозяйством - Экономика отрасли - Экономика предприятия - Экономика природопользования - Экономика труда - Экономическая безопасность - Экономическая география - Экономическая демография - Экономическая статистика - Экономическая теория и история - Экономический анализ -