Linear programming

In short

Linear programming (LP) is the branch of optimisation that maximises or minimises a linear objective function of decision variables subject to linear equalities and inequalities. It is the workhorse of operations research: production planning, blending, logistics, portfolio and manpower scheduling all reduce to LP models. In Indian B.Sc/B.Tech syllabi (UGC CBCS "Linear Programming and Optimisation", AICTE "Operations Research") it carries formulation, graphical and simplex solutions, duality, transportation and assignment problems. It is examined in GATE (MA, and the OR section of ME/PI/CE), ISI/CMI and IIT JAM style questions, UGC-NET, Indian Statistical Service and actuarial exams, and appears in analytics placement rounds at Mu Sigma, ZS Associates, Flipkart, Delhivery, TCS Analytics and supply-chain roles.

Explained

Formulation and standard forms

• Decision variables x₁…xₙ: the quantities to be chosen. Objective function Z = c₁x₁+…+cₙxₙ, linear. Constraints: linear ≤, ≥ or = relations on resources. Non-negativity: xⱼ ≥ 0.
• Steps to formulate: identify what is decided → write the objective in money or time units → write one constraint per scarce resource or requirement → add sign restrictions.
• Canonical (max) form: max Z = cᵗx subject to Ax ≤ b, x ≥ 0. Standard form (for simplex): all constraints equations with non-negative RHS, all variables ≥ 0, achieved by adding slack variables (to ≤), subtracting surplus variables (from ≥) and adding artificial variables where needed.
• A free variable xⱼ is replaced by xⱼ′ − xⱼ″ with both ≥ 0; min Z is solved as max (−Z).
• Assumptions: proportionality (returns scale linearly), additivity (no interaction terms), divisibility (fractional values allowed), certainty (parameters known and fixed), single linear objective.

Geometry: convexity and the basic feasible solution

• The feasible region is the intersection of half-spaces — a convex polyhedron (possibly unbounded, possibly empty).
• Fundamental theorem of LP: if an optimum exists, it occurs at an extreme point (vertex); if two vertices are both optimal, every point on the joining edge is optimal (alternative optima, infinitely many solutions).
• For m constraints in n variables (standard form, rank m), set n−m variables to zero and solve for the rest: that is a basic solution; if all values are ≥ 0 it is a basic feasible solution (BFS), and BFSs correspond one-to-one with vertices. Maximum number of BFSs = ⁿCₘ.
• Degenerate BFS: one or more basic variables equal zero — can cause cycling in simplex.
• Graphical method (two variables only): plot constraint lines, shade the feasible region, evaluate Z at each corner (corner-point method) or slide the iso-profit line Z = k outward until it last touches the region.
• Four outcomes: unique optimum, multiple optima, unbounded optimum (feasible region open in the improving direction), infeasible (empty region).

Simplex method

1. Convert to standard form; obtain a starting BFS (slacks as the initial basis).
2. Build the simplex table: basis column, cB, the constraint coefficients, and the b column; compute Zⱼ = ΣcB·aᵢⱼ and the net evaluation row cⱼ − Zⱼ.
3. Optimality test (max problem): optimal when all cⱼ − Zⱼ ≤ 0. Otherwise the most positive cⱼ − Zⱼ fixes the entering variable (key column). (For a min problem, enter on the most negative; equivalently use the Zⱼ − cⱼ convention consistently.)
4. Minimum-ratio test: compute b_i/a_ik for a_ik > 0 only; the least ratio fixes the leaving variable (key row). If no a_ik > 0, the solution is unbounded.
5. Pivot: divide the key row by the pivot element, then row-reduce the other rows so the key column becomes a unit vector. Repeat from step 3.
6. Ties: tie in the entering column — choose arbitrarily; tie in the ratio (degeneracy) — Bland's rule or lowest-subscript rule avoids cycling.
7. Artificial variables are needed when ≥ or = constraints leave no feasible slack basis:
   • Big-M (penalty) method: add artificials with cost −M (max) or +M (min), M arbitrarily large; if any artificial remains basic at a positive level in the optimum, the original problem is infeasible.
   • Two-phase method: Phase I minimises the sum of artificials; if the Phase I minimum > 0 the problem is infeasible, else drop the artificials and run Phase II on the real objective. Numerically safer than Big-M.
8. Reading the table: cⱼ − Zⱼ = 0 for a non-basic variable at optimality signals alternative optima; the cⱼ − Zⱼ values of the slack columns give the dual variables (shadow prices) up to sign.

Duality

