Home Online Manual
Top
Back: setring
Forward: simplify
FastBack: Functions and system variables
FastForward: Control structures
Up: Functions
Top: Singular Manual
Contents: Table of Contents
Index: Index
About: About this document

5.1.140 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 occurred;
* 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.