Dual Simplex Method

Dual Simplex Method:

Steps involved in Dual Simplex Method are as follows:

  1. Write the given linear programming problem in its standard basic feasible solution by adding appropriate slack variables.
    1. If the existing basic solution is feasible ,then use simplex method (using slack variables) to obtain optimum solution.
    2. If the existing solution is infeasible, then the values of basic variables less than or equal to zero, go to next step.
  2. check the optimality of the solution:
    1. If the solution is not optimum then add an artificial constant so that the optimality condition is satisfied.
    2. If the solution is optimum then go to next step.
  3. take the most negative value as the leaving variable & its corresponding row is the key row.
  4. 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.
  5. Reduce the leading element to unity and all other entriesto zero.
  6. Repeat the  process until the optimum solution.

Let us consider one example of simplex method to understand the topic.

Example:

Minimize: z=3x1+x2
Subject to: x1+x2=1
2x1+3x2 = 2  &  x1,x2 = 0

Solution: Converting the minimizing problem into maximizing LPP

Minimize: -z=-3x1-x2
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:

Maximize: -z=-3x1-x2+0s1+0s2
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:

Dual Simplex ex 1
(2) First Simplex Table:

Dual simplex ex. 2
(3) Second Simplex Table:

Dual simplex 3
Here, all Cj-Zj =0. Hence, the optimality reached.
We get the solution,
x1=0, x2=1
z=3(0)=(1)
=1

Maximized Value of Z is 1.

Get detailed knowledge of the remaining methods of operations research … through our posts Big M method, simplex method & Graphical Method