Operations Research (AD-504 (C)) Unit 2 Notes

How unit 2 is examined

This unit covers the transportation problem, its starting and optimal solutions, the assignment problem with the Hungarian method, and the travelling salesman problem. No question has been asked recently, so every topic is short.

Transportation problem (TP) and its formulation

Not asked since 2022

Definition. The transportation problem finds the cheapest plan to ship a single commodity from $m$ sources to $n$ destinations, given supplies, demands and unit shipping costs.

Key points.

Source $i$ has supply $a_i$, destination $j$ has demand $b_j$, and shipping one unit from $i$ to $j$ costs $c_{ij}$.
The model is: minimise $Z=\sum_{i=1}^{m}\sum_{j=1}^{n}c_{ij}x_{ij}$ subject to $\sum_j x_{ij}=a_i$, $\sum_i x_{ij}=b_j$ and $x_{ij}\ge 0$.
The problem is balanced when $\sum a_i=\sum b_j$; otherwise add a dummy destination or source with zero cost.
A basic solution has exactly $m+n-1$ allocations; fewer means degeneracy.
The tableau has $m$ rows and $n$ columns; each cell holds the unit cost in its corner and the shipped quantity $x_{ij}$ in the middle, and the last row and column carry the demands and supplies.
The problem is a special linear programming problem with $mn$ variables and $m+n$ constraints, one of which is redundant when balanced, so only $m+n-1$ are independent.
Every balanced transportation problem has a feasible solution and an optimal solution, because supplies equal demands and costs are non-negative.
Typical uses are shipping goods from factories to warehouses, allocating production across plants, and scheduling supply to markets at least total cost.

Example. Three factories with supplies 7, 9, 18 serve four markets with demands 5, 8, 7, 14. Total supply is 34 and total demand is 34, so the problem is balanced. The cost matrix rows are (19,30,50,10), (70,30,40,60), (40,8,70,20).

Answer frame. Open with the definition; draw the cost tableau with supplies and demands; write the model $Z$, the two constraint sets and non-negativity; then state balanced versus unbalanced with the dummy rule; close with the $m+n-1$ basic variables statement.

A balanced transportation problem has m+n-1 basic variables and minimises total shipping cost.

Finding basic feasible solution and optimal solution for transportation problem

Definition. An initial basic feasible solution (IBFS) is a first valid allocation with $m+n-1$ cells; it is then tested and improved to the optimum.

Key points.

North-West Corner rule starts at the top-left cell, allocates $\min(\text{supply},\text{demand})$, then moves right or down; it ignores costs.
Least Cost Method allocates first to the cheapest cell and usually gives a better start.
Vogel's Approximation Method (VAM) finds each row and column penalty (difference of two smallest costs), allocates in the largest-penalty line's cheapest cell, and is usually closest to optimal.
MODI (u-v) method sets $u_i+v_j=c_{ij}$ for allocated cells and computes $d_{ij}=c_{ij}-u_i-v_j$ for empty cells.
The solution is optimal when all $d_{ij}\ge 0$; otherwise shift units around a closed loop through the most negative cell.
A degenerate solution has fewer than $m+n-1$ allocations, so place a tiny quantity $\varepsilon$ in an independent empty cell to continue.
A closed loop uses only horizontal and vertical moves, starts and ends at the entering empty cell, and turns at allocated cells with alternating plus and minus signs.
The quantity moved is the smallest allocation on the minus corners, and after moving, recompute $u$, $v$ and $d_{ij}$ until none is negative.

Example. For the 3 by 4 problem above (supplies 7, 9, 18; demands 5, 8, 7, 14):

Method	Allocations	Total cost
North-West Corner	5, 2, 6, 3, 4, 14 in cells (1,1), (1,2), (2,2), (2,3), (3,3), (3,4)	1015
Least Cost	(3,2)=8, (1,4)=7, (3,4)=7, (2,3)=7, (3,1)=3, (2,1)=2	814

The North-West cost is $5\times19+2\times30+6\times30+3\times40+4\times70+14\times20=1015$. Least Cost gives $8\times8+7\times10+7\times20+7\times40+3\times40+2\times70=814$, so it starts far closer to the optimum.

Answer frame. Open with what an IBFS is; solve by the method named in the question, showing each allocation row by row; check that there are $m+n-1$ allocations; if asked for the optimum, compute $u$, $v$, $d_{ij}$ and either declare optimal or draw the loop; close with the total cost in bold.

==Solution is optimal when every empty-cell opportunity cost d_ij = c_ij - u_i - v_j is non-negative.==

Assignment problem and its formulation

Definition. The assignment problem allocates $n$ jobs to $n$ persons, one each, so that total cost is minimum.

Key points.

It is a special transportation problem where every supply and demand equals 1.
Model: minimise $Z=\sum_i\sum_j c_{ij}x_{ij}$ with $x_{ij}=1$ if person $i$ does job $j$, else 0.
Constraints are $\sum_j x_{ij}=1$ for each person and $\sum_i x_{ij}=1$ for each job.
An unbalanced problem is balanced by adding dummy rows or columns of zero cost; a maximisation problem is converted by subtracting all entries from the largest.
The cost matrix is square, and each row and each column receives exactly one assignment, so a solution uses exactly $n$ cells.
Because every basic variable is 0 or 1, the problem is highly degenerate, and the simplex or MODI method is inefficient, which is why the Hungarian method is used.
Typical uses are assigning workers to machines, salesmen to territories, and drivers to routes at minimum total cost or maximum profit.
A forbidden assignment is given a very large cost $M$ so that it is never selected.

