What is the Revised Simplex Method? – Intro, Python Example

How to Fix "SyntaxError: Can't Assign to Function Call" in Python?

Do you want to learn the revised simplex method and how one can implement it in Python 🤔? Then this article is just for you!

Simplex Method is an algorithm used for solving linear programming issues. It is a powerful tool that can be used to optimize a wide range of real-world problems.

The method was first proposed by George Dantzig in 1947 and is based on the simplex algorithm, a geometric method for solving linear equations. The simplex algorithm is a method for solving linear programming problems by moving from one vertex (or corner point) of a feasible region to another, at each step improving the value of the objective function.

 

 

What is the Revised Simplex Method?

The revised simplex method, also known as the primal-dual simplex method, is a variant of the traditional simplex method for solving linear programming problems. The primary difference between the two methods is that the revised simplex method uses primal and dual solutions during the solution process. In contrast, the traditional simplex method only uses the simple solution.

The revised simplex method is used to solve linear programming problems in canonical form. This form requires that the objective function be a linear function and that all constraints be expressed in the form of linear equations or inequalities. The method begins by finding an initial feasible solution, called the simple solution, which satisfies all constraints. 

The next step is to find the corresponding dual solution, which is the solution to the problem’s dual linear programming problem. So without wasting time, let’s start moving toward the article.

 

 

Why is the Revised Simplex Method More Efficient Than the Traditional Simplex Method?

The revised simplex method is considered to be more efficient than the traditional simplex method because it uses both primal and dual solutions during the solution process. This allows the method to identify the direction of the improvement more quickly, resulting in fewer iterations and faster convergence to the optimal solution.

The revised simplex method also has the ability to solve problems with degenerate solutions. A degenerate solution is a solution where some of the essential variables have a value of zero. The simplex method cannot solve problems with degenerate solutions. Still, the revised simplex method can handle them by using the primal and dual solutions to identify the direction of improvement.

Additionally, the revised simplex method can also solve problems with non-unique solutions. A non-unique solution is a solution where more than one set of essential variables produces the same optimal objective function value. The simplex method can only solve problems with unique solutions. Still, the revised simplex method can handle them by using the primal and dual solutions to identify the direction of improvement.

Overall, the revised simplex method is a more efficient and versatile alternative to the traditional simplex method for solving linear programming problems. Its ability to handle degenerate and non-unique solutions, as well as its use of both primal and dual solutions, makes it a valuable tool for solving a wide range of linear programming problems.

 

 

What Are The Limitations of The Revised Simplex Method?

However, it should be noted that the revised simplex method does have some limitations, such as the requirement for the problem to be in canonical form and the potential for cycling, which is when the method gets stuck in an infinite loop. These limitations should be taken into consideration when deciding if the revised simplex method is the best approach for a specific linear programming problem.

 

 

Libraries Used to Implement Revised Simplex Method in Python

There are several libraries in python that provide implementations of the revised simplex method. The most popular ones are:

  1. scipy.optimize.linprog(): This function in the scipy library provides a simple interface for solving linear programming problems using the revised simplex method. It can be used to solve problems with both equality and inequality constraints.
  2. cvxopt: This library provides several optimization algorithms, including the revised simplex method, to solve linear programming problems. It is a powerful library but may have a steeper learning curve than scipy.
  3. pulp: This library provides a high-level interface for modelling linear and integer programming problems. It uses the revised simplex method as the default solver for linear programs.
  4. pyomo: Pyomo is a Python-based open-source optimization modelling language with a vast set of optimization capabilities. It also has built-in solvers, one of them being the revised simplex method.

 

Code

import numpy as np

from numpy import linalg as LA

from numpy.linalg import inv



