Topic Review — Networks and Decision Mathematics — Solutions

← Networks and Decision Mathematics

This review covers project planning and critical path analysis, network flow and the max-flow min-cut theorem, the Hungarian algorithm for assignment problems, and two-person zero-sum games. Click each answer to reveal the worked solution.

Review Questions

1. An activity network has four activities: A (3 days, no predecessors); B (7 days, depends on A); C (4 days, depends on A); D (5 days, depends on both B and C). Find the Earliest Start Time (EST) for D and the minimum project completion time. ▶ Show Answer
   EST(A) = 0  •  EST(B) = 0+3 = 3  •  EST(C) = 0+3 = 3
   EST(D) = max(EST(B)+dur(B), EST(C)+dur(C)) = max(3+7, 3+4) = max(10, 7) = 10
   Minimum project completion time = 10 + 5 = 15 days
2. In a flow network, node X has two incoming edges: W→X carrying 8 units and Y→X carrying 3 units. There is one outgoing edge X→Z. How much flow must be on X→Z? ▶ Show Answer
   Flow conservation: total flow in = total flow out at every interior node.
   Flow in = 8 + 3 = 11 units.
   Flow on X→Z = 11 units
3. Row reduce the following cost matrix for a worker-task assignment problem (find the row minima and subtract each from its row):

   	Task X	Task Y	Task Z
   Worker 1	5	9	7
   Worker 2	3	6	4

   ▶ Show Answer
   Row minima: Worker 1 = 5, Worker 2 = 3.
   After subtracting each row minimum:

   	X	Y	Z
   1	0	4	2
   2	0	3	1

4. Find the saddle point (if it exists) for the following two-person zero-sum game and state the value of the game and optimal pure strategies.

   	B1	B2	B3
   A1	5	2	6
   A2	4	3	5
   A3	7	2	4

   ▶ Show Answer
   Row minima: A1=2, A2=3, A3=2. Maximin = 3 (A2).
   Column maxima: B1=7, B2=3, B3=6. Minimax = 3 (B2).
   Maximin = Minimax = 3 → Saddle point at (A2, B2).
   Optimal strategies: A plays A2; B plays B2. Value of the game = 3.
5. A flow network has two possible cuts: Cut 1 = {S→A, S→B} with capacities 8 and 6 (total 14); Cut 2 = {A→T, B→T} with capacities 9 and 7 (total 16). Which cut is the minimum cut? What does this tell you about the maximum flow? ▶ Show Answer
   Cut 1 capacity = 14 < Cut 2 capacity = 16. Cut 1 is the minimum cut.
   By the max-flow min-cut theorem, maximum flow = minimum cut capacity = 14 units. (No more than 14 units can flow from S to T regardless of routing, because every unit of flow must cross Cut 1.)
6. A project has activities A(2 days), B(4 days), C(6 days)→A, D(3 days)→A and B, E(5 days)→C and D, F(2 days)→E. Perform a complete forward and backward scan. Find all ESTs, LSTs, floats, and identify the critical path. ▶ Show Answer
   Forward scan:
   EST(A)=0, EST(B)=0, EST(C)=2, EST(D)=max(2, 4)=4, EST(E)=max(2+6, 4+3)=max(8,7)=8, EST(F)=13.
   Project duration = 13 + 2 = 15 days.
   
   Backward scan:
   LST(F)=13, LST(E)=8, LST(D)=8−3=5, LST(C)=8−6=2, LST(A)=min(2,5)−2=0, LST(B)=5−4=1.
   
   Floats: A=0−0=0 • B=1−0=1 • C=2−2=0 • D=5−4=1 • E=8−8=0 • F=13−13=0
   
   Critical path: A → C → E → F (all float = 0), duration = 2+6+5+2 = 15 days ✓
   Activities B and D are not critical (float = 1 each).
7. Use the Hungarian algorithm to find the minimum-cost assignment for the matrix below (costs in $00s). Show all steps.

   	Task X	Task Y	Task Z
   Worker 1	5	8	3
   Worker 2	7	4	6
   Worker 3	2	9	1

   ▶ Show Answer
   Row reduction (mins: 1=3, 2=4, 3=1):
   1:[2,5,0]   2:[3,0,2]   3:[1,8,0]
   
   Column reduction (col mins: X=1, Y=0, Z=0; subtract 1 from col X):
   1:[1,5,0]   2:[2,0,2]   3:[0,8,0]
   
   Zeros: (1,Z), (2,Y), (3,X), (3,Z).
   Independent zeros: 1→Z, 2→Y, 3→X → 3 zeros, one per row and column. Done.
   
   Optimal assignment: Worker 1→Task Z, Worker 2→Task Y, Worker 3→Task X
   Costs from original: 1→Z=3, 2→Y=4, 3→X=2
   Minimum total cost = 3+4+2 = 9 ($900)
