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

1. ТРАНСПОРТНАЯ ЗАДАЧА

Семинар 1:
ТРАНСПОРТНАЯ ЗАДАЧА
1

2. Постановка задачи

Имеется
m поставщиков A1 , A2, …, Am и n
потребителей B1 , B2, …, Bn некоторого груза.
Для каждого поставщика и потребителя
заданы запасы ai ≥ 0, i = 1, 2, …, m и объем
потребления bj ≥ 0, j = 1, 2, …, n.
Известна стоимость перевозки единицы
груза сij ≥ 0 от i-го поставщика к j-му
потребителю.
Требуется найти объемы всех перевозок xij
от i-го поставщика к j-му потребителю, при
которых общая стоимость минимальна.
2

3. Математическая постановка задачи

Пусть
X = (xij) – m×n матрица, где
xij – объем перевозок от i-го поставщика
к j-му потребителю.
Общие затраты на перевозку груза
определяются функцией:
m
n
z ( X ) cij xij
i 1 j 1
3

4.

Математическая
постановка
транспортной задачи определяется задачей
линейного программирования:
m
n
z ( X ) cij xij min
i 1 j 1
при условиях
m
x
i 1
ij
b j , j 1,..., n
ij
ai , i 1,..., m
n
x
j 1
xij 0
4

5.

Решение
X = (xij) транспортной задачи,
удовлетворяющее условиям и имеющее не
более m+n–1 занятой клетки , будем называть
опорным планом транспортной задачи.
Закрытая модель: суммарные запасы
поставщиков равны суммарным запросам
потребителей, т.е.
m
n
a b
i 1
i
j 1
Открытая
m
модель:
n
a b
i 1
i
j
j 1
j
5

6. Задача 1

Решите транспортную задачу методом
потенциалов. В ответе укажите
минимальную стоимость всех перевозок.
B1
B2
B3
B4
ai
A1
1
11
3
13
140
A2
12
4
8
2
160
A3
3
5
14
6
100
bj
80
40
150
130
6

7. Задача 1

Решите транспортную задачу методом
потенциалов. В ответе укажите
минимальную стоимость всех перевозок.
B1
B2
B3
B4
ai
A1
1
11
3
13
140
A2
12
4
8
2
160
A3
3
5
14
6
100
bj
80
40
150
130
400
400
7

8. Задача 1

Решите транспортную задачу методом
потенциалов. В ответе укажите
минимальную стоимость всех перевозок.
B1
B2
B3
B4
ai
A1
1
11
3
13
140
A2
12
4
8
2
160
A3
3
5
14
6
100
bj
80
40
150
130
400
400
400
8

9.

1. Метод «северо-западного угла»
B1
A1
B2
1
80
11
40
A2
12
A3
3
bj
B3
B4
3
13
8
2
20
4
130
5
30
14
6
100
80
ai
40
150
130
140
160
100
400
9

10.

1. Метод «северо-западного угла»
B1
A1
B2
1
80
11
40
A2
12
A3
3
bj
B3
B4
3
13
8
2
20
4
130
5
30
14
6
100
80
Начальный опорный план:
ai
40
150
130
140
160
100
400
80 40 20 0
X 0 0 130 30
0 0 0 100
z(X) = 1·80 + 11·40 + 3·20 + 8·130 + 2·30 + 6·100 = 2280
10

11.

2. Метод наименьшей стоимости
B1
A1
B3
B4
ai
1
11
3
13
12
4
8
2
3
5
14
6
80
A2
A3
bj
B2
80
40
150
130
140
160
100
400
11

12.

2. Метод наименьшей стоимости
B1
A1
B3
B4
ai
1
11
3
13
12
4
8
2
80
A2
130
3
A3
bj
B2
80
5
40
14
150
6
130
140
160
100
400
12

13.

2. Метод наименьшей стоимости
B1
A1
1
B3
11
B4
ai
3
13
8
2
60
80
12
A2
4
130
3
A3
bj
B2
80
5
40
14
150
6
130
140
160
100
400
13

14.

2. Метод наименьшей стоимости
B1
A1
80
1
B3
11
B4
ai
3
13
8
2
60
12
A2
4
130
3
A3
bj
B2
80
5
40
14
150
6
130
140
160
100
400
14

15.

2. Метод наименьшей стоимости
B1
A1
80
1
B3
11
B4
3
13
4
8
2
30
130
3
A3
80
ai
60
12
A2
bj
B2
5
40
14
150
6
130
140
160
100
400
15

16.

2. Метод наименьшей стоимости
B1
A1
80
1
B3
11
B4
3
13
4
8
2
30
130
3
A3
80
ai
60
12
A2
bj
B2
5
40
14
150
6
130
140
160
100
400
16

17.

2. Метод наименьшей стоимости
B1
A1
80
1
B3
11
B4
3
13
4
8
2
30
130
3
A3
5
14
6
10
80
ai
60
12
A2
bj
B2
40
150
130
140
160
100
400
17

18.

2. Метод наименьшей стоимости
B1
A1
80
1
B3
11
B4
3
13
4
8
2
30
130
3
A3
5
14
6
10
80
ai
60
12
A2
bj
B2
40
150
130
140
160
100
400
18

19.

2. Метод наименьшей стоимости
B1
A1
80
1
B3
11
B4
3
13
4
8
2
30
130
3
A3
5
10
80
ai
60
12
A2
bj
B2
14
6
90
40
150
130
140
160
100
400
19

20.

2. Метод наименьшей стоимости
B1
A1
1
B3
11
80
B4
ai
3
13
8
2
60
12
A2
4
30
130
3
A3
bj
B2
5
10
80
Начальный опорный план:
14
6
90
40
150
130
80 0 60 0
X 0 30 0 130
0 10 90 0
140
160
100
400
20
z(X) = 1·80 + 4·30 + 5·10 + 14·90 + 3·60 + 2·130 = 1950 < 2280

