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

14.1. Найти оптимальное распределение ресурсов между ТП и максимальную прибыль в задачах с исходными данными, приведенными ниже. Найти также решения задачи при измененных данных: а) том же ресурсе, но меньшем числе ТП; б) уменьшенном ресурсе, но том же количестве ТП; в) уменьшенных ресурсе и количестве ТП.

1. n 4, c 12 2. n 4, c 25

x	0	2	4	6	8	10	12		x	0	5	10	15	20	25
f1	0	8	13	20	23	26	30		f1	0	10	15	23	36	40
f2	0	18	25	27	30	33	37		f2	0	15	25	32	38	45
f3	0	10	15	27	33	37	42		f3	0	12	20	25	30	38
f4	0	10	21	28	34	38	43		f4	0	15	21	25	30	35

3. n 4, c 5 4. n 4, c 15

x	0	1	2	3	4	5		x	0	3	6	9	12	15
f1	0	4	9	12	15	18		f1	0	4	8	12	16	20
f2	0	8	10	15	18	21		f2	0	6	11	16	21	25
f3	0	6	10	15	20	25		f3	0	7	12	16	21	23
f4	0	5	9	13	17	20		f4	0	6	10	14	18	21

5. n 4, c 10 6. n 4, c 20

x	0	2	4	6	8	10		x	0	4	8	12	16	20
f1	0	8	15	20	25	30		f1	0	10	18	25	31	38
f2	0	12	18	23	28	35		f2	0	12	18	24	29	35
f3	0	12	22	30	36	40		f3	0	13	20	25	32	38
f4	0	8	17	25	30	34		f4	0	12	19	25	33	37

7. n 3, c 60 8. n 3, c 6

x	0	10	20	30	40	50	60		x	0	1	2	3	4	5	6
f1	0	15	20	25	30	35	40		f1	0	3	7	10	15	20	25
f2	0	10	17	25	32	39	43		f2	0	6	8	10	13	17	24
f3	0	12	18	23	34	40	45		f3	0	4	8	10	14	17	23

9. n 3, c 18 10. n 3, c 12

x	0	3	6	9	12	15	18		x	0	2	4	6	8	10	12
f1	0	10	15	23	28	35	40		f1	0	10	15	20	25	30	35
f2	0	12	18	25	30	38	45		f2	0	8	13	18	24	30	34
f3	0	15	21	28	34	39	46		f3	0	6	12	18	24	30	36

11. n 4, c 50 12. n 4, c 25

x	0	10	20	30	40	50		x	0	5	10	15	20	25
f1	0	8	16	24	32	40		f1	0	18	36	54	72	90
f2	0	12	20	28	36	42		f2	0	20	40	60	80	89
f3	0	10	18	26	34	42		f3	0	22	45	66	80	92
f4	0	9	17	25	33	41		f4	0	15	30	45	60	75

13. n 3, c 30 14. n 3, c 6

x	0	5	10	15	20	25	30		x	0	1	2	3	4	5	6
f1	0	10	20	29	37	45	50		f1	0	22	36	50	65	77	85
f2	0	15	24	30	39	45	49		f2	0	22	40	58	70	80	85
f3	0	14	23	32	41	50	53		f3	0	20	35	50	60	72	79

15. n 4, c 15 16. n 4, c 50

x	0	3	6	9	12	15		x	0	10	20	30	40	50
f1	0	6	15	19	25	33		f1	0	15	30	45	60	75
f2	0	9	17	24	27	30		f2	0	18	36	54	70	84
f3	0	9	15	20	25	30		f3	0	20	42	60	75	85
f4	0	7	13	23	27	31		f4	0	15	30	45	60	75

17. n 3, c 10 18. n 3, c 60

x	0	2	4	6	8	10		x	0	10	20	30	40	50	60
f1	0	6	9	12	15	18		f1	0	13	20	27	34	41	47
f2	0	4	8	12	16	19		f2	0	15	25	32	38	43	46
f3	0	4	7	10	13	15		f3	0	12	22	30	37	43	47

19. n 4, c 30 20. n 4, c 12

