|
5.1.135 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
|
See
simplexOut.
|