Topper Copies

Solve the L.P. problem Max. $Z = \frac{3}{4}x_1 - 150x_2 + \frac{1}{50}x_3 - 6x_4$ s.t. $\frac{1}{4}x_1 - 60x_2 - \frac{1}{25}x_3 + 9x_4 \le 0$ $\frac{1}{2}x_1 - 90x_2 - \frac{1}{50}x_3 + 3x_4 \le 0$ $x_3 \le 1$ and $x_1, x_2, x_3, x_4 \ge 0$

Aryan Yadav, AIR 31, 2025

Finding all Basic solns $\Rightarrow$ [?]

1) B.V $= x_1, x_2$

$\Rightarrow \frac{x_1}{4} - 60x_2 = 0$ , $\frac{x_1}{2} - 90x_2 = 0$

Clearly max will be at $x_3 = 1$ as coefficient of $x_3$ is +ve in $Z$ & -ve in both Equations

Put $x_3 = 1$

$\Rightarrow$ Max $\frac{3}{4}x_1 - 150x_2 - 6x_4 + \frac{1}{50}$

s/t $\frac{x_1}{4} - 60x_2 + 9x_4 \le \frac{1}{25}$

$\frac{x_1}{2} - 90x_2 + 3x_4 \le \frac{1}{50}$

$x_1, x_2, x_4 \ge 0$

Max $\frac{3}{4}x_1 - 150x_2 - 6x_4 + \frac{1}{50} + 0S_1 + 0S_2$

$\frac{x_1}{4} - 60x_2 + 9x_4 + [?]S_1 = \frac{1}{25}$

$\frac{x_1}{2} - 90x_2 + 3x_4 + S_2 = \frac{1}{50}$

Simplex table :

| | $C_j$ | $\frac{3}{4}$ | $-150$ | [?] | $-6$ | 0 | 0 | | | |---|---|---|---|---|---|---|---|---|---| | | | $x_1$ | $x_2$ | [?] | $x_4$ | $S_1$ | $S_2$ | $b$ | $Q$ | | 0 | $S_1$ | $\frac{1}{4}$ | $-60$ | [?] | 9 | 1 | 0 | $\frac{1}{25}$ | $\frac{4}{25}$ | | 0 | $S_2$ | $\left(\frac{1}{2}\right)$ | $-90$ | | 3 | 0 | 1 | $\frac{1}{50}$ | $\frac{1}{25}$ | | | $Z_j$ | 0 | 0 | | 0 | 0 | 0 | | | | | $C_j-Z_j$ | $\frac{3}{4}$ | $-150$ | | $-6$ | 0 | 0 | | |

($x_1$ column marked with an up arrow)

| | | $x_1$ | $x_2$ | $x_4$ | $S_1$ | $S_2$ | $b$ | $Q$ | |---|---|---|---|---|---|---|---|---| | 0 | $S_1$ | 0 | $-15$ | $\frac{15}{2}$ | 1 | $-\frac{1}{2}$ | $\frac{3}{100}$ | | | $\frac{3}{4}$ | $x_1$ | 1 | $-180$ | 6 | 0 | 2 | $\frac{1}{25}$ | | | | $Z_j$ | $\frac{3}{4}$ | $-135$ | $\frac{9}{2}$ | 0 | $\frac{3}{2}$ | | | | | $C_j-Z_j$ | 0 | $-15$ | $-\frac{21}{2}$ | 0 | $-\frac{3}{2}$ | | |

Hence optimal at $x_1 = \frac{1}{25}$, $x_2 = x_4 = 0$

Max $= \frac{3}{100} + \frac{1}{50} = $ $\frac{1}{20}$

At $x = \left(\frac{1}{25}, 0, 1, 0\right)$