Topper Copies

Use two-phase simplex method to solve the following LPP : Minimize $Z = x_1 - 2x_2 - 3x_3$ subject to $-2x_1 + x_2 + 3x_3 = 2, 2x_1 + 3x_2 + 4x_3 = 1$ and $x_1 \geq 0, x_2 \geq 0, x_3 \geq 0$.

Akshit Bhardwaj, AIR 12, 2025

Minimize $Z = x_1 - 2x_2 - x_3$

$-2x_1 + x_2 + 3x_3 = 2$

$2x_1 + 3x_2 + 4x_3 = 1$

$x_1, x_2, x_3 \geq 0$

This can be re-written as

Max $Z^* = -x_1 + 2x_2 + x_3$ | For (Phase 2) method

Max $Z^{} = -M_1A_1 - MA_2$

$-2x_1 + x_2 + 3x_3 + A_1 = 2$

$2x_1 + 3x_2 + 4x_3 + A_2 = 1$

Phase 1 simplex

| $c_j$ | 0 | 0 | 0 | $-M$ | $-M$ | | | |---|---|---|---|---|---|---|---| | | $x_1$ | $x_2$ | $x_3$ | $A_1$ | $A_2$ | $b$ | ratio | | $-M A_1$ | $-2$ | $1$ | $3$ | $1$ | $0$ | $2$ | $2/3$ | | $-M A_2$ | $2$ | $3$ | $4$ | $0$ | $1$ | $1$ | $1/4$ | | $z_j$ | $0$ | $-4M$ | $-7M$ | $-M$ | $-M$ | | | | $\Delta_j$ | $0$ | $4M$ | $7M$ | $0$ | $0$ | | |

| | $x_1$ | $x_2$ | $x_3$ | $A_1$ | $A_2$ | | |---|---|---|---|---|---|---| | $-M$ $A_1$ | $-7/2$ | $-5/4$ | $0$ | $1$ | $-3/4$ | $5/4$ | | $0$ $x_3$ | $1/2$ | $3/4$ | $1$ | $0$ | $1/4$ | $1/4$ | | $z_j$ | $7M/2$ | $5M/4$ | $0$ | $-M$ | $3M/4$ | | | $\Delta_j$ | $-7M/2$ | $-5M/4$ | $0$ | $0$ | $-7M/4$ | |

Thus all $\Delta_j < 0$

Also Artificial variable is still involved as basic variable

$\Rightarrow$ We don't need phase 2

$x_3 = \frac{1}{4}$ $x_1 -$