# What class of problem is this, and what math do I need to know to solve it?

Mushroom cultivation requires fairly precise chemical composition of substrate (a.k.a. growing medium). Let's pretend we're growing shitakes and that this is the required composition of their substrate:

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

We want to create an appropriate substrate from materials we have on hand which we know the chemical composition of.

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

How does one calculate this? It reminds me of solving matrices in high school. Is this something that can be done with matrices? What is this problem called? What do I need to know to solve it?

• Mmmm. Veery nice shitakes you've got with benzene and toluene and O2F2. Hope I don't ever come across them in a restaurant... Jul 11, 2013 at 5:56
• @Deer Hunter: I hope I never come within less than 10 miles of that cultivation facility... Jul 11, 2013 at 8:12
• FOOF! Jul 11, 2013 at 14:25
• This problem gets even more interesting if you'd have to take into account the current price of apples and oranges.
– Ingo
Jul 11, 2013 at 14:33
• "mushrooms" -> as in the clouds of same shape? Jul 11, 2013 at 20:58

## 2 Answers

This is called Linear Programming. It is NP-Hard for integer constraints but there are methods of dealing with this, see Jeff Erickson's notes on the subject. The most common method is know as the Simplex Algorithm.

Basically you're finding the vertices of shapes formed geometrically by the linear equations representing your constraints. You proceed till you find the optimal one. In this case, the ratio of needed substrate components.

• Linear Programming is actually not known to be NP-hard, it can be solved in polynomial time. It only gets hard if you add integrality constraints (e.g., you don't want 3.7 apples, but it must be a whole number). Jul 11, 2013 at 7:39
• Fixed That Issue
– user28988
Jul 12, 2013 at 22:43

Edit: this does not work, see comments

Since you have no inequalities and no cost minimization here, you don't actually need linear programming, you can just solve it as a system of linear equations. E.g. apples+oranges=1, 0.05*apples+0.20*oranges=0.05 etc.

• As long as the system solutions don't give negative fractions (e.g. mix in -22% of apples and +122% of oranges to make up 100% ...) Indeed, system of linear equations give some candidates (interior solutions?) but then edge cases need to be checked as well. Jul 11, 2013 at 7:50
• Right, I forgot about that. Jul 11, 2013 at 7:50
• An LP formulation would work well, since it could include the restriction that all quantities are positive. Jul 11, 2013 at 7:52
• Changes are that cost minimization with respect to apple/orange price ratio would be the next step in the evolution of this program.
– Ingo
Jul 11, 2013 at 14:34
• @Ingo Yeah, you're right; I hadn't thought that far when I asked the question. That will be step two. Jul 12, 2013 at 19:59