Dual Simplex Method:
Steps involved in Dual Simplex Method are as follows:
- Write the given linear programming problem in its standard basic feasible solution by adding appropriate slack variables.
- If the existing basic solution is feasible ,then use simplex method (using slack variables) to obtain optimum solution.
- If the existing solution is infeasible, then the values of basic variables less than or equal to zero, go to next step.
- check the optimality of the solution:
- If the solution is not optimum then add an artificial constant so that the optimality condition is satisfied.
- If the solution is optimum then go to next step.
- take the most negative value as the leaving variable & its corresponding row is the key row.
- Obtain the ratio of net evaluation to the corresponding coefficient in the key row. leave those with positive & zero denominators.the entering has the smallest value of ratio column corresponding to entering vector is the key column.
- Reduce the leading element to unity and all other entriesto zero.
- Repeat the process until the optimum solution.
Let us consider one example of simplex method to understand the topic.
Subject to: x1+x2=1
2x1+3x2 = 2 & x1,x2 = 0
Solution: Converting the minimizing problem into maximizing LPP
Subject to: -x1– x2=-1
-2x1-3x2 = -2 & x1,x2 = 0
Now introducing slack variables s1, s2, s3 & the artificial variables the given LPP takes the form:
Subject to: -x1-x2+s1=-1
-2x1-3x2+s2 = -2 &
where, s1, s2, x1, x2 =0
Now, we form initial simplex table:
(1) Initial Simplex Table:
(2) First Simplex Table:
(3) Second Simplex Table:
Here, all Cj-Zj =0. Hence, the optimality reached.
We get the solution,
Maximized Value of Z is 1.