# 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... Commented Jul 11, 2013 at 5:56
• @Deer Hunter: I hope I never come within less than 10 miles of that cultivation facility... Commented Jul 11, 2013 at 8:12
• FOOF! Commented 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
Commented Jul 11, 2013 at 14:33
• "mushrooms" -> as in the clouds of same shape? Commented Jul 11, 2013 at 20:58

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). Commented Jul 11, 2013 at 7:39
• Fixed That Issue
– user28988
Commented 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. Commented Jul 11, 2013 at 7:50
• Right, I forgot about that. Commented Jul 11, 2013 at 7:50
• An LP formulation would work well, since it could include the restriction that all quantities are positive. Commented 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
Commented 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. Commented Jul 12, 2013 at 19:59