USA: +1-585-535-1023

UK: +44-208-133-5697

AUS: +61-280-07-5697

DUAL SIMPLEX METHOD

The basic difference between the regular Simplex Method and the Dual Simplex Method is that whereas the regular Simplex Method starts with basic feasible solution, which is not optimal and it works towards optimality, the dual Simplex Method starts with an infeasible solution which is optimal and works towards feasibility. The following steps are involved in this method.

Step I. Convert the problem into a maximisation problem, if initially it is a minimisation problem.

Step II. If there are any ≥ type constraints, these must be converted into ~ type constraints by multiplying both sides by – 1.

Step III. Obtain the initial basic solution – For this, the inequality constraints have to be converted into equality by adding slack variables. Make a dual Simplex table by putting this information in the form of a table.

Step IV. Compute Cj – Zj for each column.

a)     If all Cj – Zj are negative or zero and all solution values are non-negative, the solution found above is the optimum basic feasible solution.

b)    If all Cj – Zj are negative and zero and at least one value of ‘solution value’ is negative then proceed to next step i.e. step V.

c)     If any Cj – Zj is positive, this method cannot be applied.

Step V. Select the row that contains the most negative ‘solution value’. This row is called the key row or the pivot row. The corresponding basic variable leaves the current solution.

Step VI. Scrutinise the elements of the key row.

a)     If all elements are non-negative, the problem does not have a feasible solution.

b)    If at least one element is negative, find the ratios of corresponding elements of Cj _ Zj row to there elements, ignoring the ratios associated with positive or zero elements of the key row. Select the smallest of these rows. The corresponding column is the key column and the associated variable is the entering variable. Mark (circle) the key element or pivot element.

Step VII. Make the key element unity (1). Carry out the row operations as is done in the regular Simplex Method and repeat until

a)     An optimal feasible solution is obtained in a finite number of steps or,

b)    An indication of non-existence of feasible solution is found,

Example 4.15. Minimise Z = 50x1 + 250 x2

Subject to 2 x1 + 20 x2 ≥ 120

5x1 + 10 x2 ≥ 70

5 x1+10 x2 ≥ 80

x1, x2 ≥   0

Solve the problem by Simplex Method using primal and dual and see if the result obtained is the same. Sol. The LPP given above can be converted into the following form by introducing the surplus variables and artificial variables.

Minimise Z = 50 x1 + 250 x2 + 0S1 + 0S2 + 0S3 + MA1 + MA2 + MA3

2x1 + 20 x2– S1 + 0S2 + 0S3 + A1 + 0A2 + 0A3 = 120

5 x1 + 10 x2 + 0S1 – S2 + 0S3 + 0A1 + A2 + 0A3 = 70

x1, + 10 x2 + 0S1 + 0S2 – S3 + 0A1 + 0A2 + A3 = 80

x1,x2 ,S1, S2, S3, A1, A2, A3 ≥ 0

where S1, S2, S3 are the surplus variables and A1, A2, A3 are the artificial variables.

For solving this problem with Simplex Method, let us construct the initial simplex table.

Initial Simplex Table

Cj

Cj

50

250

0

0

0

M

M

M

M in ratio

Basic variables

Solution variables

x1

x2

S1

S2

S3

A1

A2

A3

M

A1

120

2

20

-1

0

0

1

0

0

6

M

A2

70

5

10

0

-1

0

0

1

0

7

M

A3

80

8

10

0

0

-1

0

0

1

8

Zj

270 M

15M

40M

-M

-M

-M

M

M

M

(Cj-Zj)

50-15M

250-40M

M

M

M

0

0

0

Putting x1 = x2=0, S1 =-1. S2=7. S3=-10 and S4=3

Cj

Cj

-3

-2

0

0

0

0

Basic Variable

Solution Value

x1

x2

S1

S2

S3

S4

0

S1

-1

-1

-1

1

0

0

0

0

S2

7

1

1

0

1

0

0

0

S3

-10

-1

-2

0

0

1

0

0

S4

3

0

1

0

0

0

1

Zj

0

0

0

0

0

0

0

(Cj-Zj)

-3

-2

0

0

0

0

 

selecting the row with most negative solution value i.e. – 10, this is the key row. To find the key column.

Selecting the smaller of these ratios i.e. x2 is the key column and – 2 is the key element and – 2 is the key, element (circled). Row S3 is to be replaced by x2. Value of x2 elements is obtained by dividing the row by key element i.e. – 2. Hence the row x2 (earlier S3) is 5, ½ , 1, 0, 0, -½ , 0.

