CSC 445/545 – Summer 2021 – Network Simplex Examples I
CSC 445/545 – Summer 2021
Network Simplex Examples I
Bill Bird
Department of Computer Science
University of Victoria
July 11, 2021
University of Victoria – CSC 445/545 – Summer 2021 1
Examples
This lecture contains examples of exercises of the form ‘solve this minimum cost network
flow problem’. The term ‘solve’ means to determine if the problem is infeasible, unbounded
or has an optimal flow, and to find the optimal flow if one exists. Therefore, determining
that a problem instance is infeasible or unbounded is considered ‘solving’ that problem.
All of the examples in this lecture involve starting from a primal-feasible basis and using
primal pivoting to find an optimal flow.
The examples here all use the network equivalent of the largest coefficient rule to select the
entering arc at each step. Specifically, the entering arc is chosen to be the dual-infeasible
arc with the smallest negative dual slack value.
University of Victoria – CSC 445/545 – Summer 2021 2
Example 1 (1)
Supply/Cost Flow
a
-6
b
-5
c
1
d
3
e
6
f-2
g
10
h
-6
i
1
1
1
8
4
2
1
5
1
2
7
4
4
1
a
0
b
1
c
-7
d
-3
e
-1
f-6
g
-13
h
-11
i
-7
5
1
7
13
8
2
2
3
9
10
10
-5
0
Task: Starting from the primal feasible flow above, find an optimal flow.
University of Victoria – CSC 445/545 – Summer 2021 3
Example 1 (2)
Supply/Cost Flow
a
-6
b
-5
c
1
d
3
e
6
f-2
g
10
h
-6
i
1
1
1
8
4
2
1
5
1
2
7
4
4
1
a
0
b
1
c
-7
d
-3
e
-1
f-6
g
-13
h
-11
i
-7
5
1
7
13
8
2
2
3
9
10
10
0
-5
Iteration 1. Entering arc is (f , a).
University of Victoria – CSC 445/545 – Summer 2021 4
Example 1 (3)
Supply/Cost Flow
a
-6
b
-5
c
1
d
3
e
6
f-2
g
10
h
-6
i
1
1
1
8
4
2
1
5
1
2
7
4
4
1
a
0
b
1
c
-7
d
-3
e
-1
f-6
g
-13
h
-11
i
-7
?
13
7
3
28
2
With (f , a) entering, the leaving arc is (h, i). The flow assigned to (f , a) will be 2 units.
University of Victoria – CSC 445/545 – Summer 2021 5
Example 1 (4)
Supply/Cost Flow
a
-6
b
-5
c
1
d
3
e
6
f-2
g
10
h
-6
i
1
1
1
8
4
2
1
5
1
2
7
4
4
1
a
0
b
1
c
-7
d
-3
e
-1
f-1
g
-8
h
-6
i
-7
5
1
5
11
2
6
4
1
9
10
5
5
-5
End of Iteration 1. Total cost is 76.
University of Victoria – CSC 445/545 – Summer 2021 6
Example 1 (5)
Supply/Cost Flow
a
-6
b
-5
c
1
d
3
e
6
f-2
g
10
h
-6
i
1
1
1
8
4
2
1
5
1
2
7
4
4
1
a
0
b
1
c
-7
d
-3
e
-1
f-1
g
-8
h
-6
i
-7
5
1
5
11
2
6
4
1
9
10
5
5
-5
Iteration 2. Entering arc is (i , f ).
University of Victoria – CSC 445/545 – Summer 2021 7
Example 1 (6)
Supply/Cost Flow
a
-6
b
-5
c
1
d
3
e
6
f-2
g
10
h
-6
i
1
1
1
8
4
2
1
5
1
2
7
4
4
1
a
0
b
1
c
-7
d
-3
e
-1
f-1
g
-8
h
-6
i
-7
?
2
11
5
1
With (i , f ) entering, the leaving arc is (i , d). The flow assigned to (i , f ) will be 1 units.
University of Victoria – CSC 445/545 – Summer 2021 8
Example 1 (7)
Supply/Cost Flow
a
-6
b
-5
c
1
d
3
e
6
f-2
g
10
h
-6
i
1
1
1
8
4
2
1
5
1
2
7
4
4
1
a
0
b
1
c
-7
d
-3
e
-1
f-1
g
-8
h
-6
i
-2
5
1
4
10
3
6
4 1
9
10
5
0
5
Optimal. Total cost is 71.
University of Victoria – CSC 445/545 – Summer 2021 9
Example 2 (1)
Supply/Cost Flow
a
-6
b
-5
c
1
d
3
e
6
f-2
g
10
h
-6
i
1
1
1
8
4
2
1
5
1
2
7
4
4
-10
a
0
b
1
c
-7
d
-3
e
-1
f4
g
-13
h
-11
i
-7
5
1
9
13
2
10 4
5
9
10
5
-10 -21
Task: Starting from the primal feasible flow above, find an optimal flow.
University of Victoria – CSC 445/545 – Summer 2021 10
Example 2 (2)
Supply/Cost Flow
a
-6
b
-5
c
1
d
3
e
6
f-2
g
10
h
-6
i
1
1
1
8
4
2
1
5
1
2
7
4
4
-10
a
0
b
1
c
-7
d
-3
e
-1
f4
g
-13
h
-11
i
-7
5
1
9
13
2
10 4
5
9
10
5
-10 -21
Iteration 1. Entering arc is (i , f ).
University of Victoria – CSC 445/545 – Summer 2021 11
Example 2 (3)
Supply/Cost Flow
a
-6
b
-5
c
1
d
3
e
6
f-2
g
10
h
-6
i
1
1
1
8
4
2
1
5
1
2
7
4
4
-10
a
0
b
1
c
-7
d
-3
e
-1
f4
g
-13
h
-11
i
-7
?
2
9
5
With (i , f ) entering, the leaving arc is (e, f ). The flow assigned to (i , f ) will be 2 units.
University of Victoria – CSC 445/545 – Summer 2021 12
Example 2 (4)
Supply/Cost Flow
a
-6
b
-5
c
1
d
3
e
6
f-2
g
10
h
-6
i
1
1
1
8
4
2
1
5
1
2
7
4
4
-10
a
0
b
1
c
-7
d
-3
e
-1
f-17
g
-13
h
-11
i
-7
5
1
7
13
10 4
3
2
9
10
21
-16
11
End of Iteration 1. Total cost is 64.
University of Victoria – CSC 445/545 – Summer 2021 13
Example 2 (5)
Supply/Cost Flow
a
-6
b
-5
c
1
d
3
e
6
f-2
g
10
h
-6
i
1
1
1
8
4
2
1
5
1
2
7
4
4
-10
a
0
b
1
c
-7
d
-3
e
-1
f-17
g
-13
h
-11
i
-7
5
1
7
13
10 4
3
2
9
10
21
11
-16
Iteration 2. Entering arc is (f , a).
University of Victoria – CSC 445/545 – Summer 2021 14
Example 2 (6)
Supply/Cost Flow
a
-6
b
-5
c
1
d
3
e
6
f-2
g
10
h
-6
i
1
1
1
8
4
2
1
5
1
2
7
4
4
-10
a
0
b
1
c
-7
d
-3
e
-1
f-17
g
-13
h
-11
i
-7
?
13
7
3
2
With (f , a) entering, the leaving arc is (i , d). The flow assigned to (f , a) will be 3 units.
University of Victoria – CSC 445/545 – Summer 2021 15
Example 2 (7)
Supply/Cost Flow
a
-6
b
-5
c
1
d
3
e
6
f-2
g
10
h
-6
i
1
1
1
8
4
2
1
5
1
2
7
4
4
-10
a
0
b
1
c
-7
d
-3
e
-1
f-1
g
3
h
5
i
9
5
1
4
10
3
10 4
5
9
10
5
11
16
Optimal. Total cost is 16.
University of Victoria – CSC 445/545 – Summer 2021 16
Example 3 (1)
Supply/Cost Flow
a
-3
b
-5
c
-3
d
4
e10 f 3
g
-2
h
-4
i
-1
j
1
5
10
10
2 10
9
512 11
2
5
2
1
2 2
1
a
0
b
-10
c
-12
d
-38
e-23 f -28
g
5
h
7
i
9
j
-29
7
10 15
4
18
8
5 1
5
23
36
-5-11
-3536
40
Task: Starting from the primal feasible flow above, find an optimal flow.
University of Victoria – CSC 445/545 – Summer 2021 17
Example 3 (2)
Supply/Cost Flow
a
-3
b
-5
c
-3
d
4
e10 f 3
g
-2
h
-4
i
-1
j
1
5
10
10
2 10
9
512 11
2
5
2
1
2 2
1
a
0
b
-10
c
-12
d
-38
e-23 f -28
g
5
h
7
i
9
j
-29
7
10 15
4
18
8
5 1
5
23
36
-5-11
36
40
-35
Iteration 1. Entering arc is (f , i).
University of Victoria – CSC 445/545 – Summer 2021 18
Example 3 (3)
Supply/Cost Flow
a
-3
b
-5
c
-3
d
4
e10 f 3
g
-2
h
-4
i
-1
j
1
5
10
10
2 10
9
512 11
2
5
2
1
2 2
1
a
0
b
-10
c
-12
d
-38
e-23 f -28
g
5
h
7
i
9
j
-29
?
15
7
10 15
18
8
With (f , i) entering, the leaving arc is (h, i). The flow assigned to (f , i) will be 1 units.
University of Victoria – CSC 445/545 – Summer 2021 19
Example 3 (4)
Supply/Cost Flow
a
-3
b
-5
c
-3
d
4
e10 f 3
g
-2
h
-4
i
-1
j
1
5
10
10
2 10
9
512 11
2
5
2
1
2 2
1
a
0
b
-10
c
-12
d
-38
e-23 f -28
g
5
h
7
i
-26
j
-29
6
9 14
4
17
1
7
4
5
23
36
-5-11
36
35 5
End of Iteration 1. Total cost is 421.
University of Victoria – CSC 445/545 – Summer 2021 20
Example 3 (5)
Supply/Cost Flow
a
-3
b
-5
c
-3
d
4
e10 f 3
g
-2
h
-4
i
-1
j
1
5
10
10
2 10
9
512 11
2
5
2
1
2 2
1
a
0
b
-10
c
-12
d
-38
e-23 f -28
g
5
h
7
i
-26
j
-29
6
9 14
4
17
1
7
4
5
23
36
-5
36
35 5
-11
Iteration 2. Entering arc is (e, a).
University of Victoria – CSC 445/545 – Summer 2021 21
Example 3 (6)
Supply/Cost Flow
a
-3
b
-5
c
-3
d
4
e10 f 3
g
-2
h
-4
i
-1
j
1
5
10
10
2 10
9
512 11
2
5
2
1
2 2
1
a
0
b
-10
c
-12
d
-38
e-23 f -28
g
5
h
7
i
-26
j
-29
?
9 14
17
With (e, a) entering, the leaving arc is (b, a). The flow assigned to (e, a) will be 9 units.
University of Victoria – CSC 445/545 – Summer 2021 22
Example 3 (7)
Supply/Cost Flow
a
-3
b
-5
c
-3
d
4
e10 f 3
g
-2
h
-4
i
-1
j
1
5
10
10
2 10
9
512 11
2
5
2
1
2 2
1
a
0
b
1
c
-1
d
-27
e-12 f -17
g
5
h
7
i
-15
j
-18
6
5
4
9 8
1
7
4
5
11
23
36
-5
25
24 5
End of Iteration 2. Total cost is 322.
University of Victoria – CSC 445/545 – Summer 2021 23
Example 3 (8)
Supply/Cost Flow
a
-3
b
-5
c
-3
d
4
e10 f 3
g
-2
h
-4
i
-1
j
1
5
10
10
2 10
9
512 11
2
5
2
1
2 2
1
a
0
b
1
c
-1
d
-27
e-12 f -17
g
5
h
7
i
-15
j
-18
6
5
4
9 8
1
7
4
5
11
23
36
25
24 5
-5
Iteration 3. Entering arc is (d , f ).
University of Victoria – CSC 445/545 – Summer 2021 24
Example 3 (9)
Supply/Cost Flow
a
-3
b
-5
c
-3
d
4
e10 f 3
g
-2
h
-4
i
-1
j
1
5
10
10
2 10
9
512 11
2
5
2
1
2 2
1
a
0
b
1
c
-1
d
-27
e-12 f -17
g
5
h
7
i
-15
j
-18
?
5
4
With (d , f ) entering, the leaving arc is (d , j). The flow assigned to (d , f ) will be 4 units.
University of Victoria – CSC 445/545 – Summer 2021 25
Example 3 (10)
Supply/Cost Flow
a
-3
b
-5
c
-3
d
4
e10 f 3
g
-2
h
-4
i
-1
j
1
5
10
10
2 10
9
512 11
2
5
2
1
2 2
1
a
0
b
1
c
-1
d
-22
e-12 f -17
g
5
h
7
i
-15
j
-18
6
5
49 8
1
7
4
1
11
23
31
5
25
24 5
Optimal. Total cost is 302.
University of Victoria – CSC 445/545 – Summer 2021 26
Example 4 (1)
Supply/Cost Flow
a
0
b
0
c-6
d
-6
e
-2
f
9
g
5
48
28
10
7
65
7
38
15
56
48108
24
33
19
a
0
b
-8
c57
d
28
e
-22
f
-56
g
-41
6
6
6
3 3
2
-9
32
-1 21
74
65
-5
9
(This is the motivating example from Chapter 14 of Vanderbei)
University of Victoria – CSC 445/545 – Summer 2021 27
Example 4 (2)
Supply/Cost Flow
a
0
b
0
c-6
d
-6
e
-2
f
9
g
5
48
28
10
7
65
7
38
15
56
48108
24
33
19
a
0
b
-8
c57
d
28
e
-22
f
-56
g
-41
6
6
6
3 3
2
-9
32
-1 21
74
65
-5
9
Task: Starting from the primal feasible basis above, find an optimal flow.
University of Victoria – CSC 445/545 – Summer 2021 28
Example 4 (3)
Supply/Cost Flow
a
0
b
0
c-6
d
-6
e
-2
f
9
g
5
48
28
10
7
65
7
38
15
56
48108
24
33
19
a
0
b
-8
c57
d
28
e
-22
f
-56
g
-41
6
6
6
3 3
2
32
-1 21
74
65
-5
9
-9
Iteration 1. Entering arc is (a, c).
University of Victoria – CSC 445/545 – Summer 2021 29
Example 4 (4)
Supply/Cost Flow
a
0
b
0
c-6
d
-6
e
-2
f
9
g
5
48
28
10
7
65
7
38
15
56
48108
24
33
19
a
0
b
-8
c57
d
28
e
-22
f
-56
g
-41
?
6
3
6
With (a, c) entering, the leaving arc is (f , b). The flow assigned to (a, c) will be 3 units.
University of Victoria – CSC 445/545 – Summer 2021 30
Example 4 (5)
Supply/Cost Flow
a
0
b
0
c-6
d
-6
e
-2
f
9
g
5
48
28
10
7
65
7
38
15
56
48108
24
33
19
a
0
b
-17
c48
d
28
e
-31
f
-56
g
-50
3
6
3
9
3
2
41
-10 21
83
74
94
18
End of Iteration 1. Total cost is 1148.
University of Victoria – CSC 445/545 – Summer 2021 31
Example 4 (6)
Supply/Cost Flow
a
0
b
0
c-6
d
-6
e
-2
f
9
g
5
48
28
10
7
65
7
38
15
56
48108
24
33
19
a
0
b
-17
c48
d
28
e
-31
f
-56
g
-50
3
6
3
9
3
2
41
21
83
74
94
18
-10
Iteration 2. Entering arc is (b, a).
University of Victoria – CSC 445/545 – Summer 2021 32
Example 4 (7)
Supply/Cost Flow
a
0
b
0
c-6
d
-6
e
-2
f
9
g
5
48
28
10
7
65
7
38
15
56
48108
24
33
19
a
0
b
-17
c48
d
28
e
-31
f
-56
g
-50
?3
3
With (b, a) entering, the leaving arc is (b, c). The flow assigned to (b, a) will be 3 units.
University of Victoria – CSC 445/545 – Summer 2021 33
Example 4 (8)
Supply/Cost Flow
a
0
b
0
c-6
d
-6
e
-2
f
9
g
5
48
28
10
7
65
7
38
15
56
48108
24
33
19
a
0
b
-7
c48
d
28
e
-21
f
-56
g
-40
6
6
3
9
3
2
31
10
21
73
64
-14
8
End of Iteration 2. Total cost is 1118.
University of Victoria – CSC 445/545 – Summer 2021 34
Example 4 (9)
Supply/Cost Flow
a
0
b
0
c-6
d
-6
e
-2
f
9
g
5
48
28
10
7
65
7
38
15
56
48108
24
33
19
a
0
b
-7
c48
d
28
e
-21
f
-56
g
-40
6
6
3
9
3
2
31
10
21
73
64
4
8
-1
Iteration 3. Entering arc is (f , b).
University of Victoria – CSC 445/545 – Summer 2021 35
Example 4 (10)
Supply/Cost Flow
a
0
b
0
c-6
d
-6
e
-2
f
9
g
5
48
28
10
7
65
7
38
15
56
48108
24
33
19
a
0
b
-7
c48
d
28
e
-21
f
-56
g
-40
?
3
9
With (f , b) entering, the leaving arc is (f , a). The flow assigned to (f , b) will be 9 units.
University of Victoria – CSC 445/545 – Summer 2021 36
Example 4 (11)
Supply/Cost Flow
a
0
b
0
c-6
d
-6
e
-2
f
9
g
5
48
28
10
7
65
7
38
15
56
48108
24
33
19
a
0
b
-7
c48
d
28
e
-21
f
-55
g
-40
6
6
12
9 3
2
31
10
21
73
64
1
5
9
Optimal. Total cost is 1109.
University of Victoria – CSC 445/545 – Summer 2021 37