Simplex Method for Minimize Objective

[Home Page]  [Back]  [Content of Contributions]  [Movement: Green Leaf World]

In this article steps of the Simplex Method for solving Linear Programming Problem for Minimizing Objective Function has been explained with the help of an example where all the constraints are of >= type.

 

Minimize Z= 4x1 + 3x2
Subject to,
200x1 + 100x2 >= 4000
   x1 +   2x2 >= 50
 40x1 +  40x2 >= 1400

x1, x2 >= 0

The first step is to convert the inequalities into equalities by subtracting surplus variables s1, s2 and s3 respectively.
 

The resulting equations are,
200x1 + 100x2 -s1 = 4000
   x1 +   2x2 -s2 = 50
 40x1 +  40x2 -s3 = 1400

Now, if we let x1 and x2 are zero, that implies s1= -4000, s2= -50 and s3= -1400 which is not possible as surplus variables cannot be negative. So, we need to set s1= s2= s3= 0 in the initial solution. So, we need to introduce artificial variables A1, A2, A3. We need to assume A1, A2 and A3 are very expensive and say price is M, where M is very large.

So, the LP problem now becomes,

Minimize Z= 4x1 + 3x2 + 0.s1 + 0.s2 + 0.s3 + M.A1 + M.A2 + M.A3
Subject to,

200x1 + 100x2 -s1 + A1 = 4000
   x1 +   2x2 -s2 + A2 = 50
 40x1 +  40x2 -s3 + A3 = 1400

x1, x2, s1, s2, s3, A1, A2, A3 >= 0

In the initial solution, assume that,

x1= x2= s1= s2= s3= 0

Table 1

__________________________________________________________________

Cj                     4    3    0    0    0    M    M    M

------------------------------------------------------------------

   Basic    Solution  x1   x2   s1   s2   s3   A1   A2   A3   Min

   Variable Variable                                        Ratio

CB  B        b(=Xb)                                        

------------------------------------------------------------------

M   A1      4000     200  100   -1   0    0    1    0    0   20←

M   A2        50       1    2    0  -1    0    0    1    0   50

M   A3      1400      40   40    0   0   -1    0    0    1   35

------------------------------------------------------------------

Z=       Zj=⅀(CBi*aij)      241M 142M     -M    -M    -M      M     M      M

(⅀CBi*XBi)       Cj - Zj     4-241M 3-142M    M     M     M      0     0      0

=5450M                            ↑

Key Column  : x1 (Entering)  [ Highest -ve number in Cj - Zj ]
Key Row     : A1 (Departing) [ Lowest Min Ration ]
Key Element : 200

Table 2

__________________________________________________________________

Cj                     4    3    0       0   0   M   M    M

------------------------------------------------------------------

   Basic    Solution  x1   x2   s1       s2 s3  A1  A2   A3   Min

   Variable Variable                                        Ratio

CB  B        b(=Xb)                                        

------------------------------------------------------------------

4   x1        20       1    1   -1       0  0   -   0    0   40

                            2   200

M   A2        30       0    3   -1      -1  0   -   1    0   20←

                            2   200

M   A3       600       0   20   1/5      0 -1   -   0    1   30

------------------------------------------------------------------

Z=       Zj=⅀(CBi*aij)        4    43M+2 39M    1    M    M    -    M      M

(⅀CBi*XBi)                            2     150   50

=630M+80     Cj - Zj     0  1- 43M  1- 39M    1  M    M   -    0      0                                               2       150   50

                                  ↑

Key Column  : x2 (Entering)  [ Highest -ve number in Cj - Zj ]
Key Row     : A2 (Departing) [ Lowest Min Ratio ]
Key Element : 3/2

Table 3

__________________________________________________________________

Cj                     4    3    0      0    0   M  M   M

------------------------------------------------------------------

   Basic    Solution  x1   x2   s1      s2  s3  A1 A2  A3   Min

   Variable Variable                                        Ratio

CB  B        b(=Xb)                                        

------------------------------------------------------------------

4   x1        10       1    0   -1      1/3  0   -  -   0   30

                                300

3   x2        20       0    1   -1     -2/3  0   -  -   0  -Ve

                                300

M   A3       200       0    0   4/15   40/3 -1   -  -   1  15←

------------------------------------------------------------------

Z=       Zj=⅀(CBi*aij)       4           3     4M -  7        40M -  2      -M                     M  

(⅀CBi*XBi)                                 15  300    3    3  

 =200M+100     Cj - Zj       0      0  -4M +  7       -40M +  2     M                    0 

                                                                 15   300    3     3  

                                                  ↑

Key Column  : s2 (Entering)  [ Highest -ve number in Cj - Zj ]
Key Row     : A3 (Departing) [ Lowest Min Ratio ]
Key Element : 40/3

Note: Ignore the row if -ve min ratio found in the calculation of key row.

Table 4

__________________________________________________________________

Cj                     4    3    0      0    0    M  M   M

------------------------------------------------------------------

   Basic    Solution  x1   x2   s1      s2  s3   A1 A2  A3  

   Variable Variable                                       

CB  B        b(=Xb)                                        

------------------------------------------------------------------

4   x1         5       1    0   -1       0  1/40  -  -   - 

                                100

3   x2        30       0    1    1       0  -1    -  -   - 

                                100          20

0   s2        15       0    0   1/50     1 -3/40  -  -   - ------------------------------------------------------------------

Z=       Zj=⅀(CBi*aij)       4    3   -1/100   0  -1/20 

(⅀CBi*XBi)                    

 =110     Cj - Zj             0    0    1/100   0   1/20

                                           

Observe that,

1. All the artificial variables are reduced to zero(0), i.e. non-basic variables.
2. All the entries in index row(Cj - Zj) are >= 0, implies no further reduction in cost is possible.

So, the optimal soultion is,

x1= 5,

x2= 30

with Z= 110