Past exam of the probability, statistics and options I course of the University of Oxford / 2008 / T / 1

The dual linear program isFor feasible $x,y$, nonnegativity and the two constraint inequalities imply weak duality:If a feasible pair has equal objectives, every primal feasible objective is at most that common value and every dual feasible objective at least it. Thus both feasible solutions are optimal. Strong duality is not needed for this certificate.

The identity columns in the final tableau correspond to basic variables $x_2,x_3$. Their original basis matrix isalso visible directly in the two slack columns. Multiply the original constraint tableau and right side by $B^{-1}$ to obtain the missing entries. Subtract four times the first row and three times the second from the initial objective row, using the basic costs. The completed simplex tableau isThe last row uses the supplied convention of reduced costs $c_j-c_B^T{B}^{-1}{A}_j$, so its final right side is minus the objective. Setting the nonbasic variables to zero givesThe dual feasible vector $y=(1,1)$ has $A^{T}y=(3,4,3{)}^T\ge (1,4,3{)}^T$ and objective $4+6=10$. Part (a) independently certifies the optimum and confirms the objective-row sign.