Simplex Algorithm

[ftneek]

I uploaded a new source file. I added simplex_int() command, for integer programming problems. It should work for many examples with standard form input, but let me know if you encounter any that don't work. Also for simplicity I had to modify simplex_core() to return a 4th item, the list of basic variables. Not sure if there was a better option.

Example:

min x1-x2
s.t 2x1+x2<=5
-4x1+4x2<=5
x1,x2>=0 and integral (integer)

> simplex_int([[2,1,1,0,5],[-4,4,0,1,5],[1,-2,0,0,0]],{3,4},4,0,0,{1,2})

[-3,[1,2,1,1,0],[[1,0,0,0,1,-1/3,1],[0,1,0,0,1,0,2],[0,0,1,0,-3,2/3,1],[0,0,0,1,0,-4/3,1],[0,0,0,0,1,1/3,3]],{1,2,3,4}]

Thus min=-3 at x1=1,x2=2

Here's one example that currently doesn't work. I think because some non cas commands are used so decimals might be introduced.

Xcas > lpsolve(x1+x2,[1867*x1+1913*x2=3618894],assume=nonnegint,lp_verbose=true)

> simplex_int([[1867,1913,1,3618894],[1,1,0,0],[0,0,1,0]],{3},3,1,0,{1,2})

["No Solution",[],[[0,1,1,3618893/1913,-1410/1913],[1,0,-1913/1867,1/1867,1411/1867],[0,0,46/1867,−6756475144/3571571,-66773/3571571]]]

Here's another example that doesn't work, maybe for the same reason.

> simplex_int([[2,9,1,0,40],[11,-8,0,1,82],[-3,-13,0,0,0]],{3,4},4,0,0,{1,2})
"Error: Bad Argument Value"