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.
Akshit Bhardwaj, AIR 12, 2025
We can write the problem as
Max $z^* = 6x_1 + 4x_2 - 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, x_3, s_1, s_2, s_3, A_1 \geq 0$
SIMPLEX TABLE
| $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 | | $z_j$ | $-M$ | $-M$ | 0 | 0 | $M$ | $-M$ | | | | $\Delta_j$ | $M+6$ | $M+4$ | 0 | 0 | $-M$ | 0 | | |
| | $x_1$ | $x_2$ | $s_1$ | $s_2$ | $s_3$ | $b$ | $\theta$ | |---|---|---|---|---|---|---|---| | $0$ $s_1$ | 0 | 1 | 1 | 0 | 2 | 24 | 12 | | $0$ $s_2$ | 0 | $-1$ | 0 | 1 | (3) | 15 | 5 [?] | | $6$ $x_1$ | 1 | 1 | 0 | 0 | $-1$ | 3 | $-3$ | | $z_j$ | 6 | 6 | 0 | 0 | $-6$ | | | | $\Delta_j$ | 0 | $-2$ | 0 | 0 | 6 | | |
| | $x_1$ | $x_2$ | $s_1$ | $s_2$ | $s_3$ | $b$ | $\theta$ | |---|---|---|---|---|---|---|---| | $0$ $s_1$ | 0 | $5/3$ | 1 | $-2/3$ | 0 | 14 | | | $0$ $s_3$ | 0 | $-1/3$ | 0 | $1/3$ | 1 | 5 | | | $6$ $x_1$ | 1 | $2/3$ | 0 | $1/3$ | 0 | 8 | | | $z_j$ | 6 | 4 | 0 | 2 | 0 | | | | $\Delta_j$ | 0 | 0 | 0 | $-2$ | 0 | | |
Since All $\Delta_j \le 0$
$x_1 = 8$ $x_2 = 0$ is an optimal solution
Max $Z = 48$
Since $\Delta_j = 0$ for $x_2$, the solution is not unique
Entering $x_2$ into the table
| | $x_1$ | $x_2$ | $S_1$ | $S_2$ | $S_3$ | $b$ | |---|---|---|---|---|---|---| | $S_1$ | 0 | 0 | 1 | $-3/2$ | 0 | $-6$ | | $S_3$ | 0 | 0 | 0 | $1/2$ | 1 | 9 | | $x_2$ | $3/2$ | 1 | 0 | $1/2$ | 0 | 12 | | $\Delta_j$ | 0 | 0 | 0 | $-2$ | 0 | |
$\Rightarrow$ $x_2 = 12$ $x_1 = 0$ is Another optimal solution