• Every LP (primal) has a dual. Primal: max Z = cᵗx, Ax ≤ b, x ≥ 0 → Dual: min W = bᵗy, Aᵗy ≥ c, y ≥ 0. One dual variable per primal constraint, one dual constraint per primal variable; the dual of the dual is the primal.
• Conversion rules: max ↔ min; ≤ constraint ↔ y ≥ 0; = constraint ↔ unrestricted dual variable; unrestricted primal variable ↔ dual equality constraint.
• Weak duality: for feasible x, y, cᵗx ≤ bᵗy. Strong duality: at optimality cᵗx* = bᵗy*. If the primal is unbounded the dual is infeasible; the converse need not hold — primal and dual can both be infeasible.
• Complementary slackness: at optimality, (slack of primal constraint i) × yᵢ* = 0 and xⱼ* × (surplus of dual constraint j) = 0 — a binding constraint can have a positive shadow price; a non-binding one has zero price.
• Economic meaning: yᵢ* is the shadow price (marginal worth) of one more unit of resource i — the rupee increase in optimal profit per additional unit, valid within a range.
• Why use the dual: fewer constraints means fewer simplex iterations (an m×n problem becomes n×m); the dual simplex method restarts from an optimal-but-infeasible table, which is how added constraints and branch-and-bound are handled.

Sensitivity (post-optimality) analysis

• Objective coefficient ranging: how far cⱼ can move before the current basis stops being optimal — derived from keeping all cⱼ − Zⱼ ≤ 0.
• RHS ranging: how far bᵢ can move with the same basis; within that range Δ Z = yᵢ* × Δbᵢ.
• Adding a new variable (product): price it out — if cⱼ − Zⱼ ≤ 0 it is not worth making.
• Adding a constraint: check the current optimum; if violated, reoptimise by dual simplex.
• Revised simplex / B⁻¹ form: xB = B⁻¹b, and the simplex multipliers yᵗ = cBᵗB⁻¹ — the basis for commercial solvers.

Transportation and assignment problems

• Transportation problem: m sources with supply aᵢ, n destinations with demand bⱼ, cost cᵢⱼ; minimise Σcᵢⱼxᵢⱼ. Balanced when Σaᵢ = Σbⱼ (else add a dummy row/column with zero costs). A non-degenerate BFS has exactly m+n−1 basic cells.
• Initial basic feasible solution: North-West Corner Rule (quick, ignores cost), Least Cost (Matrix Minima), Vogel's Approximation Method (VAM) — uses the penalty (difference of the two least costs in each row/column) and usually lands closest to optimum.
• Optimality: MODI / u-v method — set uᵢ + vⱼ = cᵢⱼ for basic cells (fix one u = 0), then the opportunity cost dᵢⱼ = cᵢⱼ − uᵢ − vⱼ for non-basic cells; all dᵢⱼ ≥ 0 means optimal, else bring in the most negative cell using a closed stepping-stone loop. (Stepping-stone method is the same test done loop by loop.)
• Transportation costs are integral by nature — the optimal LP solution is automatically integer when supplies and demands are integers (unimodularity).
• Assignment problem: a special transportation problem with n jobs, n persons, all supplies and demands = 1; solved by the Hungarian method: row reduction → column reduction → cover all zeros with the minimum number of lines → if lines < n, subtract the smallest uncovered element from uncovered elements and add it at line intersections → repeat → assign on zeros. Maximisation is handled by subtracting all entries from the largest entry.
• Prohibited routes/assignments get a very large cost M; unbalanced assignment problems get dummy rows/columns.

Extensions, computation and limitations

• Integer linear programming (ILP): required when variables count things (machines, trucks, yes/no). Solved by Gomory's cutting plane or branch and bound; 0-1 problems model selection and sequencing. Rounding an LP answer is not reliable — it may be infeasible or far from optimal.
• Goal programming handles multiple conflicting objectives by minimising weighted deviations; parametric LP studies a coefficient varying continuously.
• Algorithms: simplex is exponential in the worst case but near-linear in practice; Khachiyan's ellipsoid method (1979) and Karmarkar's interior-point / projective method (1984, by Narendra Karmarkar, then at Bell Labs, an IIT Bombay alumnus) are polynomial-time; the ellipsoid method matters theoretically only, while interior-point methods descended from Karmarkar's are the engines behind large-scale solvers.
• Advantages: optimal (not merely good) solutions, shadow prices for pricing and bidding, sensitivity information, scalable software, clear what-if structure.
• Limitations: linearity rarely exact (economies of scale, setup costs, discounts); divisibility often false; single objective; parameters assumed certain (stochastic/robust LP needed otherwise); large models are data-hungry and hard to audit.
• Tools used in India: Excel Solver (Simplex LP engine) and LibreOffice Solver for coursework; Python PuLP/SciPy linprog, R lpSolve; commercial Gurobi/CPLEX and open-source CBC/HiGHS in industry; LINGO/TORA in labs.
• Monetary units in Indian problems are ₹ per unit, and resource units SI (kg, litre, machine-hour); there is no Indian Standard that governs LP method — it is mathematics, though procurement and ration-blending decisions built on it must respect the applicable rules (e.g. GST at 5%/18%/40% slabs since 22 September 2025 changes the net cost coefficients cⱼ used in a planning model).

