The simple case
The function simplex_reduce makes the reduction
by the simplex algorithm to find :
max(c.x), A.x ≤ b, x ≥ 0, b≥ 0 |
where c,x are vectors of ℝn, b≥ 0 is a vector in
ℝp and A is a matrix of p rows and n columns.
simplex_reduce takes as argument A,b,c and
returns max(c.x), the augmented solution of x
(augmented since the algorithm works by adding rows(A) auxiliary
variables) and the reduced matrix.
Example
Find
max(X+2Y) where | ⎧ ⎪ ⎨ ⎪ ⎩ |
|
Input :
Output :
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 complicated case that reduces to the simple case
With the former call of simplex_reduce, we have to :
For example, find :
min(2x+y−z+4) where | ⎧ ⎪ ⎪ ⎨ ⎪ ⎪ ⎩ |
| (1) |
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 :
⎧ ⎪ ⎨ ⎪ ⎩ |
|
or to find the minimum of :
(−X−2Y+3) where | ⎧ ⎪ ⎨ ⎪ ⎩ |
|
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 :
simplex_reduce may be called with D as single argument.
For the previous example, input :
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 Ax≤ b)
under the conditions x≥ 0. We may further assume that b≥ 0
(if not, one can change the sign of the corresponding line).
simplex_reduce
with
a single matrix argument obtained by augmenting A by the
identity, b unchanged and an artificial
c with 0 under A and 1 under the identity).
If the maximum exists and is 0, the identity submatrix above the last
column corresponds to an x solution, we may forget the artificial
variables (they are 0 if the maximum is 0).
simplex_reduce
with the original c and the value of x we found in the domain.
⎧ ⎨ ⎩ |
|
simplex_reduce([[-1,-1,0,1,1,0,1], [0,1,-1,1,0,1,3], [0,0,0,0,1,1,0]])Output: optimum=0, artificial variables=0, and the matrix
⎛ ⎜ ⎜ ⎝ |
| ⎞ ⎟ ⎟ ⎠ |
simplex_reduce([[-1/2,0,-1/2,1,2], [1/2,1,-1/2,0,1],[2,3,-1,1,0]])Output: maximum=-5, hence the minimum of the opposite is 5, obtained for (0,1,0,2), after replacement x=0, y=1, z=0 and t=2.
For more details, search google for simplex algorithm
.