x	0	5	10	15	20	25	30		x	0	2	4	6	8	10	12
f1	0	10	18	25	31	35	40		f1	0	10	18	24	28	31	35
f2	0	11	18	24	29	33	39		f2	0	9	17	24	30	35	40
f3	0	10	19	27	33	37	40		f3	0	8	16	23	29	34	38
f4	0	13	20	26	32	37	40		f4	0	12	22	30	36	40	45

21. n 3, c 21 22. n 3, c 12

x	0	3	6	9	12	15	18	21		x	0	2	4	6	8	10	12
f1	0	18	28	36	42	46	49	52		f1	0	8	15	21	26	31	35
f2	0	12	22	31	38	43	47	50		f2	0	7	14	21	27	33	38
f3	0	15	25	33	39	44	47	51		f3	0	10	16	21	25	29	32

23. n 3, c 25 24. n 3, c 6

x	0	5	10	15	20	25		x	0	1	2	3	4	5	6
f1	0	15	25	33	39	43		f1	0	24	44	60	72	81	87
f2	0	16	25	32	37	40		f2	0	21	39	54	64	72	78
f3	0	10	19	27	34	40		f3	0	20	38	53	65	75	83

25. n 4, c 50 26. n 4, c 25

x	0	10	20	30	40	50		x	0	5	10	15	20	25
f1	0	12	22	30	35	37		f1	0	25	45	63	77	87
f2	0	9	17	25	32	38		f2	0	18	35	51	65	77
f3	0	8	16	24	28	32		f3	0	20	36	50	60	68
f4	0	10	19	26	32	36		f4	0	24	46	66	78	88

27. n 4, c 15 28. n 4, c 10

x	0	3	6	9	12	15		x	0	2	4	6	8	10
f1	0	9	17	24	27	29		f1	0	9	15	25	27	30
f2	0	8	15	21	26	30		f2	0	8	16	20	25	31
f3	0	6	12	18	23	28		f3	0	5	10	15	20	25
f4	0	10	18	24	28	30		f4	0	10	15	20	25	30

29. n 4, c 20 30. n 4, c 25

x	0	4	8	12	16	20		x	0	5	10	15	20	25
f1	0	9	17	24	27	29		f1	0	5	10	17	24	29
f2	0	8	15	21	26	30		f2	0	8	13	18	24	30
f3	0	6	12	18	23	28		f3	0	6	10	16	22	28
f4	0	10	18	24	28	30		f4	0	10	17	26	29	34

14.2. Найти кратчайший путь между двумя городами 1 и 8. На рис. 14.5 указаны всевозможные маршруты между этими городами, проходящие через промежуточные населенные пункты. В табл. 14.3 даны расстояния c_ij между населенными пунктами i и j.

Таблица 14.3
Варианты	с12	с13	с14	с24	с25	с34	с36	с45	с46	с47	с57	с58	с67	с68	с78
1	2	4	7	3	6	5	2	4	2	8	2	10	1	9	3
2	5	6	6	4	3	8	5	10	7	6	3	4	6	2	11
3	2	7	10	5	6	4	8	3	4	10	7	9	11	9	2
4	7	3	5	12	3	10	2	11	14	6	1	5	4	6	9
5	10	5	6	7	8	3	7	8	5	3	9	2	7	11	15
6	5	8	6	10	5	7	12	3	2	15	1	9	4	3	10
7	8	3	13	5	9	3	7	8	6	5	8	4	5	11	7
8	2	7	9	8	4	8	3	4	9	7	13	6	2	4	10
9	6	4	8	12	9	1	8	10	5	2	7	10	4	3	6
10	8	10	4	5	1	3	2	5	1	12	2	3	6	5	7
11	1	4	2	6	7	5	6	9	6	6	1	6	2	3	5
12	5	2	6	5	9	1	10	7	5	7	9	2	1	5	4
13	7	4	2	10	5	6	1	4	3	8	2	5	7	4	9
14	3	3	5	2	8	3	11	8	5	7	6	2	3	10	3
15	9	3	6	7	5	4	7	9	2	5	10	4	3	1	5
16	5	4	2	5	8	5	8	6	2	6	7	6	5	4	10
17	5	7	10	5	6	5	8	11	8	7	4	5	7	3	9
18	3	5	8	4	7	6	3	5	3	9	3	11	2	10	4
19	6	7	7	5	4	9	6	11	8	7	4	5	7	3	12
20	3	8	11	6	7	5	9	4	5	11	8	10	12	10	3
21	8	4	6	13	4	11	3	12	15	7	2	6	5	7	10
22	11	6	7	8	9	4	8	9	6	4	10	3	8	12	16
23	6	9	7	11	6	8	13	4	3	16	2	10	5	4	11
24	7	2	12	4	8	3	7	7	5	4	7	3	4	10	7
25	3	7	10	8	5	8	4	4	9	8	12	5	2	4	9
26	6	4	7	11	10	2	8	10	4	3	8	11	4	4	7
27	8	9	4	5	2	3	3	5	2	10	3	4	6	5	8
28	2	4	3	7	7	6	6	10	7	7	2	7	2	4	6
29	6	2	7	5	10	2	10	8	5	7	10	3	2	4	5
30	4	4	5	2	9	4	10	9	6	8	7	3	3	11	4