21. Решение транспортной задачи методом потенциалов

Теорема
Если опорный план X = (xij) транспортной
задачи является оптимальным, то существуют
потенциалы поставщиков ui,
i = 1,…, m и потребителей vj, j = 1,…, n,
удовлетворяющие условиям:
ui + vj = сij при xij > 0 (для занятых клеток),
Δij = ui + vj - сij ≤ 0 при xij = 0 (для свободных
клеток).
21

22. Метод потенциалов

B1
A1
1
B3
B4
11
80
ai
3
13
8
2
60
12
A2
4
30
130
3
A3
bj
B2
5
10
80
14
6
90
40
150
130
ui
140
160
100
400
vj
22

23. Метод потенциалов

B1
A1
B2
1
B3
B4
11
80
3
13
8
2
60
12
A2
4
30
130
3
A3
5
10
bj
80
vj
1
14
6
90
40
150
130
ai
ui
140
0
160
100
400
3
23

24. Метод потенциалов

B1
A1
B2
1
B3
B4
11
80
3
13
8
2
60
12
A2
4
30
130
3
A3
5
10
14
6
90
bj
80
40
150
vj
1
-6
3
130
ai
ui
140
0
160
100
11
400
24

25. Метод потенциалов

B1
A1
B2
1
B3
B4
11
80
3
13
8
2
60
12
A2
4
30
130
3
A3
5
10
14
6
90
bj
80
40
150
130
vj
1
–6
3
–8
ai
ui
140
0
160
10
100
11
400
25

26. Метод потенциалов

B1
A1
A2
B2
1
80
B3
11
12
3
60
- 17
8
5
2
130
5
3
13
- 21
4
30
-1
B4
14
6
A3
9
bj
80
40
150
130
vj
1
–6
3
–8
10
90
-3
ai
ui
140
0
160
10
100
11
400
26

27. Метод потенциалов

B1
A1
A2
B2
1
80
B3
11
12
3
60
- 17
8
5
2
130
5
3
13
- 21
4
30
-1
B4
14
6
A3
9
bj
80
40
150
130
vj
1
–6
3
–8
10
90
-3
ai
ui
140
0
160
10
100
11
400
27

28. Метод потенциалов

B1
A1
A2
B2
1
80
B3
11
12
3
60
- 17
8
5
2
130
5
3
13
- 21
4
30
-1
B4
14
6
A3
9
bj
80
40
150
130
vj
1
–6
3
–8
10
90
-3
ai
ui
140
0
160
10
100
11
400
28

29.

Цикл
80
-
+
+
-
60
90
80
-
+
+
-
140
10
Δ = min (80, 90) = 80
29

30.

Новый опорный план
B1
1
A1
bj
B3
B4
11
ai
3
13
8
2
140
12
A2
A3
B2
4
30
130
3
80
5
10
80
14
6
10
40
150
130
ui
140
160
100
400
vj
30

31.

Новый опорный план
B1
1
A1
B3
B4
11
ai
3
13
8
2
140
12
A2
A3
B2
4
30
130
3
80
5
10
14
6
10
bj
80
40
150
vj
3
5
14
130
ui
140
160
100
0
400
31

32.

Новый опорный план
B1
1
A1
B3
B4
11
3
13
8
2
140
12
A2
A3
B2
4
30
130
3
80
5
10
14
6
10
bj
80
40
150
130
vj
3
5
14
3
ai
ui
140
- 11
160
-1
100
0
400
32

33.

Новый опорный план
B1
A1
A2
A3
B2
1
-9
3
140
- 17
8
5
10
2
130
5
3
13
- 21
4
30
- 10
B4
11
12
80
B3
14
10
6
-3
bj
80
40
150
130
vj
3
5
14
3
ai
ui
140
-11
160
-1
100
0
400
z(X) = 3·80 + 5·10 + 4·30 + 14·10 + 3·140 + 2·130 = 1230 <
1950
33

34.

Новый опорный план
B1
A1
A2
A3
B2
1
-9
3
140
- 17
8
5
10
2
130
5
3
13
- 21
4
30
- 10
B4
11
12
80
B3
14
10
6
-3
bj
80
40
150
130
vj
3
5
14
3
ai
ui
140
-11
160
-1
100
0
400
z(X) = 3·80 + 5·10 + 4·30 + 14·10 + 3·140 + 2·130 = 1230 <
1950
34

35.

Новый опорный план
B1
A1
A2
A3
B2
1
-9
3
140
- 17
8
5
10
2
130
5
3
13
- 21
4
30
- 10
B4
11
12
80
B3
14
10
6
-3
bj
80
40
150
130
vj
3
5
14
3
ai
ui
140
-11
160
-1
100
0
400
z(X) = 3·80 + 5·10 + 4·30 + 14·10 + 3·140 + 2·130 = 1230 <
1950
35

36.

Цикл
30
-
+
10
20
+
-
10
20
-
+
+
-
10
Δ = min (10, 30) = 10
36

37.

Новый опорный план
B1
1
A1
bj
B3
B4
11
ai
3
13
8
2
140
12
A2
A3
B2
4
20
10
3
80
5
130
14
6
20
80
40
150
130
ui
140
160
100
400
vj
37

38.

Новый опорный план
B1
A1
A2
A3
B2
1
-4
3
140
- 12
8
10
3
2
130
5
20
13
- 16
4
20
- 10
B4
11
12
80
B3
14
-5
6
-3
bj
80
40
150
130
vj
2
4
8
2
ai
ui
140
-5
160
0
100
1
400
z(X) = 3·80 + 5·20 + 4·20 + 8·10 + 3·140 + 2·130 = 1180 < 123038

