USA: +1-585-535-1023

UK: +44-208-133-5697

AUS: +61-280-07-5697

Revised Simplex Method (RSM)

I. Algorithm

Step 1. Write the standard form of the given LPP and convert it into maximization type if it is in minimization type i.e.,

Max. z =ex

S/t, Ax= b, x ≥  0.

Use the following notations :

 

c T = [c1, c2, . ... , cn] Profit coefficients.

 

Columns of A as A1 A2, .... , Am.

 

π = (π1, π2,…..) Simplex multipliers

xB = Basis vector

cBT = Profit coefficient in the basis

B = Basis matrix, B- 1 = Basis inverse

cj = Net evaluations, j = Index of non-basic variables

b = Current BFS

 

 

Step 2. For Iteration

 

else for other iterations

 

Find

 

Step 3. Calculate

 

 

Decisions : If all cj ≥ 0 then the current BFS is optimal, else

 

select the negative most of cj, say ck. Then xk will be the 'Entering Variable' and Ak = key column = B-1.Ak

 

Step 4. Produce the following revised simplex table :

Encircle the key element obtained from the min. ratio {[b]/[Key column]}.

 

Element corresponding to the key element will depart from [ xa].

 

Step 5. Go to step 2.

Repeat the procedure until optimal BFS is obtained.

 

Note.   (a) If, in step 4, all the elements in the key column are non-positive, then the given problem is unbounded.

(b) If, in the optimal BFS, artificial variables (if any) take zero value then the solution is degenerate else, for non-zero value, the given problem is said to be infeasible.

 

II. Advantages

 

In computational point of view, the Revised Simplex Method is superior than ordinary simplex method. Due to selected column calculations in revised simplex method, less memory is required in computer. Whereas the ordinary simplex method requires more memory space in computer.

 

Example 13. Using revised simplex method solve the following LPP :

Maximize z = 5x1 + 2x2 + 3x3

Sit,       x 1 + 2x2 + 2x38

3x1 + 4x2 + x3 ≤ 7

XI' x2, x3 ≥ 0.

 

Solution. Standard form of the given LPP is

Max. z = 5x1 + 2x2 + 3x3 + O.s1 + O.s2

S/t, x1 + 2x2 + 2x3 + S 1 = 8

Let us consider the index of the variables x1 be 1, x2 be 2, x3 be 3, s1 be 4, s2 be 5.

 

Iteration 1.

Net evaluations :

c1 = π A1 - c1 = - 5  negative most and entering variable is x1

c2 = π A2 - c2 = - 2

c3 = π A3 - c3 = - 3.

Key colunm:  = B-1.A1 =

Table 1

This indicates the departing variable as s2.

Iteration 2.

Net evaluations :

Table 2

(This indicates the departing variable as s 1).

Iteration 3.

Net evaluations :