﻿ Linear Optimization with Maxima and EMT | Observations

Linear Optimization with Maxima and EMT

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 