5.1.134 simplex

Syntax:

simplex ( matrix_expression, int_expression, int_expression, int_expression, int_expression, int_expression)

Type:

list

Purpose:

perform the simplex algorithm for the tableau given by the input, e.g. simplex (M, m, n, m1, m2, m3 ):

M matrix of numbers :

first row describing the objective function (maximize problem), the remaining rows describing constraints;

m, n, m1, m2, m3 int :

n = number of variables; m = total number of constraints; m1 = number of inequalities "<=" (rows 2 ... m1+1 of M); m2 = number of inequalities ">=" (rows m1+2 ... m1+m2+1 of M); m3 = number of equalities.

The following assumptions are made:

* ground field is of type (real,N), N>=4;

* the matrix M is of size m x n;

* m=m1+m2+m3;

* the entries M[2,1] ,..., M[m+1,1] are non-negative;

* the variables x(i) are non-negative;

* a row b, a(1) ,..., a(n) corresponds to b+a(1)x(1)+...+a(n)x(n);

* for a <=, >=, or == constraint: add "in mind" >=0, <=0, or ==0.

The output is a list L with

* L[1] = matrix

* L[2] = int:

0 = finite solution found; 1 = unbounded; -1 = no solution; -2 = error occured;

* L[3] = intvec :

L[3][k] = number of variable which corresponds to row k+1 of L[1];

* L[4] = intvec :

L[4][j] = number of variable which is represented by column j+1 of L[1] ("non-basis variable");

* L[5] = int :

number of constraints (= m);

* L[6] = int :

number of variables (= n).

The solution can be read off the first column of L[1] as it is done by the procedure simplexOut in solve.lib.

Example:

ring r = (real,10),(x),lp; // consider the max. problem: // // maximize x(1) + x(2) + 3*x(3) - 0.5*x(4) // // with constraints: x(1) + 2*x(3) <= 740 // 2*x(2) - 7*x(4) <= 0 // x(2) - x(3) + 2*x(4) >= 0.5 // x(1) + x(2) + x(3) + x(4) = 9 // matrix sm[5][5]=( 0, 1, 1, 3,-0.5, 740,-1, 0,-2, 0, 0, 0,-2, 0, 7, 0.5, 0,-1, 1,-2, 9,-1,-1,-1,-1); int n = 4; // number of constraints int m = 4; // number of variables int m1= 2; // number of <= constraints int m2= 1; // number of >= constraints int m3= 1; // number of == constraints simplex(sm, n, m, m1, m2, m3); ==> [1]: ==> _[1,1]=17.025 ==> _[1,2]=-0.95 ==> _[1,3]=-0.05 ==> _[1,4]=1.95 ==> _[1,5]=-1.05 ==> _[2,1]=730.55 ==> _[2,2]=0.1 ==> _[2,3]=-0.1 ==> _[2,4]=-1.1 ==> _[2,5]=0.9 ==> _[3,1]=3.325 ==> _[3,2]=-0.35 ==> _[3,3]=-0.15 ==> _[3,4]=0.35 ==> _[3,5]=0.35 ==> _[4,1]=0.95 ==> _[4,2]=-0.1 ==> _[4,3]=0.1 ==> _[4,4]=0.1 ==> _[4,5]=0.1 ==> _[5,1]=4.725 ==> _[5,2]=-0.55 ==> _[5,3]=0.05 ==> _[5,4]=0.55 ==> _[5,5]=-0.45 ==> [2]: ==> 0 ==> [3]: ==> 5,2,4,3 ==> [4]: ==> 1,6,8,7 ==> [5]: ==> 4 ==> [6]: ==> 4