Unit 3: Transportation, assignment and queuing models
Operation Research Applications notes · PTU syllabus (MBA 952-18)
On this page
Unit summary
Special LP structures and stochastic models solve distribution, allocation, multi-stage and waiting-line problems. This unit covers initial basic feasible solution methods and optimisation of transportation and assignment problems, deterministic and probabilistic dynamic programming, and queuing theory — basic structure and the Poisson input, exponential service model.
After this unit you can
- Solve transportation problems and test for optimality
- Solve assignment problems
- Apply deterministic and probabilistic dynamic programming
- Apply queuing models
PTU syllabus topics
- Initial basic feasible solution methods
- optimization of transportation and assignment problems
- dynamic programming (deterministic and probabilistic)
- queuing theory — basic structure
- Poisson input and exponential service models
Utilisation
ρ = λ / μ
Average number in system
L = λ / (μ − λ)
Average time in system
W = 1 / (μ − λ)
Average queue length
Lq = λ² / [μ (μ − λ)]
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
Dynamic programming
Dynamic programming (Richard Bellman) solves multi-stage decision problems by breaking them into stages, solving each stage optimally and combining them.
- Bellman's principle of optimality: an optimal policy has the property that, whatever the initial state and decision, the remaining decisions must constitute an optimal policy with regard to the state resulting from the first decision.
- Elements: stages, states, decisions, return function, recursive relationship.
- Deterministic DP: next state is known with certainty — shortest route (stagecoach) problem, allocation of resources, production scheduling.
- Probabilistic DP: next state is described by probabilities — inventory with uncertain demand, equipment replacement under risk; objective is expected value.
Example
Stagecoach problem: to find the shortest route through stages, start from the last stage, compute the shortest distance from each node to the destination, and move backwards stage by stage.
Topic 4
Queuing theory: basic structure
- 1Input (calling) population
Finite or infinite
- 2Arrival process
Poisson (random) arrivals at rate λ
- 3Queue discipline
FCFS, LCFS, priority, service in random order
- 4Service mechanism
Exponential service at rate μ; number of servers
- 5Output
Customers leave after service
- Types of situations: single queue–single server (ATM), single queue–multiple servers (bank tellers), multiple queues–multiple servers (supermarket counters), sequential service (hospital).
- Kendall's notation: (a/b/c) : (d/e/f) — arrival distribution / service distribution / servers : capacity / population / discipline. M/M/1 = Poisson arrivals, exponential service, one server.
- Customer behaviour: balking (does not join), reneging (leaves the queue), jockeying (switches queues).
Topic 5
Poisson input and exponential service model
Traffic intensity (utilisation)
ρ = λ ÷ μ (must be < 1)
Probability system is idle
P0 = 1 − ρ
Average number in system
Ls = λ ÷ (μ − λ)
Average number in queue
Lq = λ² ÷ [μ (μ − λ)]
Average time in system
Ws = 1 ÷ (μ − λ)
Average time in queue
Wq = λ ÷ [μ (μ − λ)]
Probability of n in system
Pn = (1 − ρ) ρ^n
Example
Customers arrive at 8 per hour; the clerk serves 10 per hour. ρ = 0.8; P0 = 0.2; Ls = 8 ÷ 2 = 4; Lq = 64 ÷ 20 = 3.2; Ws = 1 ÷ 2 hour = 30 minutes; Wq = 8 ÷ 20 hour = 24 minutes.
Exam tip
Little's law links them: Ls = λ × Ws and Lq = λ × Wq — use it to check your answers.
Key terms
- Initial basic feasible solution
- Starting allocation satisfying supply and demand
- MODI method
- Optimality test using u and v values
- Hungarian method
- Algorithm for the assignment problem
- Principle of optimality
- Bellman's rule for multi-stage decisions
- Traffic intensity
- Arrival rate divided by service rate
Quick revision
- Transportation: NWCR, LCM, VAM; MODI; degeneracy; unbalanced problems.
- Assignment: Hungarian method; unbalanced and maximisation cases.
- DP: stages, states, recursion; deterministic and probabilistic.
- Queue structure: arrivals, queue discipline, service, Kendall notation.
- M/M/1: ρ = λ/μ; Lq, Ls, Wq, Ws formulas.
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.Name three methods for an initial basic feasible solution.
- Q2.What is degeneracy in a transportation problem?
- Q3.How is an unbalanced assignment problem solved?
- Q4.State Bellman's principle of optimality.
- Q5.Explain Kendall's notation.
- Q6.State the formula for average queue length in M/M/1.
Long-answer questions
- Q1.Solve a transportation problem by VAM and test optimality by MODI (numerical).
- Q2.Solve an assignment problem by the Hungarian method (numerical).
- Q3.Explain deterministic and probabilistic dynamic programming.
- Q4.Explain the structure of a queuing system and the M/M/1 model.
Stuck on this unit?
Message SBS on WhatsApp for help with Operation Research Applications, or to ask about studying MBA at Synetic.