Past exam of the mathematics course of the University of Cambridge / 2004 / iii / Paper 33 / 1 / Solution

For the linear program in maximization form, a nonnegative multiplier $y$ of the resource inequalities giveswhenever $A^{T}y\ge c$. Equivalently, the Lagrangian is $b^{T}y+(c-A^{T}y{)}^{T}x$; its supremum over $x\ge 0$ is finite exactly when $A^{T}y\ge c$. Minimizing this bound gives the dual linear programThe displayed inequality proves weak duality directly.

For the final simplex tableau, the basic-variable order is $(x_2,x_1)$. With $z_1,z_2$ interpreted as the ordinary unpriced slack variables, its constraint equations giveThe bottom row is read in the reduced-cost convention $r_j=c_j-c_B^T{B}^{-1}{A}_j$, with right side minus the basic objective value. It says the reduced costs of $z_1,z_2$ are $0,-1/2$. Thus optimality requires $z_2=0$, while $z_1$ can increase without changing the objective until $x_2$ reaches zero. The complete primal optimum set is

Reconstructing a linear program from a final simplex tableau exposes a source inconsistency. The slack columns areBecause the first basic column is that of $x_2$, the original constraint data areThe slack reduced costs give $y^T=(0,1/2)$ andConsequently the recovered homogeneous linear program isEvery point in the optimum segment has value $15/2$. Since the segment contains a point with both variables positive, complementary slackness forces both dual column inequalities to be equalities. They give the unique dual optimum

The printed bottom-right entry is $-3$, but it must be $-15/2$ for this linear objective and these constraint rows. Thus no original problem in the stated homogeneous standard form has exactly the entire printed tableau. Changing that one entry to $-15/2$ gives the reconstructed problem above. Alternatively, if an affine objective is permitted, $5x_1-\frac{5}{2}{x}_2-\frac{9}{2}$ has the displayed optimum value $3$ and unchanged reduced costs; the corresponding affine dual objective is $b^{T}y-\frac{9}{2}$. Both interpretations have exactly the same primal and dual optimizer sets. The discrepancy is in the objective constant, not in the optimal segment.