Chapter 9 · Reliability, Linear Programming and Queues

9.2 Linear Programming: Simplex Method and Duality

Optimising a linear objective over a polyhedron: the geometry of extreme points and basic feasible solutions, the simplex method and its optimality test, artificial variables (Big-M and two-phase), degeneracy and unboundedness, the duality theorems and complementary slackness, and the transportation and assignment problems.

A workshop must decide how much of each product to make with limited machine time and labour; a hospital must feed its patients at least cost while meeting nutritional targets; an airline must route aircraft, a refinery must blend crude oils, a grid operator must dispatch power stations. In each problem the decision is a vector $x$ of quantities, every requirement is a linear inequality in $x$, and the goal is to maximise or minimise a linear function of $x$. This is a linear programming problem (LP). George Dantzig's simplex method (1947) solves it by walking from corner to corner of the feasible region, improving the objective at every step, and it is still one of the most used algorithms in applied mathematics. Linear programming is also the meeting point of three parts of this course: the feasible region is a convex set, its corners are found by linear algebra (choices of linearly independent columns of a matrix), and every LP comes with a twin, its dual, whose variables are prices.

The section proves the four facts on which everything rests: the corners of the feasible region are exactly its basic feasible solutions; if an LP has an optimum it has one at a corner; the simplex test "all net evaluations $z_j-c_j\ge0$" certifies optimality; and the primal and dual optimal values are equal, with complementary slackness linking their solutions. CSIR NET asks for the number of basic feasible solutions of a small system, for the optimal value of a two-variable LP (often fastest through its dual), for the reading of a simplex tableau (optimal? unbounded? alternative optima?), for the dual of a problem with mixed constraints, and in Part C for "which statements about the primal and dual are true". Transportation and assignment problems, which are LPs with special structure, appear in GATE and occasionally in CSIR. The traps are collected in the ⚠️ box.

Formulation, the Graphical Method and Convexity

We write vectors as columns, $x\ge0$ means 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; $a^{\mathsf T}x=\beta$ describes a hyperplane.

📘 Definition 9.6 — Linear programming problem; standard and canonical forms

A linear programming problem asks for the maximum (or minimum) of a linear objective function $z=c^{\mathsf T}x$ over the set of $x\in\mathbb{R}^n$ satisfying finitely many linear equations and inequalities (the constraints). A point satisfying all constraints is a feasible solution; the set of all of them is the feasible region $P$. A feasible $x^*$ with $c^{\mathsf T}x^*\ge c^{\mathsf T}x$ for all $x\in P$ is an optimal solution, and $c^{\mathsf T}x^*$ is 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 throughout:

$$\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 an $m\times n$ matrix of rank $m$ (so $m\le n$). 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 unrestricted 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.

📘 Definition 9.7 — Convex sets, extreme points, polyhedra
A set $K\subseteq\mathbb{R}^n$ is convex if $\lambda u+(1-\lambda)v\in K$ whenever $u,v\in K$ and $0\le\lambda\le1$. A point $x\in K$ is an extreme point (corner, vertex) of $K$ if $x=\lambda u+(1-\lambda)v$ with $u,v\in K$ and $0\lt\lambda\lt1$ forces $u=v=x$: it lies on no open segment inside $K$. A polyhedron is an intersection of finitely many closed half-spaces, $\{x:Ax\le b\}$; a bounded polyhedron is a polytope. The convex hull $\operatorname{conv}S$ is the set of all convex combinations $\sum_i\lambda_iv_i$ ($v_i\in S$, $\lambda_i\ge0$, $\sum\lambda_i=1$).
📐 Theorem 9.13 — Convexity of the feasible and optimal sets
  1. The feasible region of every LP is a closed convex polyhedron.
  2. The set of optimal solutions of an LP is convex (possibly empty). In particular, an LP with two different optimal solutions has infinitely many.
  3. A local maximum of a linear function over a convex set is a global maximum.
  4. If $P=\operatorname{conv}\{v_1,\dots,v_k\}$, then $\max_{x\in P}c^{\mathsf T}x=\max_ic^{\mathsf T}v_i$.

Proof. (1) An equation is two inequalities, and $x_j\ge0$ is $-x_j\le0$; so $P$ is an intersection of finitely many closed half-spaces. A half-space $\{a^{\mathsf T}x\le\beta\}$ is closed, and convex because $a^{\mathsf T}(\lambda u+(1-\lambda)v)$ $=\lambda a^{\mathsf T}u+(1-\lambda)a^{\mathsf T}v$ $\le\lambda\beta+(1-\lambda)\beta=\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$ by (1), and $c^{\mathsf T}w=\lambda z^*+(1-\lambda)z^*=z^*$, so $w$ is optimal. If $u\ne v$, the whole segment consists of different optimal solutions.

(3) Let $x^*\in K$ be a local maximum: $c^{\mathsf T}x\le c^{\mathsf T}x^*$ for $x\in K$ with $\|x-x^*\|\lt\varepsilon$. For any $u\in K$ the points $x^*+t(u-x^*)$, $0\lt t\le1$, lie in $K$ and are within $\varepsilon$ of $x^*$ for small $t$, so $c^{\mathsf T}x^*+t\,c^{\mathsf T}(u-x^*)\le c^{\mathsf T}x^*$, that is $c^{\mathsf T}u\le c^{\mathsf T}x^*$.

(4) For $x=\sum\lambda_iv_i$, $c^{\mathsf T}x=\sum\lambda_ic^{\mathsf T}v_i\le\max_ic^{\mathsf T}v_i\sum_i\lambda_i=\max_ic^{\mathsf T}v_i$, and the maximum is attained at the best $v_i\in P$. ∎

For two decision variables the feasible region can be drawn. The graphical method draws $P$, then a line $c^{\mathsf T}x=k$ (an iso-profit line), and slides it parallel to itself in the direction of $c$ (the direction of increase) until it is about to leave $P$. The last point or points of contact are optimal. If the line can slide forever while meeting $P$, the LP is unbounded.

✏️ Example 1 — A workshop's production plan
A workshop makes two products, P and Q. Each unit of P needs $2$ machine-hours and $1$ labour-hour, each unit of Q needs $1$ machine-hour and $1$ labour-hour; $10$ machine-hours and $7$ labour-hours are available per day, and the market takes at most $5$ units of Q per day. The profit is $4$ thousand rupees per unit of P and $3$ thousand per unit of Q. (a) Formulate an LP for the daily plan. (b) Solve it graphically. (c) For which profits $c_1$ per unit of P (with $c_2=3$ fixed) does the same plan stay optimal?
(a) Model Let $x_1,x_2$ be the daily outputs of P and Q. Then $$\max\ z=4x_1+3x_2\quad\text{s.t.}\quad 2x_1+x_2\le10,\ \ x_1+x_2\le7,\ \ x_2\le5,\ \ x_1,x_2\ge0.$$ (Fractional outputs are allowed: they are average daily rates.)
(b) Corners The region is a pentagon with corners $O=(0,0)$, $(5,0)$ (where $2x_1+x_2=10$ meets $x_2=0$), $(3,4)$ (where $2x_1+x_2=10$ meets $x_1+x_2=7$), $(2,5)$ (where $x_1+x_2=7$ meets $x_2=5$) and $(0,5)$. The objective takes the values $0,\ 20,\ 24,\ 23,\ 15$ there.
Answer Sliding the line $4x_1+3x_2=k$ upwards, the last point of contact is $(3,4)$: make $3$ units of P and $4$ of Q for a profit of $24$ thousand rupees per day. Both machine time and labour are used up; the market limit on Q is slack by $1$ unit. By Theorem 9.13(4) applied to the pentagon, comparing the five corner values is a complete proof.
(c) Range At $(3,4)$ the tight constraints have outward normals $(2,1)$ and $(1,1)$. The corner stays optimal exactly when $c=(c_1,3)$ lies between them, $c=\alpha(2,1)+\beta(1,1)$ with $\alpha,\beta\ge0$: $\alpha=c_1-3\ge0$ and $\beta=6-c_1\ge0$, so $3\le c_1\le6$. (For $c_1\gt6$ the optimum moves to $(5,0)$, for $c_1\lt3$ to $(2,5)$; at $c_1=3$ or $6$ a whole edge is optimal.)

Basic Feasible Solutions and Extreme Points

In three or more variables we cannot draw, so we need an algebraic description of the corners. Work with the standard form $P=\{x\in\mathbb{R}^n:Ax=b,\ x\ge0\}$, where $A=[a_1\ \cdots\ a_n]$ has rank $m$. A choice of $m$ linearly independent columns is the algebraic counterpart of "a corner".

📘 Definition 9.8 — Bases, basic solutions, basic feasible solutions, degeneracy

A basis is a set $\mathcal B=\{B_1,\dots,B_m\}$ of column indices such that the $m\times m$ matrix $B=[a_{B_1}\ \cdots\ a_{B_m}]$ is invertible; $\mathcal N$ denotes the other indices. The basic solution for $\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 and the others the nonbasic 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.

Since there are at most $\binom nm$ ways to choose $m$ columns, there are at most $\binom nm$ basic solutions.

📐 Theorem 9.14 — A test for basic feasible solutions
Let $x\in P$ and let $J=\{j:x_j\gt0\}$ be its support. Then $x$ is a basic feasible solution if and only if the columns $a_j$, $j\in J$, are linearly independent.

Proof. If $x$ is the BFS of a basis $\mathcal B$, then $J\subseteq\mathcal B$ (nonbasic components are $0$), and a subset of the independent set $\{a_j:j\in\mathcal B\}$ is independent. Conversely, let $\{a_j:j\in J\}$ be independent; then $|J|\le m$. Because $A$ has rank $m$, its columns span $\mathbb{R}^m$, and an independent set can be enlarged by columns of $A$ to a basis of $\mathbb{R}^m$ (Steinitz exchange): there is a basis $\mathcal B\supseteq J$. Now $x_j=0$ for every $j\notin\mathcal B$, and $Bx_{\mathcal B}=\sum_{j\in\mathcal B}x_ja_j=Ax=b$, so $x_{\mathcal B}=B^{-1}b$: $x$ is the basic solution for $\mathcal B$, and it is feasible because $x\in P$. ∎

📐 Theorem 9.15 — Basic feasible solutions are exactly the extreme points
A point $x$ of $P=\{x:Ax=b,\ x\ge0\}$ ($A$ of rank $m$) is an extreme point of $P$ if and only if it is a basic feasible solution. Consequently $P$ has at most $\binom nm$ extreme points.

Proof. ($\Leftarrow$) Let $x$ be the BFS of a basis $\mathcal B$, and suppose $x=\lambda u+(1-\lambda)v$ with $u,v\in P$ and $0\lt\lambda\lt1$. For $j\in\mathcal N$ we have $0=x_j=\lambda u_j+(1-\lambda)v_j$ with $u_j,v_j\ge0$ and $\lambda,1-\lambda\gt0$, so $u_j=v_j=0$. Then $Bu_{\mathcal B}=Au=b$ and $Bv_{\mathcal B}=b$, so $u_{\mathcal B}=v_{\mathcal B}=B^{-1}b=x_{\mathcal B}$. Hence $u=v=x$, and $x$ is extreme.

($\Rightarrow$) Let $x$ be an extreme point with support $J$, and suppose the columns $a_j$, $j\in J$, are dependent: $\sum_{j\in J}d_ja_j=0$ with $d\ne0$. Extend $d$ by $d_j=0$ for $j\notin J$; then $Ad=0$. Choose $\varepsilon\gt0$ with $\varepsilon|d_j|\lt x_j$ for all $j\in J$. Then $x\pm\varepsilon d\ge0$ (on $J$ because of the choice of $\varepsilon$, off $J$ because both vanish) and $A(x\pm\varepsilon d)=b$, so $x\pm\varepsilon d\in P$, and $x=\frac12(x+\varepsilon d)+\frac12(x-\varepsilon d)$ with $x+\varepsilon d\ne x-\varepsilon d$. This contradicts extremality. So the columns are independent and $x$ is a BFS by Theorem 9.14. The bound follows because a BFS is determined by its basis. ∎

📐 Theorem 9.16 — Fundamental theorem of linear programming
Consider (SF) with $A$ of rank $m$.
  1. If $P\ne\varnothing$, then $P$ has at least one basic feasible solution (extreme point).
  2. If the LP has an optimal solution, then it has an optimal basic feasible solution.

Proof. We prove (2); the proof of (1) is the same with the objective ignored. Among all optimal solutions choose one, $x$, with the fewest positive components, and let $J$ be its support. If the columns $a_j$, $j\in J$, are independent, $x$ is a BFS by Theorem 9.14 and we are done. Otherwise take $d\ne0$ with $Ad=0$ and $d_j=0$ off $J$, as in the previous proof, so that $x\pm\varepsilon d\in P$ for small $\varepsilon\gt0$.

