18

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?

canisrufus
  • 1,091
  • 7
  • 17

2 Answers2

27

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.

  • 9
    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 07:39
  • Fixed That Issue –  Jul 12 '13 at 22:43
4

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.

Falk Hüffner
  • 176
  • 3
  • 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 07:50
  • Right, I forgot about that. – Falk Hüffner Jul 11 '13 at 07:50
  • 1
    An LP formulation would work well, since it could include the restriction that all quantities are positive. – kevin cline Jul 11 '13 at 07: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
  • Falk, it works very well for the question as I posed it, and it's actually how I'm going to implement it for starters. I'm watching the Strang MIT series on linear algebra to get some more background, but it looks like I can just plug these into NumPy as matrices and have a decently high success rate. Given my current level of math education I'm finding LP kind of mind bending. – canisrufus Jul 12 '13 at 21:21