Zuordnungsproblem und Transportproblem

Ein Zuordnungsproblem verteilt Aufgaben so auf Personen, dass die Gesamtkosten möglichst klein sind. Ein Lieferdienst teilt zum Beispiel drei Fahrenden drei Touren zu und will möglichst wenig Sprit verbrauchen.

Jede Person fährt genau eine Tour, jede Tour wird von genau einer Person gefahren. Sie lösen das erst durch Probieren und lernen dann eine Verwandte kennen: das Transportproblem.

Drei Personen und drei Touren ergeben neun Zahlen. Jede Zahl sagt, was eine Person für eine Tour kostet, hier in Euro Sprit. Eine Tabelle dieser Zahlen heißt Kostenmatrix.

Eine Zuordnung gibt jeder Person genau eine Tour, und keine Tour kommt doppelt vor. Gesucht ist die Zuordnung mit der kleinsten Summe.

Bei drei Personen gibt es genau sechs Zuordnungen: Die erste Person hat drei Touren zur Wahl, die zweite noch zwei, die dritte eine. Das sind 3 mal 2 mal 1.

Sie berechnen die Summe jeder Zuordnung und nehmen die kleinste. Das ist sicher und für kleine Fälle schnell genug.

docker exec jupyter python3 -c "import itertools; c = [[4, 6, 9], [3, 9, 8], [7, 5, 6]]; print(min(sum(c[i][p[i]] for i in range(3)) for p in itertools.permutations(range(3))))"

docker exec jupyter python3 -c "from scipy.optimize import linear_sum_assignment; c = [[4, 6, 9], [3, 9, 8], [7, 5, 6]]; a, b = linear_sum_assignment(c); print(list(b), sum(c[i][b[i]] for i in range(3)))"

Person 1 nimmt die billigste Tour, Nord für 4 Euro. Person 2 muss dann Mitte oder Süd nehmen und wählt Süd für 8 Euro. Person 3 bleibt Mitte für 5 Euro. Zusammen sind das 17 Euro.

Die beste Zuordnung kostet 15 Euro. Person 1 gibt dafür Nord ab, damit Person 2 die billige Tour bekommt.

# Zwei Personen, zwei Touren. Kosten in Euro.
kosten = [[2, 3], [1, 8]]
# Gierig: Person 1 nimmt die billigere Tour, dann bleibt der Rest für Person 2.
erste_wahl = 0
if kosten[0][1] < kosten[0][0]:
    erste_wahl = 1
zweite_wahl = 1 - erste_wahl
gierig = kosten[0][erste_wahl] + kosten[1][zweite_wahl]
# Durchprobiert: beide Möglichkeiten.
moeglichkeit_a = kosten[0][0] + kosten[1][1]
moeglichkeit_b = kosten[0][1] + kosten[1][0]
print("Gierig:", gierig, "Euro")
print("Beste:", min(moeglichkeit_a, moeglichkeit_b), "Euro")
# Ändern Sie die 8 in 2 und starten Sie erneut.
# Sind gierig und beste Wahl jetzt gleich?

Zwei Lager liefern Paletten an drei Märkte. Jedes Lager hat ein Angebot, jeder Markt eine Nachfrage, und jede Strecke hat Kosten je Palette. Gesucht ist, wie viele Paletten auf jede Strecke kommen.

Das ist ein lineares Programm mit sechs Variablen. Die Summe jedes Lagers muss sein Angebot sein, die Summe jedes Marktes seine Nachfrage.

docker exec jupyter python3 -c "from scipy.optimize import linprog; r = linprog([4, 6, 9, 5, 3, 7], A_eq=[[1, 1, 1, 0, 0, 0], [0, 0, 0, 1, 1, 1], [1, 0, 0, 1, 0, 0], [0, 1, 0, 0, 1, 0], [0, 0, 1, 0, 0, 1]], b_eq=[30, 20, 10, 25, 15]); print(round(r.fun))"

Der Befehl gibt 265 aus. Die Gleichungen stehen in A_eq und b_eq, die Mengen sind die Variablen.

Bei einem Transportproblem mit ganzen Mengen kommen auch ganze Paletten heraus. Das ist nicht selbstverständlich, die letzte Lektion zeigt den Gegensatz.