39.

Новый опорный план
B1
A1
A2
A3
B2
1
-4
11
B4
3
140
- 12
12
4
13
- 16
8
План
10
130
оптимален!
5
14
2
20
- 10
3
80
B3
20
-5
-3
bj
80
40
150
130
vj
2
4
8
2
6
ai
ui
140
-5
160
0
100
1
400
z(X) = 3·80 + 5·20 + 4·20 + 8·10 + 3·140 + 2·130 = 1180 < 123039

40. Открытая модель транспортной задачи

Модель
транспортной задачи называется
открытой, если a b (суммарные
запасы не равны суммарным потребностям).
m
i 1
n
i
j 1
j
40

41.

Открытая модель транспортной
задачи
Открытую модель можно свести к закрытой:
1. Если
m
n
i 1
j 1
ai b j
, то вводят фиктивного
потребителя Вn+1 с потребностью
m
n
i 1
j 1
bn 1 ai b j
и нулевыми тарифами перевозок в столбце.
m
n
i 1
j 1
2. Если ai b j ,то вводят фиктивного
поставщика А m+1 с запасом
n
m
j 1
i 1
am 1 b j ai
и
нулевыми тарифами перевозок в строке.
41

42. Задача 2

Решите транспортную задачу методом
потенциалов. В ответе укажите
минимальную стоимость всех перевозок.
B1
B2
B3
B4
ai
A1
3
7
4
7
100
A2
10
13
24
7
100
A3
8
19
12
18
200
bj
90
80
30
170
42

43. Задача 2

Решите транспортную задачу методом
потенциалов. В ответе укажите
минимальную стоимость всех перевозок.
B1
B2
B3
B4
ai
A1
3
7
4
7
100
A2
10
13
24
7
100
A3
8
19
12
18
200
bj
90
80
30
170
m
i 1
370
n
a b
i
j 1
400
j
43

44.

Метод «северо-западного угла»
B1
B4
B5
ai
7
4
7
0
10
13
24
7
0
8
19
12
18
0
A3
bj
B3
3
A1
A2
B2
90
80
30
170
30
100
100
200
400
44

45.

Метод «северо-западного угла»
B1
A1
A2
3
90
B3
B4
B5
ai
7
4
7
0
13
24
7
0
12
18
0
10
10
70
8
A3
bj
B2
30
19
0
90
80
170
30
170
30
30
100
100
200
400
z(X) = 3·90 + 7·10 + 13·70 + 24·30 + 18·170 = 5030
45

46.

Метод потенциалов
B1
A1
B2
3
90
8
ai
4
7
0
13
24
7
0
12
18
0
30
19
0
90
B5
7
70
A3
B4
10
A2
bj
B3
80
170
30
170
30
30
ui
100
100
200
400
vj
46

47.

Метод потенциалов
B1
A1
A2
B2
3
90
B3
7
4
10
14
10
13
70
-1
8
B4
7
17
30
0
6
24
19
- 18 0
B5
7
23
12
0
12
18
0
A3
- 11
bj
90
80
30
170
30
vj
3
7
18
24
6
170
30
ai
ui
100
0
100
6
200
-6
400
47

48.

Метод потенциалов
B1
A1
A2
B2
3
90
B3
7
4
10
14
10
13
70
-1
8
B4
7
17
30
0
6
24
19
- 18 0
B5
7
23
12
0
12
18
0
A3
- 11
bj
90
80
30
170
30
vj
3
7
18
24
6
170
30
ai
ui
100
0
100
6
200
-6
400
48

49.

Метод потенциалов
B1
A1
A2
B2
3
90
B3
7
4
10
14
10
13
70
-1
8
B4
7
17
30
0
6
24
19
- 18 0
B5
7
23
12
0
12
18
0
A3
- 11
bj
90
80
30
170
30
vj
3
7
18
24
6
170
30
ai
ui
100
0
100
6
200
-6
400
49

50.

Цикл
30
0
-
+
-
+
+
-
+
-
170 30
30
140
Δ = min (30, 170) = 30
50

51.

Новый опорный план
B1
A1
A2
3
90
B3
B4
B5
ai
7
4
7
0
13
24
7
0
18
0
10
10
70
8
A3
bj
B2
30
19
12
30
90
80
30
140
170
30
30
ui
100
100
200
400
vj
51

52.

Новый опорный план
B1
A1
A2
B2
3
90
B3
7
10
10
4
-9
13
70
-1
8
B4
7
-6
- 23
0
7
30
12
0
- 11
18
0
A3
12
5
bj
90
80
30
170
30
vj
20
24
12
18
0
30
ai
- 17
24
19
B5
140
30
ui
100 -17
100
-11
200
0
400
z(X) = 3·90 + 7·10 + 13·70 + 7·30 + 18·140 + 12·30 = 4130 < 5030
52

53.

Новый опорный план
B1
A1
A2
B2
3
90
B3
7
10
10
4
-9
13
70
-1
8
B4
7
-6
- 23
0
7
30
12
0
- 11
18
0
A3
12
5
bj
90
80
30
170
30
vj
20
24
12
18
0
30
ai
- 17
24
19
B5
140
30
ui
100 -17
100
-11
200
0
400
z(X) = 3·90 + 7·10 + 13·70 + 7·30 + 18·140 + 12·30 = 4130 < 5030
53

54.

Новый опорный план
B1
A1
A2
B2
3
90
B3
7
10
10
4
-9
13
70
-1
8
B4
7
-6
- 23
0
7
30
12
0
- 11
18
0
A3
12
5
bj
90
80
30
170
30
vj
20
24
12
18
0
30
ai
- 17
24
19
B5
140
30
ui
100 -17
100
-11
200
0
400
z(X) = 3·90 + 7·10 + 13·70 + 7·30 + 18·140 + 12·30 = 4130 < 5030
54

