On 9/2/2013 11:43 AM, Robert Kern wrote:
On 2013-09-02 16:06, Tommy Vee wrote:
On 9/2/2013 5:55 AM, Robert Kern wrote:
On 2013-09-02 02:26, Tommy Vee wrote:
Anyone know where I can get an easy to use Python class or algorithm
for the
Simplex optimization algorithm? I've tried the one in the link below,
but I
can't figure out if a) I'm using it properly, or b) where to get the
solution.
BTW, I tried some test scenarios using MS Excel's "Solver" and just
can't get
this algorithm to match Excel's results (which is spot on).
http://taw9.hubpages.com/hub/Simplex-Algorithm-in-Python
BTW, if I can't something to work, I'm going to be forced to use the
VBA
programmatic Excel interface. That wouldn't be too bad, but the data
comes from
a DB and getting it properly positioned to use Excel's "Solver" is very
painful. A Python approach would be much cleaner.
Can you show some of the test scenarios that you tried? There are
different conventions in how to represent a linear programming problem,
and different solvers may choose different conventions. You may have to
convert between representations.
You may have better luck with the PuLP interface:
https://pypi.python.org/pypi/PuLP
PuLP itself is just a modelling language rather than a solver, but the
sources do contain compiled binaries for the CoinMP solver so it will
work out-of-box on popular platforms, like Windows.
https://projects.coin-or.org/CoinMP
Thank you, I will definitely look at these and other options. BTW,
try the test
scenario in the link I sent. Very simple, only 3 variables.
Maximize: 2x+3y+2z
Constraints: 2x+y+z <=4, x+2y+z <=7, z <= 5
The algorithm displays the Tableau after each pivot, but where is the
answer for
x, y and z?
You will have to read up on the Dantzig Simplex Algorithm to learn how
to read off the results from the final tableau. My understanding is that
you look at the columns representing the basic variables (in this case,
the second, third, and fourth columns represent x, y, and z,
respectively). If the column is all 0s except for a single 1, then the
row with the 1 has the variable's value in the rightmost column. If the
column has other values in it, then the variable's value is 0.
When I run this in Excel's Solver, I get x=0, y=3, z=1. which is
indeed the
maximized solution (11).
The final tableau for this problem looks like this:
[[ 1. 1. 0. 0. 1. 1. 0. 11.]
[ 0. 3. 0. 1. 2. -1. 0. 1.]
[ 0. -1. 1. 0. -1. 1. 0. 3.]
[ 0. -3. 0. 0. -2. 1. 1. 4.]]
So, for x, we look in the second column and notice that it has a bunch
of different values in it, so x=0.
For y, we look in the third column and see that it has its single 1 in
the third row. Looking all the way on the right for that row, we get a 3.
For z, we look in the fourth column and see that it has its single 1 in
the second row. Looking all the way on the right for that row, we get a 1.
So this solver does reproduce the result x=0, y=3, z=1. The maximized
solution is in the upper-rightmost element of the tableau, 11.
Sound like a pain in the ass to code up that logic? It is. PuLP and
other industrial grade solver interfaces won't make you go through this.
You nailed it. Thanks for help. And you're right. This is too
painful, I just read the PuLP doc and it may be a lot easier.
--
http://mail.python.org/mailman/listinfo/python-list
