# 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... – Deer Hunter Jul 11 '13 at 5:56
@Deer Hunter: I hope I never come within less than 10 miles of that cultivation facility... – Michael Borgwardt Jul 11 '13 at 8:12
FOOF! – Bobson Jul 11 '13 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 '13 at 14:33
"mushrooms" -> as in the clouds of same shape? – Maciej Jul 11 '13 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.

-
Thank you for the references! – canisrufus Jul 11 '13 at 1:29
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). – Falk Hüffner Jul 11 '13 at 7:39
Fixed That Issue – World Engineer Jul 12 '13 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. – rwong Jul 11 '13 at 7:50
Right, I forgot about that. – Falk Hüffner Jul 11 '13 at 7:50
An LP formulation would work well, since it could include the restriction that all quantities are positive. – kevin cline Jul 11 '13 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 '13 at 14:34
@Ingo Yeah, you're right; I hadn't thought that far when I asked the question. That will be step two. – canisrufus Jul 12 '13 at 19:59