CSC 445/545 – Summer 2021 – Network Simplex Examples III
CSC 445/545 – Summer 2021
Network Simplex Examples III
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 basis that is neither primal nor
dual feasible and applying a two phase method to solve the problem.
The examples here all use the network equivalent of the largest coefficient rule to select the
entering arc (primal pivoting) or leaving arc (dual pivoting) at each step.
University of Victoria – CSC 445/545 – Summer 2021 2
Example 1a (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
2
d
6
e
9
f14
g
-4
h
-2
i
2
-8
-9
-4
-8
2
10 4
5
-1
10
15
-11 -11
Task: Starting from the infeasible basis above, use a two phase method (dual first, primal
second) to solve the network flow problem.
University of Victoria – CSC 445/545 – Summer 2021 3
Example 1a (2)
Supply/Cost Flow
a
-6
b
-5
c
1
d
3
e
6
f-2
g
10
h
-6
i
1
0
0
0
0
0
0
0
0
0
0
0
0
0
a
0
b
0
c
0
d
0
e
0
f0
g
0
h
0
i
0
-8
-9
-4
-8
2
10 4
5
0
0
0
0 0
Phase One: All edge costs are temporarily set to zero (shown in orange on the left). This
makes any basis dual feasible, so we can use the Dual Network Simplex Method to find an
optimal flow for the modified graph.
University of Victoria – CSC 445/545 – Summer 2021 4
Example 1a (3)
Supply/Cost Flow
a
-6
b
-5
c
1
d
3
e
6
f-2
g
10
h
-6
i
1
0
0
0
0
0
0
0
0
0
0
0
0
0
a
0
b
0
c
0
d
0
e
0
f0
g
0
h
0
i
0
-8
-4
-8
2
10 4
5
0
0
0
0 0
-9
Iteration 1. Leaving arc is (b, c).
University of Victoria – CSC 445/545 – Summer 2021 5
Example 1a (4)
Supply/Cost Flow
a
-6
b
-5
c
1
d
3
e
6
f-2
g
10
h
-6
i
1
0
0
0
0
0
0
0
0
0
0
0
0
0
a
0
b
0
c
0
d
0
e
0
f0
g
0
h
0
i
0
0
0 0
?
With (b, c) leaving, the entering arc is (d , e). The flow assigned to (d , e) will be 9 units.
University of Victoria – CSC 445/545 – Summer 2021 6
Example 1a (5)
Supply/Cost Flow
a
-6
b
-5
c
1
d
3
e
6
f-2
g
10
h
-6
i
1
0
0
0
0
0
0
0
0
0
0
0
0
0
a
0
b
0
c
0
d
0
e
0
f0
g
0
h
0
i
0
-8
-13
1
9
2
10 4
5
0
0
0
0 0
End of Iteration 1. Total cost is 0.
University of Victoria – CSC 445/545 – Summer 2021 7
Example 1a (6)
Supply/Cost Flow
a
-6
b
-5
c
1
d
3
e
6
f-2
g
10
h
-6
i
1
0
0
0
0
0
0
0
0
0
0
0
0
0
a
0
b
0
c
0
d
0
e
0
f0
g
0
h
0
i
0
-8
1
9
2
10 4
5
0
0
0
0 0
-13
Iteration 2. Leaving arc is (b, e).
University of Victoria – CSC 445/545 – Summer 2021 8
Example 1a (7)
Supply/Cost Flow
a
-6
b
-5
c
1
d
3
e
6
f-2
g
10
h
-6
i
1
0
0
0
0
0
0
0
0
0
0
0
0
0
a
0
b
0
c
0
d
0
e
0
f0
g
0
h
0
i
0
0
0
0
?
With (b, e) leaving, the entering arc is (e, a). The flow assigned to (e, a) will be 13 units.
University of Victoria – CSC 445/545 – Summer 2021 9
Example 1a (8)
Supply/Cost Flow
a
-6
b
-5
c
1
d
3
e
6
f-2
g
10
h
-6
i
1
0
0
0
0
0
0
0
0
0
0
0
0
0
a
0
b
0
c
0
d
0
e
0
f0
g
0
h
0
i
0
5
1
9
13
2
10 4
5
0
0
0
0 0
Optimal. Total cost is 0.
University of Victoria – CSC 445/545 – Summer 2021 10
Example 1a (9)
Supply/Cost Flow
a
-6
b
-5
c
1
d
3
e
6
f-2
g
10
h
-6
i
1
0
0
0
0
0
0
0
0
0
0
0
0
0
a
0
b
0
c
0
d
0
e
0
f0
g
0
h
0
i
0
5
1
9
13
2
10 4
5
0
0
0
0 0
The optimal basis for the modified graph will be both primal and dual feasible. Since the
vertex supply values for the modified graph match those of the original graph, this basis will
be primal feasible for the original graph.
University of Victoria – CSC 445/545 – Summer 2021 11
Example 1a (10)
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
f4
g
-13
h
-11
i
-7
5
1
9
13
2
10 4
5
9
10
5
-10 -10
Phase Two: Starting from the feasible basis produced by Phase One, we can now run the
Primal Network Simplex Method.
University of Victoria – CSC 445/545 – Summer 2021 12
Example 1a (11)
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
f4
g
-13
h
-11
i
-7
5
1
9
13
2
10 4
5
9
10
5
-10-10
Iteration 1. Entering arc is (g , f ).
University of Victoria – CSC 445/545 – Summer 2021 13
Example 1a (12)
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
f4
g
-13
h
-11
i
-7
?
2
9
5
410
With (g , f ) entering, the leaving arc is (e, f ). The flow assigned to (g , f ) will be 2 units.
University of Victoria – CSC 445/545 – Summer 2021 14
Example 1a (13)
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
End of Iteration 1. Total cost is 86.
University of Victoria – CSC 445/545 – Summer 2021 15
Example 1a (14)
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 2. Entering arc is (f , a).
University of Victoria – CSC 445/545 – Summer 2021 16
Example 1a (15)
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 17
Example 1a (16)
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 2. Total cost is 76.
University of Victoria – CSC 445/545 – Summer 2021 18
Example 1a (17)
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 3. Entering arc is (i , f ).
University of Victoria – CSC 445/545 – Summer 2021 19
Example 1a (18)
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 20
Example 1a (19)
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 21
Example 1b (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
2
d
6
e
9
f14
g
-4
h
-2
i
2
-8
-9
-4
-8
2
10 4
5
-1
10
15
-11 -11
Task: Starting from the infeasible basis above, use a two phase method (primal first, dual
second) to solve the network flow problem.
University of Victoria – CSC 445/545 – Summer 2021 22
Example 1b (2)
Supply/Cost Flow
a
0
b
0
c
0
d
0
e
0
f0
g
0
h
0
i
0
1
1
8
4
2
1
5
1
2
7
4
4
1
a
0
b
1
c
2
d
6
e
9
f14
g
-4
h
-2
i
2
0
0
0
0
0
0 0
0
-1
10
15
-11 -11
Phase One: All vertex supplies are temporarily set to zero (shown in orange on the left).
This makes any basis primal feasible, so we can use the Primal Network Simplex Method to
find an optimal flow for the modified graph.
University of Victoria – CSC 445/545 – Summer 2021 23
Example 1b (3)
Supply/Cost Flow
a
0
b
0
c
0
d
0
e
0
f0
g
0
h
0
i
0
1
1
8
4
2
1
5
1
2
7
4
4
1
a
0
b
1
c
2
d
6
e
9
f14
g
-4
h
-2
i
2
0
0
0
0
0
0 0
0
-1
10
15
-11-11
Iteration 1. Entering arc is (g , f ).
University of Victoria – CSC 445/545 – Summer 2021 24
Example 1b (4)
Supply/Cost Flow
a
0
b
0
c
0
d
0
e
0
f0
g
0
h
0
i
0
1
1
8
4
2
1
5
1
2
7
4
4
1
a
0
b
1
c
2
d
6
e
9
f14
g
-4
h
-2
i
2
?
0
0
0
0
0
00
With (g , f ) entering, the leaving arc is (b, e). The flow assigned to (g , f ) will be 0 units.
University of Victoria – CSC 445/545 – Summer 2021 25
Example 1b (5)
Supply/Cost Flow
a
0
b
0
c
0
d
0
e
0
f0
g
0
h
0
i
0
1
1
8
4
2
1
5
1
2
7
4
4
1
a
0
b
1
c
2
d
6
e
-2
f3
g
-4
h
-2
i
2
0
0
0
0
0
0
0
0
11
10
-1
4
0
End of Iteration 1. Total cost is 0.
University of Victoria – CSC 445/545 – Summer 2021 26
Example 1b (6)
Supply/Cost Flow
a
0
b
0
c
0
d
0
e
0
f0
g
0
h
0
i
0
1
1
8
4
2
1
5
1
2
7
4
4
1
a
0
b
1
c
2
d
6
e
-2
f3
g
-4
h
-2
i
2
0
0
0
0
0
0
0
0
11
10
4
0
-1
Iteration 2. Entering arc is (e, a).
University of Victoria – CSC 445/545 – Summer 2021 27
Example 1b (7)
Supply/Cost Flow
a
0
b
0
c
0
d
0
e
0
f0
g
0
h
0
i
0
1
1
8
4
2
1
5
1
2
7
4
4
1
a
0
b
1
c
2
d
6
e
-2
f3
g
-4
h
-2
i
2
?
0
0
0
0
00
0
0
With (e, a) entering, the leaving arc is (e, f ). The flow assigned to (e, a) will be 0 units.
University of Victoria – CSC 445/545 – Summer 2021 28
Example 1b (8)
Supply/Cost Flow
a
0
b
0
c
0
d
0
e
0
f0
g
0
h
0
i
0
1
1
8
4
2
1
5
1
2
7
4
4
1
a
0
b
1
c
2
d
6
e
-1
f3
g
-4
h
-2
i
2
0
0
0
0
0
0
0
0
10
9
1
4
0
Optimal. Total cost is 0.
University of Victoria – CSC 445/545 – Summer 2021 29
Example 1b (9)
Supply/Cost Flow
a
0
b
0
c
0
d
0
e
0
f0
g
0
h
0
i
0
1
1
8
4
2
1
5
1
2
7
4
4
1
a
0
b
1
c
2
d
6
e
-1
f3
g
-4
h
-2
i
2
0
0
0
0
0
0
0
0
10
9
1
4
0
The optimal basis for the modified graph will be both primal and dual feasible. Since the
vertex supply values for the modified graph match those of the original graph, this basis will
be dual feasible for the original graph.
University of Victoria – CSC 445/545 – Summer 2021 30
Example 1b (10)
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
2
d
6
e
-1
f3
g
-4
h
-2
i
2
-2
-7
-6
6
8
2
2
3
10
9
1
4
0
Phase Two: Starting from the feasible basis produced by Phase One, we can now run the
Dual Network Simplex Method.
University of Victoria – CSC 445/545 – Summer 2021 31
Example 1b (11)
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
2
d
6
e
-1
f3
g
-4
h
-2
i
2
-2
-6
6
8
2
2
3
10
9
1
4
0
-7
Iteration 1. Leaving arc is (b, c).
University of Victoria – CSC 445/545 – Summer 2021 32
Example 1b (12)
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
2
d
6
e
-1
f3
g
-4
h
-2
i
2
1
9
4
?
With (b, c) leaving, the entering arc is (f , a). The flow assigned to (f , a) will be 7 units.
University of Victoria – CSC 445/545 – Summer 2021 33
Example 1b (13)
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
-2
d
2
e
-1
f-1
g
-8
h
-6
i
-2
5
1
6
7
1
9
-5
-4
4
10
5
5
0
End of Iteration 1. Total cost is 51.
University of Victoria – CSC 445/545 – Summer 2021 34
Example 1b (14)
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
-2
d
2
e
-1
f-1
g
-8
h
-6
i
-2
5
1
6
7
1
9
-4
4
10
5
5
0
-5
Iteration 2. Leaving arc is (h, i).
University of Victoria – CSC 445/545 – Summer 2021 35
Example 1b (15)
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
-2
d
2
e
-1
f-1
g
-8
h
-6
i
-2
4
5
0
?
With (h, i) leaving, the entering arc is (i , f ). The flow assigned to (i , f ) will be 5 units.
University of Victoria – CSC 445/545 – Summer 2021 36
Example 1b (16)
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
-2
d
2
e
-1
f-1
g
-8
h
-6
i
-2
5
1
6
7
6
4
-4
5
4
10
5
5
0
End of Iteration 2. Total cost is 51.
University of Victoria – CSC 445/545 – Summer 2021 37
Example 1b (17)
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
-2
d
2
e
-1
f-1
g
-8
h
-6
i
-2
5
1
6
7
6
4 5
4
10
5
5
0
-4
Iteration 3. Leaving arc is (i , d).
University of Victoria – CSC 445/545 – Summer 2021 38
Example 1b (18)
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
-2
d
2
e
-1
f-1
g
-8
h
-6
i
-2
4
5
?
With (i , d) leaving, the entering arc is (d , e). The flow assigned to (d , e) will be 4 units.
University of Victoria – CSC 445/545 – Summer 2021 39
Example 1b (19)
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 40
Example 2a (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
2
d
2
e
4
f-1
g
-8
h
-6
i
-2
4
-1
3
9
12
6
4 1
5
4
5
0
0
Task: Starting from the infeasible basis above, use a two phase method (dual first, primal
second) to solve the network flow problem.
University of Victoria – CSC 445/545 – Summer 2021 41
Example 2a (2)
Supply/Cost Flow
a
-6
b
-5
c
1
d
3
e
6
f-2
g
10
h
-6
i
1
0
0
0
0
0
0
0
0
0
0
0
0
0
a
0
b
0
c
0
d
0
e
0
f0
g
0
h
0
i
0
4
-1
3
9
12
6
4 1
0
0
0
0
0
Phase One: All edge costs are temporarily set to zero (shown in orange on the left). This
makes any basis dual feasible, so we can use the Dual Network Simplex Method to find an
optimal flow for the modified graph.
University of Victoria – CSC 445/545 – Summer 2021 42
Example 2a (3)
Supply/Cost Flow
a
-6
b
-5
c
1
d
3
e
6
f-2
g
10
h
-6
i
1
0
0
0
0
0
0
0
0
0
0
0
0
0
a
0
b
0
c
0
d
0
e
0
f0
g
0
h
0
i
0
4
3
9
12
6
4 1
0
0
0
0
0
-1
Iteration 1. Leaving arc is (b, c).
University of Victoria – CSC 445/545 – Summer 2021 43
Example 2a (4)
Supply/Cost Flow
a
-6
b
-5
c
1
d
3
e
6
f-2
g
10
h
-6
i
1
0
0
0
0
0
0
0
0
0
0
0
0
0
a
0
b
0
c
0
d
0
e
0
f0
g
0
h
0
i
0
0
?
With (b, c) leaving, the entering arc is (c , d). The flow assigned to (c , d) will be 1 units.
University of Victoria – CSC 445/545 – Summer 2021 44
Example 2a (5)
Supply/Cost Flow
a
-6
b
-5
c
1
d
3
e
6
f-2
g
10
h
-6
i
1
0
0
0
0
0
0
0
0
0
0
0
0
0
a
0
b
0
c
0
d
0
e
0
f0
g
0
h
0
i
0
5
1
4
10
13
6
4 1
0
00
0
0
Optimal. Total cost is 0.
University of Victoria – CSC 445/545 – Summer 2021 45
Example 2a (6)
Supply/Cost Flow
a
-6
b
-5
c
1
d
3
e
6
f-2
g
10
h
-6
i
1
0
0
0
0
0
0
0
0
0
0
0
0
0
a
0
b
0
c
0
d
0
e
0
f0
g
0
h
0
i
0
5
1
4
10
13
6
4 1
0
00
0
0
The optimal basis for the modified graph will be both primal and dual feasible. Since the
vertex supply values for the modified graph match those of the original graph, this basis will
be primal feasible for the original graph.
University of Victoria – CSC 445/545 – Summer 2021 46
Example 2a (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
-2
d
2
e
4
f-1
g
-8
h
-6
i
-2
5
1
4
10
13
6
4 1
4
55
0
0
Phase Two: Starting from the feasible basis produced by Phase One, we can now run the
Primal Network Simplex Method.
University of Victoria – CSC 445/545 – Summer 2021 47
Example 2a (8)
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
-2
d
2
e
4
f-1
g
-8
h
-6
i
-2
5
1
4
10
13
6
4 1
4
55
0
0
Optimal. Total cost is 21.
University of Victoria – CSC 445/545 – Summer 2021 48
Example 2b (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
2
d
2
e
4
f-1
g
-8
h
-6
i
-2
4
-1
3
9
12
6
4 1
5
4
5
0
0
Task: Starting from the infeasible basis above, use a two phase method (primal first, dual
second) to solve the network flow problem.
University of Victoria – CSC 445/545 – Summer 2021 49
Example 2b (2)
Supply/Cost Flow
a
0
b
0
c
0
d
0
e
0
f0
g
0
h
0
i
0
1
1
8
4
2
1
-5
1
2
7
4
4
1
a
0
b
1
c
2
d
2
e
4
f-1
g
-8
h
-6
i
-2
0
0
0
0
0
0
0 0
5
4
5
0
0
Phase One: All vertex supplies are temporarily set to zero (shown in orange on the left).
This makes any basis primal feasible, so we can use the Primal Network Simplex Method to
find an optimal flow for the modified graph.
University of Victoria – CSC 445/545 – Summer 2021 50
Example 2b (3)
Supply/Cost Flow
a
0
b
0
c
0
d
0
e
0
f0
g
0
h
0
i
0
1
1
8
4
2
1
-5
1
2
7
4
4
1
a
0
b
1
c
2
d
2
e
4
f-1
g
-8
h
-6
i
-2
0
0
0
0
0
0
0 0
5
4
5
0
0
Optimal. Total cost is 0.
University of Victoria – CSC 445/545 – Summer 2021 51
Example 2b (4)
Supply/Cost Flow
a
0
b
0
c
0
d
0
e
0
f0
g
0
h
0
i
0
1
1
8
4
2
1
-5
1
2
7
4
4
1
a
0
b
1
c
2
d
2
e
4
f-1
g
-8
h
-6
i
-2
0
0
0
0
0
0
0 0
5
4
5
0
0
The optimal basis for the modified graph will be both primal and dual feasible. Since the
vertex supply values for the modified graph match those of the original graph, this basis will
be dual feasible for the original graph.
University of Victoria – CSC 445/545 – Summer 2021 52
Example 2b (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
2
d
2
e
4
f-1
g
-8
h
-6
i
-2
4
-1
3
9
12
6
4 1
5
4
5
0
0
Phase Two: Starting from the feasible basis produced by Phase One, we can now run the
Dual Network Simplex Method.
University of Victoria – CSC 445/545 – Summer 2021 53
Example 2b (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
2
d
2
e
4
f-1
g
-8
h
-6
i
-2
4
3
9
12
6
4 1
5
4
5
0
0
-1
Iteration 1. Leaving arc is (b, c).
University of Victoria – CSC 445/545 – Summer 2021 54
Example 2b (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
2
d
2
e
4
f-1
g
-8
h
-6
i
-2
4
?
With (b, c) leaving, the entering arc is (c, d). The flow assigned to (c , d) will be 1 units.
University of Victoria – CSC 445/545 – Summer 2021 55
Example 2b (8)
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
-2
d
2
e
4
f-1
g
-8
h
-6
i
-2
5
1
4
10
13
6
4 1
4
55
0
0
Optimal. Total cost is 21.
University of Victoria – CSC 445/545 – Summer 2021 56
Example 3a (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
-2
e-12 f -17
g
-19
h
-17
i
-15
j
-18
-4 1 -4
7
7
-3
-2 -6
1
24
12
25
2011
1
5
Task: Starting from the infeasible basis above, use a two phase method (dual first, primal
second) to solve the network flow problem.
University of Victoria – CSC 445/545 – Summer 2021 57
Example 3a (2)
Supply/Cost Flow
a
-3
b
-5
c
-3
d
4
e10 f 3
g
-2
h
-4
i
-1
j
1
0
0
0
0 0
0
00 0
0
0
0
0
0 0
0
a
0
b
0
c
0
d
0
e0 f 0
g
0
h
0
i
0
j
0
-4 1 -4
7
7
-3
-2 -6
1
0
0
0
00
0
0
Phase One: All edge costs are temporarily set to zero (shown in orange on the left). This
makes any basis dual feasible, so we can use the Dual Network Simplex Method to find an
optimal flow for the modified graph.
University of Victoria – CSC 445/545 – Summer 2021 58
Example 3a (3)
Supply/Cost Flow
a
-3
b
-5
c
-3
d
4
e10 f 3
g
-2
h
-4
i
-1
j
1
0
0
0
0 0
0
00 0
0
0
0
0
0 0
0
a
0
b
0
c
0
d
0
e0 f 0
g
0
h
0
i
0
j
0
-4 1 -4
7
7
-3
-2
1
0
0
0
00
0
0-6
Iteration 1. Leaving arc is (h, i).
University of Victoria – CSC 445/545 – Summer 2021 59
Example 3a (4)
Supply/Cost Flow
a
-3
b
-5
c
-3
d
4
e10 f 3
g
-2
h
-4
i
-1
j
1
0
0
0
0 0
0
00 0
0
0
0
0
0 0
0
a
0
b
0
c
0
d
0
e0 f 0
g
0
h
0
i
0
j
0
0
0
?
With (h, i) leaving, the entering arc is (a, g). The flow assigned to (a, g) will be 6 units.
University of Victoria – CSC 445/545 – Summer 2021 60
Example 3a (5)
Supply/Cost Flow
a
-3
b
-5
c
-3
d
4
e10 f 3
g
-2
h
-4
i
-1
j
1
0
0
0
0 0
0
00 0
0
0
0
0
0 0
0
a
0
b
0
c
0
d
0
e0 f 0
g
0
h
0
i
0
j
0
6
-4 1 -4
13
1
3
4
1
0
0
00
0
0 0
End of Iteration 1. Total cost is 0.
University of Victoria – CSC 445/545 – Summer 2021 61
Example 3a (6)
Supply/Cost Flow
a
-3
b
-5
c
-3
d
4
e10 f 3
g
-2
h
-4
i
-1
j
1
0
0
0
0 0
0
00 0
0
0
0
0
0 0
0
a
0
b
0
c
0
d
0
e0 f 0
g
0
h
0
i
0
j
0
6
1 -4
13
1
3
4
1
0
0
00
0
0 0
-4
Iteration 2. Leaving arc is (b, a).
University of Victoria – CSC 445/545 – Summer 2021 62
Example 3a (7)
Supply/Cost Flow
a
-3
b
-5
c
-3
d
4
e10 f 3
g
-2
h
-4
i
-1
j
1
0
0
0
0 0
0
00 0
0
0
0
0
0 0
0
a
0
b
0
c
0
d
0
e0 f 0
g
0
h
0
i
0
j
0
0
0
00
?
With (b, a) leaving, the entering arc is (e, c). The flow assigned to (e, c) will be 4 units.
University of Victoria – CSC 445/545 – Summer 2021 63
Example 3a (8)
Supply/Cost Flow
a
-3
b
-5
c
-3
d
4
e10 f 3
g
-2
h
-4
i
-1
j
1
0
0
0
0 0
0
00 0
0
0
0
0
0 0
0
a
0
b
0
c
0
d
0
e0 f 0
g
0
h
0
i
0
j
0
6
5 -4
9 4
1
3
4
1
0
0
0
0
0
0 0
End of Iteration 2. Total cost is 0.
University of Victoria – CSC 445/545 – Summer 2021 64
Example 3a (9)
Supply/Cost Flow
a
-3
b
-5
c
-3
d
4
e10 f 3
g
-2
h
-4
i
-1
j
1
0
0
0
0 0
0
00 0
0
0
0
0
0 0
0
a
0
b
0
c
0
d
0
e0 f 0
g
0
h
0
i
0
j
0
6
5
9 4
1
3
4
1
0
0
0
0
0
0 0
-4
Iteration 3. Leaving arc is (c , d).
University of Victoria – CSC 445/545 – Summer 2021 65
Example 3a (10)
Supply/Cost Flow
a
-3
b
-5
c
-3
d
4
e10 f 3
g
-2
h
-4
i
-1
j
1
0
0
0
0 0
0
00 0
0
0
0
0
0 0
0
a
0
b
0
c
0
d
0
e0 f 0
g
0
h
0
i
0
j
0
0
0
?
With (c , d) leaving, the entering arc is (d , f ). The flow assigned to (d , f ) will be 4 units.
University of Victoria – CSC 445/545 – Summer 2021 66
Example 3a (11)
Supply/Cost Flow
a
-3
b
-5
c
-3
d
4
e10 f 3
g
-2
h
-4
i
-1
j
1
0
0
0
0 0
0
00 0
0
0
0
0
0 0
0
a
0
b
0
c
0
d
0
e0 f 0
g
0
h
0
i
0
j
0
6
5
49 8
1
7
4
1
0
0
0
0
0
0 0
Optimal. Total cost is 0.
University of Victoria – CSC 445/545 – Summer 2021 67
Example 3a (12)
Supply/Cost Flow
a
-3
b
-5
c
-3
d
4
e10 f 3
g
-2
h
-4
i
-1
j
1
0
0
0
0 0
0
00 0
0
0
0
0
0 0
0
a
0
b
0
c
0
d
0
e0 f 0
g
0
h
0
i
0
j
0
6
5
49 8
1
7
4
1
0
0
0
0
0
0 0
The optimal basis for the modified graph will be both primal and dual feasible. Since the
vertex supply values for the modified graph match those of the original graph, this basis will
be primal feasible for the original graph.
University of Victoria – CSC 445/545 – Summer 2021 68
Example 3a (13)
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
Phase Two: Starting from the feasible basis produced by Phase One, we can now run the
Primal Network Simplex Method.
University of Victoria – CSC 445/545 – Summer 2021 69
Example 3a (14)
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 70
Example 3b (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
-2
e-12 f -17
g
-19
h
-17
i
-15
j
-18
-4 1 -4
7
7
-3
-2 -6
1
24
12
25
2011
1
5
Task: Starting from the infeasible basis above, use a two phase method (primal first, dual
second) to solve the network flow problem.
University of Victoria – CSC 445/545 – Summer 2021 71
Example 3b (2)
Supply/Cost Flow
a
0
b
0
c
0
d
0
e0 f 0
g
0
h
0
i
0
j
0
5
10
10
2 10
9
512 11
2
5
2
1
2 2
1
a
0
b
-10
c
-12
d
-2
e-12 f -17
g
-19
h
-17
i
-15
j
-18
0 0 0
0
0
0
0 0
0
24
12
25
2011
1
5
Phase One: All vertex supplies are temporarily set to zero (shown in orange on the left).
This makes any basis primal feasible, so we can use the Primal Network Simplex Method to
find an optimal flow for the modified graph.
University of Victoria – CSC 445/545 – Summer 2021 72
Example 3b (3)
Supply/Cost Flow
a
0
b
0
c
0
d
0
e0 f 0
g
0
h
0
i
0
j
0
5
10
10
2 10
9
512 11
2
5
2
1
2 2
1
a
0
b
-10
c
-12
d
-2
e-12 f -17
g
-19
h
-17
i
-15
j
-18
0 0 0
0
0
0
0 0
0
24
12
25
2011
1
5
Optimal. Total cost is 0.
University of Victoria – CSC 445/545 – Summer 2021 73
Example 3b (4)
Supply/Cost Flow
a
0
b
0
c
0
d
0
e0 f 0
g
0
h
0
i
0
j
0
5
10
10
2 10
9
512 11
2
5
2
1
2 2
1
a
0
b
-10
c
-12
d
-2
e-12 f -17
g
-19
h
-17
i
-15
j
-18
0 0 0
0
0
0
0 0
0
24
12
25
2011
1
5
The optimal basis for the modified graph will be both primal and dual feasible. Since the
vertex supply values for the modified graph match those of the original graph, this basis will
be dual feasible for the original graph.
University of Victoria – CSC 445/545 – Summer 2021 74
Example 3b (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
-2
e-12 f -17
g
-19
h
-17
i
-15
j
-18
-4 1 -4
7
7
-3
-2 -6
1
24
12
25
2011
1
5
Phase Two: Starting from the feasible basis produced by Phase One, we can now run the
Dual Network Simplex Method.
University of Victoria – CSC 445/545 – Summer 2021 75
Example 3b (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
-2
e-12 f -17
g
-19
h
-17
i
-15
j
-18
-4 1 -4
7
7
-3
-2
1
24
12
25
2011
1
5-6
Iteration 1. Leaving arc is (h, i).
University of Victoria – CSC 445/545 – Summer 2021 76
Example 3b (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
-10
c
-12
d
-2
e-12 f -17
g
-19
h
-17
i
-15
j
-18
1
24
?
With (h, i) leaving, the entering arc is (a, g). The flow assigned to (a, g) will be 6 units.
University of Victoria – CSC 445/545 – Summer 2021 77
Example 3b (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
-10
c
-12
d
-2
e-12 f -17
g
5
h
7
i
-15
j
-18
6
-4 1 -4
13
1
3
4
1
12
25
2011
25
24 5
End of Iteration 1. Total cost is 134.
University of Victoria – CSC 445/545 – Summer 2021 78
Example 3b (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
-10
c
-12
d
-2
e-12 f -17
g
5
h
7
i
-15
j
-18
6
1 -4
13
1
3
4
1
12
25
2011
25
24 5
-4
Iteration 2. Leaving arc is (b, a).
University of Victoria – CSC 445/545 – Summer 2021 79
Example 3b (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
-10
c
-12
d
-2
e-12 f -17
g
5
h
7
i
-15
j
-18
12
25
2011
?
With (b, a) leaving, the entering arc is (e, c). The flow assigned to (e, c) will be 4 units.
University of Victoria – CSC 445/545 – Summer 2021 80
Example 3b (11)
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
9
e-12 f -17
g
5
h
7
i
-15
j
-18
6
5 -4
9 4
1
3
4
1
11
23
36
31
25
24 5
End of Iteration 2. Total cost is 178.
University of Victoria – CSC 445/545 – Summer 2021 81
Example 3b (12)
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
9
e-12 f -17
g
5
h
7
i
-15
j
-18
6
5
9 4
1
3
4
1
11
23
36
31
25
24 5
-4
Iteration 3. Leaving arc is (c , d).
University of Victoria – CSC 445/545 – Summer 2021 82
Example 3b (13)
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
9
e-12 f -17
g
5
h
7
i
-15
j
-18
36
31
?
With (c , d) leaving, the entering arc is (d , f ). The flow assigned to (d , f ) will be 4 units.
University of Victoria – CSC 445/545 – Summer 2021 83
Example 3b (14)
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 84
Example 4a (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
-7
c48
d
28
e
10
f
-56
g
-32
6
6
2
0
14
-5
10
-10
73
33
-14 8
-23
(This is the motivating example from Chapter 14 of Vanderbei)
University of Victoria – CSC 445/545 – Summer 2021 85
Example 4a (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
-7
c48
d
28
e
10
f
-56
g
-32
6
6
2
0
14
-5
10
-10
73
33
-14 8
-23
Task: Starting from the infeasible basis above, use a two phase method (dual first, primal
second) to solve the network flow problem.
University of Victoria – CSC 445/545 – Summer 2021 86
Example 4a (3)
Supply/Cost Flow
a
0
b
0
c-6
d
-6
e
-2
f
9
g
5
0
0
0
0
0
0
0
0
0
00
0
0
0
a
0
b
0
c0
d
0
e
0
f
0
g
0
6
6
2
0
14
-5
0
0
0
0
00 0
0
Phase One: All edge costs are temporarily set to zero (shown in orange on the left). This
makes any basis dual feasible, so we can use the Dual Network Simplex Method to find an
optimal flow for the modified graph.
University of Victoria – CSC 445/545 – Summer 2021 87
Example 4a (4)
Supply/Cost Flow
a
0
b
0
c-6
d
-6
e
-2
f
9
g
5
0
0
0
0
0
0
0
0
0
00
0
0
0
a
0
b
0
c0
d
0
e
0
f
0
g
0
6
6
2
0
14
0
0
0
0
00 0
0
-5
Iteration 1. Leaving arc is (f , g).
University of Victoria – CSC 445/545 – Summer 2021 88
Example 4a (5)
Supply/Cost Flow
a
0
b
0
c-6
d
-6
e
-2
f
9
g
5
0
0
0
0
0
0
0
0
0
00
0
0
0
a
0
b
0
c0
d
0
e
0
f
0
g
0
0
0
?
With (f , g) leaving, the entering arc is (g , b). The flow assigned to (g , b) will be 5 units.
University of Victoria – CSC 445/545 – Summer 2021 89
Example 4a (6)
Supply/Cost Flow
a
0
b
0
c-6
d
-6
e
-2
f
9
g
5
0
0
0
0
0
0
0
0
0
00
0
0
0
a
0
b
0
c0
d
0
e
0
f
0
g
0
6
6
2
5
9
5
0
0
0
0
00
0
0
Optimal. Total cost is 0.
University of Victoria – CSC 445/545 – Summer 2021 90
Example 4a (7)
Supply/Cost Flow
a
0
b
0
c-6
d
-6
e
-2
f
9
g
5
0
0
0
0
0
0
0
0
0
00
0
0
0
a
0
b
0
c0
d
0
e
0
f
0
g
0
6
6
2
5
9
5
0
0
0
0
00
0
0
The optimal basis for the modified graph will be both primal and dual feasible. Since the
vertex supply values for the modified graph match those of the original graph, this basis will
be primal feasible for the original graph.
University of Victoria – CSC 445/545 – Summer 2021 91
Example 4a (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
10
f
-56
g
-40
6
6
2
5
9
5
10
-10
73
33
-14
8
-31
Phase Two: Starting from the feasible basis produced by Phase One, we can now run the
Primal Network Simplex Method.
University of Victoria – CSC 445/545 – Summer 2021 92
Example 4a (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
10
f
-56
g
-40
6
6
2
5
9
5
10
-10
73
33
-14
8
-31
Iteration 1. Entering arc is (g , e).
University of Victoria – CSC 445/545 – Summer 2021 93
Example 4a (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
10
f
-56
g
-40
?
2
5
5
With (g , e) entering, the leaving arc is (a, e). The flow assigned to (g , e) will be 2 units.
University of Victoria – CSC 445/545 – Summer 2021 94
Example 4a (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
-56
g
-40
6
6
3
9
3
2
31
10
21
73
64
-14
8
End of Iteration 1. Total cost is 1118.
University of Victoria – CSC 445/545 – Summer 2021 95
Example 4a (12)
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 2. Entering arc is (f , b).
University of Victoria – CSC 445/545 – Summer 2021 96
Example 4a (13)
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 97
Example 4a (14)
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 98
Example 4b (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
-7
c48
d
28
e
10
f
-56
g
-32
6
6
2
0
14
-5
10
-10
73
33
-14 8
-23
Task: Starting from the infeasible basis above, use a two phase method (primal first, dual
second) to solve the network flow problem.
University of Victoria – CSC 445/545 – Summer 2021 99
Example 4b (2)
Supply/Cost Flow
a
0
b
0
c0
d
0
e
0
f
0
g
0
48
28
10
7
65
7
38
15
56
48108
24
33
19
a
0
b
-7
c48
d
28
e
10
f
-56
g
-32
0
0
0
0
0
0
10
-10
73
33
-14 8
-23
Phase One: All vertex supplies are temporarily set to zero (shown in orange on the left).
This makes any basis primal feasible, so we can use the Primal Network Simplex Method to
find an optimal flow for the modified graph.
University of Victoria – CSC 445/545 – Summer 2021 100
Example 4b (3)
Supply/Cost Flow
a
0
b
0
c0
d
0
e
0
f
0
g
0
48
28
10
7
65
7
38
15
56
48108
24
33
19
a
0
b
-7
c48
d
28
e
10
f
-56
g
-32
0
0
0
0
0
0
10
-10
73
33
-14 8
-23
Iteration 1. Entering arc is (g , e).
University of Victoria – CSC 445/545 – Summer 2021 101
Example 4b (4)
Supply/Cost Flow
a
0
b
0
c0
d
0
e
0
f
0
g
0
48
28
10
7
65
7
38
15
56
48108
24
33
19
a
0
b
-7
c48
d
28
e
10
f
-56
g
-32
?
0
0
0
With (g , e) entering, the leaving arc is (a, e). The flow assigned to (g , e) will be 0 units.
University of Victoria – CSC 445/545 – Summer 2021 102
Example 4b (5)
Supply/Cost Flow
a
0
b
0
c0
d
0
e
0
f
0
g
0
48
28
10
7
65
7
38
15
56
48108
24
33
19
a
0
b
-7
c48
d
28
e
-13
f
-56
g
-32
0
0
0
0
0
0
23
10
13
73
56
-14 8
End of Iteration 1. Total cost is 0.
University of Victoria – CSC 445/545 – Summer 2021 103
Example 4b (6)
Supply/Cost Flow
a
0
b
0
c0
d
0
e
0
f
0
g
0
48
28
10
7
65
7
38
15
56
48108
24
33
19
a
0
b
-7
c48
d
28
e
-13
f
-56
g
-32
0
0
0
0
0
0
23
10
13
73
56
4 8-1
Iteration 2. Entering arc is (f , b).
University of Victoria – CSC 445/545 – Summer 2021 104
Example 4b (7)
Supply/Cost Flow
a
0
b
0
c0
d
0
e
0
f
0
g
0
48
28
10
7
65
7
38
15
56
48108
24
33
19
a
0
b
-7
c48
d
28
e
-13
f
-56
g
-32
?
0
0
With (f , b) entering, the leaving arc is (f , a). The flow assigned to (f , b) will be 0 units.
University of Victoria – CSC 445/545 – Summer 2021 105
Example 4b (8)
Supply/Cost Flow
a
0
b
0
c0
d
0
e
0
f
0
g
0
48
28
10
7
65
7
38
15
56
48108
24
33
19
a
0
b
-7
c48
d
28
e
-12
f
-55
g
-31
0
0
0
0
0
0
22
10
12
73
55
1
5 9
Optimal. Total cost is 0.
University of Victoria – CSC 445/545 – Summer 2021 106
Example 4b (9)
Supply/Cost Flow
a
0
b
0
c0
d
0
e
0
f
0
g
0
48
28
10
7
65
7
38
15
56
48108
24
33
19
a
0
b
-7
c48
d
28
e
-12
f
-55
g
-31
0
0
0
0
0
0
22
10
12
73
55
1
5 9
The optimal basis for the modified graph will be both primal and dual feasible. Since the
vertex supply values for the modified graph match those of the original graph, this basis will
be dual feasible for the original graph.
University of Victoria – CSC 445/545 – Summer 2021 107
Example 4b (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
-12
f
-55
g
-31
6
6
12
12
-3
2
22
10
12
73
55
1
5 9
Phase Two: Starting from the feasible basis produced by Phase One, we can now run the
Dual Network Simplex Method.
University of Victoria – CSC 445/545 – Summer 2021 108
Example 4b (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
-12
f
-55
g
-31
6
6
12
12
2
22
10
12
73
55
1
5 9
-3
Iteration 1. Leaving arc is (f , g).
University of Victoria – CSC 445/545 – Summer 2021 109
Example 4b (12)
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
-12
f
-55
g
-31
22
12
55
9
?
With (f , g) leaving, the entering arc is (g , b). The flow assigned to (g , b) will be 3 units.
University of Victoria – CSC 445/545 – Summer 2021 110
Example 4b (13)
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 111