Grundsätzliche Struktur von Assignment Problems
(nicht formal)
In der Regel Kostenminimierungsprobleme
Setting:
Wir wollen ein Set von Objekten einem anderen Set von Objekten zuordnen
Für diese Zuordnung fallen Kosten an
Ziel:
Zuordnung mit minimalen Kosten zu finden
Constraints:
Assignment constraint
(z.B. muss ein komplettes Set dem anderen zugeteilt werden)
Capacity constraint
(beim Zuteilen darf die Kapazität nicht überschritten werden)
Modelierung grundsätzlicher Assignment Problems:
Ein Set von n Personen
Ein Set von m Maschinen
Assignment costs
Minimierung der Assignment Costs
An jeder Maschine muss gearbeitet werden
Es können nicht mehrere Personen an einer Maschine gleichzeitig arbeiten
Wie wird grundsätzlich modeliert, dass nur eine Alternative ausgewählt werden soll?
Wie wird grundsätzlich modeliert, dass maximal eine Alternative ausgesucht wird?
Wie wird grundsätzlich modeliert, dass mindestens eine Alternative ausgewählt wird?
Vertex coloring problem - Modeliere
Ungerichteter Graph G = (V, E)
Alle vertices sollen eingefärbt werden
für jeden Vertix soll genau eine Farbe aus dem Farben Set C gewählt werden
banchbarte Vertices sollen andere Farben erhalten
Die Anzahl der verwendeten Farben soll minimiert werden
Courses with limited enrollment - Model
Courses with limited enrollment, Modification - Model
Transportation Problem - Model
Minimum Cost Network Flows - Model
Sudoku - Model
Zuteilung der Zahlen 1 bis 9 in einer Reihe, in einer Spalte, in einem Raser
Last changeda year ago
