Алгоритм сортировки сумм суммирования по итогу и соблюдения критериев в питоне

Question

Я пытаюсь сделать расчет оптимизации корма для кормления животных, но я новичок в терминах кодирования Python.

На самом деле я пытаюсь вычислить менее дорогую комбинацию из n ингредиентов по группам k или меньше, которые обеспечивают достаточное количество критериев A и B.

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

Что я сейчас делаю:

1. Создание матрицы ингредиентов: каждый ингредиент имеет название, а затем P, A, B, C, D ... где P - цена и A, B, C, ... являются значениями для различные питательные элементы
2. Создание матрицы пределов: каждый элемент имеет минимальное и максимальное значение общего микса.
3. Создайте объективный вектор: сейчас я хочу получить вектор A = X и вектор B = Y, но в будущем я хотел бы указать C, D и т. Д.
4. Затем я вычисляю все возможные комбинации ингредиентов, суммируя их до общего числа (обычно 1000) и по группе k ингредиентов.
5. Удалите комбинации, которые не соответствуют матрице пределов, чтобы получить доступную матрицу комбинаций
6. Умножьте матрицу ингредиентов на матрицу комбинации, чтобы получить окончательную матрицу состава
7. Удалите все значения в матрице композиции, которые не соответствуют целевому вектору для критериев A и B.
8. Сортируйте полученный список по цене и дайте результат.

Я использую Numpy для большинства этих операций.

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

Спасибо

Answer 1

Это определенно проблема линейного программирования - ее часто называют проблемой диеты.Как сказал Хью Ботвелл, посмотрите на scipy.optimize.Следующее должно начать,

from scipy import array,dot
from scipy.optimize import fmin_slsqp as fmin

c = array([173.0,184.0,167.0])    # cost or prices
b = array([0.1,0.1,0.1])          # lower nutrient bounds
A = array([[ 0.39, 0.09, 0.77],   # nutrient composition
           [ 0.75, 0.32, 0.15],
           [ 0.32, 0.76, 0.65]])

x = array([0.5,0.5,0.5])          # initial guess

def obj(x):
    # I'm the objective function
    return dot(c,x)

def con(x):
    # I'm the inequality constraints
    return dot(A,x) - b

print fmin(obj,x,f_ieqcons=con)

Answer 2

Я думаю, что вы должны смотреть на scipy.optimize - он вполне с удовольствием справится с массивами numpy и, как правило, довольно быстрый.См. Ref http://docs.scipy.org/doc/scipy-0.8.x/reference/tutorial/optimize.html

Если у вас есть входной вектор A , который определяет количество каждого ингредиента, и матрица ингредиентов I , которая указывает цену и питательные вещества.значения каждого ингредиента, то AI должны дать вам общую цену и питательную ценность данной смеси.

Теперь вам нужна функция оценки, которая нормализует A (умножаетэто наименьшая возможная константа, так что все значения питательных веществ являются, по крайней мере, их минимальными необходимыми значениями) и возвращает общую цену, плюс крутое наказание за любое количество питательного вещества сверх максимального значения, плюс меньшее наказание за большое количество ингредиентов.Затем оптимизатор играет с A (сохраняя все значения> = 0), чтобы минимизировать результат функции оценки.