Was für ein Problem ist das und welche Mathematik muss ich wissen, um es zu lösen?

18

Die Kultivierung von Pilzen erfordert eine ziemlich genaue chemische Zusammensetzung des Substrats (auch als Wachstumsmedium bekannt). Stellen wir uns vor, wir bauen Shitakes an und das ist die erforderliche Zusammensetzung ihres Substrats:

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

Wir wollen ein geeignetes Substrat aus Materialien herstellen, die wir zur Hand haben und deren chemische Zusammensetzung wir kennen.

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

Wie berechnet man das? Es erinnert mich an das Lösen von Matrizen in der High School. Kann man das mit Matrizen machen? Wie heißt dieses Problem? Was muss ich wissen, um es zu lösen?

canisrufus
quelle
4
Mmmm. Sehr schöne Scheiße mit Benzol und Toluol und O2F2. Hoffe, ich habe sie nie in einem Restaurant gesehen ...
Deer Hunter
3
@ Deer Hunter: Ich hoffe, dass ich nie weniger als 10 Meilen von dieser Kultivierungsanlage entfernt bin ...
Michael Borgwardt
6
FOOF !
Bobson
2
Dieses Problem wird noch interessanter, wenn Sie den aktuellen Preis für Äpfel und Orangen berücksichtigen müssen.
Ingo
2
"Pilze" -> wie in den Wolken gleicher Form?
Maciej

Antworten:

27

Dies wird als lineare Programmierung bezeichnet . Es ist NP-schwer für ganzzahlige Bedingungen, aber es gibt Methoden, um damit umzugehen, siehe Jeff Ericksons Anmerkungen zu diesem Thema. Die gebräuchlichste Methode ist der Simplex-Algorithmus .

Grundsätzlich finden Sie die Eckpunkte von Formen, die geometrisch durch die linearen Gleichungen gebildet werden, die Ihre Abhängigkeiten darstellen. Sie fahren fort, bis Sie die optimale gefunden haben. In diesem Fall ist das Verhältnis der benötigten Substratkomponenten.

Weltingenieur
quelle
9
Die lineare Programmierung ist eigentlich nicht als NP-hart bekannt, sondern kann in polynomialer Zeit gelöst werden. Es wird nur schwierig, wenn Sie Integritätsbeschränkungen hinzufügen (z. B. möchten Sie keine 3.7-Äpfel, aber es muss eine ganze Zahl sein).
Falk Hüffner
Problem behoben
World Engineer
4

Bearbeiten: Dies funktioniert nicht, siehe Kommentare

Da Sie hier keine Ungleichungen und keine Kostenminimierung haben, brauchen Sie eigentlich keine lineare Programmierung. Sie können sie einfach als lineares Gleichungssystem lösen . ZB Äpfel + Orangen = 1, 0,05 * Äpfel + 0,20 * Orangen = 0,05 usw.

Falk Hüffner
quelle
Solange die Systemlösungen keine negativen Brüche ergeben (z. B. -22% Äpfel und + 122% Orangen zu 100% einrühren ...), ergeben lineare Gleichungssysteme tatsächlich einige Kandidaten (Innenraumlösungen?) Dann müssen aber auch Randfälle geprüft werden.
Rwong
Richtig, das habe ich vergessen.
Falk Hüffner
1
Eine LP-Formulierung würde gut funktionieren, da sie die Einschränkung enthalten könnte, dass alle Mengen positiv sind.
Kevin Cline
Änderungen bestehen darin, dass die Kostenminimierung in Bezug auf das Preisverhältnis Apfel / Orange der nächste Schritt in der Entwicklung dieses Programms wäre.
Ingo
@Ingo Ja, du hast recht; Ich hatte nicht so weit gedacht, als ich die Frage stellte. Das wird der zweite Schritt sein.
Canisrufus