This repository contains 2 folders: The first one is the Phase II Simplex and the second one is the Phases I and II Simplex. For each one, we'll briefly describe the files and how each function works.
The Simplex algorithm implementation was inspired by [1] and written in Octave programming language.
Here we implemented the Phase II Simplex Method using its three most known versions: Naive, Revised and Tableau. The Phase II Simplex starts with a initial Basic Feasible Solution (BFS) x.
This folder contains 3 files: simplex_ing, simplex_res and simplex_tab.
Each function returns two values: ind, that represents whether the problem has optimal solution (ind = 0) or the problem is unbounded (ind = -1); and v, that represents the optimal solution if it exists, or the direction vector in which the objective funcion goes to -infinity.
For the naive version, the main function is defined as follows:
[ind v] = simplex_ing(A,b,c,m,n,x,indB)
The problems treated for the 3 versions for the Phase II Simplex were obtained from [2]:
The input parameters are:
A = [4/5 6/5 1 0 0 0; 2 3 0 1 0 0; 2/3 2 0 0 1 0; 16/3 4 0 0 0 1];
c = [-40; -50; 0; 0; 0; 0];
b = [16; 30; 16; 64];
x = [0; 0; 16; 30; 16; 64];
m = size(A,1);
n = size(A,2);
indB = [3; 4; 5; 6];
For the revised version, the main function is defined as follows:
[ind v] = simplex_res(A,b,c,m,n,x,indB,Binv)
Where Binv stands for "B inverse", which is defined as:
And for the following problem we have:
The input parameters are:
A = [4/5 6/5 1 0 0 0; 2 3 0 1 0 0; 2/3 2 0 0 1 0; 16/3 4 0 0 0 1];
c = [-40; -50; 0; 0; 0; 0];
b = [16; 30; 16; 64];
x = [0; 0; 16; 30; 16; 64];
m = size(A,1);
n = size(A,2);
indB = [3; 4; 5; 6];
Binv = eye(4);
For the full tableau version, the main function is defined as follows:
[ind v] = simplex_tab(indB,tableau)
Where the parameter tableau is as follows:
And for the following problem we have:
The input parameters are:
indB = [3; 4; 5; 6];
tableau = [0 -40 -50 0 0 0 0;
16 4/5 6/5 1 0 0 0;
30 2 3 0 1 0 0;
16 2/3 2 0 0 1 0;
64 16/3 4 0 0 0 1];
In this implementation, the Phase I Simplex tries to find a BFS that is used as the parameter x in the Phase II Simplex. The last two versions are used: Revised and Full Tableau.
As an anticiclying rule, this implementation uses the Bland's rule, that selects the smallest subscript as pivot.
This folder contains 4 files: simplex_res and simplex_revisado for the two Phase Simplex revised version and simplex_tab and simplex_tableau for the two Phase Simplex tableau version.
The function is defined as:
[ind x v] = simplex_res(A,b,c,m,n)
Where x is the initial BFS found in the end of Phase I (for problems with optimal solution or unbounded problems) and v is the same as described on Section 1 and is used for both versions (revised and tableau). Where:
For the following problem:
We have:
A = [1 2 3 0; -1 2 6 0; 0 4 9 0; 0 0 3 1];
b = [3; 2; 5; 1];
c = [1; 1; 1; 0];
m = size(A, 1);
n = size(A,2);
For the tableau version, there is an unique parameter which is:
For the problem:
The input is:
tableau = [0 1 1 1 0;
3 1 2 3 0;
2 -1 2 6 0;
5 0 4 9 0;
1 0 0 3 1];
[1] Bertsimas D., Tsitsiklis N. J. Introduction to Linear Optmization (1997). Athena Scientific, Belmont, Massachusetts.
[2] Graves, S. The Simplex Method for Solving a Linear Program (2003). Massachusetts Institute of Technology. Pages 55 - 58.