Das Anweisungsproblem ist eines der grundsätzlichen kombinatorischen Optimierungsprobleme im Zweig der Optimierung oder Operationsforschung in der Mathematik. Es besteht daraus, ein maximales Gewicht zu finden, das in einem belasteten zweiteiligen Graphen zusammenpasst.

In seiner allgemeinsten Form ist das Problem wie folgt:

:There sind mehrere Agenten und mehrere Aufgaben. Jedes Reagenz kann damit beauftragt werden, jede Aufgabe durchzuführen, einige Kosten übernehmend, die sich abhängig von der Anweisung der Agent-Aufgabe ändern können. Es ist erforderlich, alle Aufgaben durch das Zuweisen genau eines Reagenzes jeder Aufgabe auf solche Art und Weise durchzuführen, dass die Gesamtkosten der Anweisung minimiert werden.

Wenn die Zahlen von Agenten und Aufgaben gleich sind und die Gesamtkosten der Anweisung für alle Aufgaben der Summe der Kosten für jeden Agenten gleich sind (oder die Summe der Kosten für jede Aufgabe, die dasselbe Ding in diesem Fall ist), dann wird das Problem das geradlinige Anweisungsproblem genannt. Allgemein, wenn es vom Anweisungsproblem ohne jede zusätzliche Qualifikation dann spricht, wird das geradlinige Anweisungsproblem gemeint.

Algorithmen und Generalisationen

Der ungarische Algorithmus ist einer von vielen Algorithmen, die ausgedacht worden sind, die das geradlinige Anweisungsproblem innerhalb der Zeit beheben, die durch einen polynomischen Ausdruck der Zahl von Agenten begrenzt ist.

Das Anweisungsproblem ist ein spezieller Fall des Transport-Problems, das ein spezieller Fall des minimalen Kostenfluss-Problems ist, das der Reihe nach ein spezieller Fall eines geradlinigen Programms ist. Während es möglich ist, einige dieser Probleme mit dem Simplexalgorithmus zu beheben, ließ jede Spezialisierung effizientere Algorithmen entwerfen, um seine spezielle Struktur auszunutzen. Wenn die Kostenfunktion quadratische Ungleichheit einschließt, wird es das quadratische Anweisungsproblem genannt.

Beispiel

Nehmen Sie an, dass ein Taxi-Unternehmen drei Taxis (die Agenten) verfügbar, und drei Kunden (die Aufgaben) Wunsch hat, so bald wie möglich aufgenommen zu werden. Das Unternehmen ist auf schnelle Erholungen stolz, so für jedes Taxi werden die "Kosten", einen besonderen Kunden aufzunehmen, von der für das Taxi genommenen Zeit abhängen, um den Erholungspunkt zu erreichen. Die Lösung des Anweisungsproblems wird darin bestehen, welch auch immer die Kombination von Taxis und Kunden auf die am wenigsten Gesamtkosten hinausläuft.

Jedoch kann das Anweisungsproblem eher flexibler gemacht werden, als es zuerst erscheint. Im obengenannten Beispiel, nehmen Sie an, dass es vier Taxis verfügbar, aber noch nur drei Kunden gibt. Dann kann eine vierte Scheinaufgabe erfunden, vielleicht genannt werden "stillsitzend, nichts", mit Kosten 0 für das ihm zugeteilte Taxi tuend. Das Anweisungsproblem kann dann auf die übliche Weise behoben werden und noch die beste Lösung des Problems geben.

Ähnliche Streiche können gespielt werden, um mehr Aufgaben zu erlauben als Agenten, Aufgaben, denen vielfache Reagenzien zugeteilt werden müssen (zum Beispiel wird eine Gruppe von mehr Kunden als ein Taxi einfügen), oder Gewinn maximierend, anstatt Kosten zu minimieren.

Formelle mathematische Definition

Die formelle Definition des Anweisungsproblems (oder geradlinigen Anweisungsproblems) ist

:Given zwei Sätze, A und T, der gleichen Größe, zusammen mit einem Gewicht fungieren C: × T → R. Finden Sie eine Bijektion f: → T solch dass die Kostenfunktion:

:is minimiert.

Gewöhnlich wird die Gewicht-Funktion als eine reellwertige Quadratmatrix C angesehen, so dass die Kostenfunktion als niedergeschrieben wird:

Das Problem ist "geradlinig", weil die Kostenfunktion, sowie alle Einschränkungen optimiert zu werden, nur geradlinige Begriffe enthält.

Das Problem kann als ein geradliniges Standardprogramm mit der objektiven Funktion ausgedrückt werden

unterwerfen Sie den Einschränkungen

Die Variable vertritt die Anweisung von Reagenz zur Aufgabe, Wert 1 nehmend, wenn die Anweisung getan wird und 0 sonst. Diese Formulierung erlaubt auch variable Bruchwerte, aber es gibt immer eine optimale Lösung, wo die Variablen Werte der ganzen Zahl nehmen. Das ist, weil die Einschränkungsmatrix völlig unimodular ist. Die erste Einschränkung verlangt, dass jedes Reagenz genau einer Aufgabe zugeteilt wird, und die zweite Einschränkung verlangt, dass jede Aufgabe genau ein Agent zugeteilt wird.

Siehe auch

• Problem von Monge-Kantorovich, eine allgemeinere Formulierung
• Stabiles Ehe-Problem
• Versteigerungsalgorithmus
• Verallgemeinertes Anweisungsproblem
• Geradliniges Engpass-Anweisungsproblem
• Quadratisches Anweisungsproblem
• Waffenzielanweisungsproblem

Weiterführende Literatur