Question

Use Big. M Method to solve the following L.P.P.

Max Z = 3x₁ + 2x₂

S.T.

2x₁ + x₂ ≤ 2

3x₁ + 4x₂ ≥ 12

x₁, x₂ ≥ 0

Answer 1

Express the problem into standard form by introducing slack variables, surplus variable and artificial variable, we have

Max Z = 3x₁ + 2x₂ + 0S₁ + 0S₂ – MA₁

S.T.

2x₁ + x₂ + S₁ = 2

3x₁ + 4x₂ – S₂ + A₁ = 12

x₁, x₂, S₁, S2, A₁ ≥ 0

The initial basic feasible solution is given by

x₁ = x₂ = 0, S₁ = 2, A₁ = 12

Now solve the above L.P.P. by general simplex method. Form the initial simplex table.

Initial simplex table

Here, all the values of Z_j – C_j are not positive hence, optimality condition of simplex method is not satisfied. To find the optimum solution, select the most negative number of Z_j – C_j. Here –4M – 2 is the most negative number. Corresponding column is treated as key column. To find key row, find min \(\left(\frac{X_B}{x_2}\right) = \min \left(\frac{2}{1}, \frac{12}4\right) = (2, 3) = 2\).

1 is key element. Therefore, S1 will leave the basis. Make all elements of key column zero by applying matrix row transformation. i.e., R₂ → R₂ – 4R₁.

Now we have the first simplex tab

First simplex table

Here, all values of Z_j – C_j ≥ 0. Hence, optimality condition of simplex method is satisfied. Also one artificial variable appears in the optimum basis at positive level, therefore the given L·P·P. will have no feasible solution.