System Engineering 3(3+0)

LESSON 2. Big M Method - Problems

SAMPLE   PROBLEMS

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

       Minimize  z  = 4x_i + 3x₂

      subject to the constraints :

                            2x₁+ x₂  ≥ 10,   -3x₁, +  2x₂  ≤ 6

                            x₁ + x₂ ≥ 6,   x₁ ≥ 0 and x₂  ≥ 0.

 Solution. Introducing surplus (negative slack) variables x₃  ≥ 0,  x₅  ≥ 0 and slack variable x₄  ≥ 0 in the constraint inequations, the problem becomes

 Maximize  z*  =  - 4x₁ - 3x₂ + 0.x₃ + 0.x₄ + 0.x₅

subject to the constraints :

                                    2x₁ + x₂ - x₃ = 10,  - 3x₁ + 2x₂ + x₄ =  6

                                      x_l + x₂ – x₅ =  6,  x_j ≥ 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 A₁ ≥ 0 and A₂ ≥ 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 :

                                         A_l = 10, x₄ = 6   and A₂ =  6

 with B = (a₆ , a₄, a₇) as the basis matrix. The cost matrix corresponding to basic feasible solution is c_B = ( -M, 0, -M )

 Now, corresponding to the basic variables A₁, x₄ and A₂. the matrix Y = B^-1A and the net evaluations z_j - c_j (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 (= z_l – c₁). The corresponding column vector y₁, therefore, enters the basis. Further, since min.  = 5;  the element y₁₁ (=2) becomes the leading element for the first iteration

First Iteration:   Introduce y₂ and drop y₇.

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

Now since the most negative (z_j—c_j) is  z₂-c₂; the non-basic vector y₂ enters the basis. Further, since min   is 2 which occurs for the  element y₃₂ ( = 1/2), the corresponding basis vector y₇ leaves the basis and the element  y₃₂ becomes the leading element for the next iteration.

 Final Iteration: Optimum Solution,

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

        x₁= 4, x₂ = 2,  maximum  z = 22.

 2. Maximize z = 3x₁, + 2x₂   subject to the constraints :

            2x₁ + x₂  ≤ 2,  3x₁ + 4x₂  ≥  12, x₁, x₂  ≥ 0.

 Solution:  

Introducing slack variable x₃ ≥ 0,  surplus variable x₅ ≥ 0 and an artificial variable A₁ ≥ 0, the reformulated L.P.P. can be written as :

Maximize z  = 3x₁ + 2x₂ + 0.x₃ + 0.x₄ – MA₁

subject to the constraints :

2x₁ + x₂ + x₃ = 2,

3x₁ + 4x₂ - x₄ + A₁ = 12

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

An obvious   starting basic feasible solution is :

x3 = 2   and   A₁ = 12.

The iterative simplex tables are :

Initial Iteration:  Introduce y₂ and drop y₃.

Final Iteration.   No solution.

 Here the coefficient of M in each z_j - c_j 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.