14.3. В табл. 14.5 содержатся сведения о работах, которые необходимо выполнить при строительстве некоторого сооружения.

Таблица 14.5

Этап	А	Б	В	Г	Д	Е	Ж	З	И	К	Л
Требуемое число дней	а	б	в	г	д	е	ж	з	и	к	л
Предшествующие этапы		А	А	Б	Г	Г	Г	В,Д	В,Г	В,Г	Е,Ж,З,И,К

Построить сетевой график, найти время выполнения проекта и критический путь (исходные данные приведены в табл. 14.6).

Таблица 14.6

Варианты	а	б	в	г	д	е	ж	з	и	к	л
1	1	2	2	4	2	2	1	1	1	1	3
2	2	3	1	5	3	1	1	2	2	1	4
3	1	3	2	5	2	1	2	1	3	2	5
4	2	4	1	6	3	4	2	2	2	3	5
5	1	4	1	7	3	2	1	3	1	1	5
6	2	5	4	8	4	6	3	4	3	4	6
7	1	7	2	10	2	5	2	3	4	2	6
8	3	6	5	9	5	4	3	3	5	3	6
9	1	3	1	8	4	3	2	3	2	1	5
10	1	5	1	10	2	5	1	4	1	2	7
11	2	8	2	14	6	7	2	3	2	1	12
12	3	10	3	18	5	6	2	2	3	2	10
13	1	9	2	20	10	7	2	5	5	3	7
14	4	12	4	21	8	4	4	2	2	2	10
15	2	14	3	24	14	8	3	4	7	4	12
16	1	2	2	3	3	5	2	3	5	3	10
17	1	3	3	5	3	3	2	2	2	2	4
18	3	4	2	6	4	2	2	3	3	2	5
19	2	4	3	6	3	2	3	2	4	3	6
20	3	5	2	7	4	5	3	3	3	4	6
21	2	5	2	8	4	3	2	4	2	2	6
22	3	6	5	9	5	7	4	5	4	5	7
23	2	8	3	11	3	6	3	4	5	3	7
24	4	7	6	10	6	4	4	4	6	4	7
25	2	10	3	18	9	8	3	5	6	4	8
26	5	10	5	20	10	5	5	3	3	3	10
27	3	15	4	25	15	9	4	5	8	5	11
28	2	10	3	15	7	8	3	4	3	2	10
29	2	3	3	4	4	5	3	4	6	4	11
30	2	5	2	10	3	4	2	5	2	2	8

14.4. Информация о строительстве электростанции задана перечнем работ АУ, последовательностью выполнения работ и их продолжительностью (табл. 14.7, 14.8). Построить сетевой график, найти минимальное время выполнения проекта и критический путь.

Таблица 14.7

Работы	Последовательность выполнения	Продол-жительность		Работы	Последовательность выполнения	Продол-жительность		Работы	Последовательность выполнения	Продол-жительность
А		а		З	В, Г, Д	з		П	Ж, З	п
Б		б		И	Г	и		Р	И, К	р
В		в		К	Ж, З	к		С	Р	с
Г		г		Л	Ж, З	л		Т	Н, П, Р	т
Д	А, Б	д		М	Е, Л	м		У	М, О	у
Е	А, Б	е		Н	Е, Л	н
Ж	А, Б	ж		О	Е, Л	о

