Linear Programming, Transportation & Assignment

Industrial Engineering supplies ~5–8 marks to GATE ME, and optimisation (LP + transportation + assignment) is its most-tested block. The corner-point idea and the standard algorithms are reliable marks.

Linear programming (LP)

Optimise a linear objective subject to linear constraints (≤, ≥, =) with non-negative variables. Key facts:

• The feasible region is a convex polygon; the optimum lies at a corner (vertex) — the basis of the graphical and simplex methods.
• Simplex moves vertex-to-vertex improving the objective. Duality: every LP (primal) has a dual; at optimality their objective values are equal (strong duality). A ≥ constraint or unbounded/infeasible region are special cases.

Transportation problem

Ship from sources (supplies) to destinations (demands) at minimum cost.

• Initial basic feasible solution: North-West corner, Least-Cost, or Vogel's Approximation Method (VAM — usually closest to optimal).
• Optimality: MODI (u–v) or stepping-stone method. A balanced problem has Σsupply = Σdemand; a feasible solution needs m + n − 1 occupied cells (else degenerate).

Assignment problem

One-to-one allocation (n jobs to n machines) minimising cost — solved by the Hungarian method (row/column reduction, then cover zeros). A special transportation case where all supplies and demands equal 1.

Exam Tricks & Tips

• 🎯 LP optimum is always at a corner of the feasible region — check vertices in the graphical method; no interior point beats them.
• 🎯 Transportation feasibility needs m + n − 1 occupied cells; fewer means degeneracy (add an epsilon allocation).
• 🎯 VAM gives the best starting solution; North-West corner is quickest but ignores cost.
• 🎯 Assignment = Hungarian method; it's a transportation problem with unit supplies/demands.
• 🎯 Balanced transportation: Σsupply = Σdemand — if unbalanced, add a dummy row/column with zero cost.
• ❌ Common mistake: confusing the least-cost start with the optimal solution — the initial basic feasible solution (NW/least-cost/VAM) must still be tested and improved via MODI/stepping-stone.

Expected exam pattern

A 1-mark LP-corner, degeneracy, or duality MCQ, and a 2-mark transportation (initial solution/cost) or assignment (Hungarian) problem. The corner-optimum, m+n−1 rule, and dummy-balancing are frequent points.

Quick recap

LP: linear objective + constraints; optimum at a corner (graphical/simplex); duality gives equal optima. Transportation: start with NW/least-cost/VAM, optimise via MODI/stepping-stone; balanced Σsupply = Σdemand, needs m+n−1 cells. Assignment: Hungarian method (unit-flow transportation).

Cover the answer, recall, then check. 11 cards on optimisation for GATE ME.

Q1. Where does the optimum of a linear program lie?
A1. At a corner (vertex) of the convex feasible region — never strictly inside it.

Q2. What does the simplex method do?
A2. Moves from vertex to vertex of the feasible region, improving the objective until no better adjacent vertex exists.

Q3. State strong duality for LP.
A3. Every primal LP has a dual; at optimality the primal and dual objective values are equal.

Q4. Name three methods for an initial transportation solution.
A4. North-West corner, Least-Cost, and Vogel's Approximation Method (VAM — usually closest to optimal).

Q5. How do you test/improve a transportation solution?
A5. By the MODI (u–v) or stepping-stone method, checking for negative opportunity costs and reallocating.

Q6. Condition for a balanced transportation problem?
A6. Total supply = total demand. If not, add a dummy source/destination with zero cost.

Q7. How many occupied cells does a non-degenerate transportation solution need?
A7. m + n − 1 (rows + columns − 1). Fewer means degeneracy.

Q8. Which method solves the assignment problem?
A8. The Hungarian method — row and column reduction, then covering zeros with minimum lines.

Q9. How is the assignment problem related to transportation?
A9. It is a special transportation problem where every supply and demand equals 1 (one-to-one allocation).

Q10. What is degeneracy in transportation?
A10. Having fewer than m + n − 1 occupied cells, which blocks the MODI test; fixed by adding a zero (epsilon) allocation.

Q11. Feasible region of an LP is always what shape?
A11. A convex polygon (polytope) — the intersection of linear half-planes.

Optimisation under constraints — maximise profit, minimise cost subject to limited resources — is the heart of operations research. GATE tests LP graphical/simplex reasoning and the special transportation and assignment algorithms, which are recurring, scoring numericals.