55.

Цикл
90
-
+
-
+
20
10
70
+
-
-
30
+
140 70
+
-
80
+ 100
- 70
Δ = min (90, 70, 140) = 70
55

56.

Новый опорный план
B1
A1
3
20
bj
B3
B4
B5
ai
7
4
7
0
13
24
7
0
18
0
80
10
A2
A3
B2
100
8
19
70
90
12
30
80
30
70
170
30
30
ui
100
100
200
400
vj
56

57.

Новый опорный план
B1
A1
A2
A3
B2
3
20
B3
7
80
10
- 13
70
4
3
13
- 12
8
B4
-7
7
6
- 23
7
100
12
30
0
-5
24
19
B5
0
- 11
18
70
0
30
bj
90
80
30
170
30
vj
8
12
12
18
0
ai
ui
100
-5
100 -11
200
0
400
z(X) = 3·20 + 7·80 + 8·70 + 12·30 + 18·70 + 7·100 = 3500 < 4130
57

58.

Новый опорный план
B1
A1
A2
A3
B2
3
20
B3
7
80
10
- 13
70
4
3
13
- 12
8
B4
-7
7
6
- 23
7
100
12
30
0
-5
24
19
B5
0
- 11
18
70
0
30
bj
90
80
30
170
30
vj
8
12
12
18
0
ai
ui
100
-5
100 -11
200
0
400
z(X) = 3·20 + 7·80 + 8·70 + 12·30 + 18·70 + 7·100 = 3500 < 4130
58

59.

Новый опорный план
B1
A1
A2
A3
B2
3
20
B3
7
80
10
- 13
70
4
3
13
- 12
8
B4
-7
7
6
- 23
7
100
12
30
0
-5
24
19
B5
0
- 11
18
70
0
30
bj
90
80
30
170
30
vj
8
12
12
18
0
ai
ui
100
-5
100 -11
200
0
400
z(X) = 3·20 + 7·80 + 8·70 + 12·30 + 18·70 + 7·100 = 3500 < 4130
59

60.

Цикл
20
70
-
+
-
+
+
-
+
-
70
90
20
50
Δ = min (20, 70) = 20
60

61.

Новый опорный план
B1
3
A1
bj
B3
7
B4
4
80
10
A2
A3
B2
B5
ai
7
0
7
0
18
0
20
13
24
100
8
19
90
90
12
30
80
30
50
170
30
30
ui
100
100
200
400
vj
61

62.

Новый опорный план
B1
A1
A2
A3
B2
3
B3
7
80
-6
10
- 13
90
4
-6
- 23
-1
7
30
0
7
100
12
ai
- 11
24
19
B5
20
-3
13
8
B4
0
- 11
18
50
0
30
bj
90
80
30
170
30
vj
8
18
12
18
0
ui
100 -11
100 -11
200
0
400
62

63.

Новый опорный план
B1
A1
A2
A3
B2
3
B3
7
80
-6
10
- 13
8
90
B4
4
7
20
-3
13
B5
24
0
- 11
7
План
100
-6
- 23
- 11
оптимален!
19
12
18
-1
30
50
ai
30
bj
90
80
30
170
30
vj
8
18
12
18
0
0
0
ui
100 -11
100 -11
200
0
400
63

64.

Новый опорный план
B1
A1
A2
A3
bj
vj
B2
3
B3
7
4
80
-6
10
- 13
-6
90
- 23
-1
90
30
80
18
30
12
ai
0
- 11
7
100
12
Оптимальный план:
8
7
24
19
B5
20
-3
13
8
B4
0
- 11
18
50
0
30
ui
100 -11
100 -11
200
0
170 0
80 30
0 20 400
X 0 0 0 100
18 90 0 030 50
z(X) = 8·90 + 7·80 + 12·30 + 7·100 + 7·20 + 18·50 = 3380 < 3500
64

65. Задача 3

Решите транспортную задачу методом
потенциалов. В ответе укажите
минимальную стоимость всех перевозок.
B1
B2
B3
B4
ai
A1
1
13
12
3
60
A2
2
16
4
6
125
A3
13
4
17
16
75
bj
100
100
50
50
65

66. Задача 3

Решите транспортную задачу методом
потенциалов. В ответе укажите
минимальную стоимость всех перевозок.
B1
B2
B3
B4
ai
A1
1
13
12
3
60
A2
2
16
4
6
125
A3
13
4
17
16
75
bj
100
100
50
50
m
i 1
300
n
a b
i
j 1
260
j
66

67.

Метод наименьшей стоимости
B1
B2
B3
B4
ai
1
13
12
3
A2
2
16
4
6
A3
13
4
17
16
A4
0
0
0
0
A1
bj
100
100
50
50
60
125
75
40
300
67

68.

Метод наименьшей стоимости
B1
B2
B3
B4
ai
1
13
12
3
A2
2
16
4
6
A3
13
4
17
16
A4
0
0
0
0
A1
bj
40
100
100
50
50
60
125
75
40
300
68

69.

Метод наименьшей стоимости
B1
B2
B3
B4
ai
1
13
12
3
A2
2
16
4
6
A3
13
4
17
16
A4
0
0
0
0
A1
bj
60
40
100
100
50
50
60
125
75
40
300
69

70.

Метод наименьшей стоимости
B1
B2
B3
B4
ai
1
13
12
3
A2
2
16
4
6
A3
13
4
17
16
A4
0
0
0
0
A1
bj
60
40
100
100
50
50
60
125
75
40
300
70

71.

Метод наименьшей стоимости
B1
B2
B3
B4
ai
1
13
12
3
2
16
4
6
A3
13
4
17
16
A4
0
0
0
0
A1
A2
bj
60
40
40
100
100
50
50
60
125
75
40
300
71