Таблица 14.8

Варианты	1	2	3	4	5	6	7	8	9	10	11	12
Продолж. работ
а	2	1	1	3	7	6	3	4	7	2	5	3
б	3	5	3	5	2	4	8	5	9	3	8	2
в	5	4	2	6	4	2	1	3	3	2	3	7
г	4	2	5	1	3	5	2	1	1	6	6	4
д	3	5	2	4	3	1	4	2	7	3	5	6
е	1	2	3	4	3	5	4	2	3	1	6	3
ж	2	5	7	3	4	1	6	5	9	3	6	7
з	1	5	7	2	4	8	3	5	10	8	3	1
и	3	6	2	1	5	3	2	7	4	6	2	3
к	1	2	3	4	6	5	7	6	4	3	2	1
л	3	2	1	4	3	2	1	5	4	3	1	2
м	6	2	7	10	3	8	5	4	9	2	1	7
н	3	5	4	2	1	3	4	7	2	5	4	3
о	9	7	8	1	6	2	9	3	5	4	3	2
п	5	4	3	2	1	5	4	3	2	1	5	4
р	1	2	3	5	7	9	7	5	3	1	2	4
с	9	1	8	7	6	4	5	3	2	7	4	5
т	6	4	3	2	5	3	7	2	1	6	3	2
у	4	9	10	7	5	2	1	3	5	4	2	1
Варианты	13	14	15	16	17	18	19	20	21	22	23	24
Продолж. работ
а	3	1	2	4	8	7	4	5	8	3	6	4
б	2	4	2	4	1	5	7	6	10	4	7	3
в	4	3	1	5	4	2	2	3	4	3	4	8
г	5	1	4	2	4	5	2	3	1	5	6	4
д	3	4	3	5	2	3	4	3	8	4	5	7
е	2	2	3	5	4	6	5	3	3	2	4	5
ж	3	6	4	4	2	5	6	10	9	4	2	1
з	2	6	6	3	5	7	4	6	10	7	4	2
и	4	5	3	2	6	4	3	8	5	7	3	4
к	2	3	4	5	7	6	8	7	5	5	4	2
л	4	3	2	5	4	3	2	6	5	4	2	3
м	7	3	8	11	4	9	6	5	10	3	2	8
н	4	6	5	3	2	4	5	8	3	6	5	4
о	10	8	9	2	7	3	10	4	6	5	4	3
п	6	5	4	3	2	6	5	4	3	2	3	5
р	2	3	4	6	8	10	8	6	4	2	4	6
с	10	2	9	8	7	5	6	4	3	8	5	6
т	7	5	4	3	6	4	8	3	2	7	4	3
у	5	10	11	8	6	4	3	5	7	4	3	2
Варианты	25	26	27	28	29	30	31	32	33	34	35	36
Продолж. работ
а	4	3	3	5	9	8	4	6	9	4	6	3
б	3	5	3	5	2	6	8	5	11	5	6	4
в	5	4	2	6	6	3	2	4	5	4	6	8
г	6	2	5	3	5	6	3	4	2	6	7	5
д	4	6	5	6	3	5	4	4	9	5	6	8
е	3	2	4	6	5	7	5	4	3	4	6	8
ж	4	7	5	4	3	6	7	11	10	5	3	2
з	3	7	6	4	6	8	5	6	11	7	5	2
и	5	6	4	3	7	5	3	8	6	9	4	6
к	2	4	5	7	9	7	9	7	5	6	5	4
л	6	4	3	7	6	5	4	6	7	5	3	4
м	7	4	9	12	5	10	7	6	11	4	3	9
н	6	8	7	5	4	6	7	9	4	6	5	5
о	9	8	7	2	6	4	10	5	6	5	4	3
п	6	4	3	3	4	7	6	5	4	3	4	6
р	3	4	5	7	9	11	9	7	5	3	4	7
с	10	3	9	7	6	7	5	4	9	6	7	8
т	8	6	4	3	7	5	9	4	3	8	5	3
у	7	12	15	9	8	6	5	7	9	6	5	4