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. Let’s look at the revised simplex method in this article, with an example.

Introduction to Revised Simplex Method

When using the regular simplex approach to solve a linear programming problem on a digital computer, the full simplex table must be stored in the computer table’s memory, which may not be possible for particularly big problems. However, each iteration must include the calculation of each table. The revised simplex method, which is a variation of the original approach, uses fewer computer resources since it computes and maintains only the data that is currently needed for testing and/or improving the current solution. To put it another way, it only requires a small amount of effort. i.e.,

• The non-basic variable that reaches the basis is determined using the net evaluation row Δj.
• The pivoting column
• To establish the minimal positive ratio, first, identify the present basis variables and their values (X_B column), and then identify the basis variable to exit the basis.

By using the inverse of the current basis matrix at any iteration, the above information can be directly extracted from the original equations.

Standard Forms of Revised Simplex Method

For the revised simplex method, there are two standard versions.

Standard form-I – In this form, an identity matrix is considered to be obtained after just adding slack variables.

Standard form-II – When artificial variables are required for an identity matrix, the two-phase approach of the ordinary simplex method is applied in a slightly different manner.

Revised Simplex Method Steps

Step 1: Formalize the problem in standard form – I

• Confirm that all b_i ≥ 0.
• Maximization should be the objective function.
• Inequalities are converted to equations using non-negative slack variables.
• The first constraint equation is also treated as the objective function.

Step 2: In the revised simplex form, build the starting table. Using appropriate notation, express the result of step 1 as a matrix.

Step 3: For a₁⁽¹⁾ and a₂⁽¹⁾, Compute Δj.

Step 4: Conduct an optimality test.

Step 5: Determine the X_k column vector.

Step 6: Find the outgoing vector. We’re not supposed to do any calculations for the Z-row.

Step 7: Choose a better solution.

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 = 2x₁ + x₂

Subject to 3x₁ + 4x₂ ≤ 6

6x₁ + x₂ ≤ 3 and x₁, x₂ ≥ 0

Solution:

Given that,

Max Z = 2x₁ + x₂+ 0s₁+ 0s₂

Subject to

3x₁ + 4x₂ + s₁ = 6

6x₁ + x₂ + s₂ = 3

and x₁, x₂, s₁, s₂ ≥ 0

Step 1: State the given problem clearly in standard form – I

Z – 2x₁ – x₂ + 0s₁ + 0s₂ = 0

3x₁ + 4x₂ + s₁ + 0s₂= 6 — (1)

6x₁ + x₂ + 0s₁ + s₂= 3

and x₁, x₂, s₁, s₂ ≥ 0

Step 2: Construction of starting table

Z’s column vector is commonly denoted by the e₁ matrix B₁, which is usually written as B₁ = [β₀⁽¹⁾, β₁⁽¹⁾, β₂⁽¹⁾ … β_n⁽¹⁾]. As a result, the column β₀⁽¹⁾, β₁⁽¹⁾, β₂⁽¹⁾ forms the basis matrix B₁ (whose inverse B₁^-1 is also B₁)

Step 3 – Estimation of Δ_j for a₁⁽¹⁾ and a₂⁽¹⁾

Δ₁ = first row of B₁^-1 × a₁⁽¹⁾ = 1 × -2 + 0 × 3 + 0 × 6 = -2

Δ₂ = first row of B₁^-1 * a₂⁽¹⁾ = 1 × -1 + 0 × 4 + 0 × 1 = -1

Step 4 – Use the optimality test.

Δ₁ and Δ₂ are both negative. Determine the entering vector by finding the largest negative value.

As a result, the most negative value is Δ₁ = -2. This means that the incoming vector is a₁⁽¹⁾ (x₁).

Step 5 – Determination of the column vector X_k

X_k = B₁ ^-1 * a₁⁽¹⁾

Step 6:

Find the outgoing vector. We’re not supposed to do any calculations for the Z row.

Step 7 – Identifying a better solution

Because e₁ will never change and x₁ will arrive, place it outside the rectangle boundary.

Set the pivot element to 1 and the column elements to 0 for each column.

To begin the second iteration, construct the table.

Δ₄ = 1 × 0 + 0 × 0 + 1/3 × 1 = 1/3

Δ₂ = 1 × -1 + 0 × 4 + ⅓ × 1 = -⅔

Hence, Δ₂ is most negative. As a result, a₂(1) is an incoming vector. Determine the column vector.

Find the outgoing vector.

Estimation of improved solution:

Δ₄ = 1 × 0 + 4/21 × 0 + 5/21 × 1 = 5/21

Δ₃ = 1 × 0 + 4/21 × 1 + 5/21 × 0 = 4/21

Thus, Δ₄ and Δ₃ are positive.

Hence, the optimal solution is Max Z = 13/7, x₁= 2/7, x₂ = 9/7.

Keep visiting BYJU’S – The Learning App and download the app to quickly understand all math concepts.