Simplex Algorithm

[Tommy Vee]

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.