Revised Simplex Method.

The function revised solves an LPP using revised simplex method. It uses big M method.

Description

This function is able to detect almost all types of properties/characteristics present in an LPP such as unbounded solution, alternate optima, degenaracy/cycling and infeasibilty. It only fails to work when there are redundant constraints present in the problem. However, it is rare and can be easily avoided by the user by just checking/ensuring that rank(a) should not be less than the number of constraints. As finding rank of big matrices has high complexity, this check has not been given here and it is expected that user would take care of such cases. In such cases usually it is easily seen that some constraints are linearly dependent and hence can be eliminated. Rest of the cases show good results. For theory of Revised Simplex method and LPP
one may see "Numerical Optimization with Applications, Chandra S., Jayadeva, Mehra A., Alpha Science Internatinal Ltd, 2009."

• MATLAB release: MATLAB 7.8 (R2009a)

[Zoltan]

It doesn't work on some examples:
J=-4x1-2x2-6x3-4x4+2x5->min
s.t. x1+x3+x5<=100, x1+2x2+x3+x4<=200
x2+x3+x4+x5<=160
xi>=0

[Hakan]

Good job, but does not work on some problems.

Works on:
% P = 20x1 + 20x2 + 30x3 --> min.
% 0.06x1 + 0.04x2 + 0.02x3 <= 0.03
% 2x1 + 4x2 + 3x3 <= 3.25
% x1 + x2 + x3 = 1
c = [20, 20, 30];
b = [0.03, 3.25, 1];
a = [0.06, 0.04, 0.02; 2, 4, 3; 1, 1, 1];
inq = [-1, -1, 0];
minimize = 1;
revised(c,b,a,inq,minimize)

Does not work on:
% P = x1 + 8x2 + 9x3 + x4 + 8x5 + 7x6 + 10x7 + 9x8 + 13x9 --> maks.
% x1 + x2 + x3 <= 12e3
% x4 + x5 + x6 <= 10e3
% x7 + x8 + x9 <= 8e3
% x1 + x4 + x7 <= 10e3
% x2 + x5 + x8 <= 12e3
% x3 + x6 + x9 <= 6e3
c = [1, 8, 9, 1, 8, 7, 10, 9, 13];
b = [12e3, 10e3, 8e3, 10e3, 12e3, 6e3];
a = [1, 1, 1, 0, 0, 0, 0, 0, 0
     0, 0, 0, 1, 1, 1, 0, 0, 0
     0, 0, 0, 0, 0, 0, 1, 1, 1
     1, 0, 0, 1, 0, 0, 1, 0, 0
     0, 1, 0, 0, 1, 0, 0, 1, 0
     0, 0, 1, 0, 0, 1, 0, 0, 1];
% inq = -ones(1,6);
% minimize = 0;
revised(c, b, a)

It gives the error:
Undefined function or variable "v".

Error in revised (line 175)
                    temp=bv(v);bv(v)=nbv(t);

varibale "v" stays undefined in some conditions.

Anyway, thanks for the effort.