Key points

• Linear programming - optimising a linear objective over a set defined by linear constraints and sign restrictions.
• Feasible region - a convex polyhedron; convexity guarantees a local optimum is global.
• Extreme point theorem - an optimal solution, if any, lies at a vertex of the feasible region.
• Basic feasible solution - set n−m variables to zero, solve; all values ≥ 0; corresponds to a vertex; at most ⁿCₘ of them.
• Slack vs surplus - slack added to a ≤ constraint (unused resource), surplus subtracted from a ≥ constraint (excess over requirement); both ≥ 0.
• Artificial variable - a purely computational device to start simplex on ≥ or = constraints; must leave the basis for feasibility.
• Optimality criterion (max) - stop when every cⱼ − Zⱼ ≤ 0; most positive value enters.
• Minimum ratio rule - leaving variable is from the least non-negative ratio bᵢ/aᵢₖ over positive aᵢₖ only.
• Unbounded - improving column has no positive entry; infeasible - an artificial stays basic positive at optimum.
• Degeneracy - a basic variable at zero, caused by a tie in the ratio test; may cause cycling.
• Alternative optima - a non-basic variable with cⱼ − Zⱼ = 0 at the optimum.
• Duality - m constraints, n variables in the primal become n constraints, m variables in the dual; optimal objective values are equal.
• Shadow price - the dual variable; rupee gain in Z per extra unit of that resource, zero for a slack (non-binding) constraint.
• Complementary slackness - product of a primal slack and its dual variable is zero at optimality.
• Transportation BFS - m+n−1 basic cells; VAM gives the best start; MODI tests optimality with dᵢⱼ = cᵢⱼ − uᵢ − vⱼ.
• Assignment - n×n one-to-one case solved by the Hungarian method in O(n³); solution is always integer.
• Integer programming - needed for indivisible items; use branch and bound or cutting planes, never plain rounding.
• Karmarkar's algorithm - polynomial-time interior-point method; simplex remains the standard classroom and many-practice method.

Formulas and examples

Example 1 — Graphical method (product mix). A Pune workshop makes chairs (₹300 profit) and tables (₹500 profit). A chair needs 2 carpentry-hours and 1 finishing-hour; a table needs 4 carpentry-hours and 1 finishing-hour. Available: 240 carpentry-hours, 80 finishing-hours.

Model: max Z = 300x + 500y s.t. 2x + 4y ≤ 240, x + y ≤ 80, x, y ≥ 0.

• Intercepts: carpentry line (120, 0) and (0, 60); finishing line (80, 0) and (0, 80).
• Intersection: from x + y = 80 → x = 80 − y; substitute: 2(80 − y) + 4y = 240 → 160 + 2y = 240 → y = 40, x = 40.
• Corner values: (0,0) → 0; (80,0) → ₹24,000; (40,40) → 300(40)+500(40) = 12,000+20,000 = ₹32,000; (0,60) → ₹30,000.
• Optimum: 40 chairs and 40 tables, Z = ₹32,000. Both constraints are binding (2·40+4·40 = 240; 40+40 = 80), so both shadow prices are positive.

Example 2 — Simplex, same problem. Standard form: 2x + 4y + s₁ = 240; x + y + s₂ = 80.

y enters (500 largest), s₁ leaves (ratio 60). Divide row 1 by 4 → (0.5, 1, 0.25, 0, 60); new row 2 = old row 2 − row 1 → (0.5, 0, −0.25, 1, 20).

x enters, s₂ leaves. Row 2 ÷ 0.5 → (1, 0, −0.5, 2, 40); row 1 − 0.5×new row 2 → (0, 1, 0.5, −1, 40).

