Topper Copies

Solve the L.P. problem Max. $Z = 6x_1 + 4x_2$ s.t. $2x_1 + 3x_2 \leq 30$ $3x_1 + 2x_2 \leq 24$ $x_1 + x_2 \geq 3$ $x_1, x_2 \geq 0$ Is your answer unique? If not, give 3 different solutions.

Divyank Gupta, AIR 21, 2024

Given: $Z = 6x_1 + 4x_2$ and conditions

adding Slack and Surplus Variables along with artificial Variables we get

$2x_1 + 3x_2 + x_3 = 30$ $3x_1 + 2x_2 + x_4 = 24$ $x_1 + x_2 - x_5 + x_{a_1} = 3$

then by Big M method, we get

$\text{Max } Z = 6x_1 + 4x_2 + 0\cdot x_3 + 0\cdot x_4 + 0\cdot x_5 - M x_{a_1}$

Now the Simplex table would be

Taking $x_3, x_4, [?]_5$ as basic Variables

| B | $C_B$ | $X_B$ | $y_1$ | $y_2$ | $y_3$ | $y_4$ | $y_5$ | $A_1$ | Min Ratio | |---|---|---|---|---|---|---|---|---|---| | $C_j$ | | | 6 | 4 | 0 | 0 | 0 | $-M$ | | | $y_3$ | 0 | 30 | 2 | 3 | 1 | 0 | 0 | 0 | 15 | | $y_4$ | 0 | 24 | 3 | 2 | 0 | 1 | 0 | 0 | 8 | | $A_1$ | $-M$ | 3 | [1] | 1 | 0 | 0 | $-1$ | 1 | 3 | | $\Delta_j$ | | | $6+M$ | $4+M$ | 0 | 0 | $-M$ | 0 | |

| B | $C_B$ | $X_B$ | $y_1$ | $y_2$ | $y_3$ | $y_4$ | $y_5$ | $A_1$ | Min Ratio | |---|---|---|---|---|---|---|---|---|---| | $y_3$ | 0 | 24 | 0 | 1 | 1 | 0 | 2 | $-2$ | 12 | | $y_4$ | 0 | 15 | 0 | $-1$ | 0 | 1 | [3] | $-3$ | 5 | | $y_1$ | 6 | 3 | 1 | 1 | 0 | 0 | $-1$ | 1 | | | $\Delta_j$ | | | 0 | $-2$ | 0 | 0 | 6 | $-M-6$ | |

| B | $C_B$ | $X_B$ | $y_1$ | $y_2$ | $y_3$ | $y_4$ | $y_5$ | $A_1$ | |---|---|---|---|---|---|---|---|---| | $y_3$ | 0 | 14 | 0 | 5/3 | 1 | $-2/3$ | 0 | 0 | | $y_5$ | 0 | 5 | 0 | $-1/3$ | 0 | 1/3 | 1 | $-1$ | | $y_1$ | 6 | 8 | 1 | 2/3 | 0 | 1/3 | 0 | 0 | | $\Delta_j$ | | | 0 | 0 | 0 | $-2$ | 0 | $-M$ |

All $\Delta_j \leq 0$ so the solution is optimal

but $x_2$, doesn't appear in the Solution

So the Solution is not Unique.

Therefore

One solution is $x_1 = 8,\ x_2 = 0$, and $z = 48$

2nd solution $x_1 = 6,\ x_2 = 3$, $z = 48$

3rd Solution $x_1 = 4,\ x_2 = 6$, $z = 48$