Simplex Algorithm

[ftneek]

Albert, I do think it is interesting that it seems your "shortcut" method is able to return the same primal solution in the examples you've shown. If the shortcut method correctly provides solutions to larger systems with mixed constraints, and you are not interested in the dual solution, I suppose it could be worth keeping as an option if speed is truly a concern on larger systems.

But the algorithm was designed to simultaneously solve the dual problem as well. If you do not use artificial variables, "half" the information the algorithm was designed to provide is missing. I guess it makes sense then that your shortcut takes roughly half as much time... But I think for this shortcut to be absolutely useful, there should be some way to recover the final tableau obtained by calling simplex2 on the system in proper standard form.

Additionally, slack variables generally represent “unused” resources. For example if the constraint is x1 + x2<=30, and x1=5 and x2=10, then the slack variable should equal 15, because that is the remaining quantity of whatever the constraint represents (x1+x2+s1=30 -> s1=15). It is nice to provide this information as well with the solutions, eg provide x3=15.

Quote:Since an artificial variable cannot be removed from the basis, the original system of constraints contains one redundant equation.

Also, I think this may be a nice piece of information to include in the result. If an artificial variable remains a basic variable at the final tableau, then the system contains a redundant equation. This should be easy enough to check. But do you have any suggestions about how to present this information to the user? I think it is probably best to keep the return type as a list of 3 items if possible.

Proper standard form arguments for Example 3.7.2:
> simplex2([[1,2,0,1,1,0,0,20],[2,1,1,0,0,1,0,10],[-1,4,-2,3,0,0,1,40],[1,4,3,2,0,0,0,0],[0,0,0,0,1,1,1,0]],{5,6,7},7,3,0)

[35,[5,0,0,15,0,0,0],[[1,1/2,1/2,0,3/4,0,-1/4,5],[0,0,0,0,-3/2,1,1/2,0],[0,3/2,-1/2,1,1/4,0,1/4,15],[0,1/2,7/2,0,-5/4,0,-1/4,-35]]]