Maxima and EMT do of course have implementations of the Simplex algorithm. The algorithm in Maxima seems to work differently for floating point numbers and for fractions. Here is an example in fractions.

We solve a problem in standard form.

\(Ax=b, \quad c^Tx \to \text{Min.}\)

Then Maxima has the function linear_program().

>&load(simplex);
>A &:= [1,1,-1,0;2,-3,0,-1;4,-5,0,0]
             1             1            -1             0 
             2            -3             0            -1 
             4            -5             0             0 
>b &:= [1,1,6]
 [1,  1,  6]
>c &:= [1,-2,0,0]
 [1,  -2,  0,  0]
>&linear_program(A,b,c)

                           13     19        3
                         [[--, 4, --, 0], - -]
                           2      2         2

Since we have carefully defined the data as numerical and symbolic variables, we can use the same data for the simplex() algorithm in EMT.

>x=simplex(A,b',c,eq=0,>min); fraction x'
 [13/2,  4,  19/2,  0]

Note „eq=0“, which sets all equations (in each row of A) to equalities. The default is „eq=-1“ which means inequalilites of the form „<=“. The solution would then be different.

There is another form of the command in Maxima.

>&minimize_lp(x-2*y, ...
>  [x+y-z=1,2*x-3*y-v=1,4*x-5*y=6,x>=0,y>=0,z>=0,v>=0])

                      3              19             13
                   [- -, [v = 0, z = --, y = 4, x = --]]
                      2              2              2

Of course, the simplex() command and the Maxima commands can do a lot more. EMT does also have efficient packages for integer programming. Start with the tutorial to learn more about this.

With only two variables, we can even draw the feasible set. With three variables, we can use Povray to do this. In the examples of EMT, you find the following plot.