Chapter 12 — Linear Programming
Optimising a linear objective under linear constraints: the geometry of corners, the simplex method and its two-phase and revised forms, duality and complementary slackness, and the two special LPs that are solved on a table — transportation and assignment.
In 1939 Leonid Kantorovich, a young mathematician in Leningrad, was asked by a plywood trust how to split work among its machines so as to produce as much as possible. He noticed that the question — maximise a linear quantity subject to linear restrictions — is the same for a factory, a farm or a railway network, and he invented a method of "resolving multipliers" to answer it. Two years later Frank Hitchcock formulated the problem of shipping a commodity from several sources to several destinations at least cost, and during the war Tjalling Koopmans studied the same problem for Allied shipping. In 1947 George Dantzig, working on planning problems for the US Air Force, gave the general problem its modern form, the linear programme, and the simplex method that still solves most of them. Kantorovich and Koopmans shared the 1975 Nobel Prize in Economics for this work.
The mathematics is a happy meeting of geometry and linear algebra. The feasible set is a convex polyhedron; its corners are exactly the solutions obtained by choosing a set of linearly independent columns of the constraint matrix; and if an optimum exists, one sits at a corner. The simplex method walks from corner to corner, improving the objective at each step and recognising when it can stop. Behind every LP stands a second one, its dual, whose variables are prices: the two optimal values coincide, and complementary slackness ties the two solutions together. Transportation and assignment problems are LPs with so much structure that the simplex method can be run on a table with pencil and paper, and in 1955 Harold Kuhn turned an idea of the Hungarian mathematicians Dénes Kőnig and Jenő Egerváry into the Hungarian method for assignments.
- formulate production, blending, diet and shipping problems as linear programmes and solve two-variable LPs graphically, recognising infeasible, unbounded and alternative-optimum cases at sight;
- list and count the basic and basic feasible solutions of a system $Ax=b$, $x\ge0$, and explain why they are exactly the corners of the feasible region;
- run the simplex method from a slack basis, and the two-phase and Big-M methods when artificial variables are needed; carry out a revised-simplex iteration with $B^{-1}$ only;
- read a simplex tableau at a glance: optimal or not, unique or alternative optima, unbounded, degenerate, infeasible;
- write the dual of any LP, use weak and strong duality and complementary slackness to solve or certify problems, and interpret dual variables as shadow prices;
- solve balanced and unbalanced transportation problems — north-west corner, least-cost and Vogel starts, MODI optimality test, loops and degeneracy — and assignment problems by the Hungarian method, including maximisation and unbalanced versions.
How this is examined
Linear programming is one of the most dependable sources of marks in GATE MA, because its questions are short and computational. MCQs and NATs ask for the optimal value of a small LP (solved graphically, by a couple of simplex pivots, or — when there are many variables and two constraints — through the dual), for the number of basic or basic feasible solutions of a system, for the value of a dual variable or a shadow price, for the initial cost given by the north-west corner, least-cost or Vogel rule, or for the minimum cost of a transportation or assignment problem. MSQs typically show a simplex tableau with a parameter or two and ask which statements are true — "the current solution is optimal", "the problem has alternative optima", "the problem is unbounded", "the next pivot is degenerate" — or list statements about duality ("if the primal is infeasible, the dual is unbounded") and about transportation bases ("a basic feasible solution has $m+n$ positive entries"). The false options are almost always the counterexamples collected in the ⚠️ boxes of the two sections. The same material appears in CSIR NET Part B and Part C and in IIT JAM-level operations research courses.
Sections in this chapter
LP Models, Simplex, Two-Phase and Revised Simplex, Duality
Formulation and the graphical method; convex sets and extreme points; basic feasible solutions; the simplex tableau, degeneracy, unbounded and alternative optima; artificial variables, two-phase and Big-M methods; the revised simplex method; duality, weak and strong duality, complementary slackness.
Transportation and Assignment Problems
Balanced and unbalanced transportation problems; bases as spanning trees; north-west corner, least-cost and Vogel starts; the MODI (u–v) method with loops and degeneracy; assignment problems, Kőnig's theorem and the Hungarian method with its unbalanced and maximisation variants.
You need the linear algebra of §3.1: solving linear systems by elimination, rank, linear independence, bases of $\mathbb{R}^m$ and the inverse of a matrix — a basic feasible solution is nothing but a choice of $m$ independent columns. The Gauss–Jordan elimination of §9.1 is exactly what a simplex pivot does. Nothing else is assumed: convex sets and extreme points are defined from scratch in §12.1. For the longer proofs (the fundamental theorem of linear programming in full, Big-M equivalence, Farkas' lemma, the dual simplex method), see CSIR Unit 4 · §9.2 Linear Programming: Simplex Method and Duality.