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$