Simplex Method for Maximize Objective(Mix Constraints)

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

In this article formulation(reconstruction) of the problem  has been shown for solving Linear Programming Problem using the Simplex Method for Maximizing Objective Function with the help of some examples with mix constraints type.

Example 01

Consider the problem,
Maximize Z= 40000x1 + 55000x2
Subject to,
1000x1 + 1500x2 <= 20000
    x1          <= 12
             x2 >= 5
         x1, x2 >= 0

Can be reduced to,
Maximize Z= 40000x1 + 55000x2
Subject to,
2x1 + 3x2 <= 40
 x1       <= 12
      -x2 <= -5
   x1, x2 >= 0
Now, it becomes all constraints of the type <=

After converting all the in-equations as equations by introducing the slack variables we can rewrite the problem as,
Maximize Z= 40000x1 + 55000x2 + 0.s1 + 0.s2 + 0.s3
Subject to,
2x1 + 3x2 +s1 = 40
 x1       +s2 = 12
      -x2 +s3 = -5
x1, x2, s1, s2, s3 >= 0

Now solve it using previous method with the initial solution x1= x2= x2= 0, So, s1=40, s2= 12, s3= -5, as explained earlier.

[ Solution: x1= 12, x2= 16/3, Z= 2320000/3 ]

 

Example 02

Consider the problem,
Maximize Z= 50x1 + 75x2
Subject to,
1.2x1 + 1.6x2 <= 1600
0.8x1 + 0.9x2 <= 700
0.2x1 + 0.2x2 <= 300
   x1         >= 150
           x2 >= 90

The problem can be rewritten after simplification as
Maximize Z= 50x1 + 75x2
Subject to,
12x1 + 16x2 <= 16000
 8x1 +  9x2 <= 7000
 2x1 +  2x2 <= 3000
   x1       >= 150
         x2 >= 90

The problem can be again rewritten after further simplification as
Maximize Z= 50x1 + 75x2
Subject to,
3x1 + 4x2 <= 4000
8x1 + 9x2 <= 7000
 x1 +  x2 <= 1500
 x1       >= 150
       x2 >= 90

Let, x1= u1+150 and x2= u2+90, with u1,u2>=0
Replacing the value of x1 and x2 in the problem we get,
Maximize Z= 50(u1+150) + 75(u2+90)
Subject to,
3(u1+150) + 4(u2+90) <= 4000
8(u1+150) + 9(u2+90) <= 7000
 (u1+150) +  (u2+90) <= 1500
             u1, u2  >= 0

Again, simplifying we get,
Maximize Z= 50u1 + 75u2 + 14250
Subject to,
3u1 + 4u2 +  810 <= 4000
8u1 + 9u2 + 2010 <= 7000
 u1 +  u2 +  240 <= 1500
          u1, u2 >= 0

Subtracting constant part from both side of the constrains we get,
Maximize Z= 50u1 + 75u2 + 14250
Subject to,
3u1 + 4u2 <= 3190
8u1 + 9u2 <= 4990
 u1 +  u2 <= 1260
   u1, u2 >= 0

Adding slack variables the problem becomes,
Maximize Z= 50u1 + 75u2 + 14250 + 0.s1 + 0.s2 + 0.s3
Subject to,
3u1 + 4u2 + s1 = 3190
8u1 + 9u2 + s2 = 4990
 u1 +  u2 + s3 = 1260
   u1, u2 >= 0

Now solve it using previous method explained earlier, with the initial solution u1= u2= 0, So, s1=3190, s2= 4990, s3= 1260.

[ Solution: u1= 0, u2= 554.4, So, x1= 150, x2= 644.4, Z= 55830 ]

 

Example 03

Consider the problem,
Maximize Z= 4x1 + 5x2 - 3x3
Subject to,
 x1 +  x2 + x3  = 10
 x1 -  x2      >= 1
2x1 + 3x2 + x3 <= 30
    x1, x2, x3 >= 0

The problem can be re-written as,
Maximize Z= 4x1 + 5x2 - 3x3 + 0.s1 + 0.s2 - M.A1 - M.A2
Subject to,
 x1 +  x2 + x3      + A1    = 10
 x1 -  x2      - s1 + A2    = 1
2x1 + 3x2 + x3 + s2         = 30
x1, x2, x3, s1, s2, A1, A2 >= 0


Now solve it using previous method explained earlier, with the initial solution x1= x2= x3= s1= 0, So, A1= 10, A2= 1 and s2= 30.



Note That, the following steps may be followed:

1. Create the initial table
2. Find Zj using the formula ⅀(CBi*aij) 
3. Find Cj - Zj
4. If all the values in  Cj - Zj are <= 0, then, there are no chance of further improvement in the maximization. So, Stop else, proceed to next step.  
5. Select the Largest +ve Value among all (Cj - Zj )  to find the Key column(Xi) and entering variable.
6. Find the minimum ration among all XB/Xi, to identify the key row & departing variable. Ignore if there are any -ve value in min ration column.
7. The intersection of key row & key column is the key element(pivot).
8. Place entering variable(Xi) by replacing Departing variable.
9. Put the Cj value of (Xi) under CB of newly entered variable(Xi).
10. Multiply the Key row by 1/key element to make the pivot(key element) 1.
11. For each remaining row i perform Rowi = Rowi - Key Row*aik, where Xk is the key column.
12. Again start computation  from step 2.