5.1.114 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. 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 <=constraints (rows 2 ... m1+1 of M); m2 = number of >=constraints (rows m1+2 ... m1+m2+1 of M); m3 = number of == constraints.

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 from the first column of L[1] as 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

See simplexOut.