3. Транспортная задача

Исходные данные транспортной задачи приведены в таблице.

Требуется:

1. Определить тип задачи.

2. Найти начальное опорное решение методом северо-западного угла и минимального элемента.

3. Лучшее решение проверить на оптимальность методом потенциалов.

Вариант 1.

	B1	B2	B3	B4	ai
A1 A2 A3 A4	20 8 3 4	22 14 25 9	10 7 23 29	7 6 8 5	220 180 210 390
bj	130	80	200	350

Вариант 2.

	B1	B2	B3	B4	ai
A1 A2 A3 A4	9 26 10 14	19 15 12 6	24 4 6 9	20 7 5 10	180 320 250 140
bj	500	130	160	220

Вариант 3.

	B1	B2	B3	B4	ai
A1 A2 A3 A4	7 8 12 5	17 10 6 7	5 6 7 9	2 9 4 15	500 400 210 80
bj	400	120	270	500

Вариант 4.

	B1	B2	B3	B4	ai
A1 A2 A3 A4	7 21 5 6	20 15 13 4	25 7 7 24	18 8 6 10	120 325 110 215
bj	360	220	130	330

Вариант 5.

	B1	B2	B3	B4	ai
A1 A2 A3 A4	6 11 15 19	9 21 17 20	12 15 8 16	8 9 7 8	500 480 130 90
bj	450	120	260	510

Вариант 6.

	B1	B2	B3	B4	ai
A1 A2 A3 A4	10 12 9 11	12 6 8 13	18 22 5 16	7 21 8 22	120 325 200 315
bj	360	225	180	250

Вариант 7.

	B1	B2	B3	B4	ai
A1 A2 A3 A4	2 3 5 4	11 17 11 17	16 20 17 21	8 9 5 9	400 300 180 280
bj	200	180	450	310

Вариант 8.

	B1	B2	B3	B4	ai
A1 A2 A3 A4	3 7 4 2	9 5 7 6	4 3 4 10	6 8 11 12	30 25 18 10
bj	12	40	25	30

Вариант 9.

	B1	B2	B3	B4	ai
A1 A2 A3 A4	25 20 21 18	16 28 14 17	22 19 15 10	10 7 9 20	400 360 180 280
bj	250	480	340	260

Вариант 10.

	B1	B2	B3	B4	ai
A1 A2 A3 A4	10 11 7 4	12 9 5 8	8 7 8 12	14 13 10 18	390 410 360 240
bj	600	220	280	300

Вариант 11.

	B1	B2	B3	B4	ai
A1 A2 A3 A4	2 7 9 11	4 6 4 9	8 3 5 4	11 1 14 15	30 46 26 18
bj	10	25	16	12

Вариант 12.

	B1	B2	B3	B4	ai
A1 A2 A3 A4	8 26 7 11	22 17 15 10	24 14 3 7	18 8 7 3	170 300 250 150
bj

Вариант 13.

	B1	B2	B3	B4	ai
A1 A2 A3 A4	12 8 6 9	13 10 9 13	32 23 15 21	22 25 21 28	100 70 85 120
bj	104	30	45	75

Вариант 14.

	B1	B2	B3	B4	ai
A1 A2 A3 A4	21 17 3 2	11 7 4 9	8 11 9 4	25 23 10 15	220 200 350 215
bj	150	120	220	420

Вариант 15.

	B1	B2	B3	B4	ai
A1 A2 A3 A4	12 6 4 3	2 5 8 1	1 2 4 7	5 7 9 2	600 900 360 250
bj	200	100	600	310

Вариант 16.

	B1	B2	B3	B4	ai
A1 A2 A3 A4	9 27 9 6	22 15 7 3	20 7 15 9	18 5 3 13	290 410 360 230
bj	600	230	290	310

Вариант 17.

	B1	B2	B3	B4	ai
A1 A2 A3 A4	8 9 7 18	20 25 19 12	23 5 6 11	18 2 4 8	620 600 250 150
bj	440	100	250	480

Вариант 18.

	B1	B2	B3	B4	ai
A1 A2 A3 A4	3 18 7 7	12 6 9 5	4 3 10 4	8 15 12 13	250 650 550 180
bj	400	450	850	550

Вариант 19.

	B1	B2	B3	B4	ai
A1 A2 A3 A4	3 7 10 12	7 4 15 20	4 2 4 7	10 9 8 4	70 110 305 65
bj	140	95	85	280

Вариант 20.

	B1	B2	B3	B4	ai
A1 A2 A3 A4	6 3 6 8	23 16 12 13	7 25 19 24	16 9 6 28	230 260 135 100
bj	120	150	120	265

Вариант 21.

	B1	B2	B3	B4	ai
A1 A2 A3 A4	15 5 9 11	26 14 6 5	12 9 16 21	17 20 18 10	200 150 130 180
bj	100	110	170	120

Вариант 22.

	B1	B2	B3	B4	ai
A1 A2 A3 A4	7 12 15 21	20 29 25 17	16 11 7 6	8 9 5 3	800 120 200 110
bj	100	800	150	220

Вариант 23.

	B1	B2	B3	B4	ai
A1 A2 A3 A4	13 8 11 18	16 14 5 4	7 9 10 6	12 17 9 20	410 190 300 200
bj	380	280	360	180

Вариант 24.

	B1	B2	B3	B4	ai
A1 A2 A3 A4	5 7 2 5	7 1 3 10	4 3 6 7	2 1 8 3	200 225 100 100
bj	130	80	190	100

