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 $$\leq$$ b, x $$\geq$$ 0, b $$\geq$$ 0

where c, x are vectors of $\mathbb {R}$ⁿ, b $\geq$ 0 is a vector of $\mathbb {R}$^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.
Example
Find

max(X + 2Y) where $$\left\{\vphantom{ \begin{array}{rcl} (X,Y) & \geq & 0 \\ -3X +2Y & \leq & 3\\ X +Y & \leq & 4 \end{array} }\right.$$$$\begin{array}{rcl} (X,Y) & \geq & 0 \\ -3X +2Y & \leq & 3\\ X +Y & \leq & 4 \end{array}$$

Input :

simplex_reduce([[-3,2],[1,1]],[3,4],[1,2])

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 :

• rewrite constraints to the form x_k $\geq$ 0,
• remove variables without constraints,
• add variables such that all the constraints have positive components.

For example, find :

min(2x + y - z + 4)     where $$\left\{\vphantom{ \begin{array}{rcl} x & \leq & 1 \\ y & \geq &... ...x+3y-z & = & 2 \\ 2x-y+z & \leq & 8\\ -x+y & \leq & 5 \end{array} }\right.$$$$\begin{array}{rcl} x & \leq & 1 \\ y & \geq & 2 \\ x+3y-z & = & 2 \\ 2x-y+z & \leq & 8\\ -x+y & \leq & 5 \end{array}$$

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 :

$$\left\{\vphantom{ \begin{array}{rcl} X & \geq & 0 \\ Y & \geq &... ...-X)-(Y+2)+ 5-X+3Y & \leq & 8\\ -(1-X) +(Y+2) & \leq & 5 \end{array} }\right.$$$$\begin{array}{rcl} X & \geq & 0 \\ Y & \geq & 0 \\ 2(1-X)-(Y+2)+ 5-X+3Y & \leq & 8\\ -(1-X) +(Y+2) & \leq & 5 \end{array}$$

or to find the minimum of :

(- X - 2Y + 3)     where $$\left\{\vphantom{ \begin{array}{rcl} X & \geq & 0 \\ Y & \geq & 0 \\ -3X+2Y & \leq & 3\\ X +Y & \leq & 4 \end{array} }\right.$$$$\begin{array}{rcl} X & \geq & 0 \\ Y & \geq & 0 \\ -3X+2Y & \leq & 3\\ X +Y & \leq & 4 \end{array}$$

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 :

simplex_reduce(D)

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 $\leq$ b) under the conditions x $\geq$ 0. We may further assume that b $\geq$ 0 (if not, one can change the sign of the corresponding line).

• The first problem is to find an x in the Ax = b, x $\geq$ 0 domain. Let m be the number of lines of A. Add artificial variables y₁,..., y_m and maximize - $\sum$y_i under the conditions Ax = b, x $\geq$ 0, y $\geq$ 0 starting with initial value 0 for x variables and y = b (to solve this with Xcas, call 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).
• Now we make a second call to simplex_reduce with the original c and the value of x we found in the domain.
• Example : find the minimum of 2x + 3y - z + t with x, y, z, t $\geq$ 0 and :
  $$\left\{\vphantom{ \begin{array}{rcl} -x-y+t&=&1\\ y-z+t&=&3 \end{array}}\right.$$$$\begin{array}{rcl} -x-y+t&=&1\\ y-z+t&=&3 \end{array}$$
  This is equivalent to find the opposite of the maximum of - (2x + 3y - z + t). Let us add two artificial variables y₁ and y₂,

  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
  $$\left(\vphantom{\begin{array}{ccccccc} -1/2 & 0 & -1/2 & 1 & 1/2 ... ... & -1/2 & 0 & -1/2 & 1/2 & 1 \\ 0 & 0 & 0 & 0 & 1 & 1 & 0 \end{array}}\right.$$$$\begin{array}{ccccccc} -1/2 & 0 & -1/2 & 1 & 1/2 & 1/2 & 2 \\ 1/2 & 1 & -1/2 & 0 & -1/2 & 1/2 & 1 \\ 0 & 0 & 0 & 0 & 1 & 1 & 0 \end{array}$$$$\left.\vphantom{\begin{array}{ccccccc} -1/2 & 0 & -1/2 & 1 & 1/2 ... ... & -1/2 & 0 & -1/2 & 1/2 & 1 \\ 0 & 0 & 0 & 0 & 1 & 1 & 0 \end{array}}\right)$$
  Columns 2 and 4 are the columns of the identity (in lines 1 and 2). Hence x = (0, 1, 0, 2) is an initial point in the domain. We are reduced to solve the initial problem, after replacing the lines of Ax = b by the two first lines of the answer above, removing the last columns corresponding to the artificial variables. We add c.x as last line

  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.