Unit 4: Transportation, assignment and project scheduling
Quantitative Techniques notes · PTU syllabus (MCOP103-18)
On this page
Unit summary
Shipping goods, assigning jobs and scheduling projects are classic optimisation problems. This unit covers the transportation problem — North-West Corner, Least Cost and Vogel's methods with the MODI optimality test — the assignment problem by the Hungarian method, and PERT/CPM project networks with scheduling and the critical path.
After this unit you can
- Find initial solutions of transportation problems by NWC, LCM and VAM
- Test and improve solutions by the MODI method
- Solve assignment problems by the Hungarian method
- Construct PERT/CPM networks and find the critical path
PTU syllabus topics
- Transportation problem — North-West Corner
- Least Cost and Vogel's Approximation methods
- optimality testing via MODI method
- assignment problem via the Hungarian method
- PERT/CPM project networks
- scheduling with known activity times
- critical path
- 1Row reduction
Subtract row minimum
- 2Column reduction
Subtract column minimum
- 3Cover zeros
With minimum lines
- 4Lines = n?
If yes, assign; if no, adjust
- 5Adjust
Subtract smallest uncovered, add at intersections
Topic 1
The transportation problem
Minimise the cost of transporting goods from m sources (supply) to n destinations (demand).
- Balanced problem: total supply = total demand; else add a dummy row/column with zero cost.
- Methods for initial basic feasible solution (IBFS): North-West Corner Rule, Least Cost Method, Vogel's Approximation Method (VAM) — VAM usually gives the best start.
- A non-degenerate solution has m + n − 1 allocations; fewer = degeneracy (add ε).
- Optimality test: MODI (u–v) method — compute ui + vj = cij for occupied cells; for unoccupied cells, Δij = cij − (ui + vj); if all Δij ≥ 0 the solution is optimal; otherwise form a closed loop and reallocate.
Example
VAM: for each row and column, compute the penalty (difference between the two lowest costs); allocate as much as possible to the lowest-cost cell in the row/column with the highest penalty; repeat.
Example
Three factories (supply 20, 30, 50) and three warehouses (demand 30, 40, 30) — balanced (100 = 100). North-West Corner: allocate 20 to F1–W1; then F2–W1 10, F2–W2 20; F3–W2 20, F3–W3 30 — five allocations = m + n − 1 = 5 (non-degenerate).
Topic 2
The assignment problem and Hungarian method
Assign n jobs to n persons (one each) to minimise total cost or time.
- 1
Row reduction
Subtract the smallest element of each row
- 2
Column reduction
Subtract the smallest element of each column
- 3
Cover all zeros with minimum lines
- 4
If lines = n, make assignments
- 5
Else subtract the smallest uncovered element from uncovered cells, add to intersections
- 6
Repeat and assign one zero in each row and column
Example
Costs (rows A, B, C; columns J1, J2, J3): A 9, 2, 7; B 6, 4, 3; C 5, 8, 1. Row reduction gives A 7, 0, 5; B 3, 1, 0; C 4, 7, 0. Column reduction (subtract 3 from J1) gives A 4, 0, 5; B 0, 1, 0; C 1, 7, 0. Three lines cover all zeros → assign A–J2 (2), B–J1 (6), C–J3 (1): total cost 9.
- Variations: maximisation (convert by subtracting from the largest), unbalanced (add dummy), restricted assignments (infinite cost), multiple optimal solutions.
Travelling salesman problem
A salesman visits each city once and returns home with minimum total distance — solved as an assignment problem with no self-assignment (diagonal = ∞) and the additional constraint that the solution must form a single complete tour (no sub-tours); if the assignment gives sub-tours, the next best zero is tried.
Topic 3
Network models: PERT and CPM
Origin
US Navy Polaris project (1958)
DuPont and Remington Rand (1957)
Activity times
Probabilistic — three estimates
Deterministic — one estimate
Orientation
Event-oriented
Activity-oriented
Used for
R&D, new projects with uncertainty
Construction, repetitive projects
Cost
Time-focused
Time–cost trade-off (crashing)
Construction of networks
- Activity (arrow), event (node), dummy activity (dashed — shows dependency without time).
- Rules: each activity has one arrow; no loops; no dangling events; only one start and one end node; dummies to avoid two activities with the same start and end nodes.
- 1Forward pass
Earliest start (ES) and earliest finish (EF)
- 2Backward pass
Latest finish (LF) and latest start (LS)
- 3Compute floats
- 4Critical activities have zero total float
- 5Critical path = longest path = project duration
Topic 4
Slack and float; PERT probabilities
Total float
LS − ES (or LF − EF)
Free float
ES of successor − EF of the activity
Independent float
ES of successor − LF of predecessor − duration
Event slack
Latest event time − Earliest event time
PERT expected time
te = (to + 4tm + tp) ÷ 6
Activity variance
σ² = [(tp − to) ÷ 6]²
Probability of completion
Z = (Scheduled time − Expected project time) ÷ √(Sum of critical variances)
Example
Activity estimates: optimistic 4, most likely 7, pessimistic 16 days → te = (4 + 28 + 16) ÷ 6 = 8 days; σ² = (12 ÷ 6)² = 4. If the critical path expected time is 40 days with total variance 16 (σ = 4), the probability of finishing in 44 days: Z = (44 − 40) ÷ 4 = 1 → about 84%.
Key terms
- Transportation problem
- Minimising cost of shipping from sources to destinations
- VAM
- Vogel's approximation method using penalties
- MODI method
- Optimality test using ui + vj = cij
- Hungarian method
- Algorithm for assignment problems
- Critical path
- Longest path determining project duration
Quick revision
- Balanced TP; IBFS by NWC, LCM, VAM; m + n − 1 allocations.
- MODI: Δij ≥ 0 for optimality; loop to improve.
- Hungarian: row/column reduction, cover zeros, adjust.
- PERT te = (to + 4tm + tp)/6; CPM deterministic.
- Critical activities have zero float.
Important exam questions
Practice questions written to the PTU exam pattern for this unit's syllabus: short answers (Section A style) and long answers (Sections B and C style).
Short-answer questions
- Q1.What is a balanced transportation problem?
- Q2.State the North-West Corner rule.
- Q3.What is the MODI method?
- Q4.How is an unbalanced assignment problem solved?
- Q5.Distinguish PERT and CPM.
- Q6.What is total float?
Long-answer questions
- Q1.Explain methods of finding an initial basic feasible solution of a transportation problem.
- Q2.Explain the MODI method of testing optimality.
- Q3.Explain the Hungarian method of solving assignment problems.
- Q4.Explain the construction of networks and determination of the critical path in PERT/CPM.
Stuck on this unit?
Message SBS on WhatsApp for help with Quantitative Techniques, or to ask about studying M.Com at Synetic.