Zuordnungsproblem bei der linearen Programmierung: Einführung und Zuweisungsmodell

Das Zuordnungsproblem ist eine spezielle Art des linearen Programmierproblems, das die Zuordnung der verschiedenen Ressourcen zu den verschiedenen Aktivitäten eins zu eins behandelt. Es tut dies so, dass die Kosten oder der Zeitaufwand für den Prozess minimal sind und der Gewinn oder Verkauf maximal ist. Probleme können zwar mit der Simplex-Methode oder mit der Transportmethode gelöst werden, das Zuweisungsmodell bietet jedoch einen einfacheren Ansatz für diese Probleme.

In einer Fabrik kann ein Supervisor sechs Arbeiter zur Verfügung haben und sechs Arbeitsplätze abfeuern. Er muss entscheiden, welche Arbeit für welchen Arbeitnehmer vorgesehen ist. Problem bildet eins zu eins Basis. Dies ist ein Zuordnungsproblem.

1. Zuweisungsmodell:

Angenommen, es gibt n erleichtert und n Jobs ist klar, dass es in diesem Fall n Zuweisungen gibt. Jede Einrichtung oder jeder Arbeitnehmer kann jede Aufgabe einzeln ausführen. Es sollte jedoch ein bestimmtes Verfahren geben, nach dem die Zuweisung erfolgen sollte, um den Gewinn zu maximieren oder die Kosten oder die Zeit zu minimieren.

In der Tabelle ist Coij als die Kosten definiert, wenn ein Job dem Arbeiter zugewiesen wird. Es sei hier darauf hingewiesen, dass dies ein Sonderfall des Transportproblems ist, wenn die Anzahl der Zeilen der Anzahl der Spalten entspricht.

Mathematische Formulierung:

Jede mögliche Lösung eines Zuordnungsproblems besteht aus (2n - 1) Variablen, bei denen die (n - 1) Variablen Null sind, n die Anzahl der Jobs oder die Anzahl der Einrichtungen ist. Aufgrund dieser hohen Entartung wird das Problem mit üblichen Transportmethoden komplex und zeitaufwändig. Somit wird eine eigene Technik dafür abgeleitet. Bevor Sie zur absoluten Methode gehen, ist es sehr wichtig, das Problem zu formulieren.

Angenommen, x jj ist eine Variable, die als definiert ist

1, wenn der i- te Job der j- ten Maschine oder Einrichtung zugeordnet ist

0, wenn der i- te Job keiner Maschine oder Einrichtung zugeordnet ist.

Nun, da das Problem eins zu eins bildet oder ein Job einer Anlage oder Maschine zugeordnet werden soll.

Die gesamten Auftragskosten werden durch angegeben

Die obige Definition kann wie folgt in ein mathematisches Modell entwickelt werden:

Bestimmen Sie x ij > 0 (i, j = 1, 2, 3… n) um

Einschränkungen unterliegen

und xij ist entweder null oder eins.

Methode zur Lösung des Problems (ungarische Technik):

Betrachten Sie die Zielfunktion des Minimierungstyps. Die folgenden Schritte betreffen die Lösung dieses Zuordnungsproblems:

1. Suchen Sie die kleinste Kostenart in jeder Zeile der angegebenen Kostentabelle, beginnend mit der ersten Zeile. Dieses kleinste Element wird nun von jedem Element dieser Zeile subtrahiert. Wir erhalten also in jeder Zeile dieser neuen Tabelle mindestens eine Null.

2. Nachdem Sie die Tabelle erstellt haben (wie in Schritt-1), nehmen Sie die Spalten der Tabelle. Beginnen Sie mit der ersten Spalte, und suchen Sie nach der kleinsten Kostenart in jeder Spalte. Ziehen Sie nun dieses kleinste Element von jedem Element dieser Spalte ab. Nachdem Sie Schritt 1 und Schritt 2 ausgeführt haben, erhalten Sie in jeder Spalte der reduzierten Kostentabelle mindestens eine Null.

3. Nun werden die Zuweisungen für die reduzierte Tabelle auf folgende Weise vorgenommen.

(i) Zeilen werden nacheinander geprüft, bis die Zeile mit genau einer (einer) Null gefunden wird. Die Zuordnung zu dieser einzelnen Null erfolgt durch Anordnen des Quadrats □ und in der entsprechenden Spalte werden alle anderen Nullen durchgestrichen (x), da diese nicht für andere Zuweisungen in dieser Spalte verwendet werden. Schritt wird für jede Zeile ausgeführt.

(ii) Schritt 3 (i) wird nun an den Spalten wie folgt durchgeführt: - Die Spalten werden nacheinander untersucht, bis eine Spalte mit genau einer Null gefunden wird. Nun wird die Zuordnung zu dieser einzelnen Null durch Platzieren des Quadrats vorgenommen. Gleichzeitig werden alle anderen Nullen in den entsprechenden Zeilen (x) für jede Spalte durchgestrichen.

(iii) Schritt 3, (i) und 3 (ii) werden wiederholt, bis alle Nullen entweder markiert oder durchgestrichen sind. Wenn nun die Anzahl der markierten Nullen oder die vorgenommenen Zuweisungen gleich der Anzahl der Zeilen oder Spalten sind, wurde eine optimale Lösung erreicht. Es gibt genau eine einzelne Zuweisung in jeder oder in jeder Spalte ohne Zuweisung. In diesem Fall fahren wir mit Schritt 4 fort.

4. Zeichnen Sie zu diesem Zeitpunkt die Mindestanzahl von Zeilen (horizontal und vertikal), die erforderlich ist, um alle Nullen in der in Schritt 3 erhaltenen Matrix abzudecken. Das folgende Verfahren wird angewendet:

(i) Häkchen (

) alle Zeilen, die keine Zuordnung haben.

(ii) Jetzt Häkchen (

) alle diese Spalten mit Nullen in den markierten Zeilen.

(iii) Markieren Sie nun alle Zeilen, die noch nicht markiert sind und die in den markierten Spalten eine Zuordnung haben.

(iv) Alle Schritte, dh (4 (i), 4 (ii), 4 (iii) werden wiederholt, bis keine Zeilen oder Spalten mehr markiert werden können.

(v) Zeichnen Sie nun gerade Linien, die alle nicht markierten Zeilen und markierten Spalten durchlaufen. Es kann auch bemerkt werden, dass in einer nxn-Matrix immer weniger als 'n'-Zeilen alle Nullen abdecken, wenn sich zwischen ihnen keine Lösung befindet.

5. Wenn in Schritt 4 die Anzahl der gezogenen Linien gleich n oder die Anzahl der Zeilen ist, ist dies die optimale Lösung, falls nicht, dann weiter mit Schritt 6.

6. Wählen Sie das kleinste Element unter allen nicht abgedeckten Elementen aus. Nun wird dieses Element von allen nicht abgedeckten Elementen abgezogen und zu dem Element addiert, das am Schnittpunkt zweier Linien liegt. Dies ist die Matrix für neue Aufgaben.

7. Wiederholen Sie den Vorgang ab Schritt (3), bis die Anzahl der Zuweisungen der Anzahl der Zeilen oder der Anzahl der Spalten entspricht.