Past exam of the mathematics course of the University of Cambridge / 2007 / ib / Paper 4 / 20C (Optimization)

Use payoff $P=-(2x_1-3x_2-2x_3)$, so maximization of $P$ is equivalent to the required minimization. In the given simplex tableau, $x_1$ can increase the payoff. The simplex ratio test has candidate ratios $3/6=1/2$ in the $z_2$ row and $15/1=15$ in the $z_3$ row; the negative coefficient in the $x_2$ row imposes no upper bound. Thus $x_1$ enters the simplex basis and $z_2$ leaves.

Divide the pivot row by $6$, then eliminate $x_1$ from the other rows. The resulting simplex dictionary isAll slack variables and original variables are nonnegative. The last row therefore proves $P\le 8$ for every feasible point; setting the nonbasic variables $x_3,z_1,z_2$ to zero attains it and leaves all basic variables nonnegative. HenceThe slack vector is $(0,0,29/2)$.

The amended payoff is $P_{\mathrm{new}}=P+3x_3$. Using the previous simplex dictionary,Thus $x_3$ enters. The positive pivot-column coefficients give ratios $3/(1/2)=6$ from $x_2$ and $(29/2)/10=29/20$ from $z_3$; the coefficient $-3/2$ in the $x_1$ row gives no bound. The simplex ratio test makes $z_3$ leave. Dividing that row by $10$ and eliminating $x_3$ givesThe positive objective-row coefficients and nonnegative slack variables prove optimality at $z_1=z_2=z_3=0$. ThereforeAll three constraints are equalities at this point. Strict positivity of the three objective-row coefficients also forces every optimal point to have all three slacks zero; the displayed dictionary then makes the optimizer unique.

Write the amended primal as $\min c^{\mathsf{T}}x$ with $Ax\le b$, $x\ge 0$. A convenient linear programming duality convention uses $y\le 0$ and gives $\max b^{\mathsf{T}}y$ subject to $A^{\mathsf{T}}y\le c$. Explicitly the dual isThe optimal dual vector is the negative of the three payoff-row slack coefficients:Indeed substitution gives $A^{\mathsf{T}}{y}^{\ast }=(2,-3,-5{)}^{\mathsf{T}}=c$, so all dual inequalities hold. To certify optimality directly by weak duality, for any feasible primal and dual vectors,where the second inequality uses $Ax\le b$ and $y\le 0$. Our feasible primal and dual vectors have equal values $-349/40$, so neither can be improved. This is a linear programming optimality certificate.