The function

max(*c*.*x*), *A*.*x* *b*, *x* 0, *b* 0

where Find

max(*X* + 2*Y*) where

Input :
**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}0, - remove variables without constraints,
- add variables such that all the constraints have positive components.

min(2*x* + *y* - *z* + 4) where

Let

(- *X* - 2*Y* + 3) where

i.e. to find the maximum of
- (-
**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 :

For the previous example, input :

and

Input :

**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).

- The first problem is to find an
*x*in the*Ax*=*b*,*x*0 domain. Let*m*be the number of lines of*A*. Add artificial variables*y*_{1},...,*y*_{m}and maximize -*y*_{i}under the conditions*Ax*=*b*,*x*0,*y*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 2
*x*+ 3*y*-*z*+*t*with*x*,*y*,*z*,*t*0 and :*x*+ 3*y*-*z*+*t*). Let us add two artificial variables*y*_{1}and*y*_{2},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*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 linesimplex_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`

.