Answer frame. Open with the definition; write the decision variable $x_{ij}$, the objective and the two constraint sets; state the balancing rule for unequal numbers; close with the link to the transportation problem.

The assignment problem is a transportation problem with all supplies and demands equal to one.

Hungarian method for solving Assignment problem

Definition. The Hungarian method solves the assignment problem by creating zeros in the cost matrix and choosing a complete set of independent zeros.

Steps.

Step 1: Subtract the row minimum from each row.
Step 2: Subtract the column minimum from each column.
Step 3: Cover all zeros with the minimum number of lines.
Step 4: If lines = n, assign at independent zeros; else subtract the smallest uncovered element from uncovered cells, add it at line intersections, and repeat Step 3.

Example. Cost matrix rows (9,2,7), (3,6,1), (5,8,4). Row reduction gives (7,0,5), (2,5,0), (1,4,0); column reduction gives (6,0,5), (1,5,0), (0,4,0). Three lines are needed, so assign 1 to job 2, 2 to job 3, 3 to job 1: cost = 2 + 1 + 5 = 8.

Key points.

The method rests on the theorem that subtracting a constant from a whole row or column changes total cost by that constant and leaves the optimal assignment unchanged.
If the matrix is not square, add a dummy row or column of zeros first; for maximisation, subtract every entry from the largest entry and then minimise.
Zeros are covered with the fewest horizontal and vertical lines; if the number of lines is less than $n$, an optimal assignment is not yet possible.
To assign, start with a row or column that has a single zero, mark it, cross out other zeros in its row and column, and repeat.
The total cost is read from the original matrix, not the reduced one; here $2+1+5=8$.

Answer frame. Open with the one-line definition; write the algo steps; show the row-reduced and column-reduced matrices; draw the covering lines; list the assignments and add their original costs; close with the bold minimum cost.

Optimal assignment is found when the minimum number of covering lines equals n.

Travelling salesmen problem

Definition. The travelling salesman problem (TSP) finds the shortest closed tour visiting each of $n$ cities exactly once and returning to the start.

Key points.

It is an assignment problem with the extra condition that the chosen assignments form one single tour, not several sub-tours.
For $n$ cities there are $(n-1)!$ possible tours, so brute force grows very fast.
Solve by the Hungarian method with the diagonal cost set to $\infty$; if sub-tours appear, use branch and bound to break them.
Example: for 4 cities with distances 0-1=10, 0-2=15, 0-3=20, 1-2=35, 1-3=25, 2-3=30, the best tour is 0-1-3-2-0 with length 80.
Cities can be joined only once as origin and once as destination, so the assignment constraints hold, and the extra tour condition rules out sub-tours such as 0-1-0 and 2-3-2.
The Hungarian solution is optimal for the tour only if it forms one cycle; otherwise the sub-tours are branched on and re-solved.
In the example above the distances are symmetric and the route 0-1-3-2-0 costs $10+25+30+15=80$, which matches the minimum over all $3!=6$ tours.
Applications include delivery routing, drilling holes on a circuit board and scheduling a visiting order for inspectors.

Answer frame. Open with the definition; write the cost matrix with $\infty$ on the diagonal; solve by the Hungarian method; check whether the assignment is one closed tour; close with the tour and its total distance.

TSP is an assignment problem whose solution must form a single tour through all cities.

Last-minute revision

Transportation problem: $m$ sources, $n$ destinations, minimise $\sum c_{ij}x_{ij}$.
Balanced when total supply equals total demand; otherwise add a dummy.
A basic feasible solution has $m+n-1$ allocations.
IBFS methods: North-West Corner, Least Cost, VAM (best start).
MODI: $u_i+v_j=c_{ij}$ on allocated cells; optimal if all $d_{ij}=c_{ij}-u_i-v_j\ge 0$.
Assignment problem: $n\times n$, each $x_{ij}\in\{0,1\}$, supplies and demands all 1.
Hungarian: row reduce, column reduce, cover zeros, assign when lines = $n$.
Maximisation assignment: subtract all entries from the largest entry.
TSP has $(n-1)!$ tours; it needs a single closed tour.
Worked assignment example gives cost 8; the 4-city TSP gives 80.

Memory hooks

NW corner ignores cost, VAM uses penalties: "North-West is lazy, Vogel is smart".
MODI: $u+v=c$ on the basics, then test $d=c-u-v$.
Hungarian: Row, Column, Cover, Count.
Assignment is a transportation problem with every supply and demand equal to 1.
TSP: one tour, no sub-tours, $(n-1)!$ options.

Coverage checklist

Transportation problem (TP) and its formulation: covered; no past questions.
Finding basic feasible solution and optimal solution for transportation problem: covered; no past questions.
Assignment problem and its formulation: covered; no past questions.
Hungarian method for solving Assignment problem: covered; no past questions.
travelling salesmen problem: covered; no past questions.

Account

Operations Research (AD-504 (C)) - Unit 2 Short Notes

How unit 2 is examined

Transportation problem (TP) and its formulation

Finding basic feasible solution and optimal solution for transportation problem

Assignment problem and its formulation

Hungarian method for solving Assignment problem

Travelling salesmen problem

Last-minute revision

Memory hooks

Coverage checklist