CS计算机代考程序代写 CSC 445/545 – Summer 2021 – Network Simplex Examples I

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