Previous Up Next

2.44.1  Simplex algorithm: simplex_reduce

The simple case
The function simplex_reduce makes the reduction by the simplex algorithm to find :

max(c.x),     A.x ≤ bx ≥ 0, b≥ 0 

where c,x are vectors of ℝn, b≥ 0 is a vector of ℝp and A is a matrix of p rows and n columns.
simplex_reduce takes as argument A,b,c et returns max(c.x), the augmented solution of x (augmented since the algorithm works by adding rows(A) auxiliary variables) and the reduced matrix.

max(X+2Y)   where

−3X +2Y3
X +Y4

Input :


Output :

7,[1,3,0,0],[[0,1,1/5,3/5,3],[1,0,(-1)/5,2/5,1], [0,0,1/5,8/5,7]]

Which means that the maximum of X+2Y under these conditions is 7, it is obtained for X=1,Y=3 because [1,3,0,0] is the augmented solution and the reduced matrix is :
[[0,1,1/5,3/5,3],[1,0,(-1)/5,2/5,1], [0,0,1/5,8/5,7]].

A more complicate case that reduces to the simple case
With the former call of simplex_reduce, we have to :

For example, find :

min(2x+yz+4)      where


Let x=1−X, y=Y+2, z=5−X+3Y the problem is equivalent to finding the minimum of (−2X+Y−(5−X+3Y)+8) where :

2(1−X)−(Y+2)+ 5−X+3Y8
−(1−X) +(Y+2)5

or to find the minimum of :

(−X−2Y+3)     where  

X +Y4

i.e. to find the maximum of −(−X−2Y+3)=X+2Y−3 under the same conditions, hence it is the same problem as to find the maximum of X+2Y seen before. We found 7, hence, the result here is 7-3=4.

The general case
A linear programming problem may not in general be directly reduced like above to the simple case. The reason is that a starting vertex must be found before applying the simplex algorithm. Therefore, simplex_reduce may be called by specifying this starting vertex, in that case, all the arguments including the starting vertex are grouped in a single matrix.

We first illustrate this kind of call in the simple case where the starting point does not require solving an auxiliary problem. If A has p rows and n columns and if we define :

B:=augment(A,idn(p)); C:=border(B,b);
d:=append(-c,0$(p+1)); D:=augment(C,[d]);

simplex_reduce may be called with D as single argument.
For the previous example, input :

A:=[[-3,2],[1,1]];B:=augment(A,idn(2)); C:=border(B,[3,4]); D:=augment(C,[[-1,-2,0,0,0]])

Here C=[[-3,2,1,0,3],[1,1,0,1,4]]
and D=[[-3,2,1,0,3],[1,1,0,1,4],[-1,-2,0,0,0]]
Input :


Output is the same result as before.

Back to the general case.
The standard form of a linear programming problem is similar to the simplest case above, but with Ax=b (instead of Axb) under the conditions x≥ 0. We may further assume that b≥ 0 (if not, one can change the sign of the corresponding line).

For more details, search google for simplex algorithm.

Previous Up Next