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

Aakash Om Trivedi, AIR 73, 2025

Convert int standard form

Maximize $z = 6x_1 + 4x_2 - MA_1$

$2x_1 + 3x_2 \leq 30 \Rightarrow 2x_1 + 3x_2 + S_1 = 30$

$3x_1 + 2x_2 \leq 24 \rightarrow 3x_1 + 2x_2 + S_2 = 24$

$x_1 + x_2 \geq 3 \Rightarrow x_1 + x_2 - S_3 + A_1 = 3$

$x_1, x_2, [?], S_1, S_2, S_3, A_1 \geq 0$

| | $c_j$ | 6 | 4 | 0 | 0 | 0 | $-M$ | | ratio | |---|---|---|---|---|---|---|---|---|---| | | | $x_1$ | $x_2$ | $S_1$ | $S_2$ | $S_3$ | $A_1$ | | | | $S_1$ | 0 | 2 | 3 | 1 | 0 | 0 | 0 | 30 | 30/2 = 15 | | $S_2$ | 0 | 3 | 2 | 0 | 1 | 0 | 0 | 24 | 24/3 = 8 | | $A_1$ | $-M$ | 1 | 1 | 0 | 0 | -1 | 1 | 3 | 3 = 3 | | | $z_j$ | $-M$ | $-M$ | 0 | 0 | $M$ | $-M$ | | | | | $c_j - z_j$ | $6+M$ | $4+M$ | 0 | 0 | $-M$ | 0 | | |

($\because$ maximum $c_j - z_j$ entry)

$R_1 \to R_1 - 2R_3$, $R_2 \to R_2 - 3R_3$

| | $c_j$ | 6 | 4 | 0 | 0 | 0 | $-M$ | | ratio | |---|---|---|---|---|---|---|---|---|---| | | | $x_1$ | $x_2$ | $S_1$ | $S_2$ | $S_3$ | $A_1$ | | | | $S_1$ | 0 | 0 | 1 | 1 | 0 | 2 | -2 | 24 | 24/2 = 12 | | $S_2$ | 0 | 0 | -1 | 0 | 1 | 3 | -3 | 15 | 15/3 = 5 | | $x_1$ | 6 | 1 | 1 | 0 | 0 | -1 | -1 | 3 | X | | | $c_j - z_j$ | 0 | -2 | 0 | 0 | 6 | $-M+6$ | | |

| | $c_j$ | 6 | 4 | 0 | 0 | 0 | $-M$ | | ratio | |---|---|---|---|---|---|---|---|---|---| | | | $x_1$ | $x_2$ | $s_1$ | $s_2$ | $s_3$ | $A_1$ | | | | $s_1$ | 0 | 0 | 5/3 | 1 | -2/3 | 0 | 0 | 14 | $\frac{14}{5}\cdot 3 = 8.4$ | | $s_3$ | 6 | 0 | -1/3 | 0 | 1/3 | 1 | -1 | 5 | - | | $x_1$ | 6 | 1 | 2/3 | 0 | 1/3 | 0 | -2 | 8 | $\frac{8}{2}\times 3$ | | | $z_j$ | 6 | 4 | 0 | 2 | 0 | -12 | 48 | | | | $c_j - z_j$ | 0 | 0 | 0 | -2 | 0 | $-M+12$ | | |

$R_1 \to R_1 - 2R_2$ [?]

$R_3 \to R_3 + R_2$ [?]

($x_1 = 8$ , $x_2 = 0$) one solution

as $c_j - z_j = 0$ for $x_2$ so alternate solution

| | $c_j$ | 6 | 4 | 0 | 0 | 0 | $-M$ | | |---|---|---|---|---|---|---|---|---| | | | $x_1$ | $x_2$ | $s_1$ | $s_2$ | $s_3$ | $A_1$ | | | $x_2$ | 4 | 0 | 1 | 3/5 | -2/5 | 0 | 0 | 42/5 | | $s_3$ | 0 | 0 | 0 | 1/5 | 1/5 | 1 | -1 | 39/5 | | $x_1$ | 6 | 1 | 0 | -2/5 | 3/5 | 0 | -2 | 12/5 |

$R_2 \to R_2 + \frac{R_1}{3}$

$R_3 \to R_3 - \frac{2R_1}{3}$

$\therefore$ ($x_1 = \frac{12}{5}$ , $x_2 = \frac{42}{5}$) alternate solution