USA: +1-585-535-1023

UK: +44-208-133-5697

AUS: +61-280-07-5697

REVISED SIMPLEX METHOD

We have seen how complex and cumbersome the iterating process in the Simplex Method can be. Every time a variable departs and new variable enters, complicated calculations requiring large space (and computer memory) have to be performed to get the new element values. Successive iteration are done by using number of row operations as has been discussed earlier. If a LPP with large number of variables and
constraints (which is in real life problem the solution will be) has to be solved by the Simplex Method, it will need a lot of time and computer space as all the tables and data will have to be stored and retrieved again and again.

However, there are methods available where the entire table does not have to be calculated during every iteration. The information required while constructing a new table is (a) Cj – Zj value, the key column and the current basic variables and their values (or the solution value constants). This information can be directly obtained by using certain properties of the matrix. The following methods have been developed which make the computations much easier and simpler :-

(a)             The revised Simplex Method.

(b)             The bounded variables method and

(c)             The decomposition method .

The student is advised to go through the basics of matrix operation as given in the appendix of this book.

Example 4.19. Maximise Z = 5x1 + 2 x2 + 3 x2 – 2 x4 + x5

Subject to 3 x1 + 2 x2 + 3 x3 + x4 = 12

x1 + 3x2 + x3 + x5 = 10

x1, x2, x3, x4, x5 ≥ 0

Sol. To find the basic feasible solution (non-optimal), put x1 = x2 = x3 = 0.

x4 = 12,

x5 = 10.

 

New value of x5 element which is to be replaced by x1 variables are 5, 1,3, 1,0, 1.

New values of x4 element are

Solution value = 12 – [3 × 5] = – 3

element x1 = 3 – [3 × 1] = 0

element x2 = 2 – [3 × 3] = – 7

element x3 = 3 – [3 × 1] = 0

element x4 = 1 – [3 × 0] = 1

element x5 =0-[3 × 1]=-3

x1 = 5,

x2 = x2 = x5 = 0,

x4 = – 2,

Zmax = 31

The revised simplex method uses matrix-vector operations to directly obtain the basic feasible solution from the original equations.

We denote the column vector P1, P2, P3, P4, P5 to represent x1, x2, x3, x4 and x5 and let the column vector b represent the right hand side constraints i.e., solution values. From the original equation of constraints.

SOME MORE DUALITY PROBLEMS

Example 4.20. Solve the following LPP with the help of Duality.

Min Z = 2x1 + 2 x2

Subject to 2 x1 + 4 x1 ≥ 1

x1 + 2 x1 ≥ 1

2 x1 + x2 ≥ 1

Sol. The dual of the given problem is

Maxirnise Z = a + b + c

Subject to 2a + b + c ≤ 2

4a + 2b + c ≤ 2

As the problem is now of maximisation, we will introduce slack variables.

Maximise Z = a + b + c + 0S1 + 0S2 + 0S3

Subject to 2a + b + c + S1 + 0S2 = 2

4a + b + c + 0S1 + S2 = 2

The Simplex table can be written as follows

Cj

1

1

1

0

0

Min Ratio

Basic Variables

Solution Values

a

b

c

S1

S2

0

S1

2

2

1

2

1

0

0

S2

2

4

2

1

0

1

Zj

0

0

0

0

0

0

(Cj-Zj)

1

1

1

0

0

 

Since all the values of (Cj – Zj) are equal i.e. 1, 1, 1 we can take anyone as the entering variable by taking it as key column. Let us take column C. S1 is the key row and (2) is the key element.

New value of C row (old S1) will be obtained by dividing by key element i.e. 2.

So the new elements are 1, 1, ½ , 1, ½ , 0.

Sol. Multiply the objective function (Z) and the constraints by – 1 and introduce slack variables in order to convert it into equalities as there are two constraints, two slack variables will be introduced.

Maximise Z = – 4x1– 6 x2 – 18 x3 + 0S1 + 0S2

Subject to constraints

– x1 +0 x2 – 3 x3 + S1 + 0S2 =- 3

0 x1 – x2 – 2 x3 + 0S1 + S2 = – 5