All cⱼ−Zⱼ ≤ 0 → optimal: x = 40, y = 40, Z = ₹32,000, matching the graphical answer. Shadow prices from the slack columns: ₹100 per carpentry-hour and ₹100 per finishing-hour. Check: 100(240) + 100(80) = 24,000 + 8,000 = ₹32,000 = Z, as strong duality requires.

Example 3 — Dual and its verification. Dual of Example 1: min W = 240y₁ + 80y₂ s.t. 2y₁ + y₂ ≥ 300 (chair), 4y₁ + y₂ ≥ 500 (table), y₁, y₂ ≥ 0.

• Both primal variables are positive, so by complementary slackness both dual constraints hold as equalities: 2y₁ + y₂ = 300 and 4y₁ + y₂ = 500 → subtracting, 2y₁ = 200 → y₁ = 100, y₂ = 300 − 200 = 100.
• W = 240(100) + 80(100) = 24,000 + 8,000 = ₹32,000 = Z*. Interpretation: one extra carpentry-hour or finishing-hour each adds ₹100 to profit — so paying overtime up to ₹100/hour is worthwhile.
• Sensitivity: if carpentry-hours rise from 240 to 250, ΔZ = 100 × 10 = ₹1,000 (new Z = ₹33,000) provided the basis stays feasible — check: y = (0.5)(250) − 80 = 45, x = −0.5(250) + 2(80) = 35, both ≥ 0, so valid.

Example 4 — Transportation by VAM, then MODI check. Three plants (supplies 20, 30, 25 tonnes) ship to three depots (demands 25, 25, 25). Costs in ₹ hundred per tonne:

Row penalties: P1 = 6−4 = 2, P2 = 5−3 = 2, P3 = 5−4 = 1. Column penalties: D1 = 5−4 = 1, D2 = 5−3 = 2, D3 = 7−4 = 3. Largest penalty = D3 → least cost in D3 is P3 (4) → allot min(25, 25) = 25 to P3D3. P3 and D3 are exhausted.

• Remaining 2×2: P1, P2 against D1, D2. Penalties: P1 = 2, P2 = 2, D1 = 1, D2 = 3 → D2 chosen, least cost P2 (3) → allot min(30, 25) = 25 to P2D2. D2 closed, P2 left with 5.
• Only D1 remains: P1 → 20 units, P2 → 5 units.
• Allocation: P1D1 = 20, P2D1 = 5, P2D2 = 25, P3D3 = 25. Basic cells = 4, but m+n−1 = 5 → degenerate; add a zero allocation (say P3D1) to complete the basis.
• Cost = 20(4) + 5(5) + 25(3) + 25(4) = 80 + 25 + 75 + 100 = ₹280 hundred = ₹28,000.
• MODI with u₁ = 0: basic cells P1D1 → v₁ = 4; P2D1 → u₂ = 5 − 4 = 1; P2D2 → v₂ = 3 − 1 = 2; P3D1 (zero cell) → u₃ = 6 − 4 = 2; P3D3 → v₃ = 4 − 2 = 2. Non-basic: d₁₂ = 6 − 0 − 2 = 4; d₁₃ = 8 − 0 − 2 = 6; d₂₃ = 7 − 1 − 2 = 4; d₃₂ = 5 − 2 − 2 = 1. All ≥ 0 → the VAM solution is optimal at ₹28,000.

Example 5 — Assignment by the Hungarian method. Four engineers, four sites; travel cost in ₹ thousand:

Row reduction (subtract row minima 10, 5, 11, 8):

Column reduction (column minima 0, 2, 2, 0):

The minimum number of lines needed to cover all zeros is 4 — for example {column S1, row E1, column S3, row E3} — which equals n, so no further adjustment is required and a complete assignment on zeros exists. Assignment on zeros: E1→S2 (its only remaining zero), E2→S3, E3→S4, E4→S1.

• Cost = 12 + 7 + 11 + 8 = ₹38 thousand. Cross-check an alternative (E1→S4, E2→S3, E3→S2, E4→S1): 11 + 7 + 14 + 8 = ₹40 thousand — higher, so ₹38,000 stands.

Where it is used