First, $c^{\mathsf T}d=0$: both $x+\varepsilon d$ and $x-\varepsilon d$ are feasible, so optimality of $x$ gives $\pm\varepsilon c^{\mathsf T}d\le0$. Hence every feasible point of the form $x+td$ is again optimal. Replacing $d$ by $-d$ if necessary, $d$ has a negative component. Put $$t^*=\min\left\{\frac{x_j}{-d_j}:d_j\lt0\right\}\gt0 .$$ Then $x+t^*d\ge0$ (for $d_j\ge0$ the component does not decrease; for $d_j\lt0$ it stays $\ge0$ by the choice of $t^*$), $A(x+t^*d)=b$, and the component achieving the minimum becomes $0$, while no component outside $J$ becomes positive. So $x+t^*d$ is an optimal solution with fewer positive components than $x$, a contradiction. ∎

Theorems 9.15 and 9.16 reduce linear programming to a finite search: if an optimum exists, it is attained at one of at most $\binom nm$ corners. Listing them all is hopeless for realistic sizes ($\binom{100}{50}\approx10^{29}$), which is why we need the simplex method. Note also what Theorem 9.16 does not say: it does not claim that an LP bounded above has an optimum. That is true (Theorem 9.19(3)), but the proof needs the simplex method or a compactness argument.

✏️ Example 2 — All basic solutions of the workshop problem
Bring Example 1 to standard form with slack variables $s_1,s_2,s_3$, list all its basic solutions, decide which are feasible, and match the BFSs with the corners found graphically.
Standard form $2x_1+x_2+s_1=10$, $x_1+x_2+s_2=7$, $x_2+s_3=5$, all five variables $\ge0$. Here $m=3$, $n=5$, so there are at most $\binom53=10$ bases. Choosing the $3$ basic variables is the same as choosing the $2$ nonbasic ones, which are set to $0$; geometrically, we intersect two of the five lines $x_1=0$, $x_2=0$, $s_1=0$, $s_2=0$, $s_3=0$.
Table
nonbasic $=0$$(x_1,x_2)$$(s_1,s_2,s_3)$status$z$
$x_1,x_2$$(0,0)$$(10,7,5)$BFS, corner $O$$0$
$x_1,s_1$$(0,10)$$(0,-3,-5)$infeasible—
$x_1,s_2$$(0,7)$$(3,0,-2)$infeasible—
$x_1,s_3$$(0,5)$$(5,2,0)$BFS$15$
$x_2,s_1$$(5,0)$$(0,2,5)$BFS$20$
$x_2,s_2$$(7,0)$$(-4,0,5)$infeasible—
$x_2,s_3$lines $x_2=0$, $x_2=5$ parallelnot a basis—
$s_1,s_2$$(3,4)$$(0,0,1)$BFS$24$
$s_1,s_3$$(2.5,5)$$(0,-0.5,0)$infeasible—
$s_2,s_3$$(2,5)$$(1,0,0)$BFS$23$
Answer Nine of the ten column sets are bases (columns of $x_1,s_1,s_2$ are $(2,1,0),(1,0,0),(0,1,0)$, which span only the plane of the first two coordinates). Five basic solutions are feasible, and they are exactly the five corners of the pentagon, as Theorem 9.15 predicts; none is degenerate. The infeasible basic solutions are intersections of constraint lines outside the region.
✏️ Example 3 — Extreme points: prove or disprove
Prove or disprove: (a) Every nonempty polyhedron has an extreme point. (b) Each extreme point of $P=\{x:Ax=b,\ x\ge0\}$ is the BFS of exactly one basis. (c) If the feasible region of an LP is unbounded, then the LP is unbounded. (d) Every optimal solution of an LP is a basic feasible solution.
(a) False The half-plane $\{x\in\mathbb{R}^2:x_1+x_2\ge1\}$ is a polyhedron, and every point of it lies inside a segment parallel to the boundary line, so it has no extreme points. A polyhedron containing a whole line never has one. In standard form this cannot happen: $x\ge0$ excludes lines, and Theorem 9.16(1) gives an extreme point whenever $P\ne\varnothing$.
(b) False Take $x_1+x_2+s_1=2$, $x_1+s_2=2$ (that is, $x_1+x_2\le2$, $x_1\le2$). The corner $(x_1,x_2)=(2,0)$ is the point $(2,0,0,0)$, with three zero components. Any basis containing column $x_1$ works: $\{x_1,x_2\}$, $\{x_1,s_1\}$ and $\{x_1,s_2\}$ are all invertible and all give this point. The point is degenerate: the three lines $x_2=0$, $x_1+x_2=2$, $x_1=2$ pass through it. A nondegenerate BFS does determine its basis (the basis must contain the $m$ positive components).
(c) False $\min\ x_1+x_2$ subject to $x_1+x_2\ge4$, $x_1+3x_2\ge6$, $x\ge0$ has an unbounded region but the finite optimal value $4$: every feasible point has $x_1+x_2\ge4$, and equality holds on the edge from $(0,4)$ to $(3,1)$ (on the line $x_1+x_2=4$ the second constraint reads $x_2\ge1$). Unboundedness of the LP needs a direction $d$ of the region along which the objective improves; here every direction of the region has $d\ge0$, along which $x_1+x_2$ increases.
(d) False In (c) the midpoint $(1.5,2.5)$ is optimal but is not a corner. Theorem 9.16 only guarantees that some optimal solution is basic; by Theorem 9.13(2) the optimal set is convex, and it is a whole edge or face whenever the objective is parallel to it.
Interactive 1 — The Geometry of an LP: Corners, Iso-profit Lines and Alternative Optima

Choose a feasible region and turn the objective direction $c=(\cos\theta,\sin\theta)$; we maximise $c^{\mathsf T}x$. The left panel shows the region, the arrow $c$ and the iso-profit line through the optimum (dashed). Every corner is labelled with the variables that vanish there (the nonbasic variables of its BFS). The right panel shows $c^{\mathsf T}v$ at every corner $v$: the optimum is always the tallest bar (Theorems 9.13(4) and 9.16). When $c$ is perpendicular to an edge (the slider snaps to within $1.5^\circ$), two bars tie and the whole edge is optimal. On the unbounded region, many directions make the LP unbounded, but some still have an optimum. The degenerate region has a corner where three constraints meet.

—
c—
optimal corner(s)—
optimal value—
zero (nonbasic) variables there—

The Simplex Method

The simplex method starts at a BFS and moves to an adjacent BFS (one that differs in a single basic variable) with a larger objective, until no neighbour is better. Everything is driven by one identity. Fix a basis $\mathcal B$ with matrix $B$, write $y_j=B^{-1}a_j$ (the coordinates of column $a_j$ in the basis), $\bar x_{\mathcal B}=B^{-1}b$, and let $c_{\mathcal B}$ be the vector of costs of the basic variables. Multiplying $Ax=b$ by $B^{-1}$ gives, for every $x$ with $Ax=b$, $$x_{\mathcal B}=\bar x_{\mathcal B}-\sum_{j\in\mathcal N}y_jx_j,$$ $$c^{\mathsf T}x=c_{\mathcal B}^{\mathsf T}x_{\mathcal B}+\sum_{j\in\mathcal N}c_jx_j=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 objective at the BFS and $z_j=c_{\mathcal B}^{\mathsf T}y_j$.

📘 Definition 9.9 — Net evaluations and the simplex tableau
For a basis $\mathcal B$ the numbers $\Delta_j=z_j-c_j=c_{\mathcal B}^{\mathsf T}B^{-1}a_j-c_j$ are the net evaluations (reduced costs, with the opposite sign in some books); $\Delta_j=0$ for $j\in\mathcal B$. The simplex tableau of $\mathcal B$ lists, row by row, the basic variable $x_{B_i}$, the $i$-th row of $B^{-1}A$ (the entries $y_{ij}$) and $\bar x_{B_i}$; its last row lists $\Delta_1,\dots,\Delta_n$ and $z_0$. The row vector $\pi^{\mathsf T}=c_{\mathcal B}^{\mathsf T}B^{-1}$ is the vector of simplex multipliers. When a slack variable $s_i$ (cost $0$, column $e_i$) is present, its net evaluation is $\Delta_{s_i}=\pi_i$.
📐 Theorem 9.17 — Optimality criterion
Let $\bar x$ be the BFS of a basis $\mathcal B$ for the problem (SF), a maximisation.
  1. If $\Delta_j\ge0$ for every $j\in\mathcal N$, then $\bar x$ is optimal.
  2. If $\Delta_j\gt0$ for every $j\in\mathcal N$, then $\bar x$ is the unique optimal solution.
  3. If $\bar x$ is nondegenerate and $\Delta_k\lt0$ for some $k$, then $\bar x$ is not optimal.

Proof. (1) For any feasible $x$, the identity $(*)$ gives $c^{\mathsf T}x=z_0-\sum_{j\in\mathcal N}\Delta_jx_j\le z_0=c^{\mathsf T}\bar x$, because $\Delta_j\ge0$ and $x_j\ge0$. (2) If moreover $x$ is optimal, then $\sum_{j\in\mathcal N}\Delta_jx_j=0$ with every term $\ge0$, so each $x_j=0$ for $j\in\mathcal N$ (as $\Delta_j\gt0$); then $x_{\mathcal B}=\bar x_{\mathcal B}$ by $(*)$, i.e. $x=\bar x$. (3) This is part (2) of the next theorem: the step length $\theta$ there is positive when $\bar x_{\mathcal B}\gt0$. ∎

📐 Theorem 9.18 — The pivot step: improvement or unboundedness
Let $\bar x$ be the BFS of $\mathcal B$ and let $k\in\mathcal N$ with $\Delta_k\lt0$; write $y_k=(y_{1k},\dots,y_{mk})^{\mathsf T}=B^{-1}a_k$.
  1. If $y_{ik}\le0$ for all $i$, the LP is unbounded: $x(t)$ defined by $x_k=t$, $x_{\mathcal B}=\bar x_{\mathcal B}-ty_k$, other components $0$, is feasible for every $t\ge0$ and $c^{\mathsf T}x(t)=z_0-t\Delta_k\to\infty$.
  2. Otherwise let $\displaystyle\theta=\min\left\{\frac{\bar x_{B_i}}{y_{ik}}:y_{ik}\gt0\right\}$ (the minimum ratio test), attained at 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$, with strict inequality if $\theta\gt0$ (in particular if $\bar x$ is nondegenerate).
The new tableau is obtained from the old one by Gauss–Jordan elimination on the pivot $y_{rk}$: divide row $r$ by $y_{rk}$ and subtract multiples of it from the other rows (and from the $\Delta$ row) to clear column $k$.

Proof. In both parts, $Ax(t)=B\bar x_{\mathcal B}-tBy_k+ta_k=b-ta_k+ta_k=b$, and $(*)$ gives $c^{\mathsf T}x(t)=z_0-\Delta_kt$, since $x_k=t$ is the only nonzero nonbasic variable. The basic components are $\bar x_{B_i}-ty_{ik}$. (1) If all $y_{ik}\le0$ these never decrease, so $x(t)\ge0$ for all $t\ge0$, while the objective grows without bound because $-\Delta_k\gt0$.

(2) The components with $y_{ik}\le0$ stay nonnegative; a component with $y_{ik}\gt0$ stays nonnegative exactly while $t\le\bar x_{B_i}/y_{ik}$. So $x(t)\in P$ for $0\le t\le\theta$, and $x_{B_r}(\theta)=0$. The columns of $\mathcal B'$ are independent: $a_k=By_k=\sum_iy_{ik}a_{B_i}$ with $y_{rk}\ne0$, so $a_{B_r}=\frac1{y_{rk}}\left(a_k-\sum_{i\ne r}y_{ik}a_{B_i}\right)$ lies in the span of the columns of $\mathcal B'$, which therefore contains all columns of $B$ and is $\mathbb{R}^m$. The point $x(\theta)$ is feasible and vanishes outside $\mathcal B'$, so it is the BFS of $\mathcal B'$. Finally, the tableau of $\mathcal B'$ is $B'^{-1}A$, and $B'^{-1}=EB^{-1}$ where $E$ is the elementary matrix of the elimination described (it maps $y_k$ to $e_r$); the $\Delta$ row transforms in the same way because $\Delta_j=c_{\mathcal B}^{\mathsf T}y_j-c_j$ is linear in the column. ∎

📐 Theorem 9.19 — Termination of the simplex method
  1. If every BFS of (SF) is nondegenerate, then the simplex method, started at any BFS, stops after finitely many pivots, either at a BFS with all $\Delta_j\ge0$ (optimal) or at a column with $\Delta_k\lt0$ and $y_k\le0$ (unbounded).
  2. Under degeneracy a pivot may have $\theta=0$: the basis changes but the point and the objective do not, and the method can cycle through a sequence of bases forever. Bland's rule — enter the smallest index $k$ with $\Delta_k\lt0$, and among tied rows let the basic variable with the smallest index leave — never cycles (we omit the proof).
  3. Consequently every LP is either infeasible, or unbounded, or has an optimal basic feasible solution. In particular, a feasible LP whose objective is bounded above attains its maximum.

