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

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

## No comments:

## Post a Comment