11. Индивидуальные задания

Задание 1.

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

1. ,

2. ,

3. потребности 2Го пункта назначения должны удовлетворяться полностью.

1.		80	40	30
	60	2	4	3
	50	0	1	5
	20	2	1	3

3.		5	6	13
	8	4	4	3
	10	2	1	6
	2	3	2	4

5.		22	33	13
	38	4	2	3
	20	6	3	5
	5	3	1	4

7.		25	15	55
	30	0	1	2
	40	1	2	3
	15	2	3	1

9.		50	70	60
	65	1	2	3
	80	1	3	2
	15	2	1	4

11.		60	50	20
	80	2	4	2
	40	3	0	1
	20	1	5	3

13.		8	10	2
	5	4	4	3
	6	3	2	2
	13	5	6	4

15.		38	20	5
	22	4	2	3
	33	5	4	1
	13	3	5	4

17.		30	40	15
	25	0	1	2
	15	2	1	3
	55	2	3	1

19.		65	80	15
	50	3	1	2
	70	2	3	1
	60	2	1	4

2.		15	35	45
	25	6	0	3
	35	5	1	2
	15	4	2	1

4.		200	300	100
	240	2	2	1
	220	3	3	5
	70	4	3	2

6.		30	70	30
	45	3	4	1
	65	2	5	3
	10	1	3	2

8.		4	7	6
	6	3	2	4
	5	1	3	2
	3	2	1	3

10.		14	16	20
	23	1	4	3
	15	1	2	2
	9	2	3	1

12.		25	35	15
	15	6	0	4
	35	3	5	2
	45	1	2	1

14.		240	220	70
	200	2	2	4
	300	1	3	3
	100	1	5	2

16.		45	65	10
	30	2	3	1
	70	4	5	3
	30	1	3	2

18.		6	5	3
	4	3	2	2
	7	4	1	1
	6	6	2	3

20.		23	15	9
	14	1	4	2
	16	4	2	3
	20	3	2	1

Задание 2.

Решить транспортную задачу. Заданы мощности поставщиков (=1, 2, 3), емкости потребителей (=1, 2, 3) т матрица затрат времени перевозок единицы продукции от каждого поставщика каждому потребителю. Требуется найти план перевозок, при котором суммарные транспортные затраты времени наименьшие.

1.		40	120	70	20
	90	15	6	8	16
	65	6	9	10	4
	75	4	7	5	9

3.		16	20	12	12
	25	16	7	5	3
	25	5	6	4	20
	10	9	10	6	7

5.		19	31	10	12
	20	15	8	3	3
	40	2	4	2	17
	12	7	6	3	4

7.		30	48	17	25
	30	9	7	4	11
	45	5	3	2	4
	45	10	8	5	12

9.		17	43	25	10
	20	8	3	6	4
	45	4	2	5	11
	30	9	4	7	10

11.		14	20	30	6
	25	4	5	9	10
	33	2	3	3	9
	12	4	6	8	4

13.		17	21	8	18
	24	5	7	4	5
	18	4	8	3	10
	20	6	9	4	2

15.		10	17	18	6
	15	6	3	7	10
	18	4	2	9	3
	18	5	3	8	11

17.		20	40	30	50
	35	6	3	7	11
	25	3	2	4	9
	80	5	4	8	4

19.		25	49	21	15
	40	5	3	6	7
	47	2	1	2	9
	23	7	4	8	6

2.		25	40	35	70
	20	13	6	4	15
	90	5	9	3	7
	60	4	8	6	10

4.		20	22	8	6
	22	17	6	3	7
	18	8	4	2	10
	16	2	3	1	20

6.		14	20	22	24
	50	13	8	9	10
	18	3	4	5	2
	12	2	7	6	14

8.		18	40	2	4
	32	9	8	4	11
	15	8	7	3	4
	17	4	3	2	3

10.		12	19	9	15
	18	5	8	2	4
	22	8	9	4	10
	15	6	7	3	12

12.		10	12	20	20
	17	8	4	9	3
	30	6	3	7	9
	15	5	2	4	10

