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?

factories | hr cost (product A) | hr cost (product B) | affordable hrs |

M1 | 2 | 2 | 12 |

M2 | 4 | 0 | 16 |

M3 | 0 | 5 | 15 |

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 **nonbasi**c 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

| x1 | x2 | x3 | x4 | x5 | c |

x3 | 2 | 2 | 1 | 0 | 0 | 12 |

x4 | 4 | 0 | 0 | 1 | 0 | 16 |

x5 | 0 | 5 | 0 | 0 | 1 | 15 |

z | 2 | 3 | 0 | 0 | 0 | |

after pivot1, x2 switched to the left as basic variable

same way, do pivot 2:

| x1 | x2 | x3 | x4 | x5 | c |

x3 | 2 | 0 | 1 | 0 | -2/5 | 6 |

x4 | 4 | 0 | 0 | 1 | 0 | 16 |

x2 | 0 | 1 | 0 | 0 | 1/5 | 3 |

z | 2 | 0 | 0 | 0 | -3/5 | |

pivot 3

| x1 | x2 | x3 | x4 | x5 | c |

x1 | 1 | 0 | 1/2 | 0 | -1/5 | 3 |

x4 | 0 | 0 | -2 | 1 | 4/5 | 4 |

x2 | 0 | 1 | 0 | 0 | 1/5 | 3 |

z | 0 | 0 | -1 | 0 | -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/