72.

Метод наименьшей стоимости
B1
B2
B3
B4
ai
1
13
12
3
2
16
4
6
A3
13
4
17
16
A4
0
0
0
0
A1
A2
bj
60
40
40
100
100
50
50
60
125
75
40
300
72

73.

Метод наименьшей стоимости
B1
B2
B3
B4
ai
1
13
12
3
2
16
4
6
A3
13
4
17
16
A4
0
0
0
0
A1
A2
bj
60
40
75
40
100
100
50
50
60
125
75
40
300
73

74.

Метод наименьшей стоимости
B1
B2
B3
B4
ai
1
13
12
3
2
16
4
6
A3
13
4
17
16
A4
0
0
0
0
A1
A2
bj
60
40
75
40
100
100
50
50
60
125
75
40
300
74

75.

Метод наименьшей стоимости
B1
A1
A2
B2
B4
ai
1
13
12
3
2
16
4
6
4
17
16
0
0
0
60
40
50
A3
13
A4
0
bj
B3
75
40
100
100
50
50
60
125
75
40
300
75

76.

Метод наименьшей стоимости
B1
A1
A2
B2
B4
ai
1
13
12
3
2
16
4
6
4
17
16
0
0
0
60
40
50
A3
13
A4
0
bj
B3
75
40
100
100
50
50
60
125
75
40
300
76

77.

Метод наименьшей стоимости
B1
A1
A2
B2
B4
ai
1
13
12
3
2
16
4
6
60
40
50
A3
13
A4
0
bj
B3
10
4
17
16
0
0
0
75
40
100
100
50
50
60
125
75
40
300
77

78.

Метод наименьшей стоимости
B1
A1
A2
B2
B4
ai
1
13
12
3
2
16
4
6
60
40
50
A3
13
A4
0
bj
B3
10
4
17
16
0
0
0
75
40
100
100
50
50
60
125
75
40
300
78

79.

Метод наименьшей стоимости
B1
A1
A2
B2
B4
ai
1
13
12
3
2
16
4
6
60
40
25
A3
13
A4
0
bj
B3
50
10
4
17
16
0
0
0
75
40
100
100
50
50
60
125
75
40
300
z(X) = 1·60 + 2·40 + 16·25+ 4·75 + 4·50 + 6·10 = 1100
79

80.

Метод потенциалов
B1
A1
A2
B2
B4
ai
1
13
12
3
2
16
4
6
60
40
25
A3
13
A4
0
bj
B3
50
10
4
17
16
0
0
0
75
40
100
100
50
50
ui
60
125
75
40
300
vj
80

81.

Метод потенциалов
B1
A1
A2
B2
1
60
13
2
2
40
B3
B4
12
-9
16
25
3
2
4
50
6
10
A4
13
4
17
16
- 23 75
- 25
- 22
0
0
0
0
40
-4
10
-2
bj
100
100
50
50
vj
2
16
4
6
A3
ai
ui
60
-1
125
0
75
-12
40
-6
300
81

82.

Метод потенциалов
B1
A1
A2
B2
1
60
13
2
2
40
B3
B4
12
-9
16
25
3
2
4
50
6
10
A4
13
4
17
16
- 23 75
- 25
- 22
0
0
0
0
40
-4
10
-2
bj
100
100
50
50
vj
2
16
4
6
A3
ai
ui
60
-1
125
0
75
-12
40
-6
300
82

83.

Метод потенциалов
B1
A1
A2
B2
1
60
13
2
2
40
B3
B4
12
-9
16
25
3
2
4
50
6
10
A4
13
4
17
16
- 23 75
- 25
- 22
0
0
0
0
40
-4
10
-2
bj
100
100
50
50
vj
2
16
4
6
A3
ai
ui
60
-1
125
0
75
-12
40
-6
300
83

84.

Цикл
25
-
+
+
-
10
40
25
-
+
+
-
35
15
Δ = min (25, 40) = 25
84

85.

Новый опорный план
B1
A1
A2
B2
B4
ai
1
13
12
3
2
16
4
6
60
40
50
A3
13
A4
0
bj
B3
35
4
17
16
0
0
0
75
25
100
100
15
50
50
ui
60
125
75
40
300
vj
85

86.

Новый опорный план
B1
A1
A2
B2
1
60
B3
13
-8
2
40
B4
12
-9
16
2
4
50
- 10
3
6
35
A4
13
- 13 75
0
25
-4
bj
100
100
50
50
vj
2
6
4
6
A3
4
17
16
- 15
- 12
0
0
0
15
-2
ai
ui
60
-1
125
0
75
-2
40
-6
300
z(X) = 1·60 + 2·40 + 4·75 + 4·50 + 6·35 = 850 < 1100
86

87.

Новый опорный план
B1
A1
A2
B2
1
60
B3
13
-8
2
40
B4
12
-9
16
2
4
50
- 10
3
6
35
A4
13
- 13 75
0
25
-4
bj
100
100
50
50
vj
2
6
4
6
A3
4
17
16
- 15
- 12
0
0
0
15
-2
ai
ui
60
-1
125
0
75
-2
40
-6
300
z(X) = 1·60 + 2·40 + 4·75 + 4·50 + 6·35 = 850 < 1100
87

88.

Новый опорный план
B1
A1
A2
B2
1
60
B3
13
-8
2
40
B4
12
-9
16
2
4
50
- 10
3
6
35
A4
13
- 13 75
0
25
-4
bj
100
100
50
50
vj
2
6
4
6
A3
4
17
16
- 15
- 12
0
0
0
15
-2
ai
ui
60
-1
125
0
75
-2
40
-6
300
z(X) = 1·60 + 2·40 + 4·75 + 4·50 + 6·35 = 850 < 1100
88

