Paper 1, Section I, H

Optimization
Part IB, 2020

Solve the following Optimization problem using the simplex algorithm:

maximisex1+x2 subject to x12x224x1+x24,x1,x20\begin{array}{rr} \operatorname{maximise} & x_{1}+x_{2} \\ \text { subject to } & \left|x_{1}-2 x_{2}\right| \leqslant 2 \\ & 4 x_{1}+x_{2} \leqslant 4, \quad x_{1}, x_{2} \geqslant 0 \end{array}

Suppose the constraints above are now replaced by x12x22+ϵ1\left|x_{1}-2 x_{2}\right| \leqslant 2+\epsilon_{1} and 4x1+x24+ϵ24 x_{1}+x_{2} \leqslant 4+\epsilon_{2}. Give an expression for the maximum objective value that is valid for all sufficiently small non-zero ϵ1\epsilon_{1} and ϵ2\epsilon_{2}.