# Demonstrating the Simplex Algorithm

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.

Diese Website verwendet Akismet, um Spam zu reduzieren. Erfahre mehr darüber, wie deine Kommentardaten verarbeitet werden.