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$