• Manufacturing and process plants: product-mix and blending at Indian Oil, Reliance and HPCL refineries (crude and gasoline blending is classic LP), cement kiln feed blending, steel charge mix at Tata Steel and SAIL.
• Supply chain and logistics: warehouse-to-store allocation and vehicle loading at Flipkart, Amazon India, Delhivery, Blue Dart; FCI grain movement and PDS allocation across states are transportation models.
• Agriculture and food: least-cost cattle-feed and poultry-feed formulation (Godrej Agrovet, Amul), cropping-pattern and irrigation-water allocation studies by ICAR and state water resource departments.
• Finance and energy: portfolio and asset-liability models in banks and insurers, generation scheduling and merit-order dispatch by POSOCO/Grid-India and SLDCs, power-purchase optimisation by DISCOMs.
• Workforce and services: shift and manpower rostering in BPOs, airlines (IndiGo, Air India crew pairing uses large integer LPs), hospital staffing, telecom network planning.
• Job roles: operations research analyst, supply chain/network design analyst, revenue management analyst, data scientist (optimisation), industrial engineer; also the OR papers of UPSC Indian Statistical Service and ISRO/DRDO technical recruitment.

Interview questions

• Q: Why does the optimal solution of an LP always occur at a corner point? A: The objective is linear and the feasible region convex, so the function's maximum over the region is attained at an extreme point; if an interior or edge point were optimal, moving along the improving direction would reach a vertex that is at least as good.
• Q: What is the difference between slack, surplus and artificial variables? A: Slack is added to a ≤ constraint and measures unused resource; surplus is subtracted from a ≥ constraint and measures excess over requirement; an artificial variable has no physical meaning and only provides a starting basis, and must leave the basis for the solution to be feasible.
• Q: How do you detect an unbounded solution in the simplex table? A: An entering column has a positive cⱼ − Zⱼ but no positive coefficient in any row, so no leaving variable exists and the objective can be improved without limit.
• Q: How do you know a problem is infeasible from the simplex table? A: The optimality condition is satisfied yet an artificial variable remains in the basis at a positive value.
• Q: What is a shadow price, and when is it zero? A: It is the dual variable — the change in the optimal objective per unit increase in that constraint's RHS; it is zero when the constraint is non-binding (positive slack), because extra capacity has no value.
• Q: State and interpret complementary slackness. A: At optimality the product of each primal slack with its dual variable, and each primal variable with its dual constraint's surplus, is zero — a resource is either fully used or worthless, and an activity is either not produced or priced exactly at its marginal worth.
• Q: Why solve the dual instead of the primal? A: If the primal has many constraints and few variables, the dual has fewer constraints and so fewer simplex iterations; the dual also supplies prices and is the basis for dual simplex reoptimisation.
• Q: What is degeneracy and why does it matter? A: A basic variable takes the value zero (usually from a tie in the minimum-ratio test); it can cause iterations that do not improve Z and, rarely, cycling, which anti-cycling rules such as Bland's rule prevent.
• Q: Can you just round off an LP solution to get an integer answer? A: No — rounding can be infeasible or significantly sub-optimal; integer problems need branch and bound or cutting planes.
• Q: Why is a transportation problem's optimal solution automatically integer? A: Its constraint matrix is totally unimodular, so every basic solution is integral when supplies and demands are integers — hence no integer programming is needed.
• Q: Which initial solution method for a transportation problem is best and why? A: Vogel's Approximation Method, because its penalty logic accounts for the cost of not using the cheapest route and usually starts very close to or at the optimum; North-West Corner is fastest but ignores cost entirely.
• Q: What are the main assumptions that limit LP in real industry use? A: Linearity and additivity, divisibility of variables, certainty of all coefficients and a single objective — real problems have setups, discounts, integers, uncertainty and multiple goals, handled by MILP, stochastic or goal programming.

Common mistakes

• Forgetting the non-negativity restrictions, or ignoring that a min problem needs max(−Z) or a consistently reversed optimality rule.
• Using negative or zero coefficients in the minimum-ratio test — only strictly positive entries of the key column qualify.
• Adding a slack where a surplus and artificial are needed (≥ constraint), or leaving a negative RHS in standard form instead of multiplying the row by −1 and flipping the inequality.
• Writing the dual mechanically: missing that an equality constraint gives an unrestricted dual variable and that the primal must first be in the right max-≤ or min-≥ orientation.
• Reading a shadow price as valid for any size of change — it holds only over the RHS range for which the current basis stays feasible.
• Not checking m+n−1 basic cells in a transportation table, so MODI is attempted on a degenerate solution without inserting a zero allocation.
• Reporting fractional machines, people or vehicles as the answer, and quoting corner-point values without verifying the intersection coordinates by substitution.

Related topics

Graph theory basics · Numerical methods · Matrix algebra and systems of linear equations · Convex optimisation and nonlinear programming · Game theory and decision analysis · Queuing theory and inventory models