8. Check for a saddle point in the payoff matrix below. If none exists, find the optimal mixed strategy for each player and the value of the game.

   	B1	B2
   A1	3	7
   A2	5	2

   ▶ Show Answer
   Row minima: A1=3, A2=2. Maximin=3 (A1). Column maxima: B1=5, B2=7. Minimax=5 (B1).
   3 ≠ 5 → No saddle point.
   
   a=3, b=7, c=5, d=2. D = (3+2)−(7+5) = 5−12 = −7
   Row player: p = (2−5)/(−7) = (−3)/(−7) = 3/7 (A plays A1 with prob 3/7, A2 with prob 4/7)
   Column player: q = (2−7)/(−7) = (−5)/(−7) = 5/7 (B plays B1 with prob 5/7, B2 with prob 2/7)
   Value of the game: V = (3×2−7×5)/(−7) = (6−35)/(−7) = (−29)/(−7) = 29/7 ≈ 4.14
   The game favours A (V > 0).
9. Find the maximum flow in the network below using augmenting paths and verify your answer with a minimum cut.
   • S→A = 8, S→B = 6
   • A→C = 5, A→D = 4
   • B→C = 3, B→D = 7
   • C→T = 6, D→T = 9
   ▶ Show Answer
   Augmenting paths:
   S→A→C→T: min(8,5,6)=5. Remaining: S→A=3, A→C=0, C→T=1.
   S→A→D→T: min(3,4,9)=3. Remaining: S→A=0, A→D=1, D→T=6.
   S→B→D→T: min(6,7,6)=6. Remaining: S→B=0, B→D=1, D→T=0.
   S→A and S→B both saturated → no more augmenting paths.
   
   Maximum flow = 5+3+6 = 14 units
   
   Verification: Cut {S→A=8, S→B=6}: capacity = 8+6 = 14 = max flow ✓
10. A project has a minimum completion time of 18 days. Activity M is not on the critical path and has a float of 5 days.
    • (a) Activity M is delayed 3 days. What is the new completion time?
    • (b) Activity M is delayed 7 days. What is the new completion time?
    • (c) A critical activity with duration 8 days is shortened to 5 days. What is the new completion time (assume no other path becomes critical)?
    ▶ Show Answer
    (a) Delay = 3 days < float (5 days). No change: project still completes in 18 days.
    
    (b) Delay = 7 days > float (5 days). Exceeds float by 7−5 = 2 days.
    New completion time = 18 + 2 = 20 days.
    
    (c) Critical activity reduced by 8−5 = 3 days. Critical path shortens by 3 days.
    New completion time = 18−3 = 15 days.
11. Apply the Hungarian algorithm to the following 4×4 cost matrix (one-to-one assignment of 4 managers to 4 projects, costs in $000s). Find the optimal assignment and minimum total cost.

    	P1	P2	P3	P4
    M1	8	5	7	4
    M2	3	6	2	9
    M3	7	4	8	3
    M4	5	8	3	6

    ▶ Show Answer
    Row reduction (mins: M1=4, M2=2, M3=3, M4=3):
    M1:[4,1,3,0]   M2:[1,4,0,7]   M3:[4,1,5,0]   M4:[2,5,0,3]
    
    Column reduction (col mins: P1=1, P2=1, P3=0, P4=0; subtract 1 from P1 and P2):
    M1:[3,0,3,0]   M2:[0,3,0,7]   M3:[3,0,5,0]   M4:[1,4,0,3]
    
    Zeros: (M1,P2), (M1,P4), (M2,P1), (M2,P3), (M3,P2), (M3,P4), (M4,P3)
    Independent zeros: M2→P1, M1→P2, M3→P4, M4→P3 (all different rows and columns). Done.
    
    Optimal assignment: M1→P2, M2→P1, M3→P4, M4→P3
    Costs from original: M1→P2=5, M2→P1=3, M3→P4=3, M4→P3=3
    Minimum total cost = 5+3+3+3 = 14 ($14,000)
12. A flow network currently has a maximum flow of 16 units. The minimum cut consists of two edges: A→T (capacity 9) and B→T (capacity 7), giving a minimum cut of 16. Engineers need to increase the maximum flow to 20 units.
    • (a) Why can’t the current network carry 20 units?
    • (b) What is the minimum total capacity upgrade needed, and how could it be applied?
    ▶ Show Answer
    (a) The max-flow min-cut theorem states maximum flow = minimum cut = 16. Since 16 < 20, the current bottleneck (cut {A→T=9, B→T=7}=16) prevents 20 units from reaching T. The network cannot carry 20 units without upgrading the minimum cut.
    
    (b) Need to increase minimum cut capacity from 16 to at least 20 → add at least 4 units of capacity to edges in the minimum cut.
    Options:
    • Upgrade A→T from 9 to 13 (+4): new cut = 13+7 = 20 ✓
    • Upgrade B→T from 7 to 11 (+4): new cut = 9+11 = 20 ✓
    • Split: e.g. A→T to 11 (+2) and B→T to 9 (+2): new cut = 20 ✓
    Upgrading edges outside the minimum cut has no effect on max flow.