89.

Цикл
60
40
25
-
+
-
+
+
-
+
-
35
75
35
Δ = min (35, 60) = 35
89

90.

Новый опорный план
B1
A1
A2
B2
1
13
B4
12
25
ai
3
35
2
16
4
6
4
17
16
0
0
0
75
50
A3
13
A4
0
bj
B3
75
25
100
100
15
50
50
ui
60
125
75
40
300
vj
90

91.

Новый опорный план
B1
A1
A2
A3
B2
1
25
B3
13
- 10
2
B4
12
35
-9
16
3
4
6
План
50
- 12
-2
оптимален!
13
4
17
16
75
75
- 11
- 13
0
0
- 12
0
0
A4
-2
bj
100
100
50
50
vj
1
3
3
3
25
0
15
ai
ui
60
0
125
1
75
1
40
-3
300
91

92.

Новый опорный план
B1
A1
A2
B2
1
25
B3
13
- 10
2
75
12
16
4
50
- 12
3
35
-9
6
-2
A4
13
- 11 75
0
25
-2
bj
100
100
50
vj
1
3
3
A3
B4
4
17
16
- 13
- 12
0
0
0
15
0
Оптимальный план:
ai
ui
60
0
125
1
75
1
40
-3
0 0300
35
25
50
X 75 0 50 0
0 3 75 0 0
z(X) = 1·25 + 2·75 + 4·75 + 4·50 + 3·35 = 780 < 850
92

93.

Транспортные задачи с
дополнительными ограничениями
В
некоторых транспортных задачах
наложены дополнительные ограничения на
перевозку грузов.
1. Если в закрытой задаче перевозки от
поставщика Ai к потребителю Bj не могут
быть осуществлены (стоит блокировка),
для определения оптимального решения
задач предполагают, что тариф перевозки
единицы груза равен сколь угодно
большому числу М.
93

94.

2. Если дополнительным условием в задаче является
обеспечение перевозки от поставщика Ai к
потребителю Bj в точности aij единиц груза, в
клетку AiBj записывают указанное число aij, а эту
клетку считают свободной со сколь угодно
большим тарифом М.
3. Если от поставщика Ai к потребителю Bj должно
быть перевезено не менее aij единиц груза, то
запасы пункта Ai и потребности Bj полагают
меньше фактических на aij единиц. После
нахождения оптимального плана перевозку в
клетке AiBj увеличивают на aij единиц.
94

95.

4. Если от поставщика Ai к потребителю Bj
требуется перевезти не более aij единиц
груза, то вводят дополнительного
потребителя Bn+1 = Bij, которому
записывают те же тарифы, что и для Bj, за
исключением тарифа в i–й строке, который
считают равным сколь угодно большому
числу М.
Потребности пункта Bj считают равными
aij, а потребности Bij полагают равными
bj - aij.
95

96. Задача 4

Найти решение транспортной задачи, если из А3 в В1 и из
А2 в В3 перевозки не могут быть осуществлены, из А1 в В2
должно быть завезено не менее 30 ед. груза, а из А 2 в В4
ровно 70 ед. груза.
B1
B2
B3
B4
ai
A1
1
11
3
13
140
A2
12
4
8
2
160
A3
3
5
14
6
100
bj
80
40
150
130
96

97. Задача 4

Найти решение транспортной задачи, если из А3 в В1 и из
А2 в В3 перевозки не могут быть осуществлены, из А1 в В2
должно быть завезено не менее 30 ед. груза, а из А 2 в В4
ровно 70 ед. груза.
B1
B2
B3
B4
ai
A1
1
11
3
13
140
A2
12
4
8
2
160
A3
3
5
14
6
100
bj
80
40
150
130
400
400
97

98. Задача 4

Найти решение транспортной задачи, если из А3 в В1 и из
А2 в В3 перевозки не могут быть осуществлены, из А1 в В2
должно быть завезено не менее 30 ед. груза, а из А 2 в В4
ровно 70 ед. груза.
B1
B2
B3
B4
ai
A1
1
11
3
13
140
A2
12
4
8
2
160
A3
3
5
14
6
100
bj
80
40
150
130
400
400
400
98

99.

Метод «северо-западного угла»
B1
B2
B3
B4
ai
A1
1
11
3
13
A2
12
4
М
М
A3
М
bj
70
80
5
10
14
150
6
130
110
160
100
400
99

100.

Метод «северо-западного угла»
B1
B2
B3
B4
ai
A1
1
11
3
13
A2
12
4
М
М
A3
М
bj
70
80
5
10
14
150
6
130
110
160
100
400
10

101.

Метод «северо-западного угла»
B1
A1
B2
1
80
11
10
A2
12
A3
М
bj
B3
B4
3
13
М
М
20
4
90
70
5
14
40
80
ai
10
6
60
150
130
110
160
100
400
10

102. Метод потенциалов

B1
A1
1
80
B3
B4
11
10
3
13
4
М
М
70
90
М
A3
5
14
40
80
ai
20
12
A2
bj
B2
10
150
6
60
130
ui
110
160
100
400
vj
10

103. Метод потенциалов

B1
A1
A2
B2
1
80
B3
11
10
3
20
12
М-16
B4
-8
4
М+2
М
13
М
М
70
90
5
14
6
A3
12-М
bj
80
10
150
130
vj
1
11
3
5
17
40
60
ai
ui
110
0
160
М-5
100
11
400
10

104. Метод потенциалов

B1
A1
A2
B2
1
80
B3
11
10
3
20
12
М-16
B4
-8
4
М+2
М
13
М
М
70
90
5
14
6
A3
12-М
bj
80
10
150
130
vj
1
11
3
5
17
40
60
ai
ui
110
0
160
М-5
100
11
400
10

105. Метод потенциалов

