Topper Copies

Using simplex Algorithm solve the problem Max. $Z = 2x_1 + 5x_2 + 7x_3$ Subject to. $3x_1 + 2x_2 + 4x_3 \leq 100$ $x_1 + 4x_2 + 2x_3 \leq 100$ $x_1 + x_2 + 3x_3 \leq 100$ $x_1, x_2, x_3 \geq 0$

Divyank Gupta, AIR 21, 2024

To find Max $Z = 2x_1 + 5x_2 + 7x_3$

s.t. $3x_1 + 2x_2 + 4x_3 \leq 100$

$x_1 + 4x_2 + 2x_3 \leq 100$

$x_1 + x_2 + 3x_3 \leq 100$

$x_1, x_2, x_3 \geq 0$

adding slack Variable $x_4, x_5, x_6$ we get

$3x_1 + 2x_2 + 4x_3 + x_4 = 100$

$x_1 + 4x_2 + 2x_3 + x_5 = 100$

$x_1 + x_2 + 3x_3 + x_6 = 100$

So $Z = 2x_1 + 5x_2 + 7x_3 + 0\cdot x_4 + 0\cdot x_5 + 0\cdot x_6$

putting $x_1, x_2, x_3 = 0$ we get

$x_4 = x_5 = x_6 = 100$ as Basic Variable

Now Simplex Table will be.

$\Delta_j = C_j - (C_B\cdot X_B)$

| B | $C_B$ | $x_B$ | $y_1$ | $y_2$ | $y_3$ | $y_4$ | $y_5$ | $y_6$ | Min Ration $x_B/y_j$ | |---|---|---|---|---|---|---|---|---|---| | | | $C_j$ | 2 | 5 | 7 | 0 | 0 | 0 | | | $y_4$ | 0 | 100 | 3 | 2 | 4 | 1 | 0 | 0 | 25 $\to$ | | $y_5$ | 0 | 100 | 1 | 4 | 2 | 0 | 1 | 0 | 50 | | $y_6$ | 0 | 100 | 1 | 1 | 3 | 0 | 0 | 1 | 100/3 | | | | $\Delta_j$ | 2 | 5 | 7 $\uparrow$ | 0 $\downarrow$ | 0 | 0 | |

| B | $C_B$ | $x_B$ | $y_1$ | $y_2$ | $y_3$ | $y_4$ | $y_5$ | $y_6$ | Min Ration | |---|---|---|---|---|---|---|---|---|---| | $y_3$ | 7 | 25 | 3/4 | 1/2 | 1 | 1/4 | 0 | 0 | 50 | | $y_5$ | 0 | 50 | $-1/2$ | 3 | 0 | $-1/2$ | 1 | 0 | 50/3 $\to$ | | $y_6$ | 0 | 25 | $-5/4$ | $-1/2$ | 0 | $-3/4$ | 0 | 1 | $-$ | | | | $\Delta_j$ | $-3.25$ | 1.5 $\uparrow$ | 0 | $-7/4$ | 0 $\downarrow$ | 0 | |

| B | $C_B$ | $x_B$ | $y_1$ | $y_2$ | $y_3$ | $y_4$ | $y_5$ | $y_6$ | |---|---|---|---|---|---|---|---|---| | $y_3$ | 7 | 50/3 | 5/6 | 0 | 1 | 1/3 | $-1/6$ | 0 | | $y_2$ | 5 | 50/3 | $-1/6$ | 1 | 0 | $-1/6$ | 1/3 | 0 | | $y_6$ | 0 | 100/3 | $-4/3$ | 0 | 0 | $-5/6$ | 1/6 | 1 | | | | $\Delta_j$ | $-3$ | 0 | 0 | $-3/2$ | $-1/2$ | 0 |

All $\Delta_j \leq 0$ But $y_6$ still appears.

So $x_1 = 0$, $x_2 = \frac{50}{3}$, $x_3 = \frac{50}{3}$

$Z = 200$