|
5.1.128 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:
See
simplexOut.
|