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
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
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
| 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/
