Linear Programming, Transportation and Assignment Problems
Section B of this paper moves from cost-management philosophy to operations-research technique — three related optimisation methods that each answer a version of the same question: given limited resources and a set of options, what is the best possible allocation?
1. Linear programming — the graphical method
Linear programming maximises or minimises an objective function subject to a set of linear constraints, and for a two-variable problem, the graphical method solves it visually. The method proceeds in a fixed sequence: express the objective function and every constraint as a linear inequality in the two decision variables; plot each constraint line on a graph; identify the feasible region — the area satisfying every constraint simultaneously.
The final step is to evaluate the objective function at each corner point (vertex) of the feasible region, since a fundamental theorem of linear programming guarantees that an optimal solution, if one exists, always occurs at a corner point of the feasible region, never at an interior point.
This corner-point property is what makes the graphical method reliable rather than a matter of visual guesswork: once the feasible region's corner points are identified, the optimal solution is found simply by computing the objective function's value at each corner and selecting the best one, without needing to check every point inside the region.
2. The transportation problem
A transportation problem minimises the total cost of shipping a homogeneous good from several supply sources to several demand destinations, given a per-unit shipping cost between every source-destination pair, and given fixed supply available at each source and fixed demand required at each destination. The problem is balanced when total supply exactly equals total demand, and unbalanced otherwise.
An unbalanced problem is first converted to a balanced one by adding a dummy source (if demand exceeds supply) or a dummy destination (if supply exceeds demand), with zero shipping cost assigned to the dummy row or column, purely as a bookkeeping device to make the standard solution method applicable.
Finding an initial basic feasible solution is the first practical step, and the North-West Corner Method is the simplest such method: starting at the top-left (north-west) cell of the cost table, allocate the maximum possible quantity there, limited by whichever of that row's remaining supply or that column's remaining demand is smaller.
Then move to the next cell to the right (if that column's demand is now satisfied) or the next cell down (if that row's supply is now exhausted), repeating until all supply and demand is allocated.
The North-West Corner Method ignores cost entirely when making its allocations, which is exactly why it is only a starting solution — it is quick to construct but rarely optimal, and further optimisation (through methods such as MODI, the Modified Distribution method) is applied to the initial solution to check whether a lower-cost allocation exists, though the mechanical detail of MODI itself goes beyond outline-level treatment.
3. The assignment problem
An assignment problem is a special case of the transportation problem where every source has a supply of exactly 1 and every destination has a demand of exactly 1 — the classic version assigns workers to jobs (or machines to tasks), one-to-one, to minimise total cost or time (or maximise total profit or output).
Because every allocation in an assignment problem is either 0 or 1 (a job is either assigned to a worker or it is not), the North-West Corner Method's practical value for finding a starting solution effectively disappears here, and the Hungarian Method is used instead.
The Hungarian Method's logic, at outline depth: reduce each row of the cost matrix by its own smallest element (so every row now contains at least one zero), then reduce each column of the resulting matrix by its own smallest element (so every column also contains at least one zero); attempt to make a complete one-to-one assignment using only the zero cells.
If a complete assignment is not yet possible, a further systematic adjustment (drawing the minimum number of lines to cover all zeros, then adjusting the matrix) is applied and the assignment attempt repeated, until a complete zero-based assignment is achieved.
The row and column reductions do not change which assignment is optimal, because subtracting a constant from an entire row or column shifts every entry in it by the same amount, which does not change which combination of cells is cheapest relative to the others — it merely reveals the zero-cost opportunities that identify the optimal assignment more easily.
Worked Examples
Example 1. A firm makes two products, X and Y. Each unit of X needs 2 hours of machine time and 1 hour of labour; each unit of Y needs 1 hour of machine time and 3 hours of labour. Available: 100 machine hours and 90 labour hours. Contribution is ₹40 per unit of X and ₹30 per unit of Y. Formulate the linear programme (objective function and constraints).
Maximise Z = 40X + 30Y, subject to: 2X + Y ≤ 100 (machine hours), X + 3Y ≤ 90 (labour hours), X ≥ 0, Y ≥ 0.
Example 2. Using Example 1's constraints, verify whether the point (30, 20) is feasible.
Machine hours: 2(30) + 20 = 80, within the 100-hour limit. Labour hours: 30 + 3(20) = 90, exactly at the 90-hour limit. Both constraints are satisfied, so (30, 20) is a feasible point (though not necessarily optimal — the optimum must be checked at the feasible region's corner points).
Example 3. A transportation problem has 3 sources with supplies of 30, 40 and 20 units, and 2 destinations with demands of 50 and 30 units. Is this problem balanced? If not, what adjustment is needed before solving it?
Total supply = 30 + 40 + 20 = 90. Total demand = 50 + 30 = 80. Since supply exceeds demand, the problem is unbalanced; a dummy destination with a demand of 10 units (90 − 80) and zero shipping cost must be added to balance it before applying the standard solution method.
Example 4. Using the North-West Corner Method, find the first allocation for a transportation table where Source 1 has 40 units supply and Destination 1 requires 25 units demand.
Allocate min(40, 25) = 25 units to the (Source 1, Destination 1) cell — Destination 1's demand is now fully satisfied, so the next allocation moves to (Source 1, Destination 2), since Source 1 still has 15 units of unallocated supply remaining.
Example 5. Explain why the North-West Corner Method's initial solution is described as a "starting" solution rather than necessarily the final answer.
The North-West Corner Method allocates purely based on position (top-left first) and available supply/demand quantities, completely ignoring the actual shipping cost of each route — so while it quickly produces a feasible allocation satisfying all supply and demand constraints, it offers no guarantee of being the lowest-cost allocation, and a further optimisation step is generally needed to check for, and move towards, a genuinely cost-minimising solution.
Example 6. In a 3×3 assignment cost matrix, every row has been reduced by its own row minimum, and every column of the resulting matrix has then been reduced by its own column minimum. Explain why this row-and-column reduction process does not change which assignment is actually optimal.
Subtracting a constant amount from every entry in an entire row (or column) shifts all of that row's (or column's) costs down by the same fixed amount, which does not change the relative cost differences between the cells within that row or column — so whichever combination of cells was cheapest relative to the others before the reduction remains the cheapest relative combination afterward.
The reductions are a technique for revealing zero-cost cells that make the optimal assignment easier to identify, not a change to the underlying cost structure's relative rankings.
Example 7. State the key structural feature that distinguishes an assignment problem from a general transportation problem.
In an assignment problem, every source has a supply of exactly 1 and every destination has a demand of exactly 1 (a strict one-to-one matching), whereas a general transportation problem allows sources and destinations to have any supply and demand quantities.
Summary
Linear programming's graphical method plots constraints to find a feasible region and relies on the corner-point property — the optimal solution always occurs at a vertex of the feasible region — to solve a two-variable maximisation or minimisation problem by evaluating the objective function at each corner alone.
The transportation problem minimises shipping cost across multiple sources and destinations, first requiring the problem to be balanced (adding a zero-cost dummy row or column if needed), with the North-West Corner Method providing a quick but cost-blind starting allocation that typically requires further optimisation to reach the genuinely lowest-cost solution.
The assignment problem is a special one-to-one case of the transportation problem (every supply and demand equal to 1), solved through the Hungarian Method's row-and-column cost reduction, which reveals zero-cost cells identifying the optimal assignment without changing the underlying relative cost rankings between cells.
