Revised Simplex Method

Introduction

The revised simplex method is technically equivalent to the traditional simplex method, but it is implemented differently. It retains a representation of a basis of the matrix containing the constraints, rather than a tableau that directly depicts the constraints scaled to a set of fundamental variables. The revised simplex method was developed by Dantzig, Orchard-Hays, and others at the RAND Corporation as an efficient computational procedure for solving LP problems on digital computers.

Revised Simplex Method Example

To understand the concept of the revised simplex method, look at the example below.

Example:

Solve the problem using the Revised simplex method

Max Z = 2x1 + x2

Subject to

3x1 + 4x2 ≤ 6

6x1 +  x2 ≤ 3

x1,  x2 ≥ 0

Solution:

STEP 01: Standard Form

The standard form is the baseline format for all linear programs before solving the optimal solution

Max Z = 2x1 + x2

Subject to

3x1 + 4x2 + s1 = 6

6x1 + x2 + s2 = 3

x1, x2, s1, s2 ≥ 0

S1 and S2 are Slack Variables.

For convenience let us assume that x1,x2,…,xm be the basic variables and the rest be the non-basic variables. Let B be the basic matrix. That means it contains columns corresponding to the basic variables. The column corresponding to the non-basic variables is denoted by the matrix D. Let us denote CB=(c1,c2,…, cm) t, CD=(cm+1,cm+2,…,cn) t, XB=(x1,x2,…,xm) t and XD=(xm+1,xm+2,…,xn) t

STEP 02: Construct the Initial Simplex Table

•   Each inequality constraint appears in its row.

•   But non-negativity constraints do not appear as rows in the simplex tableau.

•   Write the objective function in the bottom row

Like in the regular simplex method we can put down a table like below and we can put the non-basic variable also in the first column.

Initial Table

STEP 03: Find the Corresponding Matrices and Pivot columns.

Therefore we can denote:

STEP 04: Construct the Iterations.

Table 1

For this table don’t take the last row in the initial table.

First, we put the non-basic variable column, basic variable column, and B-1 column. B-1 is corresponding to the coefficient of basic variables and it is an identity matrix.

In the ordinary simplex method what we do is, out of these non-basic variables (we have  2 &1) we select the largest positive value(2), which we consider as the pivot column(X1 column).After adding the ratio test 6 going to be the pivot element.

After that, we write down the pivot column by multiplying the B-1. Next we put the B-1b  column and ratio column.

Min Ratio = (2 , 0.5) = 0.5

Now pivot the       B-1   and     B-1b columns.

Here B-1a1 corresponds to the X1, so now X1  will come into the basis and  S2  is leaving the basis because 6 is the pivot element.

Now non-basic variable is X2, S2 because we going to X1, X2,… , S1, S2,.. order .

After we pivot B-1   and     B-1b will be updated. This is the first iteration.

Now we need to find out what is the pivot column going to be. We can use CD  - CB * B-1 * D  formula and it will give the last row corresponding to the non-basic variable.

Earlier non-basic variables are X1, X2, and now X2, S2.

Min Ratio = (9/7 , 3) = 9/7

Table 2

Like previous steps, we can find B-1,  B-1b, and also the pivot column.