- •Глава 5. Транспортные задачи
- •5.1. Основные модели транспортных задач
- •5.1.1. Простейшая транспортная задача (т-задача)
- •5.1.2. Транспортная задача с ограниченными пропускными способностями (Td- задача)
- •5.1.3. Задачи с неоднородным грузом
- •5.1.4. Многоиндексные задачи
- •5.1.5. Транспортные задачи по критерию времени
- •5.2. Метод потенциалов
- •5.2.1. Построение начального плана перевозок
- •Правило северо-западного угла
- •Правило минимального элемента.
- •5.2.2. Переход от одного плана перевозок к другому
- •5.2.3. Признак оптимальности
- •5.2.4. Алгоритм метода потенциалов
- •5.2.5. Двойственная пара транспортных задач
- •5.3. Приведение открытой транспортной задачи к закрытой
- •5.4. Метод потенциалов для Td-задачи
- •5.5. Решение задачи по критерию времени
- •5.6. Транспортные задачи в сетевой постановке (транспортные сети)
- •5.7. Задания для самостоятельной работы
5.7. Задания для самостоятельной работы
I. Следующие Т-задачи решить методом потенциалов.
№1. №2.
bj ai |
10 |
20 |
20 |
10 |
|
bj ai |
80 |
30 |
50 |
40 |
10 |
10 |
15 |
15 |
8 |
|
70 |
8 |
7 |
4 |
7 |
20 |
40 |
10 |
30 |
5 |
|
40 |
3 |
5 |
6 |
4 |
10 |
35 |
25 |
40 |
10 |
|
20 |
9 |
2 |
5 |
3 |
№3. №4.
bj ai |
30 |
25 |
18 |
20 |
|
bj ai |
20 |
60 |
55 |
45 |
40 |
1 |
2 |
6 |
4 |
|
45 |
2 |
5 |
3 |
4 |
30 |
3 |
1 |
3 |
2 |
|
35 |
6 |
1 |
2 |
5 |
20 |
5 |
7 |
5 |
1 |
|
70 |
3 |
4 |
3 |
8 |
№5. №6.
bj ai |
120 |
40 |
60 |
80 |
|
bj ai |
20 |
18 |
44 |
75 |
180 |
2 |
3 |
4 |
3 |
|
40 |
1 |
7 |
2 |
5 |
60 |
5 |
3 |
1 |
2 |
|
30 |
3 |
8 |
4 |
1 |
80 |
2 |
1 |
4 |
2 |
|
50 |
6 |
3 |
5 |
3 |
№7. №8.
bj ai |
10 |
40 |
20 |
60 |
|
bj ai |
15 |
40 |
20 |
50 |
30 |
2 |
7 |
3 |
6 |
|
48 |
4 |
7 |
2 |
5 |
70 |
9 |
4 |
5 |
7 |
|
25 |
3 |
5 |
8 |
6 |
50 |
5 |
7 |
6 |
2 |
|
30 |
6 |
10 |
9 |
7 |
№9. №10.
bj ai |
2 |
3 |
3 |
16 |
|
bj ai |
10 |
2 |
30 |
40 |
68 |
18 |
2 |
9 |
7 |
|
45 |
5 |
4 |
0 |
5 |
55 |
30 |
4 |
1 |
55 |
|
20 |
3 |
5 |
3 |
0 |
40 |
6 |
4 |
8 |
3 |
|
35 |
0 |
6 |
7 |
6 |
№11. №12.
bj ai |
75 |
80 |
60 |
85 |
|
bj ai |
45 |
45 |
100 |
160 |
100 |
6 |
7 |
3 |
5 |
|
180 |
6 |
7 |
3 |
2 |
150 |
1 |
2 |
5 |
6 |
|
90 |
5 |
1 |
4 |
3 |
50 |
8 |
10 |
20 |
1 |
|
170 |
3 |
2 |
6 |
2 |
№13. №14.
bj ai |
25 |
30 |
40 |
15 |
|
bj ai |
35 |
80 |
25 |
70 |
20 |
1 |
3 |
3 |
8 |
|
30 |
1 |
9 |
7 |
2 |
20 |
8 |
6 |
2 |
6 |
|
40 |
3 |
1 |
5 |
5 |
40 |
7 |
7 |
3 |
8 |
|
70 |
6 |
8 |
3 |
4 |
45 |
5 |
2 |
4 |
5 |
|
60 |
2 |
3 |
1 |
3 |
№15. №16
bj ai |
5 |
15 |
15 |
10 |
|
bj ai |
35 |
40 |
40 |
30 |
15 |
10 |
0 |
20 |
11 |
|
40 |
3 |
2 |
4 |
1 |
25 |
12 |
7 |
9 |
20 |
|
50 |
2 |
3 |
1 |
5 |
5 |
0 |
14 |
6 |
18 |
|
30 |
3 |
2 |
4 |
4 |
№17. №18.
bj ai |
30 |
60 |
45 |
25 |
|
bj ai |
400 |
800 |
200 |
500 |
50 |
4 |
7 |
1 |
3 |
|
500 |
3 |
5 |
6 |
1 |
70 |
5 |
9 |
6 |
2 |
|
700 |
5 |
1 |
3 |
3 |
40 |
8 |
2 |
9 |
11 |
|
600 |
4 |
5 |
8 |
1 |
№19. №20.
bj ai |
80 |
80 |
60 |
80 |
|
bj ai |
20 |
34 |
16 |
10 |
25 |
160 |
5 |
4 |
3 |
4 |
|
40 |
2 |
6 |
3 |
4 |
8 |
140 |
3 |
2 |
5 |
5 |
|
30 |
1 |
5 |
6 |
9 |
7 |
60 |
1 |
6 |
3 |
2 |
|
35 |
3 |
4 |
1 |
6 |
10 |
№21. №22.
bj ai |
80 |
60 |
170 |
80 |
|
bj ai |
180 |
110 |
60 |
40 |
110 |
8 |
1 |
9 |
7 |
|
175 |
9 |
7 |
5 |
3 |
190 |
4 |
6 |
2 |
12 |
|
125 |
1 |
2 |
4 |
6 |
90 |
3 |
5 |
8 |
9 |
|
140 |
8 |
10 |
12 |
1 |
№23. №24.
bj ai |
70 |
90 |
60 |
|
bj ai |
25 |
30 |
40 |
15 |
20 |
1 |
5 |
3 |
|
10 |
1 |
3 |
3 |
8 |
40 |
1 |
2 |
4 |
|
20 |
8 |
6 |
2 |
6 |
50 |
5 |
5 |
1 |
|
35 |
4 |
7 |
7 |
3 |
40 |
3 |
5 |
2 |
|
45 |
5 |
2 |
4 |
5 |
№25. №26. №27.
bj ai |
27 |
10 |
30 |
|
bj ai |
18 |
37 |
50 |
|
bj ai |
28 |
37 |
50 |
15 |
8 |
5 |
10 |
|
60 |
4 |
7 |
3 |
|
35 |
4 |
7 |
3 |
35 |
6 |
7 |
9 |
|
42 |
9 |
5 |
13 |
|
42 |
9 |
5 |
13 |
20 |
10 |
12 |
8 |
|
20 |
11 |
8 |
9 |
|
20 |
11 |
8 |
9 |
10 |
5 |
3 |
4 |
|
75 |
7 |
12 |
20 |
|
75 |
7 |
12 |
20 |
II.Методом потенциалов решитьTd-задачи.
№1 | ||||||||||
Сij |
dij | |||||||||
b ai |
5 |
15 |
35 |
15 |
40 | |||||
30 |
18 |
3 |
8 |
5 |
14 |
15 |
7 |
21 |
22 |
6 |
50 |
5 |
19 |
12 |
5 |
9 |
2 |
6 |
18 |
5 |
25 |
20 |
17 |
20 |
11 |
10 |
9 |
3 |
4 |
1 |
7 |
8 |
10 |
2 |
15 |
12 |
13 |
6 |
9 |
5 |
3 |
3 |
7 |
№2 |
№3 | ||||||||||||||||||||
Сij |
dij |
Сij |
dij | ||||||||||||||||||
b ai |
40 |
40 |
20 |
10 |
30 |
b ai |
11 |
10 |
14 |
16 |
17 | ||||||||||
14 |
10 |
16 |
3 |
8 |
15 |
8 |
2 |
3 |
2 |
2 |
10 |
17 |
18 |
7 |
20 |
2 |
7 |
10 |
4 |
5 |
8 |
25 |
3 |
14 |
12 |
9 |
1 |
15 |
3 |
3 |
4 |
5 |
13 |
5 |
16 |
3 |
9 |
19 |
5 |
4 |
6 |
5 |
9 |
56 |
2 |
20 |
4 |
11 |
5 |
10 |
20 |
15 |
5 |
10 |
28 |
15 |
14 |
17 |
7 |
5 |
11 |
6 |
12 |
8 |
7 |
45 |
7 |
17 |
13 |
8 |
15 |
11 |
20 |
7 |
4 |
21 |
17 |
11 |
15 |
9 |
8 |
16 |
3 |
2 |
1 |
6 |
10 |
№4 |
№5 | ||||||||||||||||||||
Сij |
dij |
Сij |
dij | ||||||||||||||||||
b ai |
13 |
37 |
26 |
91 |
24 |
b ai |
24 |
30 |
27 |
16 |
33 | ||||||||||
20 |
1 |
14 |
13 |
6 |
12 |
3 |
7 |
6 |
5 |
5 |
15 |
10 |
16 |
12 |
3 |
9 |
10 |
5 |
3 |
5 |
4 |
30 |
3 |
18 |
20 |
4 |
2 |
4 |
10 |
8 |
11 |
2 |
17 |
10 |
4 |
16 |
1 |
11 |
4 |
7 |
5 |
5 |
10 |
70 |
8 |
17 |
5 |
15 |
10 |
7 |
20 |
15 |
38 |
9 |
23 |
19 |
19 |
10 |
18 |
20 |
3 |
12 |
7 |
6 |
4 |
71 |
16 |
4 |
12 |
18 |
13 |
14 |
11 |
13 |
41 |
20 |
75 |
19 |
12 |
4 |
11 |
18 |
20 |
10 |
17 |
15 |
35 |
№6 |
№7 | ||||||||||||||||||||
Сij |
dij |
Сij |
dij | ||||||||||||||||||
b ai |
30 |
50 |
13 |
70 |
17 |
b ai |
11 |
10 |
14 |
16 |
17 | ||||||||||
62 |
5 |
8 |
13 |
14 |
9 |
20 |
25 |
10 |
20 |
2 |
17 |
11 |
15 |
9 |
8 |
16 |
3 |
2 |
1 |
6 |
10 |
26 |
11 |
20 |
18 |
19 |
17 |
4 |
7 |
6 |
10 |
15 |
10 |
17 |
18 |
7 |
20 |
2 |
7 |
10 |
4 |
5 |
8 |
27 |
1 |
15 |
2 |
8 |
3 |
5 |
6 |
12 |
20 |
30 |
28 |
15 |
14 |
17 |
7 |
5 |
11 |
6 |
12 |
8 |
7 |
65 |
9 |
16 |
15 |
11 |
17 |
10 |
30 |
15 |
25 |
5 |
13 |
5 |
16 |
3 |
9 |
19 |
5 |
4 |
6 |
5 |
9 |
№8 |
№9 | ||||||||||||||||||||
Сij |
dij |
Сij |
dij | ||||||||||||||||||
b ai |
40 |
10 |
50 |
50 |
20 |
b ai |
30 |
35 |
35 |
45 |
25 | ||||||||||
60 |
20 |
5 |
4 |
5 |
14 |
14 |
5 |
20 |
25 |
13 |
30 |
9 |
10 |
12 |
7 |
1 |
4 |
10 |
15 |
8 |
10 |
50 |
2 |
19 |
20 |
4 |
5 |
15 |
19 |
22 |
4 |
12 |
70 |
4 |
16 |
9 |
19 |
10 |
21 |
20 |
23 |
16 |
15 |
40 |
8 |
9 |
6 |
19 |
1 |
15 |
6 |
8 |
5 |
10 |
50 |
17 |
20 |
11 |
1 |
12 |
10 |
5 |
8 |
25 |
12 |
20 |
20 |
7 |
15 |
6 |
11 |
2 |
14 |
7 |
23 |
20 |
20 |
14 |
13 |
15 |
7 |
8 |
5 |
4 |
6 |
7 |
10 |
№10 |
№11 | ||||||||||||||||||||
Сij |
dij |
Сij |
dij | ||||||||||||||||||
b ai |
75 |
10 |
20 |
40 |
30 |
b ai |
5 |
15 |
35 |
15 |
40 | ||||||||||
80 |
7 |
19 |
7 |
12 |
18 |
20 |
6 |
15 |
22 |
25 |
50 |
5 |
19 |
12 |
5 |
9 |
2 |
6 |
18 |
5 |
25 |
12 |
17 |
11 |
7 |
13 |
11 |
2 |
5 |
2 |
3 |
4 |
20 |
17 |
20 |
11 |
10 |
9 |
3 |
4 |
1 |
7 |
8 |
38 |
1 |
13 |
19 |
18 |
12 |
20 |
1 |
3 |
15 |
8 |
10 |
2 |
15 |
12 |
13 |
6 |
9 |
5 |
3 |
3 |
7 |
45 |
18 |
4 |
11 |
3 |
11 |
40 |
5 |
6 |
2 |
10 |
30 |
18 |
3 |
8 |
5 |
14 |
15 |
7 |
21 |
22 |
6 |
№12 |
№13 | ||||||||||||||||||||
Сij |
dij |
Сij |
dij | ||||||||||||||||||
b ai |
37 |
26 |
91 |
24 |
13 |
b ai |
45 |
38 |
40 |
28 |
34 | ||||||||||
20 |
14 |
13 |
6 |
12 |
1 |
7 |
6 |
5 |
5 |
3 |
20 |
3 |
17 |
6 |
19 |
2 |
5 |
7 |
6 |
5 |
4 |
30 |
18 |
20 |
4 |
2 |
3 |
10 |
8 |
11 |
2 |
4 |
40 |
1 |
15 |
7 |
6 |
1 |
20 |
3 |
20 |
4 |
2 |
70 |
17 |
5 |
15 |
10 |
8 |
20 |
15 |
38 |
9 |
7 |
52 |
5 |
13 |
8 |
11 |
17 |
24 |
13 |
7 |
11 |
8 |
71 |
4 |
12 |
18 |
13 |
16 |
11 |
13 |
41 |
20 |
14 |
73 |
18 |
13 |
17 |
1 |
8 |
9 |
21 |
16 |
13 |
25 |
№14 |
№15 | ||||||||||||||||||||
Сij |
dij |
Сij |
dij | ||||||||||||||||||
b ai |
10 |
50 |
40 |
50 |
20 |
b ai |
30 |
27 |
16 |
33 |
24 | ||||||||||
60 |
5 |
4 |
20 |
5 |
14 |
5 |
20 |
14 |
25 |
13 |
15 |
16 |
12 |
3 |
9 |
10 |
5 |
3 |
5 |
4 |
10 |
50 |
19 |
20 |
2 |
4 |
5 |
19 |
22 |
15 |
4 |
12 |
17 |
4 |
16 |
1 |
11 |
10 |
7 |
5 |
5 |
10 |
4 |
40 |
9 |
6 |
8 |
19 |
1 |
6 |
8 |
15 |
5 |
10 |
23 |
19 |
10 |
18 |
20 |
19 |
12 |
7 |
6 |
4 |
3 |
20 |
7 |
15 |
20 |
6 |
11 |
14 |
7 |
2 |
23 |
20 |
75 |
12 |
4 |
11 |
18 |
19 |
10 |
17 |
15 |
35 |
20 |
№16 |
№17 | ||||||||||||||||||||
Сij |
dij |
Сij |
dij | ||||||||||||||||||
b ai |
35 |
30 |
35 |
45 |
25 |
b ai |
17 |
33 |
38 |
21 |
22 | ||||||||||
30 |
10 |
9 |
12 |
7 |
1 |
10 |
4 |
15 |
8 |
10 |
48 |
8 |
12 |
6 |
12 |
5 |
20 |
19 |
17 |
3 |
6 |
70 |
16 |
4 |
9 |
19 |
10 |
20 |
21 |
23 |
16 |
15 |
27 |
3 |
1 |
12 |
2 |
19 |
10 |
14 |
30 |
18 |
7 |
50 |
20 |
17 |
11 |
1 |
12 |
5 |
10 |
8 |
25 |
12 |
46 |
6 |
3 |
3 |
1 |
18 |
18 |
16 |
11 |
13 |
17 |
20 |
13 |
14 |
15 |
7 |
8 |
4 |
5 |
6 |
7 |
10 |
10 |
5 |
3 |
20 |
7 |
25 |
9 |
1 |
16 |
5 |
11 |
№18 |
№19 | ||||||||||||||||||||
Сij |
dij |
Сij |
dij | ||||||||||||||||||
b ai |
13 |
26 |
91 |
24 |
37 |
b ai |
75 |
10 |
20 |
40 |
30 | ||||||||||
20 |
1 |
13 |
6 |
12 |
14 |
3 |
6 |
5 |
5 |
7 |
80 |
7 |
19 |
7 |
12 |
18 |
20 |
6 |
15 |
22 |
25 |
30 |
3 |
20 |
4 |
2 |
18 |
4 |
8 |
11 |
2 |
10 |
38 |
1 |
13 |
19 |
18 |
12 |
20 |
1 |
3 |
15 |
8 |
70 |
8 |
5 |
15 |
10 |
17 |
7 |
15 |
38 |
9 |
20 |
12 |
17 |
11 |
7 |
13 |
11 |
2 |
5 |
2 |
3 |
4 |
71 |
16 |
12 |
18 |
13 |
4 |
14 |
13 |
41 |
20 |
11 |
45 |
18 |
4 |
11 |
3 |
11 |
40 |
5 |
6 |
2 |
10 |
№20 |
№21 | ||||||||||||||||||||
Сij |
dij |
Сij |
dij | ||||||||||||||||||
b ai |
30 |
65 |
20 |
10 |
15 |
b ai |
15 |
30 |
65 |
20 |
10 | ||||||||||
50 |
10 |
2 |
5 |
10 |
14 |
35 |
14 |
10 |
5 |
15 |
50 |
14 |
10 |
2 |
5 |
10 |
15 |
35 |
14 |
10 |
5 |
20 |
5 |
4 |
11 |
3 |
11 |
4 |
20 |
12 |
18 |
8 |
20 |
11 |
5 |
4 |
11 |
3 |
8 |
4 |
20 |
12 |
18 |
30 |
8 |
12 |
1 |
18 |
9 |
7 |
32 |
20 |
14 |
10 |
30 |
9 |
8 |
12 |
1 |
18 |
10 |
7 |
32 |
20 |
14 |
40 |
4 |
9 |
17 |
18 |
1 |
4 |
16 |
20 |
17 |
8 |
40 |
1 |
4 |
9 |
17 |
18 |
8 |
4 |
16 |
20 |
17 |