LESSON 2. Big M Method - Problems

ARTIFICIAL  VARIABLE TECHNIQUES

You may recall that while introducing the slack and surplus variables, we had assigned a zero cost to them in the objective function. Moreover, the slack variables readily provided the initial basic feasible solution. There are, however, many linear programming problems where slack variables cannot provide such a solution. To solve such linear programming problems, there are two (closely related) methods, viz.,

  • The "big M-method" or the "method of penalties" due to A. Charnes, and

  • "two phase method" due to Dantzig, Orden and Wolfe.

SAMPLE   PROBLEMS

1. Use penalty (or Big  'M') method to

       Minimize  z  = 4xi + 3x2

      subject to the constraints :

                            2x1+ x2  ≥ 10,   -3x1, +  2x2  ≤ 6

                            x1 + x2 ≥ 6,   x1 ≥ 0 and x2  ≥ 0.

 Solution. Introducing surplus (negative slack) variables x3  ≥ 0,  x5  ≥ 0 and slack variable x4  ≥ 0 in the constraint inequations, the problem becomes

 Maximize  z*  =  - 4x1 - 3x2 + 0.x3 + 0.x4 + 0.x5

subject to the constraints :

                                    2x1 + x2 - x3 = 10,  - 3x1 + 2x2 + x4 =  6

                                      xl + x2 – x5 =  6,  xj ≥ 0 Q(j = 1,2, 3, 4, 5)

 Clearly, we do not have a ready basic feasible solution. The surplus variables carry negative coefficients (-1). We introduce two new variables A1 ≥ 0 and A2 ≥ 0 in the first and third equations respectively. These extraneous variables, commonly termed as artificial variables, play the same role as that of slack variables in providing a starting basic feasible solution.

 We assign a very high penalty cost (say -M, M ≥ 0) to these variables in the objective function so that they may be driven to zero while reaching optimality.

 Now the following initial basic feasible solution is available :

                                         Al = 10, x4 = 6   and A2 =  6

 with B = (a6 , a4, a7) as the basis matrix. The cost matrix corresponding to basic feasible solution is cB = ( -M, 0, -M )

 Now, corresponding to the basic variables A1, x4 and A2. the matrix Y = B-1A and the net evaluations zj - cj (j = 1, 2, .... 7) are computed. The initial basic feasible solution is displayed in the following simplex table :

We observe that the most negative zj - cj is  4 - 3M (= zl – c1). The corresponding column vector y1, therefore, enters the basis. Further, since min.  = 5;  the element y11 (=2) becomes the leading element for the first iteration

First Iteration:   Introduce y2 and drop y7.

 In the above table, we omitted all entries of column vector y6, because the artificial variables Al has left the basis and we would not like it to re-enter in any subsequent iterations.

Now since the most negative (zj—cj) is  z2-c2; the non-basic vector y2 enters the basis. Further, since min   is 2 which occurs for the  element y32 ( = 1/2), the corresponding basis vector y7 leaves the basis and the element  y32 becomes the leading element for the next iteration.

 Final Iteration: Optimum Solution,

 It is clear from the table that all zj - cj are positive. Therefore an optimum basic feasible solution has been attained which is given by

        x1= 4, x2 = 2,  maximum  z = 22.

 2. Maximize z = 3x1, + 2x2   subject to the constraints :

            2x1 + x2  ≤ 2,  3x1 + 4x2  ≥  12, x1, x2  ≥ 0.

 Solution:  

Introducing slack variable x3 ≥ 0,  surplus variable x5 ≥ 0 and an artificial variable A1 ≥ 0, the reformulated L.P.P. can be written as :

Maximize z  = 3x1 + 2x2 + 0.x3 + 0.x4 – MA1

subject to the constraints :

2x1 + x2 + x3 = 2,

3x1 + 4x2 - x4 + A1 = 12

x1, x2, x3, x4 ≥ 0 and A1≥ 0.

An obvious   starting basic feasible solution is :

x3 = 2   and   A1 = 12.

The iterative simplex tables are :

Initial Iteration Introduce y2 and drop y3.

Final Iteration No solution.

 Here the coefficient of M in each zj - cj is non-negative and an artificial vector appears in the basis, not at the zero level. Thus the given L.P.P. does not possess any feasible solution.

Last modified: Wednesday, 7 May 2014, 4:25 AM