14.		20	42	37	10
	45	5	3	7	9
	40	3	2	3	11
	24	6	4	8	4

16.		9	31	20	16
	20	3	9	8	4
	44	4	6	7	12
	12	2	4	5	10

18.		20	44	16	20
	30	5	2	6	6
	45	2	1	3	10
	25	4	2	8	9

20.		21	3	32	27
	46	5	9	7	10
	32	4	6	5	11
	20	3	5	4	7

Задание 3.

Найти кратчайший путь от вершины до всех остальных вершин графа. Граф описывается перечнем всех своих дуг и их длинами . Дуга кратко обозначается парой чисел , , длина задаётся одним числом. Так, например, дуга обозначается парой чисел 3, 5 и т. п.

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

1 – 5

	0,1	0,2	0,3	1,4	1,6	2,4	2,5	3,5	3,6	4,7	4,8	5,4	5,8	6,8	7,8
1.	10	11	20	8	7	10	12	14	13	11	9	14	17	4	12
2.	20	6	17	12	11	8	13	9	11	21	18	16	14	9	8
3.	11	12	16	4	17	7	9	14	11	9	21	22	8	11	13
4.	16	15	14	13	11	15	9	7	18	23	11	7	18	12	11
5.	21	23	16	12	9	8	19	27	16	11	15	16	20	13	10

6 – 10

	0,1	0,2	0,3	1,4	1,5	2,4	2,5	2,6	3,6	4,7	4,8	5,7	5,8	6,8	7,8
6.	12	14	18	12	11	6	21	15	19	23	16	15	12	11	8
7.	10	12	4	9	11	13	7	12	14	18	21	23	16	11	15
8.	17	14	11	12	8	7	12	14	13	9	14	20	17	21	10
9.	27	19	18	12	16	23	21	16	18	13	10	8	11	19	20
10.	9	21	8	11	13	25	27	17	23	16	19	14	13	16	8

11 – 15

	0,1	0,2	0,3	1,4	2,1	2,5	3,2	3,6	4,7	5,1	5,6	5,7	5,8	6,8	7,8
11.	16	23	17	21	19	8	11	13	18	19	20	22	24	16	11
12.	12	11	16	23	18	17	19	24	19	14	13	21	13	11	12
13.	14	13	11	9	17	19	8	15	13	21	16	9	7	15	8
14.	17	8	7	12	14	13	27	18	15	13	11	8	12	10	15
15.	11	13	17	15	21	10	8	19	25	21	13	14	11	8	6

16 – 20

	0,1	0,2	0,3	1,2	1,6	2,5	2,7	3,4	4,8	5,4	5,8	6,2	6,5	6,7	7,8
16.	16	14	17	15	11	18	21	25	19	17	21	11	19	15	16
17.	27	18	12	19	11	13	15	14	6	21	13	8	9	11	17
18.	16	11	13	15	21	14	23	25	18	15	11	15	14	19	8
19.	17	11	12	13	21	6	8	16	14	9	10	23	9	17	21
20.	19	9	7	18	23	16	15	17	4	12	11	13	10	15	14

Задание 4.

В задачах 1 – 20 составить сетевой график и определять минимальное время (в днях) выполнения производственного задания. Проследить длиннейшую технологическую цепочку и в двух-трех случаях указать, какие работы и на сколько могут быть ускорены для сокращения времени выполнения всего задания. Продолжительности работ и последовательность их выполнения заданы в таблице (для каждой работы указано, после окончания каких работ может быть начато её выполнение). Вместо названий работы задаются условно их номерами.

Работа	1	2	3	4	5	6	7	8	9	10
Срок	10	28	25	24	27	20	30	35	30	26
После работ	4	4	-	3	3	1,5	3	7	6, 8	6, 8

Работа	11	12	13	14	15	16	17	18	19	20
Срок	30	20	25	15	40	25	19	25	16	30
После работ	7	2, 9	10,12	6,11	10,12	14,15	5, 7	15,16	11	17,18

