Auf der Suche nach einem Algorithmus, um die Kosten von Kantenverfahren in einem zweiparteitigen Diagramm zu minimieren, das den Einschränkungen vorbehaltlich ist

Question

Ich habe einen Satz von Urnen, die jeweils unterschiedliche Sandmengen halten können. Die Porter können jeden URN mit einem Transportgebühr mit einer Transportgebühr pro Sandeinheit ausführen. Jeder Porter hat eine endliche Menge an Sand, die sie jeder Urne liefern kann. Ziel ist es, die URNs mit dem gesamten verfügbaren Sand zu füllen, während die Gesamtkosten minimiert werden. Hier ist ein motivierendes Beispiel:

schwarze Kreise zeigen Träger. Der Wert in der Mitte der Porterkreise zeigt die Gesamtmenge an Sand, die sie transportieren können. Graue Quadrate zeigen Urns. Der Wert in der Mitte der URNs zeigt die Menge an Sand, die eine Urne halten kann. Porter_urn-Kanten zeigen die Kosten des Transports 1 Sandeinheit an eine bestimmte Urne. Unter Verwendung dieses Beispiels könnte der Porter 1, der 100 Sandeinheiten aufweist, 1 ein Sandeinheit für eine Kosten von 50 bis URN 3 transportieren, was insgesamt 65 Sandeinheiten aufnehmen kann. Das wäre sehr teuer!

Gibt es einen Algorithmus, um dieses Optimierungsproblem zu lösen? Es scheint vielleicht ein Maximales Flow Problem oder vielleicht ein Multi-Rucksack Problem? Oder ein anderer Algorithmus von Operations Research?

Answer 1

Dies ist gerade ein Minimum-Kosten-Flow-Problem .Alles, was es fehlt, ist eine Kante von der Quelle zu jedem Porter mit Null-Kosten und Kapazität, die dem Porter entspricht, und eine Null-Kostenkante von jeder URN an der Spüle mit einer Kapazität, die der Urne entspricht.