Практическое занятие № 15 Тема «Основные понятия динамического программирования»

На данной сети дорог указаны стоимости доставки единицы груза из пункта в пункт. Найти наиболее экономичный маршрут перевозки груза из пункта 1 в пункт 10.

№1

4 7

3 5 2 3

2 7

4 9

5 1 8

2 6

7

Ответ: 1-3-5-7-10; 11.

№2

9 3

2 5 9 4

4

1 1

7 6 2 6

4 8

Ответ: 1-3-6-9-10; 10.

На данной сети дорог указаны стоимости доставки единицы груза из пункта в пункт. Найти наиболее экономичный маршрут перевозки груза из пункта 1 в пункт 13.

№

4

7

3 9

11

6

1 4

2

2 4

13

8

6 5 2

1

9 5

5

8 7 3

9

3 6

12

3

2 8 3 9

10

6

9 8

6 4

Ответ: 1-3-4-8-11-13; 15.

№4

Производственное объединение выделяет четырем входящим в него предприятиям кредит в сумме 100 млн.ден.ед. для расширения производства и увеличения выпуска продукции. По каждому предприятию известен возможный прирост выпуска продукции (в денежном выражении) в зависимости от выделенной суммы . Для упрощения вычислений выделяемые суммы кратны 20 млн ден.ед. (таблица). При этом предполагаем, что прирост выпуска продукции на i- м предприятии не зависит от суммы средств, вложенных в другие предприятия, а общий прирост выпуска в производственном объединении равен сумме приростов, полученных на каждом предприятии объединения.

Выделяемые средства , млн.ден.ед	Предприятие
	№1	№2	№3	№4
	Прирост выпуска продукции на предприятиях , млн. ден.ед.
20 40 60 80 100	10 31 42 62 76	12 26 36 54 78	11 36 45 60 77	16 37 46 63 80

Ответ: 85 (0; 20; 40; 40).

№5

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

Выделяемые средства , млн.ден.ед	Предприятие
	№1	№2	№3
	Прирост выпуска продукции на предприятиях , млн. ден.ед.
20 40 60	9 17 29	11 34 46	13 28 37

Ответ: 47 (0,40,20).

№6

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

Выделяемые средства , млн.ден.ед	Предприятие
	№1	№2	№3	№4
	Прирост выпуска продукции на предприятиях , млн. ден.ед.
20 40 60	9 18 24	11 19 30	16 32 40	13 27 44

Ответ: 45 (0,0,40,20).