Работа	1	2	3	4	5	6	7	8	9	10
Срок	9	29	23	25	26	18	31	34	32	25
После работ	5	7, 6	-	-	-	5	3	5	4, 8	3

Работа	11	12	13	14	15	16	17	18	19	20
Срок	30	20	26	15	35	24	20	25	15	30
После работ	9	9	10,12	1,11,16	13,14	2,10	6, 7	1	17,18	15,19

Работа	1	2	3	4	5	6	7	8	9	10
Срок	15	15	25	25	20	20	30	30	25	20
После работ	4	4	-	3	3	1, 3	3	7	5, 8	6, 8

Работа	11	12	13	14	15	16	17	18	19	20
Срок	25	25	20	20	30	30	20	20	25	20
После работ	7	2, 9	10,12	6,11	13,14	6,11	12,14	16,17	10,18	15,19

Работа	1	2	3	4	5	6	7	8	9	10
Срок	15	30	25	26	28	20	28	35	30	20
После работ	-	1	-	5	1	2	2, 3	3	4, 7	6, 8

Работа	11	12	13	14	15	16	17	18	19	20
Срок	30	20	24	17	38	22	21	26	15	27
После работ	6, 8	7	9,11	10,13	4, 7	10,13	15,16	12,17	14,18	9,11

Работа	1	2	3	4	5	6	7	8	9	10
Срок	28	10	24	25	20	27	35	30	26	30
После работ	-	3,5,7	-	2,5,7	-	5,11	-	2,4,7	4	4

Работа	11	12	13	14	15	16	17	18	19	20
Срок	20	30	15	25	40	15	19	26	30	16
После работ	12,14	1	5,11	1	8,9,13	4	10,16	1	15,18	17,19

Работа	1	2	3	4	5	6	7	8	9	10
Срок	10	28	25	24	27	20	30	35	30	26
После работ	-	1	1	1	-	-	2	2	3, 7	8,9,14

Работа	11	12	13	14	15	16	17	18	19	20
Срок	30	20	25	15	40	25	19	25	16	30
После работ	4, 5	4, 5	6,12	3,7	14,16	11,13	18,19	11,13	6,12	11,13

Работа	1	2	3	4	5	6	7	8	9	10
Срок	45	48	46	50	49	44	52	43	47	51
После работ	-	1	1	1	1	3, 8	4, 6	2	3, 8	2

Работа	11	12	13	14	15	16	17	18	19	20
Срок	45	50	48	46	49	52	45	50	53	49
После работ	4, 6	5	7,9,10	11,12	2	10	15,16	15,16	13,14,18	17,19

Работа	1	2	3	4	5	6	7	8	9	10
Срок	40	45	50	48	52	42	55	40	45	50
После работ	8	8	2	1,10	-	5	6	7	8	5

Работа	11	12	13	14	15	16	17	18	19	20
Срок	44	48	51	47	51	50	46	52	51	43
После работ	1	2, 9	3, 12	4, 11	14	12	16	4, 17	15,16	13,19

Работа	1	2	3	4	5	6	7	8	9	10
Срок	40	50	45	52	44	34	52	33	57	51
После работ	5, 9	3	-	1	2, 6	-	6, 8	4	-	4, 15

Работа	11	12	13	14	15	16	17	18	19	20
Срок	43	56	46	48	51	53	42	49	55	40
После работ	10, 12	1	2, 16	6	9, 14	12	7	17	3	9, 19

10.

Работа	1	2	3	4	5	6	7	8	9	10
Срок	20	30	18	19	45	14	26	19	32	29
После работ	-	-	-	1, 2	3, 4	7, 10	5	-	6	-

Работа	11	12	13	14	15	16	17	18	19	20
Срок	37	16	25	27	41	37	38	48	39	40
После работ	8, 9	10,11	12,16	13	8, 17	8	1, 14	-	15	15, 18

11.

Работа	1	2	3	4	5	6	7	8	9	10
Срок	21	29	19	20	44	15	25	20	30	31
После работ	-	4	2	-	-	3, 5	1, 4	6, 10	11	3

