Revised Simplex Method - Demo
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
Cite As
Yiming Yan (2024). Revised Simplex Method - Demo (https://github.com/YimingYAN/revised), GitHub. Retrieved .
MATLAB Release Compatibility
Platform Compatibility
Windows macOS LinuxCategories
- Mathematics and Optimization > Optimization Toolbox > Linear Programming and Mixed-Integer Linear Programming >
Tags
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!Discover Live Editor
Create scripts with code, output, and formatted text in a single executable document.
Versions that use the GitHub default branch cannot be downloaded
Version | Published | Release Notes | |
---|---|---|---|
1.0.0.0 | Added a sample output |
|