Revised Simplex Method - Demo

A demonstration code of revised simplex method

This class implements revised Simplex Method to solve a linear programming problem in the following format
min/max c'x
s.t. Ax {>=, =, <=} b,
x >= 0
This class is designed for class demonstration and small problems. May not be suitable for solving large problems or for high performance purpose. Detailed information for every iteration will be printed out.

Sample output:

=========== Iteration 1 ===========

B = [1 0 0;0 1 0;0 0 1];
N = [1 0;0 2;3 2];
cB = [0;0;0];
cN = [-3;-5];

* BTRAN : y^{T} = c_{B}^{T}B^{-1} = [0 0 0]
* PRICE : d_{N}^{T} = c_{N}^{T} - y^{T}N = [-3 -5]
* ChuzC : Choose the most negative reduced cost (-5) and increase x2.
* FTRAN : Find the column of x2 in the updated tableau, and the RHS

B^{-1}N_{x2} = [0;2;2]
RHS (= B^{-1}b) = [180;150;300]

* ChuzR : Find the max value of x2 that maintains feasiblity

Basis | x2 | = || Limit
----------------------------------
s1 | 0 | 180 || 180 / 0
s2 | 2* | 150 || 150 / 2
s3 | 2 | 300 || 300 / 2
----------------------------------
| -5 | || 0
* Update: Increase x2 by 75, then

x = [0;75;180;0;150], z = -375.
x2 enters the basis and s2 leaves.

=========== Iteration 2 ===========

B = [1 0 0;0 2 0;0 2 1];
N = [1 0;0 1;3 0];
cB = [0;-5;0];
cN = [-3;0];

* BTRAN : y^{T} = c_{B}^{T}B^{-1} = [0 -2.5 0]
* PRICE : d_{N}^{T} = c_{N}^{T} - y^{T}N = [-3 2.5]
* ChuzC : Choose the most negative reduced cost (-3) and increase x1.
* FTRAN : Find the column of x1 in the updated tableau, and the RHS

B^{-1}N_{x1} = [1;0;3]
RHS (= B^{-1}b) = [180;75;150]

* ChuzR : Find the max value of x1 that maintains feasiblity

Basis | x1 | = || Limit
----------------------------------
s1 | 1 | 180 || 180 / 1
x2 | 0 | 75 || 75 / 0
s3 | 3* | 150 || 150 / 3
----------------------------------
| -3 | || -375
* Update: Increase x1 by 50, then

x = [50;75;130;0;0], z = -525.
x1 enters the basis and s3 leaves.

=========== Iteration 3 ===========

B = [1 0 1;0 2 0;0 2 3];
N = [0 0;0 1;1 0];
cB = [0;-5;-3];
cN = [0;0];

* BTRAN : y^{T} = c_{B}^{T}B^{-1} = [0 -1.5 -1]
* PRICE : d_{N}^{T} = c_{N}^{T} - y^{T}N = [1 1.5]

========== ========== ==========
Terminated with status [ optimal ].
Optimal solution:
x1 = 0.000
x2 = 75.000
s1 = 130.000
s2 = 0.000
s3 = 0.000
Optimal objective function value: -525.00