B1
A1
A2
B2
1
80
B3
11
10
3
20
12
М-16
B4
-8
4
М+2
М
13
М
М
70
90
5
14
6
A3
12-М
bj
80
10
150
130
vj
1
11
3
5
17
40
60
ai
ui
110
0
160
М-5
100
11
400
10

106.

Цикл
10
20
-
+
-
+
+
-
+
-
90
10
30
80
Δ = min (10, 90) = 10
10

107.

Новый опорный план
B1
A1
1
B3
B4
11
80
ai
3
13
М
М
30
12
A2
4
10
70
80
М
A3
bj
B2
5
14
40
80
10
150
6
60
130
ui
110
160
100
400
vj
10

108.

Новый опорный план
B1
A1
A2
A3
B2
1
80
B3
11
-М-4
12
М-14
3
30
М
5
5-М
М
70
80
М
13
-10
4
10
4-М
B4
14
40
6
60
bj
80
10
150
130
vj
М-2
4
М
М
ai
ui
110
3-М
160
0
100
6-М
400
10

109.

Новый опорный план
B1
A1
A2
A3
B2
1
80
B3
11
-М-4
12
М-14
3
30
М
5
5-М
М
70
80
М
13
-10
4
10
4-М
B4
14
40
6
60
bj
80
10
150
130
vj
М-2
4
М
М
ai
ui
110
3-М
160
0
100
6-М
400
10

110.

Новый опорный план
B1
A1
A2
A3
B2
1
80
B3
11
-М-4
12
М-14
3
30
М
5
5-М
М
70
80
М
13
-10
4
10
4-М
B4
14
40
6
60
bj
80
10
150
130
vj
М-2
4
М
М
ai
ui
110
3-М
160
0
100
6-М
400
11

111.

Цикл
80
30
-
+
-
+
+
-
+
-
80
80
110
0
Δ = min (80, 80) = 80
11

112.

Новый опорный план
B1
1
A1
A2
B3
B4
11
ai
3
13
М
М
110
12
80
4
10
70
0
М
A3
bj
B2
5
14
40
80
10
150
6
60
130
ui
110
160
100
400
vj
11

113.

Новый опорный план
B1
A1
B2
1
14-М
B3
B4
11
-4-М
12
3
110
-10
4
A2
80
A3
М
18-2М 5-М
10
13
М
М
70
0
5
14
40
6
60
bj
80
10
150
130
vj
12
4
М
М
ai
ui
110
3-М
160
0
100
6-М
400
11

114.

Новый опорный план
B1
A1
B2
1
14-М
B3
B4
11
-4-М
3
110
13
-10
План
4
М
10
0
70
оптимален!
12
A2
80
A3
М
18-2М 5-М
5
М
14
40
6
60
bj
80
10
150
130
vj
12
4
М
М
ai
ui
110
3-М
160
0
100
6-М
400
11

115.

Новый опорный план
B1
A1
B2
1
14-М
-4-М
12
A3
М
18-2М 5-М
vj
110
10
12
3
М
4
5
Оптимальный план:
М
70
0
10
13
-10
4
80
80
B4
11
A2
bj
B3
14
40
6
60
150
130
0 30 110
М
М
X 80 10 0
0 0 40
ai
ui
110
3-М
160
0
100
6-М
400
0
70
60
z(X) = 12·80 + 4·10 + 11·30 + 3·110 + 14·40 + 6·60 + 2·70 = 2720
11

116. Задача 5

Найти решение транспортной задачи, если из А1 в В4
должно быть перевезено не менее 50 ед. груза, из А 3 в В3
должно быть перевезено не менее 30 ед. груза, а из А 2 в В2
ровно 40 ед. груза.
B1
B2
B3
B4
ai
A1
9
6
7
11
70
A2
3
14
25
19
170
A3
2
8
17
10
140
bj
90
60
160
70
11

117. Задача 5

Найти решение транспортной задачи, если из А1 в В4
должно быть перевезено не менее 50 ед. груза, из А 3 в В3
должно быть перевезено не менее 30 ед. груза, а из А 2 в В2
ровно 40 ед. груза.
B1
B2
B3
B4
ai
A1
9
6
7
11
70
A2
3
14
25
19
170
A3
2
8
17
10
140
bj
90
60
160
70
380
380
11

118. Задача 5

Найти решение транспортной задачи, если из А1 в В4
должно быть перевезено не менее 50 ед. груза, из А 3 в В3
должно быть перевезено не менее 30 ед. груза, а из А 2 в В2
ровно 40 ед. груза.
B1
B2
B3
B4
ai
A1
9
6
7
11
70
A2
3
14
25
19
170
A3
2
8
17
10
140
bj
90
60
160
70
380
380
380
11

119.

Метод минимальной стоимости
B1
B2
B3
B4
ai
A1
9
6
7
11
A2
3
М
25
19
A3
2
8
17
10
bj
40
90
60
130
20
20
170
110
380
11

120.

Метод минимальной стоимости
B1
B2
B3
B4
ai
A1
9
6
7
11
A2
3
М
25
19
A3
2
8
17
10
bj
40
90
90
60
130
20
20
170
110
380
12

121.

Метод минимальной стоимости
B1
B2
B3
B4
ai
A1
9
6
7
11
A2
3
М
25
19
A3
2
8
17
10
bj
40
90
90
60
130
20
20
170
110
380
12

122.

Метод минимальной стоимости
B1
B2
A1
9
A2
3
A3
2
bj
B3
B4
ai
6
7
11
М
25
19
8
17
10
20
40
90
90
60
130
20
20
170
110
380
12

123.

Метод минимальной стоимости
B1
B2
A1
9
A2
3
A3
2
bj
B3
B4
ai
6
7
11
М
25
19
8
17
10
20
40
90
90
60
130
20
20
170
110
380
12