New row values of S1, S2 and S4 can be determined by using the relationship.

New row element = (Element in old row) – [(Intersectional element in old row) × (Corresponding element in replacing row)

Element Solution value = – 1-(- 1 × 5) = – 1 + 5 = 4

Key element -½  is marked with a circle -½  in the table.

Row S4 is to be replaced by x1 All elements of S4 are divided by the key element (- ½) out these elements of new x1 row i.e. 4, 1,0,0,0, – 1, – 2.

These values can be placed in the table to determine whether it turns out to be a feasible solution or not.

Cj

Cj

-3

-2

0

0

0

0

Basic Variables

Solution Variable

x1

x2

S1

S2

S3

S4

0

S1

6

0

0

1

0

1

-1

0

S2

0

0

0

0

1

1

1

-2

x2

3

0

1

0

0

0

1

-3

x1

4

1

0

0

0

-1

-2

Zj

-18

-3

-2

0

0

3

4

(Cj-Zj)

0

0

0

0

-3

-4

 

Since all the Cj – Zj values are either zero or – ve this is the optimal feasible solution or not.

x1 =4, x2 = 3

zmax = – 3 × 4 – 2 × 3 = – 18

Step III. Add slack variables S1, S2, S3 in the constraints. The problem can now be rewritten as

Maximise K = – 2 x1 – 2 x2 – 4 x2 + S1 + 0S2 + 0S3

Subject to the constraints

– 2x1– 3 x2 – 5 x3 + S1 = – 2

3 x1 + x2 + 7 x3 + S2 = 3

x1 + 4 x2 + 6 x3 + S3 = 5

where x1, x2, x3, S1, S2 and S3  0

Putting x1 = x2 = x3 = 0 the vertical basic infeasible solution is S1 = – 2, S2 = 3, S3 = 5

This information is written in the following table.

First Infeasible Solution

Cj

Cj

-2

-2

-4

0

0

0

Basic Variables

Solution Variable

x1

x2

x3

S1

S2

S3

0

S1

-2

-2

-3

-5

1

0

0

0

S2

3

3

1

7

0

1

0

0

S3

5

1

4

6

0

0

1

Zj

0

0

0

0

0

0

0

(Cj-Zj)

-2

-2

-4

0

0

0

 

Step IV. Since Cj – Zj are either 0 or – ve and solution variable is _ ve the solution is optimal but infeasible. Hence we proceed to step V.

Step V. The row containing the most negative solution variable is S1, hence it is the key row and S1 is the row to be replaced.

We have eave 1, 2/3, 4/5 ratios only since 2/3 is the smallest ratio x2 is the variable replacing S1 and key element is -3 circled in the table.

Step VII. Make the key element unity and find the new values of S2 and S3 by using the following relationship.

New element = Old row element – [(Intersectional element in old row) × (Corresponding element in replacing row)]

By making key element unity the new values of row S1 (to be replaced by x2) are 2/3, 2/3, 1, 5/3, -1/3, 0, 0.

Step I. Convert the minimisation problem into a maximisation problem

Minimise Z = – 2y1 + 3 y2 + 5 y3

or Maximise Z* = 2 y1 – 3 y2 – 5 y3

Step II. Make RHS of the constraints positive

The second constraint becomes 2 y1 + 4 y2 – y3 ≤ 2

Step III. Make the problem as N + S coordinate problem.

Introducing slack and artificial variables

Maximise Z** = 2 y1 – 3 y2 – 5 y3 + 0S1 + 0S2 + 0S3 – MA1 – MA3

Subject to – 2 y1 – 3 y2 – S1 + A1 = 5

2 y1 + 4 y2 – y3 + S2 = 2

y1 + 3 y3 – S3 + A3 = 3

y1, y2, y3, S1, S2, S3, A1, A3 ≥ 0

S2 is the key row, y2 the key column and (4) is the key element S2 is the departing row and y2 is the entering variable.

Step V. Optimality Test. Cj – Zj is + ve in same column, the solution is not optimal. New elements of y2 are obtained by dividing the whole row by 4.

New elements of A, row are obtained using the relationship.

New element = Old row element – [(intersectional element in old row) × (Corresponding element in replacing row)]

S3 = 0 – [- 3 × 0] = 0

A1 = 1 – [- 3 × 0] = 1

A3 = 0 – [- 3 x 0] = 0

Element y1 = 1, y2=0, y3=3, S1=0, S2=0, S3=-1, A1=0, A3=1.

Iterating thrice we get

Optimality Test

The above is the optimal basic feasible solution, since all values of Cj – Zj are either 0 or – ve.