Das Zuordnungsproblem ist ein klassisches Problem aus dem Bereich der linearen Programmierung. Wenn beispielsweise n Jobs innerhalb einer Produktionsschicht auf m Maschinen gefertigt werden müssen müssen die Jobs den Maschinen optimal zugewiesen werden. In diesem Fall möchten Sie möglicherweise die anfallenden Herstellungskosten reduzieren und daher den kostenoptimalen Produktionsplan finden. In diesem Beispiel besteht die Einschränkung darin, dass jede Maschine während der bevorstehenden Schicht nur einen Auftrag erfüllen kann. Alle Jobs müssen geplant werden, d.h. Jobs müssen einer Maschine zugewiesen werden.

Das Problem kann in einem mathematischen Modell angegeben werden. Im Folgenden wird das Problem für einen Fall angegeben, in dem 3 Jobs und 3 Maschinen vorhanden sind. Die Kosten für die Herstellung von Auftrag 1 auf Maschine ebtragen 1 USD, aber 2 USD für die Herstellung von Auftrag 2 auf Maschine 2. Auftrag 2 kostet 2 USD auf Maschine 1 und 3 USD auf Maschine 2. Auftrag 3 kostet 5 USD auf Maschine 1 und 1 USD auf Maschine 2. Maschine 3 kann Job 1 für 2 USD und Job 2 für 3 USD ausführen.

Das mathematische Modell hierfür sieht dann wie folgt aus:

Wir können dieses Problem mit dem lpSolve-Paket in R modellieren und lösen, einem Paket für lineare Optimierung (für kontinuierliche und ganzzahlige Probleme). Die Funktion lp.assign kann das Problem lösen:

library(lpSolve)

# Bereite die Kostenmatrix vor
cost.mat <- rbind(c(1,2,3),
                     c(2,3,3),
                     c(5,1,3))

# Modell erstellen und mit lp.assign lösen
solution <- lp.assign(cost.mat=cost.mat,
                      direction="min")

lp.assign ist eine Funktion, die speziell zur Lösung des Zuweisungsproblems gedacht ist. Das Zuweisungsproblem ist per Definition ein Problem, bei dem alle Entscheidungsvariablen ganzzahlige Variablen sind. Wir müssen lp.assign daher nicht ausdrücklich mitteilen, dass die Entscheidungsvariablen als ganzzahlige Variablen betrachtet werden müssen.

Was sind denn also nun die minimalen Kosten für das vorliegende Problem? Wir können uns die Lösung anzeigen lassen:

solution

## Success: the objective function is 5

Die minimalen Kosten sind also 5 USD. Und was ist der dazugehörende Produktionsplan? Hier ist die Lösung:

solution$solution

##      [,1] [,2] [,3]
## [1,]    1    0    0
## [2,]    0    0    1
## [3,]    0    1    0

Linnart Felkl

Wirtschaftsingenieur mit Interesse an Optimierung, Simulation und mathematischer Modellierung in R, SQL, VBA und Python