Transportation problem and queuing theory
The transportation model ships goods from sources to destinations at least cost; VAM usually gives the best starting solution. Queuing models balance waiting cost against service cost.
Transportation model basics
- A special linear programming problem: ship from m sources (supply) to n destinations (demand) at the least total cost.
- Balanced if total supply = total demand. If not, add a dummy row or column with zero costs.
- A basic feasible solution needs m + n − 1 occupied cells. Fewer means degeneracy: put a tiny quantity ε in a suitable empty cell.
- A prohibited route gets a very large cost M. For a profit-maximising problem, first convert profits into opportunity losses.
- The assignment problem is a special case, solved by the Hungarian method (H. W. Kuhn, 1955).
Finding an initial basic feasible solution
| Method | Rule | Quality |
|---|---|---|
| North-west corner rule (NWCR) | Start at the top-left cell, allocate as much as possible, then move right or down | Fast but ignores cost; usually the worst start |
| Least cost method (LCM) | Allocate to the cheapest remaining cell first | Better than NWCR |
| Vogel's approximation method (VAM) | Penalty = gap between the two lowest costs in each row and column; allocate in the line with the highest penalty, at its cheapest cell | Usually the best start, often optimal |
Worked example 1: NWCR, least cost and VAM
Three plants ship to three depots. Cost per unit (₹) to D1, D2, D3: P1 → 2, 3, 4; P2 → 9, 5, 6; P3 → 8, 7, 10. Supplies: 40, 60, 70. Demands: 80, 50, 40. Both total 170, so the problem is balanced.
- NWCR: P1D1 40 (₹2), P2D1 40 (₹9), P2D2 20 (₹5), P3D2 30 (₹7), P3D3 40 (₹10). Cost = 80 + 360 + 100 + 210 + 400 = ₹1,150.
- Least cost: P1D1 40 (₹2), P2D2 50 (₹5), P2D3 10 (₹6), P3D1 40 (₹8), P3D3 30 (₹10). Cost = 80 + 250 + 60 + 320 + 300 = ₹1,010.
- VAM round 1: row penalties 1, 1, 1; column penalties 6, 2, 2. D1 has the highest (6): allocate 40 to P1D1 (₹2). P1 is used up.
- VAM round 2: rows P2 1, P3 1; columns D1 1, D2 2, D3 4. D3 is highest: allocate 40 to P2D3 (₹6).
- VAM round 3: rows P2 (9, 5) = 4, P3 (8, 7) = 1; columns D1 1, D2 2. P2 is highest: allocate 20 to P2D2 (₹5). P3 takes the rest: D1 40 (₹8) and D2 30 (₹7).
- VAM cost = 80 + 240 + 100 + 320 + 210 = ₹950. Each method fills 3 + 3 − 1 = 5 cells.
NWCR ₹1,150; least cost ₹1,010; VAM ₹950. The MODI test below shows ₹950 is optimal.
Worked example 2: testing optimality by MODI
Test the VAM solution above, whose occupied cells are P1D1, P2D2, P2D3, P3D1 and P3D2.
- Set u1 = 0 and use u + v = c for occupied cells: v1 = 2; u3 = 8 − 2 = 6; v2 = 7 − 6 = 1; u2 = 5 − 1 = 4; v3 = 6 − 4 = 2.
- Empty cells, Δ = c − (u + v): P1D2 = 3 − (0 + 1) = 2; P1D3 = 4 − (0 + 2) = 2; P2D1 = 9 − (4 + 2) = 3; P3D3 = 10 − (6 + 2) = 2.
- Every Δ is positive, so no reallocation can cut the cost.
The VAM solution (₹950) is optimal, and unique because no Δ is zero.
Queuing system: elements and terms
| Element | Meaning |
|---|---|
| Arrival process | Usually Poisson with mean rate λ, so the times between arrivals are exponential |
| Service process | Usually exponential service times with mean rate μ |
| Queue discipline | FCFS (FIFO), LIFO, service in random order (SIRO), priority |
| Servers and capacity | Single or multiple channels; a finite or infinite queue |
| Customer behaviour | Balking: refuses to join. Reneging: leaves after waiting. Jockeying: switches lines |
| Kendall notation (1953) | A/B/c: arrival distribution / service distribution / number of servers; M means Markovian (Poisson arrivals, exponential service) |
| Origin | A. K. Erlang's work on Copenhagen telephone traffic (1909) |
M/M/1 formulas (valid only when λ < μ)
| Measure | Formula |
|---|---|
| Utilisation | ρ = λ ÷ μ |
| P(system idle) | P₀ = 1 − ρ |
| P(n in system) | Pₙ = (1 − ρ)ρⁿ |
| Average number in system | Ls = λ ÷ (μ − λ) |
| Average number in queue | Lq = λ² ÷ [μ(μ − λ)] |
| Average time in system | Ws = 1 ÷ (μ − λ) |
| Average time in queue | Wq = λ ÷ [μ(μ − λ)] |
| P(more than k in system) | ρ^(k + 1) |
| Little's law (J. D. C. Little, 1961) | Ls = λWs and Lq = λWq |
Worked example 3: M/M/1
Customers reach a single ATM at 8 an hour (Poisson). Each takes 6 minutes on average, so μ = 10 an hour (exponential). Find the queue measures.
- ρ = 8 ÷ 10 = 0.8, so the ATM is busy 80% of the time; P₀ = 0.2.
- Ls = 8 ÷ (10 − 8) = 4 customers. Lq = 64 ÷ (10 × 2) = 3.2 customers.
- Ws = 1 ÷ (10 − 8) = 0.5 hour = 30 minutes. Wq = 8 ÷ (10 × 2) = 0.4 hour = 24 minutes.
- Check with Little's law: Ls = λWs = 8 × 0.5 = 4. P(more than 2 in the system) = 0.8³ = 0.512.
ρ = 0.8, Ls = 4, Lq = 3.2, Ws = 30 minutes, Wq = 24 minutes.
NET gives a small table and asks for the NWCR or VAM cost, the m + n − 1 rule, what to do when the problem is unbalanced or degenerate, and quick M/M/1 sums (ρ, Ls, Lq, Ws, Wq). Queue behaviour terms (balking, reneging, jockeying) are matched.
Typical MCQ: “A 3 × 4 transportation solution has 5 occupied cells. What is wrong?” It is degenerate: it needs 3 + 4 − 1 = 6 cells, so add ε to a suitable empty cell. Trap: thinking 5 cells are enough.
Typical MCQ: “In an M/M/1 queue, what happens if λ ≥ μ?” There is no steady state; the queue grows without limit. Trap: plugging the values into Ls = λ ÷ (μ − λ) and reporting a negative or infinite answer.
Typical MCQ: “λ = 4 an hour and μ = 6 an hour. Find Wq.” Wq = 4 ÷ (6 × 2) = 1/3 hour = 20 minutes. Trap: giving Ws = 1 ÷ (6 − 4) = 30 minutes instead.
NWCR is blind (ignores cost), LCM is greedy, VAM is wise (uses penalties). In M/M/1, everything hangs on μ − λ.