Proof. (1) Each pivot has $\theta\gt0$, so by Theorem 9.18(2) the objective strictly increases, and no basis can be visited twice (a basis determines the objective value). There are at most $\binom nm$ bases. When the method stops, either all $\Delta_j\ge0$ (optimal by Theorem 9.17) or Theorem 9.18(1) applies. (3) If the LP is feasible, Phase I (Theorem 9.20 below) finds a BFS; from there the simplex method with Bland's rule stops by (2), at an optimal BFS or with a proof of unboundedness. ∎

🧭 Problem-solving strategy — the simplex tableau (maximisation)
  1. Start. Put the problem in SF with $b\ge0$. If every constraint was $\le$, the slacks form the starting basis ($B=I$, $\pi=0$, $\Delta_j=-c_j$). Otherwise add artificial variables (next subsection).
  2. Test. If all $\Delta_j\ge0$: stop, the BFS is optimal. If also some nonbasic $\Delta_j=0$, there may be alternative optima: pivot that column in to find another optimal BFS.
  3. Enter. Choose $k$ with $\Delta_k\lt0$ (Dantzig's rule: the most negative; Bland's rule under degeneracy).
  4. Leave. If column $k$ has no positive entry, stop: unbounded. Otherwise take the row $r$ with the smallest ratio $\bar x_{B_i}/y_{ik}$ over $y_{ik}\gt0$ only.
  5. Pivot on $y_{rk}$ and repeat. Check after each pivot that the right-hand side stays $\ge0$ and that $z_0$ did not decrease.
  6. Read off. $x_{\mathcal B}$ from the last column, $z^*$ from the corner entry, and the dual solution $\pi_i=\Delta_{s_i}$ from the slack columns (Theorem 9.23). For a minimisation, maximise $-c^{\mathsf T}x$ and change the sign of the final value.
✏️ Example 4 — The workshop problem by the simplex method
Solve Example 1 by the simplex tableau, starting from the slack basis, and interpret each tableau as a corner of the pentagon. Read off the optimal solution of the dual problem from the final tableau.
Tableau 0 Basis $\{s_1,s_2,s_3\}$ at $O=(0,0)$, $z_0=0$. With $B=I$ and $c_{\mathcal B}=0$, $\Delta_j=-c_j$.
basis$x_1$$x_2$$s_1$$s_2$$s_3$$\bar x_{\mathcal B}$ratio
$s_1$$\mathbf{2}$$1$$1$$0$$0$$10$$10/2=5$ ←
$s_2$$1$$1$$0$$1$$0$$7$$7/1=7$
$s_3$$0$$1$$0$$0$$1$$5$—
$\Delta_j$$-4$$-3$$0$$0$$0$$0$
$x_1$ enters (most negative $\Delta$); $s_1$ leaves (smallest ratio; the $s_3$ row has $y=0$ and is skipped).
Tableau 1 Pivot on the $2$: divide the $s_1$ row by $2$ and clear the rest of column $x_1$. We are at the corner $(5,0)$ with $z_0=20$.
basis$x_1$$x_2$$s_1$$s_2$$s_3$$\bar x_{\mathcal B}$ratio
$x_1$$1$$\tfrac12$$\tfrac12$$0$$0$$5$$10$
$s_2$$0$$\mathbf{\tfrac12}$$-\tfrac12$$1$$0$$2$$4$ ←
$s_3$$0$$1$$0$$0$$1$$5$$5$
$\Delta_j$$0$$-1$$2$$0$$0$$20$
$x_2$ enters; ratios $5/\tfrac12=10$, $2/\tfrac12=4$, $5/1=5$, so $s_2$ leaves.
Tableau 2 Pivot on $\tfrac12$. We are at the corner $(3,4)$ with $z_0=20+4\cdot1=24$, as Theorem 9.18 predicts ($\theta=4$, $\Delta_k=-1$).
basis$x_1$$x_2$$s_1$$s_2$$s_3$$\bar x_{\mathcal B}$
$x_1$$1$$0$$1$$-1$$0$$3$
$x_2$$0$$1$$-1$$2$$0$$4$
$s_3$$0$$0$$1$$-2$$1$$1$
$\Delta_j$$0$$0$$1$$2$$0$$24$
Answer All $\Delta_j\ge0$ and the nonbasic ones ($s_1,s_2$) are strictly positive, so $x^*=(3,4)$ with $z^*=24$ is the unique optimum (Theorem 9.17(2)). The path was $O\to(5,0)\to(3,4)$: two pivots, each along an edge of the pentagon. The slack columns give $\pi=(\Delta_{s_1},\Delta_{s_2},\Delta_{s_3})=(1,2,0)$, the optimal dual solution: a machine-hour is worth $1$ thousand rupees and a labour-hour $2$ thousand at the margin; the market limit, which is slack, is worth $0$. Check: $10\cdot1+7\cdot2+5\cdot0=24=z^*$.

Artificial variables. If some constraints are $\ge$ or $=$, the slack columns do not provide an identity matrix and there is no obvious starting 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 we force the artificial variables to $0$.

📘 Definition 9.10 — Phase I problem and the Big-M problem
For (SF) with $b\ge0$, the Phase I problem is $$\min\ w=\textstyle\sum_ia_i\quad\text{s.t.}\quad Ax+a=b,\ \ x\ge0,\ a\ge0,$$ started from the BFS $x=0$, $a=b$ (artificial variables are needed only in rows without a slack; a slack can play the role of $a_i$ in its row). The two-phase method solves Phase I and then, from the BFS it ends with, applies the simplex method to the original objective (Phase II). The Big-M method instead solves in one pass $$\max\ c^{\mathsf T}x-M\textstyle\sum_ia_i\quad\text{s.t.}\quad Ax+a=b,\ \ x,a\ge0,$$ treating $M$ as a number larger than any number it is compared with.
📐 Theorem 9.20 — What Phase I and Big-M decide
  1. The Phase I problem has an optimal solution, and its optimal value $w^*$ is $0$ if and only if the original problem is feasible.
  2. If $w^*=0$ and no artificial variable is basic in the final Phase I tableau, its basis is a feasible basis of the original problem. If an artificial variable is basic (necessarily at level $0$), it can be pivoted out on any nonzero entry of its row in an original column; if its row has no such entry, the corresponding original equation is redundant and may be deleted.
  3. If the Big-M problem has an optimal solution with all $a_i=0$, its $x$-part is optimal for the original problem. If the Big-M simplex method, with every net evaluation written as $\alpha M+\beta$ and compared first by $\alpha$, stops at an optimal tableau in which some artificial variable is positive, the original problem is infeasible.

Proof. (1) $x=0$, $a=b$ is feasible for Phase I and $w\ge0$ on its region, so Phase I is feasible and bounded below; by Theorem 9.19(3) (applied to $\max(-w)$, starting from the given BFS, so no further Phase I is needed) it has an optimal solution. If the original problem has a feasible $x$, then $(x,0)$ is feasible for Phase I with $w=0$, so $w^*=0$. Conversely, if $w^*=0$ at $(x^*,a^*)$, then $a^*=0$ (a sum of nonnegative numbers is $0$), so $Ax^*=b$, $x^*\ge0$.

