Paper 2, Section I, H

Optimization
Part IB, 2016

Use the simplex algorithm to find the optimal solution to the linear program:

maximise3x+5y subject to 8x+3y+10z9,x,y,z05x+2y+4z82x+y+3z2\operatorname{maximise} 3 x+5 y \text { subject to } \begin{aligned} 8 x+3 y+10 z & \leqslant 9, \quad x, y, z \geqslant 0 \\ 5 x+2 y+4 z & \leqslant 8 \\ 2 x+y+3 z & \leqslant 2 \end{aligned}

Write down the dual problem and find its solution.