Question

Solve the following L.P.P. using Big. M. method.

Min Z = x₁ + x₂

S.T.

2x₁ + x₂ ≥ 4

x₁ + 7x₂ ≥ 7

x₁, x₂ ≥ 0

Answer 1

First convert the problem into maximization form and introducing the surplus variables and artificial variable to convert the problem in standard form.

Max Z = –x₁ – 4x₂ + 0S₁ + 0S₂ – MA₁ – MA₂

S.T.

2x₁ + x₂ – S₁ + A₁ = 4

x₁ + 7x₂ – S₂ + A₂ = 7

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

The initial solution is given by

x₁ = x₂ = 0, A₁ = 4, A₂ = 7.

Now prepare the initial simplex table.

Initial simplex table

Here, all the values of Z_j – C_j are not positive. Therefore, solution is not optimum. To find optimum solution, select the most negative value of Z_j – C_j . Here, Z₂ – C₂ = –8M – 4 is the most negative value. It will enter in the basis and corresponding column is treated as key column. Find key row by taking min \(\left(\frac{X_B}{x_2}\right) = \min \left(\frac 41, \frac 77\right)\) = min (4, 1) = 1.

Artificial variable A₂ will leave the basis. 7 is treated as key element. Make it unity and other element of key column to zero by applying matrix row transformation.

First simplex table

Here, all values of Z_j – C_j are not positive.

Optimality condition is not satisfied. Now

R₁ →  7/13 R₁ and then taking

R₂ → R₂ – 1/7 R₁, we have second simplex table.

Second simplex table

Here all the values of Z_j – C_j are positive and no artificial variable appears in optimum basis. Therefore, the required solution is given by

x₁ = \(\frac{21}{13}\), x₂ = \(\frac{10}{13}\), and min Z = \(\frac{82}{13}\)