Что это за проблема, и какую математику мне нужно знать, чтобы ее решить?

18

Для выращивания грибов требуется достаточно точный химический состав субстрата (иначе говоря, среда для выращивания). Давайте представим, что мы выращиваем шитаке и что это необходимый состав их субстрата:

Nitrogen | Benzene | Toluene | Dioxygen Diflouride
5%       | 5%      | 10%     | 80%

Мы хотим создать подходящую подложку из материалов, которые у нас есть под рукой, химический состав которых мы знаем.

Material | Nitrogen | Benzene | Toluene | Dioxygen Diflouride
apples   | 5%       | 0%      | 5%      | 90%
oranges  | 20%      | 20%     | 50%     | 10%
Etc...

Как рассчитать это? Это напоминает мне о решении матриц в средней школе. Это то, что можно сделать с помощью матриц? Как называется эта проблема? Что мне нужно знать, чтобы решить это?

canisrufus
источник
4
Мммм. Очень приятные дерьмо с бензолом, толуолом и O2F2. Надеюсь, я никогда не сталкивался с ними в ресторане ...
Охотник на оленей
3
Охотник на оленей: Я надеюсь, что никогда не окажусь на расстоянии менее 10 миль от этого места для совершенствования ...
Майкл Боргвардт
6
FOOF !
Бобсон
2
Эта проблема становится еще интереснее, если принять во внимание текущую цену на яблоки и апельсины.
Инго
2
«грибы» -> как в облаках одинаковой формы?
Мацей

Ответы:

27

Это называется линейным программированием . Это NP-Hard для целочисленных ограничений, но есть способы борьбы с этим, см. Заметки Джеффа Эриксона на эту тему. Наиболее распространенный метод известен как Симплексный алгоритм .

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

Мировой инженер
источник
9
Линейное программирование на самом деле не является NP-сложным, оно может быть решено за полиномиальное время. Это становится трудным, только если вы добавляете ограничения целостности (например, вы не хотите 3.7 яблок, но это должно быть целое число).
Фальк Хюффнер
Исправлена ​​эта проблема
мировой инженер
4

Изменить: это не работает, см. Комментарии

Поскольку здесь нет неравенств и минимизации затрат, вам не нужно линейное программирование, вы можете просто решить его как систему линейных уравнений . Например, яблоки + апельсины = 1,05 * яблоки + 0,20 * апельсины = 0,05 и т. Д.

Фальк Хюффнер
источник
Пока системные решения не дают отрицательных фракций (например, смешайте в -22% яблок и + 122% апельсинов, чтобы составить 100% ...) Действительно, система линейных уравнений дает некоторых кандидатов (внутренние решения?) но тогда крайние случаи должны быть проверены также.
Rwong
Хорошо, я забыл об этом.
Фальк Хюффнер
1
Формулировка LP будет работать хорошо, так как она может включать ограничение, что все количества являются положительными.
Кевин Клайн
Изменения заключаются в том, что минимизация затрат по отношению цены на яблоко / апельсин станет следующим шагом в развитии этой программы.
Инго
@ Инго Да, ты прав; Я не думал так далеко, когда я задал вопрос. Это будет второй шаг.
canisrufus