12.1 LP Models, Simplex, Two-Phase and Revised Simplex, Duality
Linear programmes and their geometry — convex feasible regions, extreme points and basic feasible solutions; the simplex method with its optimality, unboundedness and degeneracy tests; artificial variables, the two-phase and Big-M methods and the revised simplex method; and duality, from weak and strong duality to complementary slackness.
A dairy cooperative decides how much paneer and how much curd to make from a limited supply of milk and a limited number of working hours; a feed mill blends grains to meet nutrient targets at least cost; a power utility dispatches its generating stations to meet demand at least fuel cost. In each case the decision is a vector $x$ of quantities, each requirement is a linear inequality in $x$, and the goal is to maximise or minimise a linear function of $x$. Such a problem is a linear programme (LP). Its feasible region is a convex polyhedron, an optimum — if there is one — sits at a corner, and the corners can be found by pure linear algebra: they are the basic feasible solutions, obtained by choosing linearly independent columns of the constraint matrix. The simplex method walks along edges from corner to corner, improving the objective at each step, and its final tableau also solves a second LP, the dual, whose variables are prices.
GATE MA examines this section in a very predictable way. NATs and MCQs ask for the optimal value of a small LP (graphically, by one or two pivots, or — for many variables and two constraints — by solving the dual), for the number of basic feasible solutions of a system $Ax=b$, $x\ge0$, for a dual variable or a shadow price, or for the dual of a problem with mixed constraints. MSQs show a simplex tableau with a parameter and ask which statements hold: optimal, unique, alternative optima, unbounded, degenerate. Others list statements about duality and expect you to know which are theorems and which have counterexamples. The linear algebra used is that of §3.1 (rank, independence, inverses); a simplex pivot is the Gauss–Jordan step of §9.1. The notation follows the CSIR NET course, where the long proofs are written out in full (see the 📚 Go deeper box).
LP Models, Convex Sets and the Graphical Method
Vectors are columns; $x\ge0$ means that every component is nonnegative, and $c^{\mathsf T}x=\sum_jc_jx_j$. An inequality $a^{\mathsf T}x\le\beta$ with $a\ne0$ describes a closed half-space and $a^{\mathsf T}x=\beta$ a hyperplane.
A linear programming problem asks for the maximum (or minimum) of a linear objective function $z=c^{\mathsf T}x$ over all $x\in\mathbb{R}^n$ satisfying finitely many linear equations and inequalities (the constraints). A point satisfying every constraint is a feasible solution; the set of them is the feasible region $P$. A feasible $x^*$ with $c^{\mathsf T}x^*\ge c^{\mathsf T}x$ for every $x\in P$ is an optimal solution and $c^{\mathsf T}x^*$ the optimal value. The LP is infeasible if $P=\varnothing$ and unbounded if $\sup_{x\in P}c^{\mathsf T}x=+\infty$. Two forms are used:
$$\text{(SF)}\quad\max\ c^{\mathsf T}x\ \ \text{s.t.}\ \ Ax=b,\ x\ge0,$$ $$\text{(CF)}\quad\max\ c^{\mathsf T}x\ \ \text{s.t.}\ \ Ax\le b,\ x\ge0.$$In the standard form (SF) $A$ is $m\times n$ of rank $m$. Every LP can be brought to SF: $\min c^{\mathsf T}x=-\max(-c)^{\mathsf T}x$; a constraint $a^{\mathsf T}x\le\beta$ becomes $a^{\mathsf T}x+s=\beta$ with a slack variable $s\ge0$, and $a^{\mathsf T}x\ge\beta$ becomes $a^{\mathsf T}x-s=\beta$ with a surplus variable $s\ge0$; a variable free in sign is written $x_j=x_j^+-x_j^-$ with $x_j^\pm\ge0$; redundant equations are deleted until the rows of $A$ are independent.
- The feasible region of every LP is a closed convex set (a polyhedron).
- The set of optimal solutions is convex. Hence an LP with two different optimal solutions has infinitely many.
- If $P=\operatorname{conv}\{v_1,\dots,v_k\}$ is a polytope, then $\max_{x\in P}c^{\mathsf T}x=\max_ic^{\mathsf T}v_i$.
- If $P\ne\varnothing$ has a direction $d$ with $c^{\mathsf T}d\gt0$, the LP $\max_{x\in P}c^{\mathsf T}x$ is unbounded.
Proof. (1) An equation is two inequalities and $x_j\ge0$ is $-x_j\le0$, so $P$ is an intersection of closed half-spaces. A half-space is convex because $a^{\mathsf T}(\lambda u+(1-\lambda)v)=\lambda a^{\mathsf T}u+(1-\lambda)a^{\mathsf T}v\le\beta$ when $a^{\mathsf T}u,a^{\mathsf T}v\le\beta$; intersections of closed convex sets are closed and convex. (2) If $u,v$ are optimal with value $z^*$, then $w=\lambda u+(1-\lambda)v\in P$ and $c^{\mathsf T}w=\lambda z^*+(1-\lambda)z^*=z^*$. (3) For $x=\sum\lambda_iv_i$ with $\lambda_i\ge0$, $\sum\lambda_i=1$: $c^{\mathsf T}x=\sum\lambda_ic^{\mathsf T}v_i\le\max_ic^{\mathsf T}v_i$. (4) For any $x\in P$, the points $x+td$ are feasible and $c^{\mathsf T}(x+td)=c^{\mathsf T}x+t\,c^{\mathsf T}d\to\infty$. ∎
When there are two decision variables the region can be drawn. The graphical method draws $P$, then an iso-profit line $c^{\mathsf T}x=k$, and slides it parallel to itself in the direction of $c$ (the direction in which $z$ increases) until it is about to leave $P$. The last points of contact are optimal; if the line can slide for ever while still meeting $P$, the LP is unbounded. Interactive 1 below animates exactly this.
- Draw each constraint line; shade the side that satisfies it (test the origin). The feasible region $P$ is the common part.
- Infeasible if the shaded parts have no common point (often visible as two constraints that "point away" from each other).
- Find the corners (intersections of two boundary lines that satisfy all constraints) and evaluate $z$ at each.
- If $P$ is bounded, the best corner value is the optimum (Theorem 12.1(3)). If $P$ is unbounded, look at its edge directions $d$: if $c^{\mathsf T}d\gt0$ for one of them, the LP is unbounded; otherwise the best corner is optimal.
- Alternative optima occur when the iso-profit line is parallel to an edge through the optimal corner: $c$ is a multiple of that edge's normal (or $c^{\mathsf T}d=0$ for an unbounded edge direction $d$, giving a whole ray of optima).
Basic Feasible Solutions and Extreme Points
In three or more variables we cannot draw, so we need an algebraic description of corners. Work with (SF): $P=\{x\in\mathbb{R}^n:Ax=b,\ x\ge0\}$, $A=[a_1\ \cdots\ a_n]$ of rank $m$.
A basis is a set $\mathcal B=\{B_1,\dots,B_m\}$ of column indices for which the $m\times m$ matrix $B=[a_{B_1}\ \cdots\ a_{B_m}]$ is invertible; $\mathcal N$ is the set of the other indices. The basic solution of $\mathcal B$ is the unique $x$ with $x_j=0$ for $j\in\mathcal N$ and $Ax=b$, namely $x_{\mathcal B}=B^{-1}b$; its components $x_j$, $j\in\mathcal B$, are the basic variables. A basic solution with $x_{\mathcal B}\ge0$ is a basic feasible solution (BFS). A BFS is degenerate if some basic variable is $0$, i.e. it has fewer than $m$ positive components.
There are at most $\binom nm$ ways to choose $m$ columns, so at most $\binom nm$ basic solutions.
Proof. (i)⇒(ii): if $x$ is the BFS of $\mathcal B$ then $J\subseteq\mathcal B$, and part of an independent set is independent. (ii)⇒(i): an independent set of columns of the rank-$m$ matrix $A$ extends to $m$ independent columns $\mathcal B\supseteq J$; then $x$ vanishes off $\mathcal B$ and $Bx_{\mathcal B}=Ax=b$, so $x_{\mathcal B}=B^{-1}b$. (ii)⇒(iii): suppose $x=\lambda u+(1-\lambda)v$ with $u,v\in P$, $0\lt\lambda\lt1$. If $x_j=0$ then $u_j=v_j=0$ (two nonnegative numbers with a positive-weight average $0$). So $u-v$ is supported in $J$ and $\sum_{j\in J}(u_j-v_j)a_j=A(u-v)=b-b=0$; independence gives $u=v$, hence $u=v=x$. (iii)⇒(ii): if $\sum_{j\in J}d_ja_j=0$ with $d\ne0$ (set $d_j=0$ off $J$), choose $\varepsilon\gt0$ with $\varepsilon|d_j|\lt x_j$ on $J$; then $x\pm\varepsilon d\in P$ and $x=\tfrac12(x+\varepsilon d)+\tfrac12(x-\varepsilon d)$ is not extreme. ∎
Proof idea. For (2), take an optimal $x$ with the fewest positive components. If its support columns were dependent, the vector $d$ of the last proof would satisfy $c^{\mathsf T}d=0$ (both $x\pm\varepsilon d$ are feasible, so neither can beat $x$), and moving along $\pm d$ until the first positive component hits $0$ gives an optimal solution with smaller support — a contradiction; by Theorem 12.2 $x$ is a BFS. Part (1) is the same argument with the objective ignored. Part (3) needs the algorithm: if $P\ne\varnothing$, Phase I (Theorem 12.6 below) finds a BFS, and from it the simplex method with Bland's rule (Theorem 12.5) stops either at an optimal BFS or with a proof of unboundedness; see the 📚 Go deeper box. ∎
So an LP in standard form is a finite search: if an optimum exists, one of at most $\binom nm$ BFSs is optimal. Listing them all is hopeless in practice ($\binom{100}{50}\approx10^{29}$), but for GATE-sized systems it is a standard question.
| basis | solution $(x_1,x_2,x_3,x_4)$ | status |
|---|---|---|
| $\{x_1,x_2\}$ | $(0,2,0,0)$ | BFS, degenerate |
| $\{x_1,x_3\}$ | $(2,0,2,0)$ | BFS |
| $\{x_1,x_4\}$ | $(4,0,0,-2)$ | infeasible |
| $\{x_2,x_3\}$ | $(0,2,0,0)$ | BFS, degenerate |
| $\{x_2,x_4\}$ | $(0,2,0,0)$ | BFS, degenerate |
| $\{x_3,x_4\}$ | $(0,0,4,2)$ | BFS |
The Simplex Method: Optimality, Unboundedness, Degeneracy
Fix a basis $\mathcal B$ with matrix $B$; write $y_j=B^{-1}a_j$ (the coordinates of $a_j$ in the basis), $\bar x_{\mathcal B}=B^{-1}b$, and $c_{\mathcal B}$ for the costs of the basic variables. Multiplying $Ax=b$ by $B^{-1}$ shows that every solution of $Ax=b$ satisfies $$x_{\mathcal B}=\bar x_{\mathcal B}-\sum_{j\in\mathcal N}y_jx_j,$$ $$c^{\mathsf T}x=z_0-\sum_{j\in\mathcal N}(z_j-c_j)\,x_j,\qquad(*)$$ where $z_0=c_{\mathcal B}^{\mathsf T}\bar x_{\mathcal B}$ is the value at the BFS and $z_j=c_{\mathcal B}^{\mathsf T}y_j$. Everything in the simplex method is read off from $(*)$.
- If $\Delta_j\ge0$ for all $j\in\mathcal N$, then $\bar x$ is optimal; if $\Delta_j\gt0$ for all $j\in\mathcal N$, it is the unique optimum.
- If $\Delta_j\ge0$ for all $j$ and $\Delta_k=0$ for some nonbasic $k$, then the points $x(t)$ of parts 3–4 for this $k$ are all optimal (for $0\le t\le\theta$, or for all $t\ge0$ if $y_k\le0$): there are alternative optima unless $\theta=0$ (degeneracy), and a whole ray of them if $y_k\le0$.
- If $\Delta_k\lt0$ and $y_{ik}\le0$ for every $i$, the LP is unbounded: $x(t)$ with $x_k=t$, $x_{\mathcal B}=\bar x_{\mathcal B}-ty_k$, other components $0$, is feasible for all $t\ge0$ and $c^{\mathsf T}x(t)=z_0-t\Delta_k\to\infty$.
- If $\Delta_k\lt0$ and some $y_{ik}\gt0$, let $\theta=\min\{\bar x_{B_i}/y_{ik}:y_{ik}\gt0\}$ (the minimum ratio test), attained in row $r$. Then $\mathcal B'=(\mathcal B\setminus\{B_r\})\cup\{k\}$ is a basis, $x(\theta)$ is its BFS, and $c^{\mathsf T}x(\theta)=z_0-\theta\Delta_k\ge z_0$, strictly if $\theta\gt0$. The new tableau is obtained by Gauss–Jordan elimination on the pivot $y_{rk}$.
Proof. (1) For feasible $x$, $(*)$ gives $c^{\mathsf T}x=z_0-\sum_{\mathcal N}\Delta_jx_j\le z_0$. If all nonbasic $\Delta_j\gt0$ and $c^{\mathsf T}x=z_0$, every nonbasic $x_j$ is $0$, so $x_{\mathcal B}=\bar x_{\mathcal B}$ and $x=\bar x$. (3)–(4): $Ax(t)=B(\bar x_{\mathcal B}-ty_k)+ta_k=b-tBy_k+ta_k=b$, and by $(*)$ $c^{\mathsf T}x(t)=z_0-t\Delta_k$. The basic components $\bar x_{B_i}-ty_{ik}$ never decrease when $y_{ik}\le0$; when $y_{ik}\gt0$ they stay $\ge0$ exactly for $t\le\bar x_{B_i}/y_{ik}$. So in (3) $x(t)\in P$ for all $t\ge0$, and in (4) for $0\le t\le\theta$, with $x_{B_r}(\theta)=0$. Since $a_k=\sum_iy_{ik}a_{B_i}$ with $y_{rk}\ne0$, $a_{B_r}$ is a combination of the columns of $\mathcal B'$, which therefore span $\mathbb{R}^m$; $x(\theta)$ vanishes off $\mathcal B'$, so it is its BFS. (2) is (4) or (3) with $\Delta_k=0$: the value stays $z_0$. ∎
- If every BFS is nondegenerate, the simplex method stops after finitely many pivots, at an optimal BFS (all $\Delta_j\ge0$) or at a column proving unboundedness.
- At a degenerate BFS a pivot may have $\theta=0$: the basis changes but the point and $z$ do not (a degenerate pivot). The method can then cycle through bases for ever. Bland's rule — enter the smallest index $k$ with $\Delta_k\lt0$, and among tied rows let the basic variable of smallest index leave — never cycles.
Proof of (1). Each pivot has $\theta\gt0$, so $z$ increases strictly (Theorem 12.4(4)); a basis determines its BFS and hence $z$, so no basis recurs, and there are at most $\binom nm$ of them. The proof that Bland's rule never cycles is a careful combinatorial argument which we omit. ∎
- Start. Write the problem in SF with $b\ge0$. If every constraint was $\le$, the slacks form the first basis ($B=I$, $\Delta_j=-c_j$). Otherwise add artificial variables (next subsection).
- Test. All $\Delta_j\ge0$: stop, optimal. A nonbasic $\Delta_k=0$ signals alternative optima: pivot column $k$ in to find another optimal BFS.
- Enter. Choose $k$ with $\Delta_k\lt0$ (Dantzig's rule: the most negative).
- Leave. If column $k$ has no positive entry: stop, unbounded. Otherwise the smallest ratio $\bar x_{B_i}/y_{ik}$ over $y_{ik}\gt0$ only; a tie means the next BFS is degenerate.
- Pivot on $y_{rk}$ and repeat. Checks: right-hand sides stay $\ge0$; $z_0$ never decreases; $z_0$ increases by $\theta\cdot|\Delta_k|$.
- Read off $x$ from the last column, $z^*$ from the corner, and the dual solution $\pi_i=\Delta_{s_i}$ from the slack columns. For a minimisation, maximise $-c^{\mathsf T}x$ and change the sign of the final value.
| basis | $x_1$ | $x_2$ | $s_1$ | $s_2$ | $s_3$ | $\bar x_{\mathcal B}$ | ratio |
|---|---|---|---|---|---|---|---|
| $s_1$ | $1$ | $\mathbf{2}$ | $1$ | $0$ | $0$ | $14$ | $7$ ← |
| $s_2$ | $3$ | $2$ | $0$ | $1$ | $0$ | $18$ | $9$ |
| $s_3$ | $1$ | $0$ | $0$ | $0$ | $1$ | $5$ | — |
| $\Delta_j$ | $-3$ | $-5$ | $0$ | $0$ | $0$ | $0$ |
| basis | $x_1$ | $x_2$ | $s_1$ | $s_2$ | $s_3$ | $\bar x_{\mathcal B}$ | ratio |
|---|---|---|---|---|---|---|---|
| $x_2$ | $\tfrac12$ | $1$ | $\tfrac12$ | $0$ | $0$ | $7$ | $14$ |
| $s_2$ | $\mathbf{2}$ | $0$ | $-1$ | $1$ | $0$ | $4$ | $2$ ← |
| $s_3$ | $1$ | $0$ | $0$ | $0$ | $1$ | $5$ | $5$ |
| $\Delta_j$ | $-\tfrac12$ | $0$ | $\tfrac52$ | $0$ | $0$ | $35$ |
| basis | $x_1$ | $x_2$ | $s_1$ | $s_2$ | $s_3$ | $\bar x_{\mathcal B}$ |
|---|---|---|---|---|---|---|
| $x_2$ | $0$ | $1$ | $\tfrac34$ | $-\tfrac14$ | $0$ | $6$ |
| $x_1$ | $1$ | $0$ | $-\tfrac12$ | $\tfrac12$ | $0$ | $2$ |
| $s_3$ | $0$ | $0$ | $\tfrac12$ | $-\tfrac12$ | $1$ | $3$ |
| $\Delta_j$ | $0$ | $0$ | $\tfrac94$ | $\tfrac14$ | $0$ | $36$ |
Artificial Variables: the Two-Phase and Big-M Methods; the Revised Simplex Method
If some constraints are $\ge$ or $=$, the slack columns do not supply an identity matrix and there is no obvious first BFS. We then add an artificial variable $a_i\ge0$ to each such row (after making $b\ge0$), which supplies the missing unit column, and force the artificial variables down to $0$.
- Phase I has an optimal solution, and its optimal value $w^*$ is $0$ if and only if the original problem is feasible.
- If $w^*=0$ and no artificial variable is basic at the end, the final basis is a feasible basis of the original problem. An artificial variable that is still basic (necessarily at level $0$) can be pivoted out on any nonzero entry of its row in an original column; if there is none, its equation is redundant and is deleted.
- In the Big-M method every net evaluation has the form $\alpha M+\beta$, and $\alpha$ is exactly the Phase I net evaluation. If Big-M ends optimal with some $a_i\gt0$, the original problem is infeasible.
Proof. (1) Phase I starts from the BFS $x=0$, $a=b$, and $w\ge0$ rules out unboundedness, so the simplex method with Bland's rule (Theorem 12.5) ends at an optimal BFS. If $x$ is feasible for the original problem, $(x,0)$ has $w=0$; conversely $w^*=0$ forces $a=0$ (a sum of nonnegative numbers), so $Ax^*=b$, $x^*\ge0$. (2) Pivoting on a nonzero entry of a row whose right-hand side is $0$ changes no values (a degenerate pivot; the pivot entry may even be negative). If the row of $a_r$ is zero in all original columns, a nonzero combination of the rows of $A$ is the zero row, and the same combination of $b$ equals $\bar x_{B_r}=0$, so that equation is a combination of the others. (3) $z_j-c_j$ is linear in the costs, and the Big-M costs are $c+M\cdot(\text{Phase I costs})$. An optimal Big-M tableau has every $\alpha_j\ge0$, so the same basis is Phase I optimal; if some $a_i\gt0$ there, $w^*\gt0$ and the problem is infeasible by (1). ∎
| basis | $x_1$ | $x_2$ | $s_1$ | $s_3$ | $a_1$ | $a_2$ | $\bar x_{\mathcal B}$ | ratio |
|---|---|---|---|---|---|---|---|---|
| $a_1$ | $1$ | $2$ | $-1$ | $0$ | $1$ | $0$ | $8$ | $8$ |
| $a_2$ | $\mathbf{3}$ | $1$ | $0$ | $0$ | $0$ | $1$ | $9$ | $3$ ← |
| $s_3$ | $1$ | $1$ | $0$ | $1$ | $0$ | $0$ | $6$ | $6$ |
| $\Delta_j$ | $-4$ | $-3$ | $1$ | $0$ | $0$ | $0$ | $-17$ |
| basis | $x_1$ | $x_2$ | $s_1$ | $s_3$ | $a_1$ | $a_2$ | $\bar x_{\mathcal B}$ |
|---|---|---|---|---|---|---|---|
| $x_2$ | $0$ | $1$ | $-\tfrac35$ | $0$ | $\tfrac35$ | $-\tfrac15$ | $3$ |
| $x_1$ | $1$ | $0$ | $\tfrac15$ | $0$ | $-\tfrac15$ | $\tfrac25$ | $2$ |
| $s_3$ | $0$ | $0$ | $\tfrac25$ | $1$ | $-\tfrac25$ | $-\tfrac15$ | $1$ |
| $\Delta_j$ | $0$ | $0$ | $0$ | $0$ | $1$ | $1$ | $0$ |
The revised simplex method. A full tableau stores and updates the $m\times n$ array $B^{-1}A$ at every pivot, although a pivot uses only one column of it ($y_k$), the right-hand side and the $\Delta$ row. When $n$ is much larger than $m$ — the usual case in practice — it is cheaper to keep only $B^{-1}$ and compute what is needed from the original data.
- Price. Compute $\pi^{\mathsf T}=c_{\mathcal B}^{\mathsf T}B^{-1}$ and $\Delta_j=\pi^{\mathsf T}a_j-c_j$ for $j\in\mathcal N$. If all $\Delta_j\ge0$, stop: optimal, with dual solution $\pi$.
- Column. For an entering $k$ with $\Delta_k\lt0$, compute $y_k=B^{-1}a_k$; if $y_k\le0$, stop: unbounded.
- Ratio test on $\bar x_{\mathcal B}$ and $y_k$ gives the pivot row $r$ and $\theta$.
- Update. $B^{-1}_{\text{new}}=E\,B^{-1}$ and $\bar x_{\mathcal B}^{\text{new}}=E\,\bar x_{\mathcal B}$, where the eta matrix $E$ is the identity with its $r$-th column replaced by $\eta$, $\eta_r=1/y_{rk}$, $\eta_i=-y_{ik}/y_{rk}$ ($i\ne r$).
Proof. $B^{-1}B'$ has the columns $e_i$ ($i\ne r$) and $B^{-1}a_k=y_k$ in position $r$. $E$ maps $y_k$ to $e_r$: its $r$-th entry is $y_{rk}\cdot\frac1{y_{rk}}=1$, and its $i$-th entry is $y_{ik}+y_{rk}\cdot\left(-\frac{y_{ik}}{y_{rk}}\right)=0$; and $E$ fixes every $e_i$, $i\ne r$. So $EB^{-1}B'=I$. ∎
Duality and Complementary Slackness
Suppose a contractor offers to rent all the cooperative's crews, boiling time and market quota at prices $y_1,y_2,y_3\ge0$. The cooperative agrees only if the inputs of a tonne of jaggery earn at least its profit, $y_1+3y_2+y_3\ge3$, and likewise $2y_1+2y_2\ge5$ for syrup; the contractor wants to pay as little as possible, $14y_1+18y_2+5y_3$. This LP is the dual of Example 1, and its optimum is the price vector $(\tfrac94,\tfrac14,0)$ read off in Example 4.
The dual of the canonical problem (P) $\max c^{\mathsf T}x$ s.t. $Ax\le b$, $x\ge0$ ($A$ any $m\times n$ matrix) is
$$\text{(D)}\qquad\min\ b^{\mathsf T}y\quad\text{s.t.}\quad A^{\mathsf T}y\ge c,\ \ y\ge0 .$$One dual variable belongs to each primal constraint and one dual constraint to each primal variable. For mixed problems:
| primal (max) | dual (min) |
|---|---|
| constraint $i$: $\le b_i$ / $\ge b_i$ / $=b_i$ | variable $y_i\ge0$ / $y_i\le0$ / $y_i$ free |
| variable $x_j\ge0$ / $x_j\le0$ / $x_j$ free | constraint $j$: $\ge c_j$ / $\le c_j$ / $=c_j$ |
| objective coefficients $c$ | right-hand sides $c$ |
| right-hand sides $b$ | objective coefficients $b$ |
Read from right to left, the table gives the dual of a minimisation problem. Memory aid: a "natural" constraint ($\le$ in a max, $\ge$ in a min) goes with a natural variable ($\ge0$).
Proof. (D) is the canonical problem $\max(-b)^{\mathsf T}y$ s.t. $(-A^{\mathsf T})y\le-c$, $y\ge0$. Its dual by definition is $\min(-c)^{\mathsf T}x$ s.t. $(-A^{\mathsf T})^{\mathsf T}x\ge-b$, $x\ge0$, i.e. $-\max c^{\mathsf T}x$ s.t. $Ax\le b$, $x\ge0$: problem (P). The mixed rules come from rewriting $\ge$ rows as $\le$ rows (a sign change of the dual variable), equations as two inequalities (a difference of two nonnegative variables, i.e. a free variable) and $x_j\le0$ or free $x_j$ by substitution; doing this twice undoes it. ∎
Proof. Using $x\ge0$ with $A^{\mathsf T}y\ge c$, then $y\ge0$ with $Ax\le b$: $c^{\mathsf T}x\le(A^{\mathsf T}y)^{\mathsf T}x=y^{\mathsf T}Ax\le y^{\mathsf T}b$. For (i), any feasible $x'$ has $c^{\mathsf T}x'\le b^{\mathsf T}y=c^{\mathsf T}x$; symmetrically for $y$. For (ii), a feasible $y$ would bound $c^{\mathsf T}x$ above. (iii) is (ii) for the pair (D), (P). ∎
- If (P) has an optimal solution, so does (D), and $\max c^{\mathsf T}x=\min b^{\mathsf T}y$. If $\mathcal B$ is an optimal simplex basis of (P) with slacks, $y^{\mathsf T}=c_{\mathcal B}^{\mathsf T}B^{-1}$ is an optimal dual solution; its components are the net evaluations of the slack columns.
- (Duality theorem) Exactly one of the following holds: both (P) and (D) have optimal solutions with equal values; one is unbounded and the other infeasible; both are infeasible.
Proof. (1) Run the simplex method (with an anti-cycling rule) on (P) with slacks; since (P) has an optimum it ends at a basis with all $\Delta_j\ge0$. Put $y^{\mathsf T}=c_{\mathcal B}^{\mathsf T}B^{-1}$. For a column $a_j$ of $A$, $\Delta_j=y^{\mathsf T}a_j-c_j\ge0$, i.e. $A^{\mathsf T}y\ge c$; for a slack column, $\Delta_{s_i}=y_i\ge0$. So $y$ is dual feasible, and $b^{\mathsf T}y=c_{\mathcal B}^{\mathsf T}B^{-1}b=c_{\mathcal B}^{\mathsf T}\bar x_{\mathcal B}=z^*$; by Theorem 12.9(i) it is optimal. (2) The cases exclude one another by weak duality. If (P) is feasible and bounded it has an optimum (Theorem 12.3(3)), giving the first case; if it is unbounded, (D) is infeasible. If (P) is infeasible and (D) feasible, (D) cannot have an optimum (by (1) applied to (D), (P) would have one), so (D) is unbounded. ∎
Proof. The duality gap is $$b^{\mathsf T}y-c^{\mathsf T}x=y^{\mathsf T}(b-Ax)+x^{\mathsf T}(A^{\mathsf T}y-c),$$ a sum of products of nonnegative numbers. If every product is $0$ the gap is $0$ and both are optimal (Theorem 12.9(i)). If both are optimal the gap is $0$ (Theorem 12.10), and a zero sum of nonnegative terms has all terms $0$. ∎
Complementary slackness is the fastest tool in a GATE paper: it certifies a claimed optimum (solve for $y$ from the tight conditions, then check dual feasibility), it solves an LP with many variables and two constraints through its two-variable dual, and it explains shadow prices: if the optimal basis stays feasible when $b$ changes to $b+\delta$ ($B^{-1}(b+\delta)\ge0$), it stays optimal (the $\Delta_j$ do not involve $b$), and $z^*(b+\delta)=z^*+y^{\mathsf T}\delta$. So $y_i$ is the marginal value of resource $i$, valid over the range of $b_i$ in which the basis stays feasible.
- Optimal solutions need not be corners. The optimal set is convex (Theorem 12.1(2)); in Example 2(d) it is a whole ray. Theorem 12.3 promises only that some optimal solution is basic.
- Unbounded region ≠ unbounded LP. Example 2(c) has an unbounded region and a unique finite optimum. What decides is the sign of $c^{\mathsf T}d$ on the directions $d$.
- Count points, not bases. In Example 3 five bases are feasible but there are only three BFSs; a degenerate BFS belongs to several bases.
- The ratio test uses positive entries only. A zero or negative $y_{ik}$ is skipped. If no entry is positive the LP is unbounded, not infeasible.
- The optimality test is sufficient, not necessary. For $\max2x_1+3x_2$ on the triangle of Example 3, the optimal corner $(0,2)$ with basis $\{x_2,x_4\}$ has $\Delta_{x_1}=-\tfrac12\lt0$; a degenerate pivot ($\theta=0$) is needed before all $\Delta_j\ge0$ (Interactive 2, third problem).
- Degeneracy can cause cycling (Beale's classical example has $3$ constraints and $7$ variables). Bland's rule prevents it; nondegenerate problems never cycle.
- $\Delta_k=0$ need not give a new point. At a degenerate optimal BFS, pivoting in a column with $\Delta_k=0$ may have $\theta=0$ and change only the basis. Conversely, all nonbasic $\Delta_j\gt0$ guarantees uniqueness.
- Phase I with $w^*\gt0$ means infeasible — not unbounded. An artificial variable left basic at level $0$ with $w^*=0$ is harmless (Theorem 12.6(2)).
- A numerical "Big M" can be too small. $\max x_1$ s.t. $-x_1+x_2=0$, $x_1\le3$, $x_2\le1$ has optimum $x=(1,1)$. With the artificial $a=x_1-x_2$ and $M=\tfrac12$, the Big-M objective is $\tfrac12x_1+\tfrac12x_2$, maximised at $x=(3,1)$ with $a=2\gt0$ — as if the problem were infeasible. Keep $M$ symbolic, as $\alpha M+\beta$.
- Dual sign rules. In a minimisation a $\le$ constraint gives $y_i\le0$; an equation gives a free variable and a free variable an equation. Writing every dual variable $\ge0$ is the commonest error.
- Weak duality allows double infeasibility. $\max x_1+x_2$ s.t. $x_1-x_2\le-2$, $-x_1+x_2\le1$, $x\ge0$ is infeasible (add the rows: $0\le-1$), and so is its dual (Exercise IV.8). "(D) infeasible ⇒ (P) unbounded" is false.
- Complementary slackness works one way per pair. $y_i^*\gt0$ forces constraint $i$ to be tight, but a tight constraint may have $y_i^*=0$: for $\max x_1$ s.t. $x_1\le1$, $2x_1\le2$, both constraints are tight at $x^*=1$, yet $y^*=(1,0)$ is optimal.
- CSIR Unit 4 · §9.2 Linear Programming: Simplex Method and Duality — the complete proofs of the test for basic feasible solutions via Steinitz exchange and of the fundamental theorem of linear programming, the termination theorem and the existence of optima for bounded feasible LPs, the full Phase I / Big-M argument with the $\alpha M+\beta$ bookkeeping, strong duality via the simplex multipliers and the three-case duality theorem, Farkas' lemma as a consequence, the dual simplex method, and a first treatment of transportation and assignment problems (continued here in §12.2).
Two Labs
Exercises
- 1 A feed mill blends two grains. A kilogram of grain A costs ₹6 and supplies $2$ units of protein and $1$ unit of fibre; a kilogram of grain B costs ₹4 and supplies $1$ unit of protein and $2$ of fibre. A sack must contain at least $8$ units of protein and $7$ of fibre. Formulate the least-cost blend as an LP and solve it graphically.
- 2 Show that the disc $\{x\in\mathbb{R}^2:x_1^2+x_2^2\le1\}$ is convex and that every boundary point is an extreme point. Is it a polyhedron?
- 3 Prove that an LP cannot have exactly two optimal solutions.
- 4 Solve graphically: $\max\ 2x_1+4x_2$ s.t. $x_1+2x_2\le8$, $x_1\le6$, $x\ge0$. Describe all optimal solutions.
- 5 Decide graphically: $\max\ 3x_1+2x_2$ s.t. $x_1-x_2\le1$, $x_1+x_2\ge3$, $x\ge0$.
- 6 Decide graphically: $\min\ x_1+x_2$ s.t. $x_1-x_2\ge2$, $-x_1+x_2\ge1$, $x\ge0$.
- 7 Find all extreme points of $\{x\in\mathbb{R}^3:\ x\ge0,$ $x_1+x_2+x_3=1,$ $x_1\le\tfrac12\}$.
- 8 On the pentagon of Example 1, for which real $k$ does $\max\ x_1+kx_2$ have more than one optimal solution?
- 1 List the basic solutions of $x_1+x_2+x_3=4$, $x_1-x_2+x_4=2$ and count the basic feasible ones.
- 2 What is the largest possible number of basic solutions of a system of $3$ independent equations in $6$ unknowns, and exactly when is it attained? Give an example.
- 3 Prove that a nondegenerate basic feasible solution belongs to exactly one basis.
- 4 Solve by the simplex method: $\max\ 2x_1+5x_2+3x_3$ s.t. $2x_1+x_2+x_3\le13$, $3x_1+2x_2\le6$, $2x_1+x_3\le11$, $x\ge0$.
- 5 A maximisation tableau (variables $x_1,\dots,x_4$, basis $x_1,x_2$) has rows $x_1:(1,0,-2,1\mid3)$, $x_2:(0,1,a,2\mid5)$ and net evaluations $(0,0,b,3\mid21)$. For which $a,b$ is the current solution optimal? uniquely optimal? When are there alternative optima, and what do they look like? When is the LP unbounded? If $b\lt0\lt a$, what is $z$ after the next pivot?
- 6 Solve $\max\ 2x_1+x_2$ s.t. $x_1-x_2\le1$, $x_1\le3$, $x\ge0$ by the simplex method, and give a ray along which $z\to\infty$.
- 7 Prove: if all nonbasic net evaluations of an optimal tableau are positive, the optimal solution is unique. Is the converse true?
- 8 For $\max\ 3x_1+2x_2$ s.t. $x_1+x_2\le4$, $x_1\le4$, $x\ge0$, the first ratio test is a tie. Break it in favour of $s_2$ and continue; then redo it in favour of $s_1$. Explain the difference.
- 1 Solve by the two-phase method: $\min\ 2x_1+x_2+3x_3$ s.t. $x_1+x_2+x_3=6$, $x_1-x_2+2x_3\ge2$, $x\ge0$.
- 2 Use Phase I to show that $\max\ x_1+x_2$ s.t. $x_1+2x_2\le2$, $2x_1+x_2\ge6$, $x\ge0$ is infeasible. What is $w^*$?
- 3 Write the first Big-M tableau for Exercise III.1 and check that its net evaluations are $\alpha M+\beta$ with $\alpha$ the Phase I row.
- 4 Apply Phase I to $x_1+2x_2+x_3=4$, $2x_1+4x_2+2x_3=8$, $x\ge0$. What happens to the second artificial variable, and why?
- 5 In Exercise II.4, after the first pivot the basis is $(s_1,x_2,s_3)$. Write $B$ and $B^{-1}$, compute $\pi$ and the prices of $x_1,x_3,s_2$, and carry out the next revised-simplex iteration, including the eta matrix.
- 6 An LP has $m=50$ constraints and $n=1000$ variables. Roughly how many numbers does a full tableau update per pivot, and how many does a revised-simplex iteration update? Which extra work does the revised method do?
- 7 Explain why Phase I never ends with "unbounded".
- 1 Write the dual of $\max\ 3x_1-x_2+2x_3$ s.t. $x_1+x_2+x_3\le5$, $2x_1-x_2\ge1$, $x_1+3x_3=4$, $x_1\ge0$, $x_2\le0$, $x_3$ free.
- 2 Prove that the dual of (D) in Definition 12.7 is (P).
- 3 For Example 1, check that $x=(3,4)$ is primal feasible and $y=(2,1,0)$ dual feasible, and deduce bounds on $z^*$ without solving.
- 4 Solve $\min\ 8x_1+6x_2+5x_3$ s.t. $2x_1+x_2+x_3\ge4$, $x_1+2x_2+x_3\ge3$, $x\ge0$ by solving its dual graphically and using complementary slackness.
- 5 Use complementary slackness to prove that $x=(0,3,10)$ is optimal in Exercise II.4, and find the dual optimum.
- 6 In Example 1 the crew supply rises from $14$ to $15$. Predict the new optimal profit from the dual solution, and find the range of crew supplies over which this prediction method works.
- 7 Prove: if (P) is infeasible and (D) is feasible, then (D) is unbounded.
- 8 Show that $\max\ x_1+x_2$ s.t. $x_1-x_2\le-2$, $-x_1+x_2\le1$, $x\ge0$ and its dual are both infeasible.
E1. GATE MA · MCQ CSIR Part B The number of distinct basic feasible solutions of $x_1+x_2+x_3=2$, $x_1+2x_2+x_4=2$, $x_1,x_2,x_3,x_4\ge0$ is (A) $2$; (B) $3$; (C) $5$; (D) $6$.
E2. GATE MA · MCQ The dual of $\ \min\ 3x_1+2x_2\ $ s.t. $x_1+x_2\ge4$, $x_1-x_2\le2$, $x_1\ge0$, $x_2$ free, is: maximise $4y_1+2y_2$ subject to (A) $y_1+y_2\le3$, $y_1-y_2=2$, $y_1\ge0$, $y_2\le0$; (B) $y_1+y_2\le3$, $y_1-y_2=2$, $y_1\ge0$, $y_2\ge0$; (C) $y_1+y_2\le3$, $y_1-y_2\le2$, $y_1\ge0$, $y_2\le0$; (D) $y_1+y_2\ge3$, $y_1-y_2=2$, $y_1\ge0$, $y_2\le0$.
E3. GATE MA · MSQ In a simplex tableau of a maximisation problem in the variables $x_1,\dots,x_5$, the basic variables are $x_1,x_2$, the rows are $x_1:\ (1,0,-1,2,0\mid4)$, $x_2:\ (0,1,\alpha,1,-1\mid\beta)$ with $\beta\ge0$, and the net evaluations $z_j-c_j$ are $(0,0,\gamma,3,1)$ with current value $20$. Which of the following is/are true? (One or more options may be correct.) (A) If $\gamma\gt0$, the current basic feasible solution is the unique optimal solution. (B) If $\gamma=0$, $\beta\gt0$ and $\alpha\le0$, the problem has infinitely many optimal solutions. (C) If $\gamma\lt0$ and $\alpha\le0$, the problem is unbounded. (D) If $\gamma\lt0$, $\alpha\gt0$ and $\beta=0$, the next simplex iteration strictly increases the objective value.
E4. GATE MA · MSQ CSIR Part C Let (P) be $\max c^{\mathsf T}x$ s.t. $Ax\le b$, $x\ge0$ and (D) its dual $\min b^{\mathsf T}y$ s.t. $A^{\mathsf T}y\ge c$, $y\ge0$. Which of the following is/are true? (One or more options may be correct.) (A) If (P) is unbounded, then (D) is infeasible. (B) If (D) is infeasible, then (P) is unbounded. (C) If $\bar x$ is feasible for (P), $\bar y$ is feasible for (D) and $c^{\mathsf T}\bar x=b^{\mathsf T}\bar y$, then $\bar x$ is optimal for (P). (D) If $y^*$ is optimal for (D) and $y_i^*=0$, then the $i$-th constraint of (P) holds with strict inequality at every optimal solution of (P).
E5. GATE MA · NAT The optimal value of $\ \max\ 2x_1+3x_2+4x_3+x_4\ $ subject to $x_1+x_2+2x_3+x_4\le8$, $2x_1+3x_2+x_3+x_4\le9$, $x_1,\dots,x_4\ge0$ is ______ (rounded off to two decimal places).
E6. GATE MA · NAT In the LP of E5, the right-hand side $8$ of the first constraint is replaced by $8+\delta$, $\delta\ge0$. The largest value of $\delta$ for which the optimal value equals $18+1.8\,\delta$ is ______ (rounded off to two decimal places).
Suggested plan — 3 lectures × 60 min.
- Models and geometry. Formulate Example 1 with the class (let them name the constraints). Definitions 12.1–12.2, Theorem 12.1 with its four one-line proofs. Project Interactive 1 on the pentagon: sweep, then move $c_1$ through $\tfrac52$ and $\tfrac{15}2$ (Example 1(c)). Example 2 on the board, then Interactive 1 on the unbounded region with $c_1$ from $-3$ to $1$ (the jump at $c_1=-1$). Definition 12.3, Theorem 12.2 (the equivalence (ii)⇔(iii) in full), Example 3 and E1 live.
- The simplex method. Derive $(*)$ and Definition 12.4; Theorem 12.4 read as a checklist for a tableau. Example 4 on the board, with Interactive 2 (first problem) projected alongside. Theorem 12.5 and the degenerate problem of Interactive 2; pitfall 5. Exercise II.5 and E3 in pairs.
- Artificial variables, revised simplex, duality. Definition 12.5, Example 5 with Interactive 2 (second problem: Phase I walks into the segment). Definition 12.6, Theorem 12.7 and Example 6 (ask the class to spot $B^{-1}$ in Tableau 2 of Example 4). The contractor story, Definition 12.7 and the sign table; Theorems 12.9–12.11 with the duality-gap identity. Example 7 and E2, E5 live.
Discussion questions. (1) Why does the simplex method never need to look at interior points, and why might an algorithm that does (an interior-point method) still be faster on huge problems? (2) In Example 4 the dual prices are $(\tfrac94,\tfrac14,0)$; what would you pay for one more boiling hour, and for how many extra hours does that price hold? (3) If the optimal tableau has a zero net evaluation in a nonbasic column, must the LP have more than one optimal solution? (Look at degeneracy.)
Misconceptions to watch for. Counting bases instead of distinct BFSs; including zero or negative entries in the ratio test; calling a no-positive-entry column "infeasible"; believing that an unbounded region forces an unbounded LP, or that every optimal solution is a corner; treating the optimality test as necessary at degenerate corners; writing all dual variables $\ge0$; reading complementary slackness backwards ("tight ⇒ positive price"); concluding "(D) infeasible ⇒ (P) unbounded".
Suggested homework. I(1, 4, 5, 7, 8), II(1, 4, 5, 8), III(1, 2, 5), IV(1, 4, 6, 8); GATE corner E1, E3, E6.
Research question. How many pivots does the simplex method really need? On typical problems it is famously fast, yet there are problems on which Dantzig's rule visits every one of $2^n$ corners. Can you observe both behaviours?
Why it matters. Airlines schedule crews, refineries plan blends and electricity markets clear prices by solving LPs with millions of variables, and the simplex method remains one of the workhorses. In 1972 Victor Klee and George Minty built a slightly squashed cube on which the method with Dantzig's rule makes $2^n-1$ pivots; this started the search for polynomial-time algorithms (the ellipsoid method of 1979, Karmarkar's interior-point method of 1984) and, much later, the "smoothed analysis" explaining why the simplex method is fast in practice.
What to do.
- Write a short tableau simplex routine (Dantzig's rule, slack starting basis) for problems $\max c^{\mathsf T}x$, $Ax\le b$, $x\ge0$ with $b\ge0$; test it on Example 1 and Exercise II.4.
- Generate random problems with $m$ constraints and $2m$ variables (entries of $A$ and $c$ random integers $1$–$9$, $b$ random in $10$–$50$) for $m=5,10,20,40$, and record the average number of pivots over $20$ problems.
- Solve the Klee–Minty problem $\max\sum_{j=1}^n2^{n-j}x_j$ s.t. $2\sum_{j=1}^{i-1}2^{i-j}x_j+x_i\le5^i$ ($i=1,\dots,n$), $x\ge0$, for $n=2,\dots,8$; count the pivots and check the optimal value.
- Repeat step 3 with a different entering rule (largest improvement $\theta|\Delta_k|$, or Bland's rule) and compare.
Tools: Python with fractions or numpy (or a spreadsheet for $n\le3$).
Hand in: a table of average pivot counts for the random problems, a plot of pivots against $n$ for Klee–Minty on a log scale, and a paragraph on what "worst case" and "typical case" mean for an algorithm.
Going further. Read about interior-point methods, which follow a curved path through the interior of the polyhedron, and about Spielman and Teng's smoothed analysis (2001), which shows that small random perturbations of any LP make the expected number of simplex pivots polynomial.
🧪 Self-check quiz
Q1. A system $Ax=b$ of $3$ independent equations in $7$ unknowns has at most how many basic solutions?
Q2. In a maximisation tableau all $z_j-c_j\ge0$, and a nonbasic variable $x_k$ has $z_k-c_k=0$. Then
Q3. Phase I of the two-phase method ends with minimum sum of artificial variables $w^*=3$. The original LP is
Q4. If the primal (a maximisation) is unbounded, its dual is
Q5. At an optimal pair $(x^*,y^*)$ the dual variable $y_2^*$ is $5$. What can you conclude?