Topper Copies

Use Big-M method to solve the following LPP : Maximize $Z = 6x_1 + 4x_2$, subject to $2x_1 + 3x_2 \leq 30, 3x_1 + 2x_2 \leq 24, x_1 + x_2 \geq 3$ and $x_1 \geq 0, x_2 \geq 0$. Is the solution unique? If not, give two different solutions

Aryan Yadav, AIR 31, 2025

ReWriting problem $\Rightarrow$

Max $z' = 6x_1 + 4x_2 + 0S_1 + 0S_2 + 0S_3 - Ma_1$

$2x_1 + 3x_2 + S_1 = 30$

$3x_1 + 2x_2 + S_2 = 24$

$x_1 + x_2 - S_3 + a_1 = 3$

$x_1, x_2, a_1, S_1, S_2, S_3 \geq 0$

$S_1, S_2, S_3$ are slack , $a_1$ is Artificial

| | $c_j$ | 6 | 4 | 0 | 0 | 0 | -M | | | |---|---|---|---|---|---|---|---|---|---| | | | $x_1$ | $x_2$ | $S_1$ | $S_2$ | $S_3$ | $a_1$ | b | $\theta$ | | 0 | $S_1$ | 2 | 3 | 1 | 0 | 0 | 0 | 30 | 15 | | 0 | $S_2$ | 3 | 2 | 0 | 1 | 0 | 0 | 24 | 8 | | -M | $a_1$ | [1] | 1 | 0 | 0 | -1 | 1 | 3 | 3 | | | $C_j - Z_j$ | M+6 | M+4 | 0 | 0 | M | 0 | | |

| | $c_j$ | 6 | 4 | 0 | 0 | 0 | -M | | | |---|---|---|---|---|---|---|---|---|---| | | | $x_1$ | $x_2$ | $S_1$ | $S_2$ | $S_3$ | $a_1$ | b | $\theta$ | | 0 | $S_1$ | 0 | 1 | 1 | 0 | 2 | -2 | 24 | 12 | | 0 | $S_2$ | 0 | -1 | 0 | 1 | [3] | -3 | 15 | 5 | | 6 | $x_1$ | 1 | 1 | 0 | 0 | -1 | 1 | 3 | -1 | | | $C_j - Z_j$ | 0 | -2 | 0 | 0 | 6 | -M | | |

| | $c_j$ | 6 | 4 | 0 | 0 | 0 | -M | | | |---|---|---|---|---|---|---|---|---|---| | | | $x_1$ | $x_2$ | $S_1$ | $S_2$ | $S_3$ | $a_1$ | b | $\theta$ | | 0 | $S_1$ | 0 | [5/3] | 1 | -2/3 | 0 | 0 | 14 | 8.4 | | 0 | $S_3$ | 0 | -1/3 | 0 | 1/3 | 1 | -1 | 5 | -15 | | 6 | $x_1$ | 1 | 2/3 | 0 | 1/3 | 0 | 0 | 8 | 12 | | | $c_j - z_j$ | 0 | 0 | 0 | -2 | 0 | -M | | |

Hence optimality reached

Max = 48 at (8,0)

Since $c_j - z_j$ of $x_2 = 0$ but its non basic $\Rightarrow$ Not unique

solving further,

| | $c_j$ | 6 | 4 | 0 | 0 | 0 | -M | | | |---|---|---|---|---|---|---|---|---|---| | | | $x_1$ | $x_2$ | $S_1$ | $S_2$ | $S_3$ | $a_1$ | b | | | | $x_2$ | 0 | 1 | 3/5 | -2/5 | 0 | 0 | 8.4 | | | | $S_3$ | 0 | 0 | 1/5 | 1/15 | 1 | -1 | 7.8 | | | | $x_1$ | 1 | 0 | -2/5 | 3/5 | 0 | 0 | 2.4 | | | | $c_j - z_j$ | 0 | 0 | 0 | -4/5 | 0 | -M | | |

All $c_j - z_j \leq 0$ $\Rightarrow$ Optimal

Hence (2.4, 8.4) is also sol$^n$

Since LPP sol'ns are convex set

Another sol$^n$ is $\frac{8+2.4}{2}$ , $\frac{0+8.4}{2}$

$= 5.2, 4.2$

Hence $(5.2, 4.2)$ & $(2.4, 8.4)$ are 2 more solutions

Max $= 48$