Big M Method (Penalty Method):
Big M method (i.e. penalty method) is the method based on the Simplex Method with slight changes in it, it uses the Artificial Variables along with the slack variables, Which helps us to solve the problem with ease. But there is another variable which is ‘Artificial variable’.
The iterative process for this method is as follows:
- Write the given LPP into its standard form, & if there exist already a solution then, go to step 4, but if, there does not exist any solution, then follow next step.
- Add slack variables to convert inequalities into equations. Assign a high penalty variable(M) to these variables in the objective function.
- One important thing is, if the problem is to maximize, then the artificial variable (M) taken to be negative if the problem is of minimizing then, the artificial variable taken is positive.
- Apply Simplex method to the modified LPP Following cases may arise.
- At least one artificial variable is present in the basis with zero value. then, the optimum feasible solution is degenerate.
- If there is at least one artificial variable in the basis with positive value, then, that LPP does not possess an optimum basic feasible solution.
Let us consider one example of simplex method to understand the topic.
Subject to: 2x1+3x2=30
3x1+2x2 = 24 & x1+x2 = 3
Solution: By introducing slack variables s1, s2, s3 & the artificial variables the given LPP takes the form:
Subject to: 2x1+3x2+s1=30
3x1+2x2+s2 = 24 & x1+x2-s3+R = 3
where, s1, s2, s3, x1, x2 =0
Now, we form initial simplex table:
(1) Initial Simplex Table:
(2) First Simplex Table:
(3) Second Simplex Table:
Here, all Cj-Zj =0. Hence, we deduce that the optimality reached here.
So, We get the solution,
Substituting these values of x1& x2 in the objective function,
We get the solution from above example that , The Maximum value of given function using big M method, comes out to be Z=48