Paper 3, Section II, H

Optimization
Part IB, 2013

Use the two phase method to find all optimal solutions to the problem

maximize2x1+3x2+x3 subject to x1+x2+x3402x1+x2x310x2+x310x1,x2,x30\begin{aligned} \operatorname{maximize} 2 x_{1}+3 x_{2}+x_{3} \\ \text { subject to } x_{1}+x_{2}+x_{3} & \leqslant 40 \\ 2 x_{1}+x_{2}-x_{3} & \geqslant 10 \\ -x_{2}+x_{3} & \geqslant 10 \\ x_{1}, x_{2}, x_{3} & \geqslant 0 \end{aligned}

Suppose that the values (40,10,10)(40,10,10) are perturbed to (40,10,10)+(ϵ1,ϵ2,ϵ3)(40,10,10)+\left(\epsilon_{1}, \epsilon_{2}, \epsilon_{3}\right). Find an expression for the change in the optimal value, which is valid for all sufficiently small values of ϵ1,ϵ2,ϵ3\epsilon_{1}, \epsilon_{2}, \epsilon_{3}.

Suppose that (ϵ1,ϵ2,ϵ3)=(θ,2θ,0)\left(\epsilon_{1}, \epsilon_{2}, \epsilon_{3}\right)=(\theta,-2 \theta, 0). For what values of θ\theta is your expression valid?