(2) With no artificial in the basis, the final basis consists of original columns and its BFS $(x^*,0)$ is feasible for the original problem. Suppose $a_r$ is basic in row $r$. Its value is $0$, since $w^*=0$. If the row has an entry $y_{rj}\ne0$ in an original column $j$, pivot on it: the ratio is $0/|y_{rj}|$, the pivot keeps all values (it is a degenerate pivot, which may use a negative pivot element because the row's right-hand side is $0$), and $a_r$ leaves. If all entries of row $r$ in original columns vanish, then row $r$ of $B^{-1}A$ is $0$: a nonzero combination of the rows of $A$ (with coefficients from row $r$ of $B^{-1}$) is the zero row, and the same combination of $b$ is $\bar x_{B_r}=0$. So that equation is a combination of the others and can be deleted.

(3) If $(x^*,0)$ is Big-M optimal and $x$ is feasible for the original problem, then $(x,0)$ is Big-M feasible with the same objective value, so $c^{\mathsf T}x\le c^{\mathsf T}x^*$; and $x^*$ is feasible because $Ax^*=b$. For the second claim, split the Big-M costs as $c^{(0)}+Mc^{(1)}$, where $c^{(1)}_j=-1$ for artificial columns and $0$ otherwise. Since $z_j-c_j$ is linear in the costs, each net evaluation is $\Delta_j=\alpha_jM+\beta_j$, where $\alpha_j$ is exactly the Phase I net evaluation of column $j$ (Phase I maximises $-\sum a_i$). An optimal tableau for "arbitrarily large $M$" has $\alpha_j\ge0$ for all $j$, so the same basis is optimal for Phase I, with value $w^*=\sum_ia_i\gt0$. By (1) the original problem is infeasible. ∎

So one never chooses a numerical $M$: each net evaluation is kept in the form $\alpha M+\beta$ and compared first by $\alpha$, then by $\beta$. The $\alpha$-row is the Phase I row, which is why the Big-M method and the two-phase method usually make the same pivots while artificial variables remain in the basis.

✏️ Example 5 — A minimum-cost problem by the two-phase method
Solve $\min z=3x_1+2x_2$ subject to $x_1+x_2\ge4$, $x_1+3x_2\ge6$, $x_1,x_2\ge0$ by the two-phase method. Check graphically, and compare with the Big-M method.
Set-up With surplus variables, $x_1+x_2-s_1+a_1=4$ and $x_1+3x_2-s_2+a_2=6$. Phase I maximises $-w=-a_1-a_2$ from the basis $\{a_1,a_2\}$; then $\Delta_j=-(\text{column sum})$ for the original columns and $\Delta_{s_i}=+1$.
basis$x_1$$x_2$$s_1$$s_2$$a_1$$a_2$$\bar x_{\mathcal B}$
$a_1$$1$$1$$-1$$0$$1$$0$$4$
$a_2$$1$$\mathbf{3}$$0$$-1$$0$$1$$6$
$\Delta_j$$-2$$-4$$1$$1$$0$$0$$-10$
Phase I $x_2$ enters, ratios $4$ and $2$, $a_2$ leaves. In the new tableau the rows are $a_1:\ (\tfrac23,0,-1,\tfrac13,1,-\tfrac13\mid2)$, $x_2:\ (\tfrac13,1,0,-\tfrac13,0,\tfrac13\mid2)$ and $\Delta=(-\tfrac23,0,1,-\tfrac13,0,\tfrac43\mid-2)$. Now $x_1$ enters, ratios $2/\tfrac23=3$ and $2/\tfrac13=6$, $a_1$ leaves:
basis$x_1$$x_2$$s_1$$s_2$$a_1$$a_2$$\bar x_{\mathcal B}$
$x_1$$1$$0$$-\tfrac32$$\tfrac12$$\tfrac32$$-\tfrac12$$3$
$x_2$$0$$1$$\tfrac12$$-\tfrac12$$-\tfrac12$$\tfrac12$$1$
$\Delta_j$$0$$0$$0$$0$$1$$1$$0$
$w^*=0$, so the problem is feasible, and $\{x_1,x_2\}$ is a feasible basis: the corner $(3,1)$.
Phase II Delete the artificial columns and use the objective $\max(-3x_1-2x_2)$, $c_{\mathcal B}=(-3,-2)$: $\Delta_{s_1}=(-3)(-\tfrac32)+(-2)(\tfrac12)=\tfrac72$, $\Delta_{s_2}=(-3)(\tfrac12)+(-2)(-\tfrac12)=-\tfrac12$, value $-11$. So $s_2$ enters; only the $x_1$ row has a positive entry ($\tfrac12$, ratio $6$), so $x_1$ leaves. The new rows are $s_2:\ (2,0,-3,1\mid6)$, $x_2:\ (1,1,-1,0\mid4)$ with $\Delta=(1,0,2,0\mid-8)$, all $\ge0$.
Answer $x^*=(0,4)$ with $\min z=8$ (surplus $s_2=6$: the second requirement is over-satisfied). Graphically the corners of the unbounded region are $(0,4),(3,1),(6,0)$ with costs $8,11,18$, and the costs grow along both unbounded edges, so $(0,4)$ is optimal. The dual, $\max4u_1+6u_2$ s.t. $u_1+u_2\le3$, $u_1+3u_2\le2$, $u\ge0$, has optimum $u=(\Delta_{s_1},\Delta_{s_2})=(2,0)$ with value $8$.
Big-M Maximising $-3x_1-2x_2-Ma_1-Ma_2$, the first net evaluations are $\Delta_{x_1}=-2M+3$ and $\Delta_{x_2}=-4M+2$. The Big-M method makes the same three pivots ($x_2$ for $a_2$, $x_1$ for $a_1$, $s_2$ for $x_1$) and ends at the same point; the $M$-parts of the net evaluations are exactly the Phase I net evaluations.

Duality and Complementary Slackness

Return to the workshop. Suppose a contractor offers to rent all of its machine time, labour and market quota at prices $y_1,y_2,y_3\ge0$ per unit. The workshop accepts only if renting out the inputs of one unit of P earns at least the $4$ it would make from P, $2y_1+y_2\ge4$, and similarly $y_1+y_2+y_3\ge3$ for Q. The contractor wants to pay as little as possible, $10y_1+7y_2+5y_3$. This new LP is the dual of the workshop's problem, and its optimal prices turn out to be the values $(1,2,0)$ read off in Example 4.

📘 Definition 9.11 — The dual problem

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,\qquad y\in\mathbb{R}^m .$$ One dual variable belongs to each primal constraint and one dual constraint to each primal variable. For LPs with mixed constraints the rules are:

primal (max)dual (min)
constraint $i$: $a_i^{\mathsf T}x\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$ freeconstraint $j$: $(A^{\mathsf T}y)_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 same table gives the dual of a minimisation problem.

📐 Theorem 9.21 — The dual of the dual is the primal
The dual of (D) is (P). More generally, applying the rules of Definition 9.11 twice returns the original problem, and a problem and the problem obtained from it by the elementary rewritings of Definition 9.6 have equivalent duals.

Proof. Write (D) as a canonical maximisation: $\max(-b)^{\mathsf T}y$ s.t. $(-A^{\mathsf T})y\le-c$, $y\ge0$. Its dual by the definition is $\min(-c)^{\mathsf T}x$ s.t. $(-A^{\mathsf T})^{\mathsf T}x\ge-b$, $x\ge0$, that is $-\max c^{\mathsf T}x$ s.t. $Ax\le b$, $x\ge0$: problem (P). For the mixed rules: a constraint $a_i^{\mathsf T}x\ge b_i$ is $(-a_i)^{\mathsf T}x\le-b_i$ with a multiplier $u\ge0$ entering the dual through $-u$, i.e. a variable $y_i=-u\le0$. An equation is two inequalities with multipliers $u,v\ge0$, entering as $u-v$, a free variable. A variable $x_j\le0$ is $x_j=-x_j'$ with $x_j'\ge0$, which flips its dual constraint to $\le$, and a free variable $x_j=x_j^+-x_j^-$ gives both $\ge$ and $\le$, an equation. ∎

📐 Theorem 9.22 — Weak duality
If $x$ is feasible for (P) and $y$ is feasible for (D), then $c^{\mathsf T}x\le b^{\mathsf T}y$. Consequently: (i) if $c^{\mathsf T}x=b^{\mathsf T}y$, then $x$ and $y$ are both optimal; (ii) if (P) is unbounded, (D) is infeasible; (iii) if (D) is unbounded, (P) is infeasible.

Proof. Using $x\ge0$ and $A^{\mathsf T}y\ge c$ for the first inequality, and $y\ge0$ and $Ax\le b$ for the second, $$c^{\mathsf T}x\le(A^{\mathsf T}y)^{\mathsf T}x=y^{\mathsf T}Ax\le y^{\mathsf T}b .$$ (i) For any feasible $x'$, $c^{\mathsf T}x'\le b^{\mathsf T}y=c^{\mathsf T}x$, so $x$ is optimal; symmetrically for $y$. (ii) A feasible $y$ would bound $c^{\mathsf T}x$ above by $b^{\mathsf T}y$. (iii) is (ii) for the pair (D), (P), using Theorem 9.21. ∎

📐 Theorem 9.23 — Strong duality and the duality theorem
  1. If (P) has an optimal solution, then so does (D), and the optimal values are equal: $\max c^{\mathsf T}x=\min b^{\mathsf T}y$. If $\mathcal B$ is an optimal basis of (P) in standard form (with slacks) satisfying $\Delta_j\ge0$ for all $j$, then $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.
  2. (Duality theorem) For the pair (P), (D) exactly one of the following holds: both have optimal solutions, with equal values; one is unbounded and the other infeasible; both are infeasible.

Proof. (1) Add slacks: (P) becomes $\max c^{\mathsf T}x+0^{\mathsf T}s$ s.t. $[A\ \ I]\binom xs=b$, $x,s\ge0$, whose constraint matrix has rank $m$. Run Phase I and then the simplex method with Bland's rule (Theorem 9.19(2)–(3)). Since (P) has an optimum, the method cannot stop with a proof of unboundedness, so it stops at a basis $\mathcal B$ 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 the slack column $e_i$, with cost $0$: $\Delta_{s_i}=y^{\mathsf T}e_i=y_i\ge0$. So $y$ is feasible for (D). Its value is $b^{\mathsf T}y=c_{\mathcal B}^{\mathsf T}B^{-1}b=c_{\mathcal B}^{\mathsf T}\bar x_{\mathcal B}=z^*$, and by Theorem 9.22(i) $y$ is optimal.

(2) The three cases are mutually exclusive by Theorem 9.22. If (P) is feasible and bounded, it has an optimum (Theorem 9.19(3)), and (1) gives the first case. If (P) is unbounded, (D) is infeasible. If (P) is infeasible, then (D) is either infeasible (third case) or feasible; in the latter case (D) cannot have an optimum, because by (1) applied to (D) (whose dual is (P), Theorem 9.21) (P) would have one; so (D) is unbounded (second case). ∎

All three cases occur. Example 4 is the first. In Example 5 replace "min" by "max": the primal $\max3x_1+2x_2$ is unbounded, and its dual $\min4y_1+6y_2$ s.t. $y_1+y_2\ge3$, $y_1+3y_2\ge2$, with $y\le0$ (the primal constraints are $\ge$ in a maximisation), is infeasible because $y_1+y_2\le0$. For the third case, take $\max x_1$ s.t. $x_1-x_2\le-1$, $-x_1+x_2\le-1$, $x\ge0$ (adding the constraints gives $0\le-2$); its dual $\min-y_1-y_2$ s.t. $y_1-y_2\ge1$, $-y_1+y_2\ge0$, $y\ge0$ is infeasible too (adding gives $0\ge1$).

📐 Theorem 9.24 — Complementary slackness
Let $x$ be feasible for (P) and $y$ feasible for (D). Then $x$ and $y$ are both optimal if and only if $$y_i\,(b-Ax)_i=0\ \ (i=1,\dots,m)\qquad\text{and}\qquad x_j\,(A^{\mathsf T}y-c)_j=0\ \ (j=1,\dots,n).$$ In words: a positive dual price forces its primal constraint to be tight, a slack primal constraint has price $0$, a positive primal variable forces its dual constraint to be tight, and a dual constraint with surplus forces its primal variable to be $0$.

Proof. A direct computation gives the duality gap $$b^{\mathsf T}y-c^{\mathsf T}x=y^{\mathsf T}(b-Ax)+x^{\mathsf T}(A^{\mathsf T}y-c)=\sum_iy_i(b-Ax)_i+\sum_jx_j(A^{\mathsf T}y-c)_j ,$$ a sum of products of nonnegative numbers. If all products vanish, the gap is $0$ and both are optimal by Theorem 9.22(i). Conversely, if both are optimal, (P) has an optimum, so by Theorem 9.23 the gap is $0$; a sum of nonnegative terms equal to $0$ has every term $0$. ∎

Complementary slackness is the fastest way to (a) verify a claimed optimal solution, by solving for a $y$ from the tight conditions and checking dual feasibility; (b) solve a problem with many variables but two constraints, by solving its two-variable dual graphically (Example 6); and (c) interpret prices: at the optimum, a resource that is not used up has shadow price $0$. More precisely, if the optimal basis stays feasible when $b$ changes to $b+\delta$ (that is, $B^{-1}(b+\delta)\ge0$), it stays optimal, because the net evaluations do not involve $b$; then $z^*(b+\delta)=y^{\mathsf T}(b+\delta)$, so $y_i=\partial z^*/\partial b_i$ is the marginal value of resource $i$ (Exercise IV.6). A last consequence is a classical theorem of the alternative.

📐 Theorem 9.25 — Farkas' lemma
For a real $m\times n$ matrix $A$ and $b\in\mathbb{R}^m$, exactly one of the following systems has a solution: (I) $Ax=b$, $x\ge0$; (II) $A^{\mathsf T}y\ge0$, $b^{\mathsf T}y\lt0$.

Proof. Not both: $0\gt b^{\mathsf T}y=(Ax)^{\mathsf T}y=x^{\mathsf T}(A^{\mathsf T}y)\ge0$ is impossible. Suppose (I) has no solution. The LP $\max0^{\mathsf T}x$ s.t. $Ax=b$, $x\ge0$ is then infeasible. By the rules of Definition 9.11 its dual is $\min b^{\mathsf T}y$ s.t. $A^{\mathsf T}y\ge0$, $y$ free, which is feasible ($y=0$). By the duality theorem (Theorem 9.23(2), whose proof works for mixed forms by Theorem 9.21), a feasible dual of an infeasible primal is unbounded: there is $y$ with $A^{\mathsf T}y\ge0$ and $b^{\mathsf T}y\lt0$. ∎

🧭 Problem-solving strategy — the dual simplex method (brief)
Use it when a basis is dual feasible (all $\Delta_j\ge0$) but not primal feasible (some $\bar x_{B_i}\lt0$), typically for $\min c^{\mathsf T}x$, $Ax\ge b$ with $c\ge0$ after multiplying the rows by $-1$ to get a slack basis, or after a new constraint is added to a solved problem.
  1. Leave first: choose a row $r$ with $\bar x_{B_r}\lt0$ (the most negative). If every entry $y_{rj}\ge0$, the primal is infeasible.
  2. Enter: among $j$ with $y_{rj}\lt0$, choose $k$ minimising $\Delta_j/|y_{rj}|$ (this keeps all $\Delta_j\ge0$).
  3. Pivot on $y_{rk}$ and repeat until $\bar x_{\mathcal B}\ge0$; the basis is then optimal. The method is the ordinary simplex method applied to the dual, read in the primal tableau.
✏️ Example 6 — Four variables, two constraints: solve the dual
Solve $\min w=9x_1+7x_2+10x_3+10x_4$ subject to $x_1+x_2+2x_3+x_4\ge3$, $2x_1+x_2+x_3+3x_4\ge4$, $x\ge0$, by solving its dual graphically and then using complementary slackness. Interpret the dual variables.
Dual By Definition 9.11 (read for a minimisation with $\ge$ constraints and $x\ge0$): $$\max\ 3y_1+4y_2\quad\text{s.t.}\quad y_1+2y_2\le9,\ y_1+y_2\le7,\ 2y_1+y_2\le10,\ y_1+3y_2\le10,\ y\ge0.$$
Graph The dual region is a quadrilateral with corners $(0,0)$, $(5,0)$ (on $2y_1+y_2=10$), $(4,2)$ (where $2y_1+y_2=10$ meets $y_1+3y_2=10$) and $(0,\tfrac{10}3)$; the first two constraints are redundant ($y_1+2y_2=8\lt9$ and $y_1+y_2=6\lt7$ at $(4,2)$). The objective $3y_1+4y_2$ takes the values $0,\ 15,\ 20,\ \tfrac{40}3$, so $y^*=(4,2)$ and $\max=20$. It is the unique optimum, since $(3,4)=1\cdot(2,1)+1\cdot(1,3)$ with both coefficients positive.
Complementary slackness At $y^*$ the first two dual constraints have surplus $9-8=1$ and $7-6=1$, so $x_1=x_2=0$. Both $y_i^*\gt0$, so both primal constraints are tight: $2x_3+x_4=3$ and $x_3+3x_4=4$, giving $x_3=x_4=1$.
Answer $x^*=(0,0,1,1)$ with $\min w=10+10=20=\max(3y_1+4y_2)$, so both are optimal by Theorem 9.22(i). Read as a diet problem ($x_j$ = amounts of four foods, the constraints = two nutrient requirements), $y_1^*=4$ and $y_2^*=2$ are the imputed values of a unit of each nutrient: raising the first requirement from $3$ to $3+\delta$ raises the minimum cost by $4\delta$ while the basis $\{x_3,x_4\}$ stays feasible. Foods 1 and 2 are not bought because their cost exceeds the value of their nutrients ($9\gt4+2\cdot2$, $7\gt4+2$).
Interactive 2 — The Simplex Path and Its Dual Shadow

Each problem has two constraints and two variables, so both the primal region (left, $x$-plane) and the dual region $\{y\ge0: A^{\mathsf T}y\ge c\}$ (right, $y$-plane) can be drawn. Press Play or Step: the simplex method (Dantzig's rule) walks along the primal corners, and at every basis the multipliers $y^{\mathsf T}=c_{\mathcal B}^{\mathsf T}B^{-1}$ give a point of the dual plane, red while it violates a dual constraint and green once it is dual feasible. Throughout, $c^{\mathsf T}x=b^{\mathsf T}y$; the primal becomes optimal exactly when its dual point becomes feasible (Theorem 9.23). Try the alternative-optimum problem (a degenerate dual corner), the degenerate primal (the primal point stays put while the dual point jumps), and the unbounded problem (empty dual region).

step—
primal BFS x, value cᵀx—
multipliers y, value bᵀy—
status—

Transportation and Assignment Problems

Some LPs are so structured that the simplex method can be run on a table instead of a tableau. The most important is the problem of shipping a commodity from $m$ sources to $n$ destinations at least cost.

📘 Definition 9.12 — Transportation and assignment problems

Source $i$ has supply $a_i\gt0$, destination $j$ has demand $b_j\gt0$, and shipping one unit from $i$ to $j$ costs $c_{ij}$. The problem is balanced if $\sum_ia_i=\sum_jb_j$. The transportation problem (TP) is $$\min\sum_{i,j}c_{ij}x_{ij}\quad\text{s.t.}\quad\sum_jx_{ij}=a_i\ (i\le m),\quad\sum_ix_{ij}=b_j\ (j\le n),\quad x_{ij}\ge0 .$$ An unbalanced problem is balanced by a dummy source or destination with zero costs (or penalty costs). The assignment problem is the case $m=n$, $a_i=b_j=1$, with the extra requirement $x_{ij}\in\{0,1\}$: assign $n$ workers to $n$ jobs, one each, at least total cost. A loop is a sequence of at least four cells, alternately in the same row and the same column, returning to the start.

📐 Theorem 9.26 — Structure of the transportation problem
For a balanced TP:
  1. It is feasible ($x_{ij}=a_ib_j/T$ with $T=\sum a_i$) and has an optimal solution.
  2. The $m+n$ equality constraints have rank exactly $m+n-1$, so a basic solution has $m+n-1$ basic cells (some possibly at level $0$), and the basic cells contain no loop.
  3. If all $a_i,b_j$ are integers, every basic solution is integral; in particular there is an integral optimal solution.
  4. (MODI / u–v optimality test) Let $x$ be a basic feasible solution, and choose numbers $u_i,v_j$ with $u_i+v_j=c_{ij}$ on the basic cells. If $d_{ij}=c_{ij}-u_i-v_j\ge0$ for every cell, then $x$ is optimal.

Proof. (1) $\sum_ja_ib_j/T=a_i$ and $\sum_ia_ib_j/T=b_j$. The region is bounded ($0\le x_{ij}\le\min(a_i,b_j)$) and closed, and the objective is continuous, so a minimum exists (alternatively, Theorem 9.19(3): the objective is bounded below by $0$ if costs are nonnegative, and by $\min c_{ij}\cdot T$ in general).

(2) Let $R_i$ and $C_j$ be the coefficient rows of the row and column constraints. Then $\sum_iR_i=\sum_jC_j$ (both are the all-ones row), so the rank is at most $m+n-1$. The rows other than $C_n$ are independent: if $\sum_i\alpha_iR_i+\sum_{j\lt n}\beta_jC_j=0$, the entry for cell $(i,n)$ gives $\alpha_i=0$ for every $i$, and then the entry for cell $(1,j)$ gives $\beta_j=0$. If the columns of some cells contained a loop, the alternating sum $+1,-1,+1,\dots$ of their columns would be $0$ (each row and column of the loop is visited by one $+$ and one $-$), so they are dependent and cannot all be basic.

(3) A set of basic cells without loops forms a forest in the bipartite graph of rows and columns, with $m+n-1$ edges on $m+n$ vertices, hence a spanning tree. A tree has a leaf, a row or column with a single basic cell, whose value is then forced to equal that row's supply or column's demand (an integer); delete it, reduce the corresponding demand or supply by this integer, and repeat. All values are integers. By Theorem 9.16 an optimal BFS exists, and it is integral.

(4) The dual of the TP is $\max\sum_ia_iu_i+\sum_jb_jv_j$ s.t. $u_i+v_j\le c_{ij}$, with $u,v$ free (equality constraints). If all $d_{ij}\ge0$, $(u,v)$ is dual feasible, and since $x_{ij}=0$ off the basic cells, $$\sum_{i,j}c_{ij}x_{ij}=\sum_{\text{basic}}(u_i+v_j)x_{ij}=\sum_iu_i\sum_jx_{ij}+\sum_jv_j\sum_ix_{ij}=\sum_ia_iu_i+\sum_jb_jv_j ,$$ so the primal and dual values agree, and $x$ is optimal by weak duality. The $m+n-1$ equations $u_i+v_j=c_{ij}$ along a spanning tree determine $u,v$ once one of them (say $u_1=0$) is fixed. ∎

The transportation algorithm finds an initial BFS (north-west corner rule: fill the top-left cell as much as possible and move right or down; the least-cost rule; Vogel's approximation, which uses penalties = differences of the two smallest costs in each row and column), computes $u,v$ and the $d_{ij}$, and if some $d_{pq}\lt0$ brings cell $(p,q)$ into the basis: it forms the unique loop of $(p,q)$ with basic cells, adds $\theta$ to the cells with sign $+$ and subtracts it from those with sign $-$ (alternately), with $\theta$ the smallest "$-$" value, which leaves. This is exactly the simplex pivot of Theorem 9.18, and $d_{pq}$ is the net change in cost per unit shipped through the loop.

📐 Theorem 9.27 — Row and column reduction; the Hungarian method
Let $C=(c_{ij})$ be the $n\times n$ cost matrix of an assignment problem.
  1. Subtracting a constant from every entry of one row (or one column) changes the cost of every assignment by the same constant, so the optimal assignments are unchanged.
  2. If a matrix $C'$ obtained by such reductions has nonnegative entries and contains $n$ zeros, no two in the same row or column, then these zeros give an optimal assignment for $C$.
  3. (König's theorem, stated) The largest number of independent zeros (no two in a row or column) equals the smallest number of lines (rows or columns) covering all the zeros.
Moreover, the LP relaxation ($0\le x_{ij}$ instead of $x_{ij}\in\{0,1\}$) has the same optimal value: by Theorem 9.26(3) it has an integral optimal BFS, which is a permutation matrix (Birkhoff–von Neumann).

Proof. (1) An assignment is a permutation $\sigma$ with cost $\sum_ic_{i\sigma(i)}$, which uses exactly one entry of each row and each column; subtracting $k$ from row $r$ lowers every such sum by exactly $k$. (2) The chosen zeros form an assignment of cost $0$ for $C'$, and every assignment costs $\ge0$ for $C'$, so it is optimal for $C'$, hence for $C$ by (1). ∎

The Hungarian method: subtract each row minimum, then each column minimum. Cover all zeros with the fewest lines. If $n$ lines are needed, an optimal assignment can be chosen among the zeros (König). Otherwise let $k$ be the smallest uncovered entry, subtract $k$ from every uncovered entry and add it to entries covered twice (this equals subtracting $k$ from the uncovered rows and adding it to the covered columns, so (1) applies), and repeat. Each round keeps the matrix nonnegative and creates a new zero.

✏️ Example 7 — Shipping cement and assigning crews
(a) Three plants $S_1,S_2,S_3$ supply $20,35,20$ tonnes of cement to three sites $D_1,D_2,D_3$ needing $15,30,30$ tonnes; the costs (hundreds of rupees per tonne) are $c=\begin{pmatrix}4 & 6 & 9\\ 5 & 3 & 8\\ 7 & 5 & 4\end{pmatrix}$. Find a BFS by the north-west corner rule and improve it to an optimum by the u–v method. (b) Three crews must be assigned to three jobs, one each, with costs $\begin{pmatrix}8 & 4 & 7\\ 5 & 2 & 3\\ 9 & 4 & 8\end{pmatrix}$ (crew $i$, job $j$). Solve by the Hungarian method.
(a) NW corner The problem is balanced ($75=75$). $x_{11}=15$ (column 1 done, $S_1$ has $5$ left), $x_{12}=5$ ($S_1$ done, $D_2$ needs $25$), $x_{22}=25$ ($S_2$ has $10$ left), $x_{23}=10$, $x_{33}=20$. That is $5=m+n-1$ basic cells, and the cost is $60+30+75+80+80=325$.
u–v test With $u_1=0$: $v_1=4$, $v_2=6$ (cells $(1,1),(1,2)$); $u_2=3-6=-3$; $v_3=8+3=11$; $u_3=4-11=-7$. Then $d_{13}=9-0-11=-2$, $d_{21}=5+3-4=4$, $d_{31}=7+7-4=10$, $d_{32}=5+7-6=6$. Cell $(1,3)$ has $d\lt0$: each tonne sent through it saves $2$.
Pivot The loop is $(1,3)^+\to(2,3)^-\to(2,2)^+\to(1,2)^-$. The "$-$" cells hold $10$ and $5$, so $\theta=5$ and $(1,2)$ leaves: $x_{13}=5$, $x_{12}=0$, $x_{22}=30$, $x_{23}=5$, and the cost drops by $2\cdot5$ to $315$. New potentials: $u_1=0$, $v_1=4$, $v_3=9$, $u_2=-1$, $v_2=4$, $u_3=-5$, and $d_{12}=2$, $d_{21}=2$, $d_{31}=8$, $d_{32}=6$, all positive.
(a) Answer Ship $S_1\to D_1$: $15$, $S_1\to D_3$: $5$, $S_2\to D_2$: $30$, $S_2\to D_3$: $5$, $S_3\to D_3$: $20$; minimum cost $315$ hundred rupees. It is the unique optimum because all $d_{ij}\gt0$ off the basis (Theorem 9.17(2) in this setting).
(b) Hungarian Row minima $4,2,4$ give $\begin{pmatrix}4 & 0 & 3\\ 3 & 0 & 1\\ 5 & 0 & 4\end{pmatrix}$; column minima $3,0,1$ give $\begin{pmatrix}1 & 0 & 2\\ 0 & 0 & 0\\ 2 & 0 & 3\end{pmatrix}$. Row 2 and column 2 cover all zeros: $2\lt3$ lines. The smallest uncovered entry is $1$; subtracting it from the uncovered entries and adding it at the intersection gives $\begin{pmatrix}0 & 0 & 1\\ 0 & 1 & 0\\ 1 & 0 & 2\end{pmatrix}$.
(b) Answer Row 3 has a single zero (job 2), then row 1 must take job 1, and row 2 job 3: crew 1 → job 1, crew 2 → job 3, crew 3 → job 2, cost $8+3+4=15$. Check against all $3!=6$ assignments: the costs are $18,15,17,16,16,18$, so $15$ is the unique minimum.
⚠️ Counterexamples and pitfalls
  1. An optimal solution need not be a corner. The optimal set is convex (Theorem 9.13(2)); when $c$ is perpendicular to an edge every point of the edge is optimal, e.g. the midpoint $(1.5,2.5)$ for $\min x_1+x_2$ in Example 3(c). Only some optimal solution is basic.
  2. Unbounded region ≠ unbounded LP. Example 5 has an unbounded region and a finite minimum. Conversely a bounded objective on a nonempty region always gives an attained optimum for an LP (Theorem 9.19(3)), but not for a linear function on a general closed convex set: $\max(-x_2)$ on $\{x_1\gt0,\ x_1x_2\ge1\}$ has supremum $0$, never attained (Exercise I.8).
  3. Not every polyhedron has a corner. A half-plane has none; $\{Ax=b,\ x\ge0\}$ always has one if nonempty (Theorem 9.16(1)).
  4. Degenerate corners have several bases, and the optimality test is sufficient, not necessary. For $\max2x_1+x_2$ s.t. $x_1+x_2\le2$, $x_1\le2$, the optimal corner $(2,0)$ with basis $\{x_1,s_1\}$ has $\Delta_{x_2}=-1\lt0$; pivoting $x_2$ in has ratio $0$ (a degenerate pivot) and only then are all $\Delta_j\ge0$ (Interactive 2, third problem).
  5. The ratio test uses only positive entries. Including a zero or negative $y_{ik}$ either divides by zero or produces a negative basic variable. If no entry is positive the LP is unbounded, not infeasible.
  6. Degeneracy can make the simplex method cycle (classical examples by Beale need $3$ constraints and $7$ variables); Bland's smallest-index rule or lexicographic ratios prevent it. A nondegenerate problem never cycles.
  7. Phase I with $w^*\gt0$ means infeasible, not unbounded; an artificial variable left in the basis at level $0$ with $w^*=0$ is harmless (Theorem 9.20(2)).
  8. Dual sign rules. In a minimisation with $\ge$ constraints the dual variables are $\ge0$; a $\le$ constraint in a minimisation gives $y_i\le0$; an equation gives a free variable, and a free variable gives an equation. Writing all dual variables $\ge0$ regardless is the commonest error.
  9. Weak duality does not exclude double infeasibility. If (P) is infeasible, (D) may be infeasible too ($\max x_1$ s.t. $x_1-x_2\le-1$, $-x_1+x_2\le-1$).
  10. Complementary slackness works one way per pair. $y_i^*\gt0$ forces constraint $i$ tight, but a tight constraint may have $y_i^*=0$: in Interactive 2's second problem, the optimal $x=(3,1)$ makes both constraints tight, yet the unique dual optimum is $y^*=(2,0)$. Strict complementarity holds only for a suitable pair of optimal solutions (Goldman–Tucker).
  11. Transportation bases have $m+n-1$ cells, not $m+n$. A degenerate BFS with fewer positive cells must be completed with zero cells (no loops) before the $u,v$ can be computed.
  12. Rounding an LP solution does not solve an integer program. For $\max x_2$ s.t. $-2x_1+2x_2\le1$, $2x_1+2x_2\le7$, $x\ge0$, the LP optimum is $(1.5,2)$; the rounded points $(1,2)$ and $(2,2)$ are infeasible, and the integer optimum has $x_2=1$. Transportation and assignment problems are the happy exception (Theorem 9.26(3)).

Exercises

I
Formulation, convexity and the graphical method.
  • 1 A farm mixes two feeds. A kilogram of feed A costs $20$ rupees and gives $3$ units of protein and $2$ of energy; a kilogram of feed B costs $30$ rupees and gives $6$ units of protein and $1$ of energy. A daily ration needs at least $24$ units of protein and $8$ of energy. Formulate and solve graphically.
  • 2 Solve graphically: $\max z=x_1+3x_2$ s.t. $-x_1+x_2\le2$, $x_1+x_2\le6$, $x_1\le4$, $x\ge0$.
  • 3 For the region of Exercise 2, find all objective vectors $c$ for which the corner $(4,2)$ is optimal, and those for which it is the unique optimum.
  • 4 Give an objective for the region of Exercise 2 whose optimal set is a segment, and prove in general that the optimal set of an LP is convex.
  • 5 Show that $K=\{x\in\mathbb{R}^2:x_1^2\le x_2\}$ is convex, find all its extreme points, and deduce that $K$ is not a polyhedron.
  • 6 Bring to standard form: $\max z=x_1-2x_2+3x_3$ s.t. $x_1+x_2+x_3\le7$, $x_1-x_2+x_3\ge2$, $3x_1-x_2-2x_3=-5$, $x_1,x_2\ge0$, $x_3$ unrestricted.
  • 7 Prove directly that a linear function attains its maximum over the polytope $\operatorname{conv}\{v_1,\dots,v_k\}$ at one of the $v_i$.
  • 8 Give a closed convex set $K\subset\mathbb{R}^2$ and a linear function bounded above on $K$ that does not attain its supremum. Why can this not happen for a polyhedron?
1 $x_1,x_2$ = kg of A and B: $\min20x_1+30x_2$ s.t. $3x_1+6x_2\ge24$, $2x_1+x_2\ge8$, $x\ge0$. Corners: $(0,8)$, $(\tfrac83,\tfrac83)$ (intersection of $x_1+2x_2=8$ and $2x_1+x_2=8$), $(8,0)$, with costs $240$, $\tfrac{400}3\approx133.33$, $160$. Costs increase along both unbounded edges, so the optimum is $\tfrac83$ kg of each feed, at $133.33$ rupees per day.
2 Corners $(0,0),(4,0),(4,2),(2,4),(0,2)$ with $z=0,4,10,14,6$. Optimum $(2,4)$, $z^*=14$.
3 The constraints tight at $(4,2)$ are $x_1+x_2\le6$ and $x_1\le4$, with normals $(1,1)$ and $(1,0)$. The corner is optimal iff $c=\alpha(1,1)+\beta(1,0)$ with $\alpha,\beta\ge0$, i.e. $c_1\ge c_2\ge0$; it is the unique optimum iff $c_1\gt c_2\gt0$ (for $c_2=0$ the edge $x_1=4$ is optimal, for $c_1=c_2$ the edge $x_1+x_2=6$).
4 $\max x_1+x_2$: the optimal set is the segment from $(4,2)$ to $(2,4)$, value $6$. Convexity: Theorem 9.13(2) — a convex combination of two optimal points is feasible and has the same value.
5 If $u_1^2\le u_2$, $v_1^2\le v_2$, then by convexity of $t\mapsto t^2$, $(\lambda u_1+(1-\lambda)v_1)^2$ $\le\lambda u_1^2+(1-\lambda)v_1^2$ $\le\lambda u_2+(1-\lambda)v_2$. Every boundary point $(t,t^2)$ is extreme: if $(t,t^2)=\lambda u+(1-\lambda)v$ with $u,v\in K$, $0\lt\lambda\lt1$, then $t^2=\lambda u_2+(1-\lambda)v_2\ge\lambda u_1^2+(1-\lambda)v_1^2\ge t^2$, and equality in the strict convexity inequality forces $u_1=v_1=t$, hence $u_2=v_2=t^2$. Interior points lie on short vertical segments in $K$ and are not extreme. A polyhedron $\{Ax\le b\}$ in $\mathbb{R}^2$ has finitely many extreme points (each is the unique solution of two linearly independent tight constraints, and there are finitely many pairs), but $K$ has infinitely many.
6 Write $x_3=x_3^+-x_3^-$, add a slack $s_1$ and a surplus $s_2$, and multiply the equation by $-1$ so that its right-hand side is positive: $\max x_1-2x_2+3x_3^+-3x_3^-$ s.t. $x_1+x_2+x_3^+-x_3^-+s_1=7$, $x_1-x_2+x_3^+-x_3^--s_2=2$, $-3x_1+x_2+2x_3^+-2x_3^-=5$, all six variables $\ge0$.
7 For $x=\sum\lambda_iv_i$ with $\lambda_i\ge0$, $\sum\lambda_i=1$: $c^{\mathsf T}x=\sum_i\lambda_ic^{\mathsf T}v_i\le\max_ic^{\mathsf T}v_i$, and equality holds at the maximising $v_i$.
8 $K=\{x:x_1\gt0,\ x_1x_2\ge1\}$ is closed (a limit of points with $x_1x_2\ge1$, $x_1\gt0$ has $x_1x_2\ge1$, so $x_1\ne0$, and $x_1\ge0$) and convex (the epigraph of the convex function $1/x_1$ on $(0,\infty)$). The function $-x_2$ is $\le0$ on $K$ with supremum $0$ (let $x_1\to\infty$), never attained. On a polyhedron in standard form Theorem 9.19(3) excludes this; a general polyhedron can be rewritten in standard form (Definition 9.6).
II
Basic feasible solutions and the simplex method.
  • 1 Find all basic solutions of $x_1+2x_2+x_3=4$, $2x_1+x_2+5x_3=5$, and say which are basic feasible and which are degenerate.
  • 2 Solve by the simplex method: $\max z=5x_1+2x_2+6x_3$ s.t. $4x_1+3x_3\le14$, $x_1+x_2+3x_3\le9$, $x_1+3x_2+3x_3\le11$, $x\ge0$. Also give the optimal dual solution.
  • 3 In Example 1 keep the profit $4$ of P and let the profit of Q be $c_2$. For which $c_2$ does $(3,4)$ remain optimal?
  • 4 Apply the simplex method to $\max z=x_1+2x_2$ s.t. $x_1-x_2\le2$, $-2x_1+x_2\le2$, $x\ge0$, and exhibit a ray of feasible solutions along which $z\to\infty$.
  • 5 Prove: if at an optimal tableau $\Delta_j\gt0$ for every nonbasic $j$, then the optimal solution is unique. Is the converse true?
  • 6 Solve $\max z=2x_1+4x_2$ s.t. $x_1+2x_2\le5$, $x_1+x_2\le4$, $x\ge0$, show that it has alternative optima, and describe all optimal solutions.
  • 7 Solve $\max z=3x_1+2x_2$ s.t. $x_1+x_2\le4$, $2x_1+x_2\le6$, $x_1\le3$, $x\ge0$ by the simplex method, noting what the tie in the first ratio test produces.
  • 8 Show that $\{x:Ax=b,\ x\ge0\}$ ($A$ of size $m\times n$, rank $m$) has at most $\binom nm$ basic feasible solutions, and give, for every $n$, an example with $m=1$ attaining the bound.
Check lab: all basic solutions of a 2 × n system

Enter the two rows of $A$ (up to $6$ entries each, separated by commas) and the right-hand side $b$. The lab runs through all pairs of columns, solves $Bx_{\mathcal B}=b$ when $B$ is invertible, and classifies each basic solution as a BFS (nondegenerate or degenerate) or infeasible. It starts with Exercise II.1; try the system of Example 3(b): rows $1,1,1,0$ and $1,0,0,1$ with $b=2,2$.

basic solutions—
number of BFS—
1 Basis $\{x_1,x_2\}$: $x=(2,1,0)$, a nondegenerate BFS. $\{x_1,x_3\}$: $x_1+x_3=4$, $2x_1+5x_3=5$ give $x=(5,0,-1)$, infeasible. $\{x_2,x_3\}$: $2x_2+x_3=4$, $x_2+5x_3=5$ give $x=(0,\tfrac53,\tfrac23)$, a nondegenerate BFS. So two BFSs, both nondegenerate.
2 From the slack basis, $x_3$ enters ($\Delta=-6$; ratios $\tfrac{14}3,3,\tfrac{11}3$) and $s_2$ leaves: $z=18$ at $(0,0,3)$. Then $x_1$ enters ($\Delta=-3$; ratios $\tfrac53$ and $9$) and $s_1$ leaves: $z=23$ at $(\tfrac53,0,\tfrac{22}9)$. Then $x_2$ enters ($\Delta=-1$; ratios $\tfrac{11}2$ and $1$) and $s_3$ leaves: the final tableau has $\bar x=(x_1,x_3,x_2)=(2,2,1)$ and $\Delta=(0,0,0,1,\tfrac12,\tfrac12)$. Optimum $x^*=(2,1,2)$, $z^*=24$, unique; dual optimum $y=(1,\tfrac12,\tfrac12)$, and indeed $14+\tfrac92+\tfrac{11}2=24$.
3 As in Example 1(c): $(4,c_2)=\alpha(2,1)+\beta(1,1)$ gives $\alpha=4-c_2\ge0$, $\beta=2c_2-4\ge0$, so $2\le c_2\le4$.
4 $x_2$ enters ($\Delta=-2$); only the second row has a positive entry, so $s_2$ leaves: $z=4$ at $(0,2)$, with rows $s_1:(-1,0,1,1\mid4)$, $x_2:(-2,1,0,1\mid2)$ and $\Delta=(-5,0,0,2\mid4)$. Now $x_1$ enters, but its column $(-1,-2)$ has no positive entry: unbounded. The ray is $x_1=t$, $x_2=2+2t$ ($s_1=4+t$), feasible for all $t\ge0$, with $z=4+5t$.
5 By $(*)$, $z(x)=z_0-\sum_{j\in\mathcal N}\Delta_jx_j$; an optimal $x$ has $\sum\Delta_jx_j=0$, so $x_{\mathcal N}=0$ and $x=\bar x$. The converse fails under degeneracy: for $\max x_1$ s.t. $x_1+x_2\le1$, $x_1\le1$ the unique optimum $(1,0)$ has the basis $\{x_1,s_2\}$ with $\Delta_{x_2}=1$, $\Delta_{s_1}=1$, but also the basis $\{x_1,s_1\}$, where $\Delta_{x_2}=0$. Without degeneracy the converse holds: a nonbasic $\Delta_k=0$ with a positive ratio $\theta\gt0$ gives a second optimal point, and with $y_k\le0$ a whole optimal ray.
6 $x_2$ enters, $s_1$ leaves (ratios $\tfrac52$, $4$): $x_2=\tfrac52$, $s_2=\tfrac32$, $z=10$, $\Delta=(0,0,2,0)$ — optimal, with $\Delta_{x_1}=0$ for the nonbasic $x_1$. Pivoting $x_1$ in (ratios $5$ and $3$, $s_2$ leaves) gives the second optimal BFS $(3,1)$, also $z=10$. All optimal solutions: $\lambda(0,\tfrac52)+(1-\lambda)(3,1)$, $0\le\lambda\le1$.
7 $x_1$ enters; ratios $4,3,3$ tie, and $s_2$ (smaller index) leaves. The BFS $(3,0)$ has $s_3=0$ in the basis: degenerate (three lines meet at $(3,0)$). Now $\Delta_{x_2}=-\tfrac12$; the $s_3$ row has entry $-\tfrac12$ and is skipped, the ratios are $1/\tfrac12=2$ ($s_1$) and $3/\tfrac12=6$ ($x_1$), so $s_1$ leaves. Final: $x^*=(2,2)$, $z^*=10$, $\Delta=(0,0,1,1,0)$. The degenerate basic variable did not block progress here because its entry in the entering column was negative.
8 A BFS is determined by its basis (Theorem 9.14 and $x_{\mathcal B}=B^{-1}b$), and there are at most $\binom nm$ bases. For $m=1$ take $x_1+\cdots+x_n=1$: each unit vector $e_j$ is a BFS, giving $n=\binom n1$ of them (they are the corners of the standard simplex).
III
Artificial variables, degeneracy and the dual simplex method.
  • 1 Solve by the Big-M method: $\min z=3x_1+4x_2$ s.t. $2x_1+x_2\ge6$, $x_1+2x_2=6$, $x\ge0$.
  • 2 Use Phase I to show that $\max z=x_1+x_2$ s.t. $x_1+2x_2\le2$, $2x_1+x_2\ge6$, $x\ge0$ is infeasible, and interpret $w^*$.
  • 3 Run Phase I on $x_1+x_2=2$, $2x_1+2x_2=4$, $x\ge0$ and explain what the artificial variable left in the basis tells you.
  • 4 Solve Example 5's constraints with the objective $\min z=2x_1+3x_2$ by the dual simplex method, starting from the slack basis after multiplying both constraints by $-1$.
  • 5 Prove that if the Big-M problem has an optimal solution with all artificial variables $0$, its $x$-part is optimal for the original problem.
  • 6 Show that a pivot with $\theta=0$ changes the basis but not the basic feasible solution or the objective value.
  • 7 Give an LP in standard form with an extreme point that is the BFS of exactly three bases.
1 Rows $2x_1+x_2-s_1+a_1=6$, $x_1+2x_2+a_2=6$; maximise $-3x_1-4x_2-Ma_1-Ma_2$. Initially $\Delta_{x_1}=-3M+3$, $\Delta_{x_2}=-3M+4$, $\Delta_{s_1}=M$. $x_1$ enters (ratios $3,6$), $a_1$ leaves; then $\Delta_{x_2}=\tfrac{-3M+5}2$ is the most negative, ratios $6$ and $2$, $a_2$ leaves. Final rows $x_1:(1,0,-\tfrac23\mid2)$, $x_2:(0,1,\tfrac13\mid2)$, $\Delta_{s_1}=\tfrac23\ge0$ and the artificial columns have $\Delta$ of order $M\gt0$. Optimum $x^*=(2,2)$, $\min z=14$. (Check: on $x_1=6-2x_2$, feasibility needs $x_2\le2$ and $z=18-2x_2$.)
2 Rows $x_1+2x_2+s_1=2$ and $2x_1+x_2-s_2+a_2=6$, Phase I maximises $-a_2$: $\Delta=(-2,-1,0,1,0)$. $x_1$ enters, ratios $2$ ($s_1$) and $3$ ($a_2$), $s_1$ leaves; then $\Delta=(0,3,2,1,0)\ge0$ with $a_2=2$ still basic. So $w^*=2\gt0$ and the problem is infeasible. Indeed, $w^*=6-m$, where $m=4$ is the largest value of $2x_1+x_2$ subject to $x_1+2x_2\le2$, $x\ge0$: the second constraint misses by $2$ units at best.
3 Initially $\Delta=(-3,-3)$ for $x_1,x_2$; $x_1$ enters, the ratios $2/1$ and $4/2$ tie, $a_1$ leaves. The $a_2$ row becomes $(0,0\mid0)$ in the original columns with $a_2=0$ basic, and $w^*=0$. By Theorem 9.20(2) the second equation is redundant ($=2\times$ the first): delete the row. The feasible set is the segment $x_1+x_2=2$, $x\ge0$.
4 Maximise $-2x_1-3x_2$ with rows $-x_1-x_2+s_1=-4$, $-x_1-3x_2+s_2=-6$: the slack basis has $\Delta=(2,3,0,0)\ge0$ but $\bar x=(-4,-6)$. $s_2$ leaves (most negative); the ratios $\Delta_j/|y_{2j}|$ are $2/1$ and $3/3$, so $x_2$ enters: rows $s_1:(-\tfrac23,0,1,-\tfrac13\mid-2)$, $x_2:(\tfrac13,1,0,-\tfrac13\mid2)$, $\Delta=(1,0,0,1)$. Now $s_1$ leaves; ratios $1/\tfrac23=\tfrac32$ ($x_1$) and $1/\tfrac13=3$ ($s_2$), so $x_1$ enters: $x_1=3$, $x_2=1$, $\Delta=(0,0,\tfrac32,\tfrac12)$. Optimum $(3,1)$ with $\min z=9$, and the dual solution $(\tfrac32,\tfrac12)$ is read off the slack columns.
5 Let $(x^*,0)$ be Big-M optimal. For any feasible $x$ of the original problem, $(x,0)$ is feasible for the Big-M problem with objective $c^{\mathsf T}x$, so $c^{\mathsf T}x\le c^{\mathsf T}x^*-M\cdot0=c^{\mathsf T}x^*$; and $x^*$ itself is feasible since $Ax^*=b-0$.
6 In Theorem 9.18(2) the new point is $x(\theta)=x(0)=\bar x$; the leaving variable had value $0$ and the entering variable gets value $0$. The objective $z_0-\theta\Delta_k$ is unchanged. Only the labelling of the zero variables changes.
7 $x_1+x_2+s_1=2$, $x_1+s_2=2$, all $\ge0$ (Example 3(b)): the point $(2,0,0,0)$ is the BFS of $\{x_1,x_2\}$, $\{x_1,s_1\}$ and $\{x_1,s_2\}$; the other three pairs do not contain $x_1$ and give other points or no basis.
IV
Duality, complementary slackness, transportation and assignment.
  • 1 Write the dual of $\min z=2x_1+5x_2-x_3$ s.t. $x_1+x_2+x_3\ge4$, $2x_1-x_2+3x_3\le6$, $x_1+3x_2-x_3=5$, $x_1\ge0$, $x_2\le0$, $x_3$ free.
  • 2 For $\max z=3x_1+2x_2+4x_3$ s.t. $x_1+x_2+2x_3\le8$, $2x_1+x_2+x_3\le10$, $x\ge0$, use complementary slackness to decide whether $(4,0,2)$ and $(0,0,4)$ are optimal.
  • 3 Solve $\min z=4x_1+3x_2+6x_3$ s.t. $x_1+x_2+2x_3\ge3$, $2x_1+x_2+x_3\ge4$, $x\ge0$ through its dual.
  • 4 Show that if $b\ge0$ and $c\le0$, then $x=0$ and $y=0$ are optimal for (P) and (D).
  • 5 Prove that if both (P) and (D) are feasible, then both have optimal solutions.
  • 6 In Example 1 the labour available changes from $7$ to $7+\delta$. Using the final tableau of Example 4, find the range of $\delta$ for which the basis $\{x_1,x_2,s_3\}$ stays optimal and the optimal profit as a function of $\delta$.
  • 7 A balanced transportation problem has supplies $40,60$, demands $30,50,20$ and costs $\begin{pmatrix}3 & 5 & 4\\ 6 & 4 & 5\end{pmatrix}$. Start from the north-west corner solution and find the optimum.
  • 8 Solve the assignment problem with cost matrix $\begin{pmatrix}10 & 7 & 8 & 12\\ 9 & 6 & 11 & 9\\ 7 & 12 & 9 & 10\\ 11 & 8 & 7 & 13\end{pmatrix}$.
  • 9 Prove that the $m+n$ constraints of a balanced transportation problem have rank exactly $m+n-1$.
1 Reading Definition 9.11 from right to left (primal min): a $\ge$ constraint gives $y_1\ge0$, a $\le$ constraint $y_2\le0$, an equation $y_3$ free; $x_1\ge0$ gives a $\le$ dual constraint, $x_2\le0$ a $\ge$ one, $x_3$ free an equation: $$\max\ 4y_1+6y_2+5y_3\ \ \text{s.t.}\ \ y_1+2y_2+y_3\le2,\ \ y_1-y_2+3y_3\ge5,\ \ y_1+3y_2-y_3=-1 ,$$ with $y_1\ge0$, $y_2\le0$, $y_3$ free.
2 The dual is $\min8y_1+10y_2$ s.t. $y_1+2y_2\ge3$, $y_1+y_2\ge2$, $2y_1+y_2\ge4$, $y\ge0$. For $(4,0,2)$: both constraints are tight; $x_1,x_3\gt0$ force $y_1+2y_2=3$, $2y_1+y_2=4$, so $y=(\tfrac53,\tfrac23)\ge0$, and $y_1+y_2=\tfrac73\ge2$: dual feasible, so $(4,0,2)$ is optimal with $z^*=20=8\cdot\tfrac53+10\cdot\tfrac23$. For $(0,0,4)$: the second constraint has slack $6$, so $y_2=0$; $x_3\gt0$ forces $2y_1=4$, $y_1=2$; but then $y_1+2y_2=2\lt3$: no dual feasible $y$ satisfies the conditions, so $(0,0,4)$ (value $16$) is not optimal.
3 Dual: $\max3y_1+4y_2$ s.t. $y_1+2y_2\le4$, $y_1+y_2\le3$, $2y_1+y_2\le6$, $y\ge0$. Corners $(0,0),(3,0),(2,1),(0,2)$ with values $0,9,10,8$ ($(3,0)$ is degenerate: three lines meet there). So $y^*=(2,1)$, value $10$. The third dual constraint has surplus $1$, so $x_3=0$; $y^*\gt0$ makes both primal constraints tight: $x_1+x_2=3$, $2x_1+x_2=4$, so $x^*=(1,2,0)$ with $\min z=4+6=10$.
4 $x=0$ is feasible for (P) because $A0=0\le b$, and $y=0$ is feasible for (D) because $A^{\mathsf T}0=0\ge c$. Both values are $0$, so both are optimal by Theorem 9.22(i).
5 A feasible $y$ bounds $c^{\mathsf T}x\le b^{\mathsf T}y$ on the feasible set of (P), so (P) is feasible and bounded, hence has an optimum (Theorem 9.19(3)); then (D) has one by Theorem 9.23.
6 The slack columns of the final tableau give $B^{-1}=\begin{pmatrix}1 & -1 & 0\\ -1 & 2 & 0\\ 1 & -2 & 1\end{pmatrix}$. Then $B^{-1}(10,7+\delta,5)^{\mathsf T}$ $=(3-\delta,\ 4+2\delta,\ 1-2\delta)\ge0$ iff $-2\le\delta\le\tfrac12$. The net evaluations do not depend on $b$, so the basis stays optimal there, with $z^*=4(3-\delta)+3(4+2\delta)=24+2\delta$: the shadow price of labour is $y_2=2$.
7 NW corner: $x_{11}=30$, $x_{12}=10$, $x_{22}=40$, $x_{23}=20$, cost $90+50+160+100=400$. Potentials $u_1=0$, $v_1=3$, $v_2=5$, $u_2=-1$, $v_3=6$; $d_{13}=4-6=-2$, $d_{21}=6+1-3=4$. Loop $(1,3)^+(2,3)^-(2,2)^+(1,2)^-$, $\theta=\min(20,10)=10$: $x_{13}=10$, $x_{12}=0$, $x_{22}=50$, $x_{23}=10$, cost $380$. New potentials $u_1=0$, $v_1=3$, $v_3=4$, $u_2=1$, $v_2=3$; $d_{12}=2$, $d_{21}=2$: optimal, minimum cost $380$.
8 Row minima $7,6,7,7$ give $\begin{pmatrix}3 & 0 & 1 & 5\\ 3 & 0 & 5 & 3\\ 0 & 5 & 2 & 3\\ 4 & 1 & 0 & 6\end{pmatrix}$; column minima $0,0,0,3$ then give a fourth column $(2,0,0,3)$. The zeros at $(1,2),(2,4),(3,1),(4,3)$ are independent, so the assignment $1\to2$, $2\to4$, $3\to1$, $4\to3$ is optimal, with cost $7+9+7+7=30$ (unique: the next best of the $24$ assignments costs $32$).
9 The sum of the row-constraint coefficient vectors equals the sum of the column-constraint vectors (both are all ones), so the rank is at most $m+n-1$. The $m+n-1$ vectors left after deleting the last column constraint are independent: in a vanishing combination $\sum\alpha_iR_i+\sum_{j\lt n}\beta_jC_j$, the coordinate of cell $(i,n)$ is $\alpha_i$, and then the coordinate of $(1,j)$ is $\beta_j$ (Theorem 9.26(2)).
🎯 Exam corner CSIR Part BCSIR Part CGATE ST

E1. CSIR Part B The number of extreme points of $\{x\in\mathbb{R}^3:x\ge0,\ x_1+x_2+x_3\le2,\ x_1\le1\}$ is (A) $4$; (B) $5$; (C) $6$; (D) $8$.

Idea The region is the simplex with corners $0,2e_1,2e_2,2e_3$ cut by the plane $x_1=1$. Equivalently, count the BFSs of $x_1+x_2+x_3+s_1=2$, $x_1+s_2=1$ (at most $\binom52=10$).
Count The corners with $x_1\le1$ survive: $(0,0,0),(0,2,0),(0,0,2)$. The corner $(2,0,0)$ is cut off, and the three edges leaving it meet $x_1=1$ at $(1,0,0),(1,1,0),(1,0,1)$, which are new corners. Total $6$. (The BFS count agrees: of the $10$ column pairs, $6$ give feasible basic solutions, all distinct.)
Answer (C).

E2. CSIR Part B GATE ST The optimal value of $\min z=5x_1+4x_2+4x_3$ subject to $x_1+x_2+2x_3\ge2$, $2x_1+x_2+x_3\ge3$, $x\ge0$ is (A) $6$; (B) $7$; (C) $8$; (D) $9$.

Idea Three variables, two constraints: solve the dual $\max2y_1+3y_2$ s.t. $y_1+2y_2\le5$, $y_1+y_2\le4$, $2y_1+y_2\le4$, $y\ge0$ graphically.
Compute Dual corners $(0,0),(2,0),(1,2),(0,\tfrac52)$ with values $0,4,8,7.5$; so the dual optimum is $8$ at $(1,2)$. By strong duality the primal optimum is also $8$; complementary slackness gives $x_2=0$ (the second dual constraint is slack) and $x_1+2x_3=2$, $2x_1+x_3=3$, so $x^*=(\tfrac43,0,\tfrac13)$ with $z=\tfrac{20}3+\tfrac43=8$. Weak duality alone already rules out (A) and (B): the dual feasible point $y=(1,2)$ proves $z\ge8$ for every primal feasible $x$, and $x^*$ shows that $8$ is attained, ruling out (D). (Using one variable only gives $10$ with $x_1=2$ or $12$ with $x_2=3$; mixing pays.)
Answer (C).

E3. CSIR Part B The final simplex tableau of a maximisation problem with slack variables $s_1,s_2$ is $$\begin{array}{c|ccccc|c}\text{basis} & x_1 & x_2 & x_3 & s_1 & s_2 & \bar x_{\mathcal B}\\ \hline x_1 & 1 & 0 & 2 & 1 & -1 & 3\\ x_2 & 0 & 1 & -1 & 0 & 1 & 2\\ \hline \Delta_j & 0 & 0 & 0 & 3 & 1 & 17\end{array}$$ Which statement is correct? (A) The optimal solution $(3,2,0)$ is unique. (B) The problem has alternative optimal solutions, one of which is $(0,\tfrac72,\tfrac32)$. (C) The problem is unbounded because column $x_3$ has a negative entry. (D) The basic feasible solution shown is degenerate.

Idea All $\Delta_j\ge0$: optimal. The nonbasic $x_3$ has $\Delta_3=0$ and a positive entry, so pivoting it in gives another optimal BFS.
Compute Ratio test in column $x_3$: only the $x_1$ row is positive, $\theta=3/2$. Then $x_3=\tfrac32$, $x_1=3-2\cdot\tfrac32=0$, $x_2=2+\tfrac32=\tfrac72$, and $z$ stays $17-\tfrac32\cdot0=17$. (A) is false because of this second optimum. (C) is false: unboundedness needs $\Delta_k\lt0$ and no positive entry. (D) is false: both basic variables are positive. (The tableau comes from $\max3x_1+4x_2+2x_3$ s.t. $x_1+x_2+x_3\le5$, $x_2-x_3\le2$; both points give $17$.)
Answer (B).

E4. CSIR Part C Let $A$ be an $m\times n$ real matrix of rank $m$, and suppose $P=\{x\in\mathbb{R}^n:Ax=b,\ x\ge0\}$ is nonempty. Which of the following are true? (One or more options may be correct.) (A) $P$ has at least one and at most $\binom nm$ extreme points. (B) If $P$ is unbounded, then $\max\{c^{\mathsf T}x:x\in P\}$ is $+\infty$ for every $c\ne0$. (C) Every extreme point of $P$ has at most $m$ positive components. (D) Every point of $P$ with at most $m$ positive components is an extreme point of $P$.

(A) True At least one by Theorem 9.16(1); at most $\binom nm$ by Theorem 9.15.
(B) False $P=\{x\in\mathbb{R}^2:x_1-x_2=0,\ x\ge0\}$ is the unbounded ray $\{(t,t)\}$, and $c=(1,-1)$ gives the constant $0$; $c=(-1,0)$ gives the maximum $0$ at the origin.
(C) True An extreme point is a BFS, whose positive components are basic, and there are $m$ basic variables.
(D) False What matters is the independence of the support columns (Theorem 9.14), not their number. For $A=\begin{pmatrix}1 & 1 & 0\\ 1 & 1 & 1\end{pmatrix}$, $b=(2,2)$, the point $(1,1,0)$ has two positive components but $a_1=a_2$; it is the midpoint of the corners $(2,0,0)$ and $(0,2,0)$.
Answer (A) and (C).

E5. CSIR Part C GATE ST Consider (P) $\max c^{\mathsf T}x$ s.t. $Ax\le b$, $x\ge0$ and its dual (D) $\min b^{\mathsf T}y$ s.t. $A^{\mathsf T}y\ge c$, $y\ge0$. Which of the following are true? (A) If (P) is infeasible, then (D) is unbounded. (B) If (P) and (D) are both feasible, then both have optimal solutions and the optimal values are equal. (C) If $x^*$, $y^*$ are optimal and $x_1^*\gt0$, then $(A^{\mathsf T}y^*)_1=c_1$. (D) If $y^*$ is optimal for (D) and $y_i^*=0$, then the $i$-th constraint of (P) is slack at every optimal $x^*$.

(A) False Both can be infeasible: $\max x_1$ s.t. $x_1-x_2\le-1$, $-x_1+x_2\le-1$ and its dual (Theorem 9.23(2) and the example after it).
(B) True Weak duality bounds each problem by the other's feasible value, so both are bounded and have optima (Theorem 9.19(3)); strong duality equates the values (Exercise IV.5).
(C) True Complementary slackness: $x_1^*(A^{\mathsf T}y^*-c)_1=0$ (Theorem 9.24).
(D) False The implication goes the other way (slack ⇒ price $0$). For $\max2x_1+2x_2$ s.t. $x_1+x_2\le4$, $x_1+3x_2\le6$, the unique dual optimum is $y^*=(2,0)$, but the optimal $x^*=(3,1)$ makes the second constraint tight ($3+3=6$).
Answer (B) and (C).

E6. CSIR Part C Consider a balanced transportation problem with $m$ sources and $n$ destinations, and the $n\times n$ assignment problem. Which of the following are true? (A) The transportation problem has an optimal solution with at most $m+n-1$ positive entries. (B) If all supplies and demands are integers, the transportation problem has an integral optimal solution. (C) Replacing $x_{ij}\in\{0,1\}$ by $x_{ij}\ge0$ in the assignment problem can give a strictly smaller optimal cost. (D) Adding the same constant $k$ to every cost in the first row of a transportation problem changes its set of optimal solutions.

(A) True An optimal BFS exists (Theorem 9.16) and has at most $m+n-1$ basic cells (Theorem 9.26(2)).
(B) True Every basic solution is integral (Theorem 9.26(3)).
(C) False The relaxation is a transportation problem with unit supplies and demands; it has an integral optimal BFS, i.e. a permutation matrix, so the two optimal costs coincide (Theorem 9.27).
(D) False Every feasible plan ships exactly $a_1$ units out of source 1, so every plan's cost rises by the same amount $ka_1$; the optimal plans are unchanged (the analogue of Theorem 9.27(1)).
Answer (A) and (B).
🧑‍🏫 For the teacher

Suggested plan — 3 lectures × 60 min.

  1. Geometry. Start with Example 1 drawn on the board, then project Interactive 1 and turn $\theta$ slowly: ask the class to predict the optimal corner before each stop, and stop at the two "edge" directions. Definitions 9.6–9.8, Theorems 9.13–9.15 with full proofs (the $x\pm\varepsilon d$ argument is the heart of the section), Example 2 as a table built with the class, Theorem 9.16 and Example 3.
  2. The simplex method. Derive $(*)$ slowly; Theorems 9.17 and 9.18 follow from it in a few lines each. Example 4 on the board, pointing at the picture after each pivot. Theorem 9.19 (state Bland's rule, show the degenerate pivot in Interactive 2, problem 3). Definition 9.10, Theorem 9.20, Example 5 with the two-phase tableaux; mention Big-M as the same pivots.
  3. Duality and special structures. The renting story, Definition 9.11 with the rules table (practise on Exercise IV.1), Theorems 9.21–9.24 with proofs (weak duality and complementary slackness are one-liners; strong duality reads the dual off the optimal tableau). Project Interactive 2, problem 1, and stop at each step to check $c^{\mathsf T}x=b^{\mathsf T}y$. Example 6 (the most examined technique). Farkas briefly. Transportation and assignment with Example 7, linking the $u$–$v$ test to complementary slackness. Finish with E4 and E5.

Discussion questions. (1) Why does the simplex method never need to look at points inside the region, while a general convex optimisation method must? (2) The dual solution of the workshop problem prices the market limit at $0$. What would have to change for it to become positive, and what would the workshop then be willing to pay for one more unit of quota? (3) Why does a degenerate pivot exist at all — what is "moving" when the point does not move?

Misconceptions to watch for. Taking ratios with zero or negative entries; stopping when the most negative $\Delta$ is removed instead of when all $\Delta_j\ge0$; reading the optimal $x$ from the $\Delta$ row and the dual from the right-hand side (it is the other way round); writing the dual of a minimisation with all signs as for a maximisation; believing that "optimal" means "a corner" or that "unbounded region" means "unbounded problem"; forgetting that a transportation basis has $m+n-1$ cells.

Suggested homework. I(1, 3, 5, 8), II(1, 2, 4, 6), III(1, 2, 4), IV(1, 2, 3, 6, 7); Exam corner E1, E3, E5.

🔬 Research–Teaching NexusResearch-tutored · optional, about 60 minutes

Research question. How many pivots does the simplex method really need? Is it fast on typical problems and slow only on carefully built ones?

Why it matters. The simplex method solves LPs with millions of variables every day — in airline crew scheduling, electricity markets, logistics and the planning of radiotherapy doses — and it is usually fast. Yet in 1972 Klee and Minty built problems on which Dantzig's rule visits every one of the $2^n$ corners of a squashed cube. The tension between these facts led to polynomial-time methods (Khachiyan's ellipsoid method, 1979; Karmarkar's interior-point method, 1984) and to "smoothed analysis" (Spielman and Teng, 2001), which explains why tiny random perturbations make the simplex method fast.

What to do.

  1. Implement the tableau simplex method of this section (slack basis, Dantzig's rule, ratio test) in a few dozen lines of Python, and test it on Example 4 and Exercise II.2.
  2. Run it on the Klee–Minty problems $\max\sum_{j=1}^n2^{n-j}x_j$ s.t. $2\sum_{j\lt i}2^{i-j}x_j+x_i\le5^i$ ($i=1,\dots,n$), $x\ge0$, for $n=2,\dots,8$, and count the pivots. Find the pattern and prove it for $n=2$ by hand.
  3. Run it on $30$ random problems $\max c^{\mathsf T}x$, $Ax\le\mathbf 1$, $x\ge0$ with $A$ an $m\times m$ matrix of independent $U(0,1)$ entries and $c$ uniform, for $m=10,20,40,80$. Plot the mean number of pivots against $m$.
  4. Rerun the Klee–Minty problems with Bland's rule, and with the rule "enter the variable giving the largest increase of $z$". Does the exponential behaviour survive?

Tools: Python with numpy (and scipy.optimize.linprog to check optimal values).

Hand in: Your code, a table of pivot counts for Klee–Minty ($n=2,\dots,8$) and for random problems ($m=10,\dots,80$), a plot, and a paragraph comparing worst-case and typical behaviour.

Going further. Read about interior-point methods, which follow a curve through the inside of the region (the "central path") and need a number of iterations that grows only like a small power of the size, and about the Hirsch conjecture on the diameter of polytopes (disproved by Santos in 2010, though a polynomial bound is still open).

Instructor note: with Dantzig's rule and the formulation above, the Klee–Minty problems need exactly $2^n-1$ pivots ($3,7,15,31$ for $n=2,3,4,5$, as a quick run confirms) and end at $x=(0,\dots,0,5^n)$. For the random problems with $m=n$, a run of $30$ problems per size gave mean pivot counts of about $4.6$, $10.2$, $20.8$ and $48.2$ for $m=10,20,40,80$ — roughly $m/2$, growing linearly. Students should not expect identical numbers (they depend on the random seed), but the linear trend is robust. Under Bland's rule the Klee–Minty count changes, and other cube-like constructions defeat most deterministic pivot rules — a good discussion point about worst-case analysis.

🧪 Self-check quiz

0/5 correct

Q1. For $Ax=b$, $x\ge0$ with $A$ of size $3\times6$ and rank $3$, the number of basic feasible solutions is at most

Q2. In the simplex tableau of a maximisation problem, a basic feasible solution is certified optimal when

Q3. Phase I ends with optimal value $w^*=3$. Then the original problem is

Q4. If the primal (a maximisation) is unbounded, its dual is

Q5. At optimal solutions $x^*$, $y^*$ of (P) and (D), if $y_2^*\gt0$ then