Optimization | Part IB, 2001

Consider the following linear programming problem,

minimize(3p)x1+px2 subject to 2x1+x28x1+3x29x16x1,x20\begin{array}{lrl} \operatorname{minimize} \quad(3-p) x_{1}+p x_{2} & \\ \text { subject to } & 2 x_{1}+x_{2} & \geqslant 8 \\ x_{1}+3 x_{2} & \geqslant 9 \\ x_{1} & \leqslant 6 \\ x_{1}, x_{2} & \geqslant 0 \end{array}

Formulate the problem in a suitable way for solution by the two-phase simplex method.

Using the two-phase simplex method, show that if 2p942 \leqslant p \leqslant \frac{9}{4} then the optimal solution has objective function value 9p9-p, while if 94<p3\frac{9}{4}<p \leqslant 3 the optimal objective function value is 185p18-5 p.

Typos? Please submit corrections to this page on GitHub.