Какой алгоритм следует использовать для максимального использования ресурсов при планировании производства?

Question

Какой алгоритм мне следует использовать для решения этой проблемы?

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

Это звучит достаточно широко для того, чтобы кто-то занялся этим, но это вне моих ограниченных алгоритмических знаний.Любые указатели, чтобы решить это очень ценится.

Answer 1

Это кричит о смешанном целочисленном программировании (MIP), которое стоит на вершине линейного программирования (LP).Часть LP (линейные неравенства над действительными переменными) обычно решается с помощью симплексного алгоритма.Часть MIP имеет дело с целочисленными ограничениями (например, какой порядок лучше?).Ничего из этого вы не хотите реализовать с нуля!Было много, много десятилетий развития в этой области, и доступны первоклассные решения.Рассмотрим CPLEX для коммерческого решения или SOPLEX для бесплатного решения.Если вы тип .NET, загляните в Microsoft Solver Foundation.

Надеюсь, это поможет.

Answer 2

Мне кажется, что вы должны начать смотреть на линейное программирование . Существует множество пакетов для решения таких проблем, у систем общего назначения, таких как Matlab или Mathematica, тоже есть возможности, или вы можете написать свой собственный (если вам повезет) на вашем любимом языке.

Не совсем ясно, что ваша проблема носит строго линейный характер, поэтому вам, возможно, придется читать дальше этой темы, но это хорошее место, чтобы начать изучение проблем оптимизации.

Answer 3

Симплексный метод будет работать здесь (метод распределения ресурсов оптимальным образом),

рассмотрите это: http://www.phpsimplex.com/en/simplex_method_example.htm

и это (примеры в Интернете): http://www.zweigmedia.com/RealWorld/tutorialsf4/framesSimplex.html

или просто используйте Google: -)