3.II.23G

Optimization
Part IB, 2004

Consider the following linear programming problem:

 maximize x1+3x2 subject to x1+x23x1+2x26x1+x22,x25,xi0,i=1,2.\begin{aligned} \text { maximize }-x_{1}+3 x_{2} \\ \text { subject to } \quad x_{1}+x_{2} & \geqslant 3 \\ -x_{1}+2 x_{2} & \geqslant 6 \\ -x_{1}+x_{2} & \leqslant 2, \\ x_{2} & \leqslant 5, \\ x_{i} & \geqslant 0, \quad i=1,2 . \end{aligned}

Write down the Phase One problem in this case, and solve it.

By using the solution of the Phase One problem as an initial basic feasible solution for the Phase Two simplex algorithm, solve the above maximization problem. That is, find the optimal tableau and read the optimal solution (x1,x2)\left(x_{1}, x_{2}\right) and optimal value from it.