Algorithmus für Substrat Herstellung

[Kröte]

Hallo liebe Gemeinde,
ich habe folgendes Problem:

ich möchte aus einer Datenbank verschiedene Inhaltsstoffe auswählen und dann möglichst nah an meine vorgegebene Mischung rankommen. Hier ist es aber wichtig, dass gewisse Randbedingungen (min, max) erfüllt sein müssen.

Beispielsweise wenn ich sage ich möchte 100kg Substrat herstellen, was x% Zink, y% Nitrat, z% Calcium, p% Bor, q% Magnesium, r% Kupfer, s% Phosphor, t% Kalium, u% Eisen enthalten soll.

Dann wähle ich aus meiner Datenbank aus: ich möchte dieses Substrat aus Sand, Sägespänen, Perlit, Vermiculit, Kompost, Gartenkalk, Torf und Kokosfasern herstellen. Dann soll die Funktion in der Datenbank die einzelnen Nährstoffe abfragen und mir sagen wie ich am nächsten an das gewünschte Ergebnis heran komme. Hierfür sollten aber zuvor die Randbedingungen entfernt werden, denn zuviel oder zu wenig Nährstoffe dürfen in dem Substrat nicht enthalten sein.

ich stelle mir das script so in der art vor, wobei x ,y, z, g meine Inhaltsstoffe sind, und m und k mein gewünschtes Ergebnis.

Code: Alles auswählen

inhaltsstoffe = {x: {'m': 1, 'k': 4},
                 y: {'m': 3, 'k': 1},
                 z: {'m': 6, 'k': 7},
                 g: {'m': 4, 'k': 9}}

substrat_inha = {'x', 'y', 'z'}

substrat_soll = {'m': 2, 'k': 4}

# hier passiert die Magie [...]

results = {{'x': 0, 'y': 0, 'z': 0} -> {'m': 0, 'k': 0},
           {'x': 0, 'y': 0, 'z': 1} -> {'m': 1, 'k': 0},
           {'x': 0, 'y': 0, 'z': 2} -> {'m': 1, 'k': 0},
           {'x': 0, 'y': 0, 'z': 3} -> {'m': 1, 'k': 0},
           {'x': 0, 'y': 0, 'z': 4} -> {'m': 1, 'k': 0},
           {'x': 0, 'y': 0, 'z': 5} -> {'m': 1, 'k': 0},
           {'x': 0, 'y': 0, 'z': 6} -> {'m': 1, 'k': 0},
           {'x': 0, 'y': 0, 'z': 7} -> {'m': 1, 'k': 0},
           {'x': 0, 'y': 0, 'z': 8} -> {'m': 1, 'k': 0},
           {'x': 0, 'y': 1, 'z': 0} -> {'m': 0, 'k': 0},
           {'x': 0, 'y': 1, 'z': 1} -> {'m': 1, 'k': 0},
           {'x': 0, 'y': 1, 'z': 2} -> {'m': 1, 'k': 0},
           {'x': 0, 'y': 1, 'z': 3} -> {'m': 1, 'k': 0},
           {'x': 0, 'y': 1, 'z': 4} -> {'m': 1, 'k': 0},
           {'x': 0, 'y': 1, 'z': 5} -> {'m': 1, 'k': 0},
           {'x': 0, 'y': 1, 'z': 6} -> {'m': 1, 'k': 0},
           {'x': 0, 'y': 1, 'z': 7} -> {'m': 1, 'k': 0},
           {'x': 0, 'y': 1, 'z': 8} -> {'m': 1, 'k': 0},
           {'x': 0, 'y': 2, 'z': 0} -> {'m': 0, 'k': 0},
           {'x': 0, 'y': 2, 'z': 1} -> {'m': 1, 'k': 0},
           {'x': 0, 'y': 2, 'z': 2} -> {'m': 1, 'k': 0},
           {'x': 0, 'y': 2, 'z': 3} -> {'m': 1, 'k': 0},
           {'x': 0, 'y': 2, 'z': 4} -> {'m': 1, 'k': 0},
           {'x': 0, 'y': 2, 'z': 5} -> {'m': 1, 'k': 0},
           {'x': 0, 'y': 2, 'z': 6} -> {'m': 1, 'k': 0},
           {'x': 0, 'y': 2, 'z': 7} -> {'m': 1, 'k': 0},
           {'x': 0, 'y': 2, 'z': 8} -> {'m': 1, 'k': 0}}


print solution

Ich habe mal was von Kombinatorik mit mehreren Werten gelesen und auch mit linearer Optimierung. Was meint Ihr, was man hierfür am besten einsetzt?

Vielen Dank!
Kröte

[nezzcarth]

Zu exakten Lösungsverfahren können die mitlesenden Informatiker vielleicht etwas sagen. Ich löse derartige Aufgaben gerne mit heuristischen Verfahren, die sich an dem orientieren, was ich Mal über genetische/evolutionäre Algorithmen aufgeschnappt habe. Das würde für deine Aufgabe auch funktionieren. Wenn die Merkmalsmenge aber überschaubar ist, ist es vielleicht etwas Overkill.

[__deets__]

Das ist ewig her, das ich mal einen Simplex in Python implementiert habe... da faellt mir auf Anhieb nix mehr ein. Aber wenn man danach googelt, dann gibt's da doch was in scipy zB. Das wuerde ich dann halt mal probieren.