Topic Review — Networks and Decision Mathematics
← 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.
Review Questions
- 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.
- 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?
- 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 - 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 - 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?
- 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.
- 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 - 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 - 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
- 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)?
- 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 - 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?
- 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?
- 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 - 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.