124.

Метод минимальной стоимости
B1
B2
A1
9
A2
3
A3
2
bj
B3
B4
ai
6
7
11
М
25
19
8
17
10
20
40
90
20
90
60
130
20
20
170
110
380
12

125.

Метод минимальной стоимости
B1
B2
A1
9
A2
3
A3
2
bj
B3
B4
ai
6
7
11
М
25
19
8
17
10
20
40
90
20
90
60
130
20
20
170
110
380
12

126.

Метод минимальной стоимости
B1
B2
A1
9
A2
3
A3
2
bj
B3
B4
ai
6
7
11
М
25
19
17
10
20
40
130
8
90
20
90
60
130
20
20
170
110
380
12

127. Метод потенциалов

B1
9
A1
A2
A3
bj
B2
B3
B4
ai
6
7
11
М
25
19
17
10
20
3
0
40
130
2
8
90
20
90
60
130
20
ui
20
170
110
380
vj
12

128. Метод потенциалов

B1
A1
A2
A3
B2
9
-М
B3
6
20
М
40
25
8
М-9
11
6-М
130
2
90
7
24-М
3
0
B4
19
-8
17
7
10
20
bj
90
60
130
20
vj
3
М
25
11
ai
ui
20
6-М
170
0
110
-1
380
12

129. Метод потенциалов

B1
A1
A2
A3
B2
9
-М
B3
6
20
М
40
25
8
М-9
11
6-М
130
2
90
7
24-М
3
0
B4
19
-8
17
7
10
20
bj
90
60
130
20
vj
3
М
25
11
ai
ui
20
6-М
170
0
110
-1
380
12

130.

Цикл
0
90
40
+
-
-
+
40
50
+
-
-
+
40
Δ = min (90, 40) = 40
13

131.

Новый опорный план
B1
9
A1
A2
A3
bj
B2
B3
B4
ai
6
7
11
М
25
19
17
10
20
3
40
130
2
50
8
40
90
20
60
130
20
ui
20
170
110
380
vj
13

132.

Новый опорный план
B1
A1
A2
A3
B2
9
-9
B3
6
20
2
25
130
8
40
11
-3
М
9-М
50
7
15
3
40
B4
19
-8
17
7
10
20
bj
90
60
130
20
vj
2
8
24
10
ai
ui
20
-2
170
1
110
0
380
13

133.

Новый опорный план
B1
A1
A2
A3
B2
9
-9
B3
6
20
2
25
130
8
40
11
-3
М
9-М
50
7
15
3
40
B4
19
-8
17
7
10
20
bj
90
60
130
20
vj
2
8
24
10
ai
ui
20
-2
170
1
110
0
380
13

134.

Цикл
20
40
50
-
- 130
60
+
-
-
+
+
40
30
- 110
+
-
+
20
+ 60
Δ = min (50, 20,130) = 20
13

135.

Новый опорный план
B1
9
A1
A2
A3
bj
B2
B3
B4
6
ai
7
11
25
19
17
10
20
3
М
60
110
2
30
8
60
90
20
60
130
20
ui
20
170
110
380
vj
13

136.

Новый опорный план
B1
A1
A2
A3
B2
9
-24
B3
6
-15
2
25
110
8
60
11
-18
М
9-М
30
7
20
3
60
B4
19
-8
17
7
10
20
bj
90
60
130
20
vj
2
8
24
10
ai
ui
20
-17
170
1
110
0
380
13

137.

Новый опорный план
B1
A1
A2
A3
B2
9
-24
B3
6
-15
2
25
110
8
60
11
-18
М
9-М
30
7
20
3
60
B4
19
-8
17
7
10
20
bj
90
60
130
20
vj
2
8
24
10
ai
ui
20
-17
170
1
110
0
380
13

138.

Новый опорный план
B1
A1
A2
A3
B2
9
-24
B3
6
-15
2
25
110
8
60
11
-18
М
9-М
30
7
20
3
60
B4
19
-8
17
7
10
20
bj
90
60
130
20
vj
2
8
24
10
ai
ui
20
-17
170
1
110
0
380
13

139.

Цикл
60
30
+
-
-
+
110 90
+
-
-
+
80
30
Δ = min (30, 110) = 30
13

140.

Новый опорный план
B1
9
A1
A2
B3
B4
6
ai
7
11
25
19
17
10
20
3
М
90
80
2
A3
bj
B2
8
60
90
30
60
130
20
20
ui
20
170
110
380
vj
14

141.

Новый опорный план
B1
A1
A2
A3
B2
9
-24
B3
6
-8
2
25
80
19
-1
8
60
11
-11
М
16-М
-7
7
20
3
90
B4
17
30
10
20
bj
90
60
130
20
vj
-5
8
17
10
ai
ui
20
-10
170
8
110
0
380
14

142.

Новый опорный план
B1
A1
A2
A3
B2
9
-24
B3
B4
6
-8
7
20
11
-11
План
М
25
16-М
80
-1
оптимален!
3
90
2
-7
8
60
19
17
30
10
20
bj
90
60
130
20
vj
-5
8
17
10
ai
ui
20
-10
170
8
110
0
380
14

143.

Новый опорный план
B1
A1
A2
A3
bj
vj
B2
9
-24
B3
6
-8
М
16-М
2
-7
25
8
-5
8
Оптимальный
план:
19
-1
17
30
60
11
-11
80
60
90
7
20
3
90
B4
10
20
130
20
ai
ui
20
-10
170
8
110
0
380
0 0 20 50
17
10
X 90 0 80 0
0 60 60 20
z(X) = 3·90 + 8·60 + 17·60 + 25·80 + 7·20 + 11·50 + 10·20 = 4660
14

144. Спасибо за внимание!

14