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?

6
  • 4
    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
  • 3
    @Deer Hunter: I hope I never come within less than 10 miles of that cultivation facility... Jul 11, 2013 at 8:12
  • 6
    FOOF!
    – Bobson
    Jul 11, 2013 at 14:25
  • 2
    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
  • 2
    "mushrooms" -> as in the clouds of same shape?
    – Maciej
    Jul 11, 2013 at 20:58

2 Answers 2

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.

2
  • 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). Jul 11, 2013 at 7:39
  • Fixed That Issue
    – user28988
    Jul 12, 2013 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.

6
  • 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, 2013 at 7:50
  • Right, I forgot about that. Jul 11, 2013 at 7:50
  • 1
    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.
    – canisrufus
    Jul 12, 2013 at 19:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.