def simplex_iteration(A, b, C, m: int, n: int):


    Iteration = 0

    Z = 0

    X = np.zeros((n + m))

    XB = np.zeros((m))

    CB = np.zeros((m))

    XN = np.zeros((n))

    CN = np.zeros((n))

    RC = np.zeros((n + m))

    Basis: int = np.zeros((m))

    B = np.zeros((m, m))

    NB = np.zeros((m, n))

    Index_Enter = -1

    Index_Leave = -1

    eps = 1e-12




    for i in range(0, m):

        Basis[i] = n + i

        for j in range(0, m):

            B[i, j] = A[i, n + j]

        for j in range(0, n):

            NB[i, j] = A[i, j]




    for i in range(0, n):

        CN[i] = C[i]

        print("CN: ", CN[i])




    RC = C - np.dot(CB.transpose(), np.dot(inv(B), A))

    MaxRC = 0

    for i in range(0, n + m):

        if (MaxRC < RC[i]):

            MaxRC = RC[i]

            Index_Enter = i




    print("Basis", Basis)

    while (MaxRC > eps):

        Iteration = Iteration + 1

        print("=> Iteration: ", Iteration)




        print(" Index_Enter: ", Index_Enter)

        Index_Leave = -1

        MinVal = 1000000

        print("Enter B: ", B)

        for i in range(0, m):

            if (np.dot(inv(B), A)[i, Index_Enter] > 0):

                bratio = np.dot(inv(B), b)[i] / np.dot(inv(B), A)[i, Index_Enter]

                print("  bratio: ", bratio)

                if (MinVal > bratio):

                    Index_Leave = i

                    print("  Index_Leave: ", Index_Leave)

                    MinVal = bratio

                    print("  MinVal: ", MinVal)

        if (Index_Leave == -1):

            print("Problem Unbounded.")

            return Z, X, RC

        Basis[Index_Leave] = Index_Enter

        print("before updated Basis", Basis)

        print("  Index_Leave: ", Index_Leave)

        for i in range(m - 1, 0, -1):

            if (Basis[i] < Basis[i - 1]):

                temp = Basis[i - 1]

                Basis[i - 1] = Basis[i]

                Basis[i] = temp




        print("updated Basis", Basis)




        for i in range(0, m):

            for j in range(0, n + m):

                if (j == Basis[i]):

                    B[:, i] = A[:, j]

                    CB[i] = C[j]




        print("Exit Basis", Basis)

        print("Exit B: ", B)




        RC = C - np.dot(CB.transpose(), np.dot(inv(B), A))

        MaxRC = 0

        for i in range(0, n + m):

            if (MaxRC < RC[i]):

                MaxRC = RC[i]

                Index_Enter = i

        print("MaxRC", MaxRC)

        X = np.dot(inv(B), b)

        Z = np.dot(CB, X)

    return Z, X, RC

A=np.array([[1,3,2,1,0,0],[2,2,1,0,1,0],[1,1,2,0,0,1]])

b=np.array([[4],[2],[3]])

C=np.array([2,3,2,0,0,0])




print("Z", A)

print("X",b)

print("RC",C)

 

Output

Z [[1 3 2 1 0 0]

 [2 2 1 0 1 0]

 [1 1 2 0 0 1]]

X [[4]

 [2]

 [3]]

RC [2 3 2 0 0 0]

 

 

Conclusion

In conclusion, the revised simplex method is a powerful tool for solving linear programming problems. Its use of both primal and dual solutions and its ability to handle degenerate and non-unique solutions make it a more efficient and versatile alternative to the traditional simplex method

It is an essential algorithm in the field of optimization and can be applied to many real-world problems. Despite its limitations, the revised simplex method remains a valuable and widely used approach for solving linear programming problems.

Furthermore, we have discussed in this article what is a simplex method, what is a revised simplex method, its efficiency and Limitations and also its implementation in Python code.

Let’s have a recap of the topics discussed in the above article

  1. What is a revised Simplex method?
  2. Why is a Revised Simplex method more efficient than Simplex Method?
  3. Limitations of the Revised Simplex method
  4. Libraries to Implement  Revised Simplex Method

If you’ve found this article helpful, comment below and let 👇 know which solutions have helped you solve the problem.

 

Total
0
Shares
Leave a Reply

Your email address will not be published. Required fields are marked *

Related Posts
Total
0
Share