Past exam of the mathematics course of the University of Cambridge / 2007 / ib / Paper 4 / 20C / iii

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.