x1, x2, x3, S1, S2 ≥ 0

New elements are 5, 0, 1 , 2, 0, – 1.

New elements of row S1 are obtained by the relationship already known.

These are – 3 – 0 × 5 = – 3. All these elements will remain the same.

New row x3 (old S1) will be obtained by dividing old S1 row by – 3 i.e. 1, 1/3, 0, 1, -1/3, 0.

New x1 row will be obtained by the relationship already known

There is no negative value in the solution value, the optimal solution has been obtained.

x1=0,

x2 =3,

x3 =1,

Zj=-36.

Example 4.22. Solve the following LPP by Dual Simplex

Minimise Z = 6 x1 + 7 x2 + 3 x3 + 5 x4

Subject to 5 x1 + 6 x2 – 3 x3 + 4 x4 ≥ 12

x1+5 x3-6 x4 ≥ 10

2 x1 + 5 x2 + x3 + x4 ≥ 8

x1, x2, x3, x4 ≥  0

Sol. To convert it into a maximisation problem, the objective function and constraints will be multiplied by – 1.

Maximise Z = – 6 x1 – 7 x2– 3 x3 – 5 x4

Subject to – 5 x1 – 6 x2 + 3 x3 – 4 x4 ≤ – 12

– x1 – 5 x3 + 6 x4 ≤ – 10

-2 x1, -5 x2, x3, x4 ≤ -8

x1, x2, x3, x4 ≥ 0

Introducing slack variables, the objective function and constraints can be written as

Max Z = – 6 X1 – 7 X2 – 3 X3 – 5 X4 + 0S1 + 0S2 + 0S3

Subject to – 5 X1 – 6 X2 + 3 X3 – 4 X4 + S1 + 0S2 + 0S3 = – 12

– X2 – 5 X3 + 6 X4 + 0S1 + S1 + 0S3 = – 10

– 2 X1 – 5 X2– X3 – X4 + 0S1 + 0S2 + S3 = – 8

and X1, X2, X3, X4 , S1, S2, S3 ≥ 0

REVIEW

  1. 1.   Discuss in brief ‘Duality’ in linear programming.
  2. 2.   Explain the primal-dual relationships.
  3. 3.   State and explain dual L.P.P.
  4. 4.   Prove that the dual of the dual of a given primal is again primal.
  5. 5.   State the fundamental properties of duality and prove anyone of them.
  6. 6.   If the kth constraint of the primal problem is an equality, then prove that the dual variable
  7. 1.   If the kth constraint of the primal problem is an equality, then prove that the dual variable wk is unrestricted in sign
    1. 1.   If any variable of the primal problems is unrestricted in sign, the corresponding constraint in the dual will be a strict equality. Prove it.
    2. 2.   Slate the dual theorem and explain its implications.
    3. 3.   If either the primal or the dual problem has a finite optimal solution, then the other problem also has finite optimal solution and the values of the two objective functions are equal. Prove this.
    4. 4.   Prove that the necessary and sufficient condition for any linear programming problem and its dual to have an optimal solution is that both have feasible solutions.
    5. 5.   Prove that if the primal has an unbounded solution, the dual has either no solution or an unbounded solution.
    6. 6.   What is the essential difference between regular simplex method and dual simplex method?
    7. 7.   Develop the theory of dual simplex algorithm.
    8. 8.   Write a short note on ‘Complementary Slackness’.
    9. 9.   State and prove the complementary slackness theorem for the symmetrical dual problem
    10. 10. What do you understand by ‘duality’ in linear programming’! State and prove the theorem of dual primal relationships.

  1. 1.   Dual Problem.
  2. 2.   Dual of a Primal.
  3. 3.   Shadow Prices in LPP.
  4. 4.   Concept of Duality in LPP.
  5. 5.   Explain primal-dual relationship.
  6. 6.   Explain the role of duality in Linear Programming and discuss its uses in decision-making.
  7. 7.   Explain the primal-dual relationship. How Dual problem can be useful in management decision making?

  1. 1.   Write the dual of the following L.P. Problem:

Maximize: 6R1 + 2R2