Revised Simplex Method - Demo

A demonstration code of revised simplex method
341 Downloads
Updated 29 Nov 2015

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
Created with R2013b
Compatible with any release
Platform Compatibility
Windows macOS Linux
Categories
Find more on Linear Programming and Mixed-Integer Linear Programming in Help Center and MATLAB Answers

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Versions that use the GitHub default branch cannot be downloaded

Version Published Release Notes
1.0.0.0

Added a sample output

To view or report issues in this GitHub add-on, visit the GitHub Repository.
To view or report issues in this GitHub add-on, visit the GitHub Repository.