13. A project has two parallel critical paths, both 20 days long: Path 1: A(3)+C(5)+E(8)+G(4)=20 and Path 2: B(6)+D(7)+F(3)+G(4)=20. Note that G is shared by both paths.
    • (a) A project manager reduces activity C from 5 to 2 days (saving 3 days). Does the project finish in 17 days? Explain.
    • (b) What is the most efficient single change to reduce the project duration to 17 days?
    ▶ Show Answer
    (a) Reducing C shortens Path 1 to 3+2+8+4=17 days. But Path 2 remains at 6+7+3+4=20 days.
    No — the project still takes 20 days because Path 2 is unchanged and determines the critical length.
    
    (b) The most efficient strategy is to reduce activity G by 3 days (G is shared by both paths).
    New Path 1: 3+5+8+1 = 17 ✓  New Path 2: 6+7+3+1 = 17 ✓
    Both paths are shortened to 17 days with just one change, whereas reducing activities in only one path requires changes to both Path 1 and Path 2 separately.
14. Two sports teams (A and B) simultaneously choose an offensive or defensive play. The payoff matrix (yards gained by A) is shown below. Find the optimal mixed strategy for each team and the expected yards gained by A per play.

    	B: Rush defence	B: Pass defence
    A: Rush play	3	8
    A: Pass play	6	1

    ▶ Show Answer
    Row minima: Rush=3, Pass=1. Maximin=3. Column maxima: Rush-D=6, Pass-D=8. Minimax=6. 3≠6 → no saddle point.
    
    a=3, b=8, c=6, d=1. D = (3+1)−(8+6) = 4−14 = −10
    Team A: p = (1−6)/(−10) = 1/2 (Rush with prob 1/2, Pass with prob 1/2)
    Team B: q = (1−8)/(−10) = 7/10 (Rush defence with prob 7/10, Pass defence with prob 3/10)
    Value: V = (3×1−8×6)/(−10) = (3−48)/(−10) = 4.5 yards per play
    Team A gains 4.5 yards on average each play when both teams use their optimal strategies.
15. A construction company uses three decision-making techniques for a new warehouse project.
    • Critical path: The main project path is P(4 wk)→Q(7 wk)→R(5 wk)→S(3 wk). Activity T (3 wk) depends only on P and also leads into S. Calculate T’s EST, LST, and float. Can T be delayed 5 weeks without delaying the project?
    • Network flow: Concrete (truckloads/day) is pumped from depot S to site T through a pipe network. Maximum flow = 12 truckloads/day. Minimum cut = {pipe CD = 7, pipe EF = 5}. Could 14 truckloads/day be delivered? What is the minimum upgrade needed?
    • Assignment: Three trucks (X, Y, Z) must be assigned to three delivery routes (1, 2, 3) at minimum total cost ($00s): X:[4,7,3], Y:[2,6,5], Z:[8,3,7]. Find the optimal assignment and minimum cost.
    ▶ Show Answer
    Critical path:
    Project duration = 4+7+5+3 = 19 weeks. EST(S) = 4+7+5 = 16.
    EST(T) = 4 (T depends on P). T feeds into S, which needs T to finish: T ends at 4+3=7 ≤ EST(S)=16 → T does not delay S.
    LST(T) = LST(S)−dur(T) = 16−3 = 13. Float(T) = 13−4 = 9 weeks.
    A 5-week delay: 5 < 9 (float). Yes, T can be delayed 5 weeks without delaying the project.
    
    Network flow:
    Current max flow = 12 < 14. No, 14 truckloads cannot be delivered.
    Min cut = 12. Need 2 more units of cut capacity.
    Minimum upgrade: add 2 units to any min-cut edge — e.g. upgrade CD from 7 to 9 (new cut=9+5=14) or EF from 5 to 7 (new cut=7+7=14).
    
    Assignment:
    Row reduction (mins: X=3, Y=2, Z=3): X:[1,4,0] Y:[0,4,3] Z:[5,0,4].
    Column mins all 0; no column reduction needed.
    Zeros: (X,R3), (Y,R1), (Z,R2). 3 independent zeros. Done.
    Optimal assignment: X→Route 3, Y→Route 1, Z→Route 2
    Costs: X→3=$300, Y→1=$200, Z→2=$300. Minimum total cost = $800.