imported>Thomas Dresler: Format

2025-07-01T22:05:32Z

Format

Neue Seite

Das (lineare) '''Zuordnungsproblem''' ist ein diskretes [[Optimierungsproblem]] aus der [[Graphentheorie]]. Es ist ein spezielles klassisches [[Transportproblem]] und findet Anwendung in der [[Operations Research]].

Es kann mittels [[Ganzzahlige lineare Optimierung|ganzzahliger linearer Optimierung]] oder mithilfe der [[Ungarische Methode|Ungarischen Methode]] gelöst werden.

== Problembeschreibung==
Es kann wie folgt verbal formuliert werden:

Einer Anzahl von <math>n</math> Arbeitern soll die gleiche Anzahl Tätigkeiten bei bekannten (Ausführungs-)Kosten zugeordnet werden, wobei sich die Ausführungskosten von Arbeiter zu Arbeiter und von Aufgabe zu Aufgabe unterscheiden.
* Jedem Arbeiter wird genau eine Tätigkeit zugeordnet und jede Tätigkeit wird von genau einem Arbeiter ausgeführt.
* Anschließend wird unter allen zulässigen Plänen der kostenminimale [[Arbeitsplan]] gewählt.

== Mathematisches Modell ==
=== Graphentheoretische Beschreibung ===
Es sei ein bipartiter, gewichteter Graph <math>G = (L\cup R,E)</math> mit <math>|L|=|R|=n</math> gegeben. Zwischen allen Knoten <math> l\in L, r\in R</math> existiert je eine Kante, deren Gewicht die Kosten repräsentiert, die entstehen, wenn man <math>l</math> und <math>r</math> [[Matching (Graphentheorie)|matcht]].

Ziel ist es nun, ein maximales Matching mit minimalen Kosten zu finden.

=== Matrixdarstellung ===
Anlehnend an die Problembeschreibung können wir eine <math>n\times n</math> Matrix <math>A\in\mathbb{R}^{n,n}</math> erzeugen, indem wir in die Zelle <math>a_{i,j}</math> die Kosten eintragen, die entstehen, wenn wir dem Arbeiter <math>i</math> die Aufgabe <math>j</math> zuordnen.

Das Ziel ist es dann, eine [[Permutation]] der Zeilen der Matrix zu finden, die deren [[Spur (Mathematik)|Spur]] minimiert.

=== Beschreibung als lineares Programm ===

Mit den (zu bestimmenden) Variablen <math>x_{ij}</math>
:<math>x_{ij}=\begin{cases}
1, & \text{falls Arbeiter i die Tätigkeit j ausführen soll}\\
0, & \text{sonst}
\end{cases}</math>
und den (gegebenen) Ausführungskosten <math>c_{ij}</math> ergibt sich das folgende mathematische Modell:

Minimiere die Kostensumme

:<math>F= \sum_{i=1}^n \sum_{j=1}^n c_{ij} x_{ij}</math>

unter den Nebenbedingungen

:<math>\sum_{j=1}^n x_{ij} = 1</math> für <math>i=1,\cdots ,n</math>,

:<math>\sum_{i=1}^n x_{ij} = 1</math> für <math>j=1,\cdots ,n</math>.

== Zeitkomplexität ==
Das Problem ist mithilfe der [[Ungarische Methode|Ungarischen Methode]] in <math>\mathcal{O}(n^3)</math> lösbar.

== Beispiele und Aufwand ==
Beispiele für das lineare Zuordnungsproblem sind die Zuordnung von Schülern zu Schulprojekten oder die Zuordnung von Studenten auf Seminarplätze.

Für durchgerechnete Beispiele siehe [[Ungarische_Methode#Beispiel_1|Ungarische Methode, Beispiele]].

== Verallgemeinerungen und Varianten ==
Beim Zuordnungsproblem handelt es sich um einen Spezialfall eines maximalen Matchings minimalen Gewichtes in einem bipartiten, gewichteten Graphen.

Sind statt absoluten Kosten nur relative Kosten bekannt, so handelt es sich um ein [[Stable Marriage Problem]].

== Literatur ==
* A. Bogatzki: ''Fabrikplanung: Verfahren zur Optimierung von Maschinenaufstellung.'' Diss. Universität Wuppertal 1998. Roderer, 1998, ISBN 3-89073-234-8.
* [[Wolfgang Domschke]], Andreas Drexl: ''Einführung in Operations Research''. Springer, 2011, ISBN 978-3-642-18111-5, S. 188ff. ({{Google Buch|BuchID=CuEgSZD6if8C|Seite=188|Linktext=Auszug (Google)|KeinText=ja}})

== Weblinks ==
* [http://www.mathe.tu-freiberg.de/~schreier/Transport/BUCH02.pdf Kapitel ''Transportoptimierung.''] (PDF; 516 kB). Skript TU Freiberg, S. 33–40.

[[Kategorie:Problem (Graphentheorie)]]
[[Kategorie:Kombinatorische Optimierung]]
[[Kategorie:Wirtschaftsmathematik]]
[[Kategorie:Optimierung]]

Zuordnungsproblem - Versionsgeschichte

imported>Thomas Dresler: Format