Вариант 25.

	B1	B2	B3	B4	ai
A1 A2 A3 A4	5 4 7 3	8 2 3 6	7 2 5 2	10 5 9 4	450 200 250 100
bj	125	325	250	110

Вариант 26.

	B1	B2	B3	B4	ai
A1 A2 A3 A4	3 2 7 7	12 4 14 10	9 11 12 8	1 2 5 11	350 330 270 210
bj	170	220	150	180

Вариант 27.

	B1	B2	B3	B4	ai
A1 A2 A3 A4	20 27 26 18	10 19 17 22	13 20 19 23	13 16 21 20	200 300 250 210
bj	150	120	135	230

Вариант 28.

	B1	B2	B3	B4	ai
A1 A2 A3 A4	22 19 30 30	14 17 30 36	16 26 31 41	20 30 39 17	350 200 300 130
bj	140	200	195	145

Вариант 29.

	B1	B2	B3	B4	ai
A1 A2 A3 A4	10 9 14 15	15 8 8 10	18 12 9 11	19 15 10 9	230 130 135 210
bj	150	120	135	135

Вариант 30.

	B1	B2	B3	B4	ai
A1 A2 A3 A4	11 8 15 7	13 9 12 8	10 10 13 9	21 15 11 15	150 210 320 250
bj	130	190	270	140

4. Теория графов

Решить задачу коммивояжера методами ближайшего соседа и ветвей и границ.

A B C D E F G

1 A ∞ 31 66 28 84 45 60

2

1.

B 31 ∞ 9 45 86 41 90

3 C 66 9 ∞ 56 85 23 45

4 D 28 45 56 ∞ 46 85 26

5 E 84 86 85 46 ∞ 71 64

6 F 45 41 23 85 71 ∞ 55

7G 60 90 45 26 64 55 ∞

A B C D E F G

8 A ∞ 26 86 42 15 36 10

9 B 26 ∞ 45 86 21 93 45

1

2.

0C 86 45 ∞ 20 58 46 31

11 D 42 86 20 ∞ 54 26 84

12 E 15 21 58 54 ∞ 23 45

13 F 36 93 46 26 23 ∞ 29

14 G 10 45 31 84 45 29 ∞

A B C D E F G

15 A ∞ 46 85 23 75 81 68

16 B 46 ∞ 68 15 64 57 20

1

3.

7 C 85 68 ∞ 19 67 51 27

18 D 23 15 19 ∞ 46 51 23

19 E 75 64 67 46 ∞ 24 29

20 F 81 57 51 51 24 ∞ 52

21 G 68 20 27 23 29 52 ∞

A B C D E F G

22 A ∞ 68 42 15 20 25 42

2

4.

3 B 68 ∞ 26 58 74 15 13

24 C 42 26 ∞ 68 52 14 12

25 D 15 58 68 ∞ 18 27 19

26 E 20 74 52 18 ∞ 47 31

27 F 25 15 14 27 47 ∞ 20

28 G 42 13 12 19 31 20 ∞

A B C D E F G

29 A ∞ 36 25 74 85 12 90

30 B 36 ∞ 23 54 68 12 23

3

5.

1 C 25 23 ∞ 23 12 45 78

32 D 74 54 23 ∞ 23 50 47

33 E 85 68 12 23 ∞ 15 26

34 F 12 12 45 50 15 ∞ 20

35 G 90 23 78 47 26 20 ∞

A B C D E F G

1 A ∞ 31 66 28 84 45 60

2

6.

B 31 ∞ 9 4576 41 90

3 C 46 9 ∞ 56 85 23 45

4 D 28 45 56 ∞ 46 85 26

5 E 84 86 85 46 ∞ 71 64

6 F 45 41 23 85 71 ∞ 55

7G 60 90 4516 64 55 ∞

A B C D E F G

8 A ∞ 26 86 42 15 36 10

9 B 26 ∞ 45 86 23 93 45

1

7.

0 C 86 45 ∞ 20 58 46 31

11 D 42 86 20 ∞ 54 26 84

12 E 14 21 58 54 ∞ 23 47

13 F 36 93 46 26 23 ∞ 29

14 G 10 45 31 84 45 29 ∞

A B C D E F G

15 A ∞ 46 85 23 75 81 68

16 B 46 ∞ 68 15 64 37 20

1

8.

7 C 85 68 ∞ 19 67 51 27

18 D 23 15 19 ∞ 46 51 23

19 E 71 64 67 46 ∞ 24 29

20 F 81 57 51 51 24 ∞ 52

21 G 68 20 27 13 29 52 ∞

A B C D E F G

22 A ∞ 68 42 15 20 25 42

2

9.

3 B 68 ∞ 26 58 74 15 13

24 C 42 26 ∞ 68 52 14 12

25 D 15 48 68 ∞ 18 27 19

26 E 20 74 52 18 ∞ 47 31

27 F 25 15 14 67 47 ∞ 20

28 G 12 13 12 19 31 20 ∞

A B C D E F G

29 A ∞ 36 65 74 85 12 90

30 B 36 ∞ 23 54 68 32 23

3

10.

1 C 25 23 ∞ 23 12 45 78

32 D 74 54 23 ∞ 23 50 47

33 E 75 68 12 23 ∞ 15 26

34 F 12 12 45 50 15 ∞ 20

35 G 90 23 78 27 26 20 ∞

5