Работа	11	12	13	14	15	16	17	18	19	20
Срок	35	17	25	27	40	38	41	46	39	42
После работ	7, 10	9	12	12	13,14	11,15	13	8	10	16,18,19

12.

Работа	1	2	3	4	5	6	7	8	9	10
Срок	22	32	20	21	47	16	30	21	34	31
После работ	-	-	1	2, 3	1, 8	4, 9	-	3	7	11,14

Работа	11	12	13	14	15	16	17	18	19	20
Срок	39	18	27	29	43	39	40	50	41	42
После работ	2, 8	10	-	13,15	6	14	13	12,17	12	16,17

13.

Работа	1	2	3	4	5	6	7	8	9	10
Срок	18	28	16	17	43	12	26	17	30	27
После работ	2	-	-	-	3	9	3, 6	1, 5	4, 8	3

Работа	11	12	13	14	15	16	17	18	19	20
Срок	35	14	23	25	39	35	36	46	37	38
После работ	4	5, 16	10	11	14	-	16	7	4	16

14.

Работа	1	2	3	4	5	6	7	8	9	10
Срок	20	30	18	19	45	14	28	19	32	29
После работ	2	-	1	-	3	2, 4	5, 10	9	1, 14	6, 8

Работа	11	12	13	14	15	16	17	18	19	20
Срок	37	16	25	27	41	37	38	48	39	40
После работ	6, 9	10,14	14	-	14,16	4	15,19	17	16	18

15.

Работа	1	2	3	4	5	6	7	8	9	10
Срок	19	31	17	20	44	15	27	20	31	30
После работ	-	-	1	1	2	3	4, 5	6, 7	8	-

Работа	11	12	13	14	15	16	17	18	19	20
Срок	36	17	24	28	40	38	37	49	38	41
После работ	10	9, 14	11	11	13	10,18	14	13	12,18	10,17

16.

Работа	1	2	3	4	5	6	7	8	9	10
Срок	22	28	20	17	47	12	30	17	34	27
После работ	-	-	1	1	1	2	2	2, 3	2, 4	4, 5

Работа	11	12	13	14	15	16	17	18	19	20
Срок	39	14	27	25	43	35	40	46	41	38
После работ	8, 9	7, 16	9	9, 10	11	-	14,16	16	17	18,19

17.

Работа	1	2	3	4	5	6	7	8	9	10
Срок	21	29	19	18	46	13	29	20	31	30
После работ	-	-	-	3	3	2, 3	5, 6	1, 6	4,7,8	7

Работа	11	12	13	14	15	16	17	18	19	20
Срок	38	15	26	26	42	36	39	47	40	39
После работ	8	8	10,12	9,11	5	6	12,13	14	14	17,19

18.

Работа	1	2	3	4	5	6	7	8	9	10
Срок	18	32	16	21	43	16	26	21	30	31
После работ	19	8	8, 15	7	-	8, 12	-	11	-	1

Работа	11	12	13	14	15	16	17	18	19	20
Срок	35	18	23	29	39	39	36	50	37	42
После работ	4	9, 11	2,17,20	10,16	5, 7	1	6	10	3	5, 14

19.

Работа	1	2	3	4	5	6	7	8	9	10
Срок	20	30	17	19	45	15	28	19	31	29
После работ	4,10	18	-	3,15	7,11	17	2	11,17	12,17	9,14

Работа	11	12	13	14	15	16	17	18	19	20
Срок	37	18	25	27	40	37	38	49	39	40
После работ	4, 19	3	10	12	-	13	-	15	20	17,18

20.

Работа	1	2	3	4	5	6	7	8	9	10
Срок	40	39	48	38	37	41	27	25	16	37
После работ	14,18	18	-	20	13	-	4	10	4, 10	14,17

Работа	11	12	13	14	15	16	17	18	19	20
Срок	29	32	19	28	14	45	19	18	30	20
После работ	12	13,15	2, 16	3	2, 10	3, 19	6	-	-	17,19

Задание 5.

Найти оптимальные стратегии и цену игры. Сделать проверку, если дана матрица игры .

< Предыдущая