Paper 3, Section II, H

Optimization
Part IB, 2014

Use the two-phase simplex method to maximise 2x1+x2+x32 x_{1}+x_{2}+x_{3} subject to the constraints

x1+x21,x1+x2+2x34,xi0 for i=1,2,3x_{1}+x_{2} \geqslant 1, \quad x_{1}+x_{2}+2 x_{3} \leqslant 4, \quad x_{i} \geqslant 0 \text { for } i=1,2,3

Derive the dual of this linear programming problem and find the optimal solution of the dual.