It is easy to use the simplex algorithm in Euler Math Toolbox (EMT). In fact, there are two functions for this: A C code in the kernel and the LPSOLVE package. Here is a short and very simple example for the first.

We solve

\(x-2y+3=1, \\ x+2y+z=1, \\ x,y,z \ge 0, \\ x+y+2z \to \text{Max.}\)

As usual we write this in the standard form

\(Ax=b, \quad x \ge 0, \quad c^T x \to \text{Min.}\)

The function simplex() can be called to solve this optimization problem as follows.

>A=[1,-2,3;1,2,1]
         1        -2         3 
         1         2         1 
>b=[1;1]
         1 
         1 
>c=[1,1,2]
         1         1         2 
>fraction simplex(A,b,c,0,>max)
         0 
       1/4 
       1/2

Note the fourth argument 0 in the call to simplex(). By default, the simplex() function assumes inequalities. But this can be changed for each row of the matrix or for all rows (-1 means less or equal, 0 means equal, and 1 means greater or equal). The parameter >max is a shortcut for max=1 in EMT. The default is minimization. We could of course take -c instead of >max.

The purpose of this page is to show you, how to do this step by step. The simplex algorithm uses the Gauss algorithm for the following matrix.

>fracformat(10); M=A|b_c
         1        -2         3         1 
         1         2         1         1 
         1         1         2         0

The first two lines are A and b, and the last line is the target function. (Some authors put the target function to the top line, which does not change much.) As a first step, we make the the first column a unit vector.

>M[2]=M[2]-M[1]; M[3]=M[3]-M[1]
         1        -2         3         1 
         0         4        -2         0 
         0         3        -1        -1

In the same way we could also divide a line by a factor. But we do not have to do this here. There is a function that helps with the Gauss algorithm. We apply it to make the second column the second unit vector.

>pivotize(M,2,2)
         1         0         2         1 
         0         1      -1/2         0 
         0         0       1/2        -1

By good luck, our vertex (x=1, y=0, z=0) is now admissible. Remember that we get the vertex by setting the columns, which are not in our base equal to 0 (in our case that is z=0), and reading off the values for the other columns (in our case x=1, y=0).

Our vector is not yet optimal, since the target function contains a positive element. We have to exchange the third column into our base. In fact, we need to exchange it with the first column.

>pivotize(M,1,3)
       1/2         0         1       1/2 
       1/4         1         0       1/4 
      -1/4         0         0      -5/4

Now we are done. The solution is x=0, y=1/4 and z=1/2.