What algorithm should I use to maximize resource utilization in production planning?

Question

Hi,

What kind of algorithm should I use to solve this problem?

Ore is blended in a particular ratio to produce metal with the desired quality characteristics. The ore is blended in batches of 5, the batches are to be mixed in a particular ratio that will maximize ore utilization as well as produce an output of the desired quality. 
1. A batch of ore contains 30 or more minerals
2. The percentage proportion of each mineral within a batch is known
3. Batches blended with each other should produce a product meeting a criteria such as
   0.5 < m1 < 0.52
   0.2 < m2 < 0.21
   a3 < m3 < b3
   ....
   ....
   a30 < m30 < b30
   where m1, m2, m3 ... m30 are percentage presence of ore in the final product and a1,a2...a30;b1,b2...b30 are tolerable limits within which quality is maintained
4. In what order should n batches (n <= 20) be processed to maximize ore output
5. In what ratio should the batches be blended so that quality is maintained

This sounds mainstream enough for someone to have tackled it but it is outside my limited algorithmic knowledge. Any pointers to solve this is much appreciated.

Answer 1

It looks to me as if you should start looking at linear programming. There are many packages for tackling such problems, general-purpose systems such as Matlab or Mathematica have the capabilities too, or you could code your own (if you're feeling lucky) in your favourite language.

It's not entirely clear that your problem is strictly linear, so you may have to read beyond that topic but it's a good place to start learning about optimisation problems.

Answer 2

Simplex method would work here ( method of allocating resources in an optimal way),

consider this: http://www.phpsimplex.com/en/simplex_method_example.htm

and this ( examples online): http://www.zweigmedia.com/RealWorld/tutorialsf4/framesSimplex.html

or just use some google:-)

Answer 3

This is crying out for mixed integer programming (MIP), which sits on top of linear programming (LP). The LP part (linear inequalities over real variables) is usually solved by using the simplex algorithm. The MIP part deals with the integer constraints (e.g., what order is best?). Neither of these are the sort of thing you want to implement from scratch! There has been many, many decades of development in this area and first rate solutions are available. Consider CPLEX for a commercial solution or SOPLEX for a free solution. If you're a .NET type, look into Microsoft's Solver Foundation.

Hope this helps.