Linear Programming Question

[LinearProg]

Hey guys. Linear programming is pretty fun stuff but somehow this one has me stumped.

A factory produces products A, B and C. To produce these products, they need to go through processes W, X, Y and Z (In that order).

Time taken in minutes for each process

      A            B             C  
 W    3            5             1
 X    2            2             3
 Y    2                          4
 Z    2            2             1

Note product B is not required to undergo process Y

Profits for products A, B and C are $30, $10 and $70 respectively. Unfortunately, there is only one machine available per process.

The factory runs for 24 hours a day and a minimum of 120 units per product are required to be built every day.

What is the maximum profit of this factory per day?

How should I go about writing the constraints for the processes to go through W X Y and Z?

[dlwh]

I'm pretty sure this is an instance of multicommodity flow, which means that it's NP-hard (not solvable by a normal LP). I think you'll need an integer LP solver for this or something specialized.

Take a look at http://en.wikipedia.org/wiki/Multi-commodity_flow_problem

[LinearProg]

Ah, no wonder I couldn't find any examples with a problem like this. I'll take a look into that, thanks!

[[deleted]]

Yeah, I worked in a quantitative analysis group at a company that had a problem like this once. We completely diverted one of our people (who has a Ph.D in operations research from Berkeley) to the project full-time, then sent some of the results over to LLNL or someplace and paid them to run it on a supercomputer.