System Engineering 3(3+0)

LESSON 1. Artificial Variable Techniques- Big M Method

1.2 Big M method

The Big-M-Method is an alternative method of solving a linear programming problem involving artificial variables. To solve a L.P.P by simplex method, we have to start with the initial basic feasible solution and construct the initial simplex table. In the previous problems we see that the slack variables readily provided the initial basic feasible solution. However, in some problems, the slack variables cannot provide the initial basic feasible solution. In these problems atleast one of the constraint is of = or ≥ type. “Big-M-Method is used to solve such L.P.P.

1.3 ALGORITHM

The Big M-method

The big M-method or the method of penalties consists of the following basic steps :

Step 1:

Express the linear programming problem in the standard form by introducing slack and/or surplus variables, if any.

Step 2:

Introduce non-negative variables to the left hand side of all the constraints of (> or = ) type. These variables are called artificial variables. The purpose of introducing artificial variables is just to obtain an initial basic feasible solution. However, addition of these artificial variables causes violation of the corresponding constraints. Therefore we would like to get rid of these variables and would not allow them to appear in the optimum simplex table. To achieve this, we assign a very large penalty ' — M ' to these artificial variables in the objective function, for maximization objective function.

Step 3:

Solve the modified linear programming problem by simplex method.

At any iteration of the usual simplex method there can arise any one of the following three cases :

(a) There is no vector corresponding to some artificial variable, in the basis y_b.

In such a, case, we proceed to step 4.

(b) There is at least one vector corresponding to some artificial variable, in the basis y_B, at the zero level. That is, the corresponding entry in X_B is zero. Also, the co-efficient of M in each net evaluation Z_j- C_j(j = 1, 2, .... n) is non- negative.

In such a case, the current basic feasible solution is a degenerate one. This is a case when an optimum solution to the given L.P.P. includes an artificial basic variable and an optimum basic feasible solution still exists.

(c) At least one artificial vector is in the basis y_B, but not at the zero level. That is, the corresponding entry in X_B is non-zero. Also coefficient of M in each net evaluation Z_j - C_j is non-negative,

In this case, the given L.P.P. does not possess any feasible solution.

Step 4:

Application of simplex method is continued until either an optimum basic feasible solution is obtained or there is an indication of the existence of an unbounded solution to the given L.P.P.

Note. While applying simplex method, whenever a vector corresponding to some artificial variable happens to leave the basis, we drop that vector and omit all the entries corresponding to its column from the simplex table.

Example:

Maximize z = x₁ + 5x₂

Subject to

3x₁ + 4x₂ ≤  6
  x₁ + 3x₂ ≤ 2

x₁, x₂ ≥ 0

Solution:

Converting inequalities to equalities

       By introducing surplus variables, slack variables and artificial variables, the standard form of LPP becomes

 Maximize x₁ + 5x₂ + 0x₃ + 0x₄ – MA₁

Subject to

3x₁ + 4x₂ + x₃ = 6
x₁ + 3x₂ – x₄ + A₁ = 2

x₁ ≥  0, x₂ ≥  0, x₃ ≥  0, x₄ ≥ 0, A₁≥  0

where,

x₃ is a slack variable
x₄ is a surplus variable
A₁ is an artificial variable.

 Initial basic feasible solution

                     x₁ = x₂ = x₄ = 0, A₁ = 2, x₃ = 6

Iteration 1:

	cj	1	5	0	0	–M
cB	Basic variables B	x1	x2	x3	x4	A1	Solution values b (= XB)
0	x3	3	4	1	0	0	6
–M	A1	1	3	0	–1	1	2
zj–cj		–M–1	–3M–5	0	M	0

 

Calculating values for index row (z_j – c_j)

z₁ – c₁ = 0 × 3 + (–M) × 1 – 1 = –M – 1
z₂ – c₂ = 0 × 4 + (–M) × 3 – 5 = –3M – 5
z₃ – c₃ = 0 × 1 + (–M) × 0 – 0 = 0
z₄ – c₄ = 0 × 0 + (–M) × (–1) – 0 = M
z₅ – c₅ = 0 × 0 + (–M) × 1 – (–M) = 0

As M is a large positive number, the coefficient of M in the z_j–c_j row would decide the incoming basic variable.
As -3M < -M, x₂ becomes a basic variable in the next iteration.
Key column = x₂ column.
Minimum (6/4, 2/3) = 2/3
Key row = A1 row
Pivot element = 3.
A1 departs and x₂ enters.

Note: The iteration just completed, artificial variable A₁ was eliminated from the basis. The new solution is shown in the following table.

Iteration 2:

	cj	1	5	0	0
cB	Basic variables B	x1	x2	x3	x4	Solution values b (= XB)
0	x3	5/3	0	1	4/3	10/3
5	x2	1/3	1	0	–1/3	2/3
zj–cj		2/3	0	0	–5/3

 

 Iteration 3:

	cj	1	5	0	0
cB	Basic variables B	x1	x2	x3	x4	Solution values b (= XB)
0	x4	5/4	0	3/4	1	5/2
5	x2	3/4	1	1/4	0	3/2
zj–cj		11/4	0	5/4	0

 

Result:

The optimal solution is x₁ = 0, x₂ = 3/2
                          Max z = 0 + 5 x 3/2 =15/2