Topper Copies

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

Kanishak Aggarwal, AIR 72, 2025

$\text{Max } Z = 6x_1 + 4x_2 + 0s_1 + 0s_2 + 0e_1 - Ma_1$

s.t.

$2x_1 + 3x_2 + s_1 = 30$

$3x_1 + 2x_2 + s_2 = 24$

$x_1 + x_2 - e_1 + a_1 = 3$

$x_1, x_2, s_1, s_2, e_1, a_1 \ge 0$

IBFS $s_1 = 30$, $s_2 = 24$, $a_1 = 3$.

Table 1

| | | 6 | 4 | 0 | 0 | 0 | $-M$ | | | |---|---|---|---|---|---|---|---|---|---| | $C_B$ | $x_B$ | $x_1$ | $x_2$ | $s_1$ | $s_2$ | $e_1$ | $a_1$ | $b$ | ratio | | 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$ | $-3M$ | | | $\Delta_j = c_j - Z_j$ | | $6+M$ ↑ | $4+M$ | 0 | 0 | $-M$ | 0 | | |

Table 2

| $C_B$ | $x_B$ | $x_1$ | $x_2$ | $s_1$ | $s_2$ | $e_1$ | $a_1$ | $b$ | ratio | |---|---|---|---|---|---|---|---|---|---| | 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 | | | $Z_j$ | | 6 | 6 | 0 | 0 | -6 | 6 | 18 | | | $\Delta_j = c_j - Z_j$ | | 0 | -2 | 0 | 0 | 6 ↑ | $-M-6$ | | |

Table 3

| $C_B$ | $x_B$ | $x_1$ | $x_2$ | $s_1$ | $s_2$ | $e_1$ | $a_1$ | $b$ | $\theta$ | |---|---|---|---|---|---|---|---|---|---| | 0 | $s_1$ | 0 | [5/3] | [?] 1 | 0 -2/3 [?] | 0 | 0 | 14 | 42/5 | | 0 | $e_1$ | 0 | -1/3 | 0 | [?] | 1 | -1 | 5 | | | 6 | $x_1$ | [?] 1 | 2/3 | 0 | 1/3 | 0 | 0 | 8 | 12 | | $z_j$ | | 6 | 4 | 0 | 2 | 0 | 0 | 48 | | | $c_j - z_j$ | | 0 | 0 | 0 | -2 | 0 | $-M$ | | |

All $c_j \le 0$

but $c_j - z_j$ of $x_2 = 0$

$\therefore$ alternate exists.

Table 4

| $C_B$ | $x_B$ | $x_1$ | $x_2$ | $s_1$ | $s_2$ | $e_1$ | $a_1$ | $b$ | |---|---|---|---|---|---|---|---|---| | 4 | $x_2$ | [?] 0 | 1 | 0 3/5 | -2/5 | 0 | 0 | 42/5 | | 0 | $e_1$ | [?] 0 | 0 | 0 1/5 | 1/5 | 1 | -1 | 39/5 | | 6 | $x_1$ | [?] 1 | 0 | [?] -2/5 | 3/5 | 0 | 0 | 12/5 | | | | | | | | | | 48 |

$\text{Max } z = 48$

$(x_1, s_1, e_1) = (0, 0, 0)$

$(x_1, x_2, e_1) = (12/5, 42/5, 39/5)$