Tuesday, August 19, 2014

linear programming -- simplex method

I used to like Linear Programming at school, but barely use it for problems in real world. However, it could probably offer some help to RTB problems. Well, forget about RTB, let's start with an easier example. (I make up this example for easy calculating. Of course it would be much more complicated in a real problem.)

We have three manufacture factories (M1, M2, M3) that can make two types of products: A and B. M1 and M2 can make product A; M1, M3 can make product B. To make each A, it needs 2 hours at M1, 4 hours at M2; tow make each B, it needs 2 hours at M1 and 5 hours at M3. The profit is $2 for each product A and $3 for each product B. However, M1 can afford 12 hrs at most a day; M2 can afford 16 hrs at most; M3 can afford 15 hrs at most. For making as much money as we can, how many product should we make for product A and B respectively each day?

factorieshr cost (product A)hr cost (product B)affordable hrs
M12212
M24016
M30515

If we put it in a math way:
objective:    max  2*x1 + 3*x2
 sub             2*x1 + 2* x2 <= 12
                   4*x1              <= 16
                               5*x2  <= 15

Of course it can transform into a min optimization based on LP duality.
Here I want to show the solution by simplex method. First, let's make all condition as equations by adding three variables x3, x4, x5
             2*x1 + 2* x2 + x3 = 12
             4*x1             + x4 = 16
                         5*x2  + x5 = 15

as we put them in a matrix and do the pivots
pivot 1:
the purpose is to find out the basic and nonbasic variable that can improve the solution
- step1:  find max in z_row (that can contribute to improve the solution). that is 3. so x2 is the basic variable (i.e. entering variable)
- step2  in the column (where z=3), for positive x(i,j) find min{x(i,j)/c}, that would be row_x5. so x5 is the nonbasic variable (i.e. departing variable)
detail of pivot1:
 - row_x5 = row_x5/5
 - row_x3 = row_x3 - row_x5 * 2
 - row_z = row_z - row_x5*3
x1x2x3x4x5c
x32210012
x44001016
x50500115
z23000

after pivot1, x2 switched to the left as basic variable
same way, do pivot 2:
x1x2x3x4x5c
x32010-2/56
x44001016
x201001/53
z2000-3/5


pivot 3
x1x2x3x4x5c
x1101/20-1/53
x400-214/54
x201001/53
z00-10-1/5


now, x1, x2 are both basic variables on the left, so the solution is: when x1 =3 and x2 =3, the problem have max value (Note: not all LP problems have feasible solution).

Finally, to make life easier, python has a module for the simplex method.
PyGLPK   http://tfinley.net/software/pyglpk/discussion.html
Here is an example of PyGLPK using simplex method  http://tfinley.net/software/pyglpk/ex_maxflow.html
Other resource: PuLP  http://www.coin-or.org/PuLP/