Simplex Method for Minimize 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 Minimizing Objective Function with the help of some examples with mix constraints type.

 

Example

Consider the problem,
Minimize Z= 3x1 + 8x2
Subject to,
x1 + x2  = 200

x1      <= 80

     x2 >= 60

x1,  x2 >=0

After converting all the in-equations as equations by introducing the slack and suplus variables we can rewrite the problem as,

Minimize Z= 3x1 + 8x2 + 0.s1 + 0.s2 + M.A1 + M.A2
Subject to,
x1 + x2      + A1 = 200

x1      + s1      = 80

     x2 - s2 + A2 = 60

x1,  x2 >=0

The initial solution can be obtained by assuming,

x1= x2= s2= 0

So, 

A1= 200

s1= 80

A2= 60

Note That, the following steps may be followed to solve the LP problem:

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 minimization. So, Stop else, proceed to next step.  
5. Select the Smallest Value among all (Cj - Zj) which are -ve  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 corresponding to 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.