M-Method

M Method
In this method also we need artificial variables for determining the initial basic feasible solution. The M method is explained in the next Example.
Example: Use M method to :
Maximize -12.5 x1 – 14.5 x2
Subject to:
x1 + x2 – s3 = 2000
40 x1 + 75 x2 – s4 = 100000
75 x1 + 100 x2 + s5 = 200000
x1, x2, s3, s4, s5 ? 0.
Solution :
Introduce the artificial variables a6 and a7 in order to provide basic feasible solution in the first and second constraints. The objective function is revised using a large positive number say M.
Thus, instead of the original problem, consider the following problem i.e.
Maximize -12.5 x1 – 14.5 x2 – M (a6 + a7)
Subject to:
x1 + x2 – s3 + a6 = 2000
40 x1 + 75 x2 – s4 + a7 = 100000
75 x1 + 100 x2 + s5 = 200000
x1, x2, s3, s4, s5, a6, a7 ? 0.
The coefficient of a6 and a7 are large negative number in the objective function. Since the objective function is to be maximized in the optimum solution, the artificial variables will be zero.
The simplex table is as follows:

Since M is a large positive number, the coefficient of M in the zj – cj row would decide the entering basic variable. As – 76 M < - 41 M, so, x2 becomes a basic variable in the next iteration replacing a7.
The artificial variable a7 can’t be re-entering as basic variable.

Now x1 becomes a basic variable replacing a6. Like a7 the variable a6 also artificial variable so it can’t be re-entering in the table.