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
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).
Exam tip
Before solving a transportation problem, check that total supply equals total demand (add a dummy row or column if not). A basic feasible solution must have m + n − 1 allocations; fewer means the solution is 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
Example
Finding the critical path: activities A (3 days) → C (4) and B (5) → D (2), both ending at F (3). Path A–C–F = 10 days; path B–D–F = 10 days; if A's time rises to 4, the critical path becomes A–C–F = 11 days. PERT expected time te = (a + 4m + b) ÷ 6.
Exam tip
Activities on the critical path have zero float; delaying them delays the project.
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%.
Exam tip
The critical path is the longest path through the network; every activity on it has zero total float. The project's expected duration is the length of this path, and its variance is the sum of the variances of the critical activities.
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.
