USA: +1-585-535-1023

UK: +44-208-133-5697

AUS: +61-280-07-5697

Big M Method

The method is also known as 'penalty method' due to Charnes. If there is ≥ type constraint, we add surplus variable and if there.is '=' type, then the constraint is in equilibrium. Generally, in these cases there may not be any unit matrix in the standard form of the coefficient matrix.

 

To bring unit matrix we take help of another type of variable, known as ' artificial variable'. The addition of artificial v:ariable creates infeasibility in the system which was already in equilibrium. To overcome this, we give a very large number denoted as M to the coefficient of the artificial variable in. the objective function. For maximization problem, we add "- M. (artificial variable)" in the objective function so that the profit comes down. For minimization problem we add "M (artificial variable)" in the objective functions so that the cost goes up. Therefore the simplex method tries to reduce the artificial variable to the zero li:wel so that the feasibility is restored and the objective function is optimized.

 

The only drawback of the big M method is that the value of M is not known but it is a very large number. Therefore we cannot develop computer program for this · method.

 

Note. (a) Once the artificial variable departs from the basis, it will never again enter in the subsequent iterations due to big M. Due to this we drop the artificial variable column in the subsequent iterations once · the variable departs from the basis.

 

(b) If in the optimal table, the artificial variable remains with non-zero value, then the problem is said to be 'infeasible·. ·

 

If the artificial variable remains in the optimal table with zero value, then the solution is said to be 'pseudo optimal'.

 

(c) The rule for 'multiple solution' and 'unbounded solution' are same as given by simplex method. The big-M method is a simple variation of simpiex method.

 

Example 7. Using Big-M method solve the following LPP :

Minimize z = 10x1 + 3x2

Sit, x1 + 2x2 3, x1 + 4x2 4; x1, x2 0

 

Solution. Standard form of the given LPP is

Min. z =- Max. (- 2 = - 10x1 - 3x2 + O.s1 + O.s2 - Ma1 - Ma2)

S/t,  x1  + 2x2 - s 1 + a l = 3

x 1 + 4x2 - s2 + a2 = 4

x1, x2 ≥ 0, s1 , s2 surplus ≥ 0, a1, a2 artificial ≥ 0

 

Iteration 1.

Iteration 2.

Iteration 3.

Iteration 4. (Optimal)

Since all zj - cj  ≥ 0, the current solution is optimal.

 

x1 = 0, x2 =2, z =2.

 

Example 8. Solve the following LPP by Big-M method:

Minimize z = 2x1 + x2 + 3x3

Sit, - 3x1 + x2 - 2x3 ≥ 1, x1 - 2x2 + x3 2; x 1, x2, x3 ≥  0.

 

Solution. The standard form of the given problem can be written as follows :

 

Min. z = - Max. (- z = - 2x1 - x2 - 3x3 + O.s1 + O.s2 - Ma1 - Ma2)

S/t, - 3x 1 + x2 - 2x3 - s 1 + a 1 = 1,

x1 - 2x2 + x3 - s2 + a2 = 2,

x1, x2, x3  ≥ 0, s1 , s2 surplus s ≥  0, a1 , a2 artificial variables ≥ 0.

Iteration 1.

Since all zj - cj ≥0, the first iteration itself give optimal solution. But in solution i.e., a1 = 1, a2 = 2 present with non-zero value. Hence the given problem does not possess any feasible solution.