Core concept: linear programming finds the best value of a linear objective subject to linear constraints; the optimum always lies at a corner (vertex) of the feasible region.

Deep explanation

Beginner — LP formulation and graphical method

An LP has an objective function (maximise/minimise), decision variables, and constraints (linear inequalities) plus non-negativity. Graphically (2 variables): plot constraints, shade the feasible region (a convex polygon), and evaluate the objective at each corner point — the optimum is at one vertex (or an edge if there are alternate optima).

Intermediate — simplex and duality

For more variables, the simplex method moves vertex to vertex improving the objective. Concepts: slack/surplus variables, basic feasible solution, and the optimality test (all reduced costs non-negative for minimisation). Every LP has a dual; the optimal objective values are equal (strong duality), and shadow prices (dual values) give the marginal worth of each resource. Degeneracy, unboundedness and infeasibility are special cases to recognise.

Advanced — transportation and assignment

• Transportation problem: minimise shipping cost from sources to destinations. Initial basic feasible solution by North-West Corner, Least-Cost, or Vogel's Approximation Method (VAM, best); then optimise with MODI/stepping-stone. A feasible basis needs (m + n − 1) allocations; balance supply and demand first (add dummy if unbalanced).
• Assignment problem: one-to-one allocation (n jobs to n machines) minimising cost — a special transportation case solved efficiently by the Hungarian method (row/column reduction, then cover zeros with minimum lines).

Worked example

Maximise Z = 3x + 5y subject to x ≤ 4, y ≤ 6, x + y ≤ 8, x,y ≥ 0. Find the optimum.
Corner points of the feasible region: (0,0), (4,0), (4,4), (2,6), (0,6).
Evaluate Z: (0,0)→0; (4,0)→12; (4,4)→3(4)+5(4)=32; (2,6)→3(2)+5(6)=36; (0,6)→30.
Maximum Z = 36 at (x,y) = (2,6). The optimum is at a vertex, as LP theory guarantees.

GATE relevance

LP graphical optimisation, simplex/duality concepts, and transportation (VAM, MODI, m+n−1 rule) and assignment (Hungarian) methods are staple Industrial Engineering questions. Corner-point evaluation and the balanced-problem/dummy concept are frequently tested.

Exam tricks & shortcuts

• The LP optimum is always at a corner point — for 2 variables, just evaluate the objective at each vertex.
• Transportation basic feasible solution needs (m + n − 1) occupied cells; add a dummy row/column to balance.
• Assignment → Hungarian method (reduce rows and columns, cover zeros with minimum lines = n at optimum).
• Mnemonic: "The best corner wins in LP."

Key formulas / methods

• LP standard form: maximise/minimise Z = Σcⱼxⱼ subject to constraints, xⱼ ≥ 0.
• Graphical/simplex: optimum at a corner (extreme point) of the feasible region.
• Transportation feasibility: m + n − 1 basic cells (m sources, n destinations); balanced if Σsupply = Σdemand.
• Methods: NW corner, least cost, VAM (initial); MODI/stepping-stone (optimality).
• Assignment (Hungarian method): n×n cost matrix → minimum-cost one-to-one allocation.

Linear programming optimises a linear objective under constraints; transportation/assignment are special network LPs.

Worked Example

Problem: Solve the linear program graphically:
Maximize Z = 3x + 5y, subject to x ≤ 4, 2y ≤ 12, 3x + 2y ≤ 18, x ≥ 0, y ≥ 0.

Solution:
Rewrite the constraints: x ≤ 4, y ≤ 6, 3x + 2y ≤ 18.

Find the corner points (vertices) of the feasible region by intersecting the boundary lines:

• (0, 0), (4, 0), and (0, 6) — from the axes and simple bounds.
• x = 4 with 3x + 2y = 18 → 12 + 2y = 18 → y = 3 → (4, 3).
• y = 6 with 3x + 2y = 18 → 3x + 12 = 18 → x = 2 → (2, 6).

Evaluate Z = 3x + 5y at each vertex:
(0,0): 0; (4,0): 12; (4,3): 12 + 15 = 27; (2,6): 6 + 30 = 36; (0,6): 30.

The maximum is Z = 36 at the vertex (2, 6).

Answer: Optimal solution x = 2, y = 6 with Z_max = 36.