3 Wichtige Instrumente der Operationsforschung
Dieser Artikel beleuchtet die drei wichtigen Instrumente der Operationsforschung. Die Werkzeuge sind: 1. Lineare Programmierung 2. Transportprobleme 3. Zuordnungsproblem.
Operations Research: Werkzeug # 1. Lineare Programmierung:
Die lineare Programmierung ist eine mathematische Technik, die auf fast alle Arten von Entscheidungsproblemen anwendbar ist. Diese Technik wird angewendet, um als beste Alternative aus einer Reihe realisierbarer Alternativen auszuwählen.
In LPP können sowohl Zielfunktionen als auch Einschränkungen als lineare mathematische Funktion ausgedrückt werden, die zur Lösung der praktischen Planungsprobleme verwendet werden können. Es ist eine Methode zur Untersuchung des Verhaltens von Systemen.
LP befasst sich hauptsächlich mit der Beschreibung des Zusammenhangs der Komponenten eines Systems. Diese Technik soll Managern bei der Planung, Entscheidungsfindung und der Zuteilung der Ressourcen helfen. Das Management hat immer die Tendenz, eine Organisationsressource am effektivsten zu nutzen. Zu den Ressourcen zählen Maschinenrohstoffe, Arbeitskräfte, Lager, Zeit und Geld.
Diese Ressourcen können zur Herstellung von Produkten verschiedener Arten verwendet werden, beispielsweise Maschinen, Teile / Komponenten, Möbel und Lebensmittelprodukte usw. In ähnlicher Weise können Ressourcen zur Bereitstellung von Dienstleistungen verwendet werden, wie beispielsweise Zeitplan für den Versand, Werbekonzepte und Investitionsentscheidungen.
Alle Organisationen müssen eine Entscheidung über die Zuweisung ihrer begrenzten Ressourcen treffen. Das Management muss daher ständig knappe Ressourcen bereitstellen, um die Organisationsziele / -ziele zu erreichen.
Das Adjektiv linear wurde verwendet, um eine Beziehung zwischen zwei oder mehr Variablen zu beschreiben. Bei der Programmierung geht es darum, bestimmte mathematische Gleichungen zu verwenden, um die bestmögliche Lösung für ein Problem mit begrenzten / knappen Ressourcen zu erhalten.
Daher wird die lineare Programmierung für Optimierungsprobleme verwendet, die folgende Bedingung erfüllen:
(i) Die zu optimierende Zielfunktion sollte gut definiert und als lineare Funktion von Variablen ausgedrückt werden.
(ii) Die Einschränkung im Hinblick auf das Erreichen dieser Ziele wird auch als lineare Qualitäten / Ungleichungen von Variablen ausgedrückt.
(iii) Einige alternative Vorgehensweisen sind ebenfalls verfügbar.
(iv) Die Entscheidungsvariablen sind miteinander verbunden und nicht negativ.
(v) Ressourcen sind begrenzt.
Anwendung der linearen Programmierung auf industrielle Probleme:
(i) Entwicklung von Zeitplänen für die Nahrungsmittelindustrie und für Erdölraffinerien usw.
(ii) In der metallverarbeitenden Industrie wird es zur Ladenbeladung und zur Entscheidung der Wahl zwischen dem Kauf und der Herstellung verschiedener Teile verwendet.
(iii) Es wird zur Bewertung verschiedener Eisenerze in der Eisen- und Stahlindustrie verwendet.
(iv) Es wird verwendet, um die Trimmverluste in Papierfabriken zu reduzieren.
(v) Es wird verwendet, um die optimale Weiterleitung von Nachrichten im Kommunikationsnetzwerk zu finden.
Lineare Programmierung Definition:
Die lineare Programmierung ist ein mathematisches Werkzeug / eine Technik zur Bestimmung der besten Nutzung der Ressourcen einer Organisation. Die lineare Programmierung soll Managern bei der Planung und Entscheidungsfindung helfen. Als Instrument der Entscheidungsfindung hat es seinen Wert in verschiedenen Bereichen wie der Produktion gezeigt. Marketingfinanzierung, Forschung und Personaleinsätze.
Ermittlung des optimalen Produktmixes, Zuordnung von Transportmappen zu Portfolioauswahlmaschinen; Anlagestandort, Arbeitsaufteilung usw. sind die wenigen Arten von Problemen, die mit Hilfe der linearen Programmierung gelöst werden können.
"Die Analyse von Problemen, bei denen eine lineare Funktion einer Anzahl von Variablen maximiert (oder minimiert) werden soll, wenn diese Variablen einer Anzahl von Beschränkungen in Form von linearen Gleichungen unterliegen.", Samuelson und Slow
Laut Loomba ist „die lineare Programmierung nur ein Aspekt eines sogenannten Systemansatzes für das Management, bei dem alle Programme hinsichtlich ihrer endgültigen Auswirkungen auf die Verwirklichung der Geschäftsziele entworfen und bewertet werden“.
Lineare Programmierprobleme - Grafische Methode:
Die Schritte der grafischen Methode können wie folgt zusammengefasst werden:
1. Formulieren Sie das lineare Programmierproblem.
2. Zeichnen Sie die angegebenen Randbedingungslinien als Gleichungen auf.
3. Identifizieren Sie anhand des obigen Diagramms den möglichen Lösungsbereich.
4. Suchen Sie die Eckpunkte der möglichen Lösungsregion.
5. Berechnen Sie den Wert der Zielfunktion an den Eckpunkten.
6. Wählen Sie nun den Punkt aus, an dem die Zielfunktion den optimalen Wert hat.
Lineare Programmierprobleme - Mathematische Lösung:
Die grafische Methode zur Lösung von LPP ist zwar ein wertvolles Hilfsmittel, um ihre Grundstruktur zu verstehen. Das Verfahren ist bei industriellen Problemen von begrenztem Nutzen, da die Anzahl der dort auftretenden Variablen sehr groß ist. Daher ist eine andere mathematische Lösung, die als Simplex-Methode bezeichnet wird, geeignet, LPP mit einer großen Anzahl von Variablen zu lösen.
Es ist ein iteratives Verfahren, das LPP entweder in einer endlichen Anzahl von Schritten löst oder einen Hinweis darauf gibt, dass es eine unbegrenzte Lösung für das Verfahren von L.PR gibt. Das Simplex-Verfahren ist ein algebraisches Verfahren zum Lösen linearer Programmierprobleme oder besteht aus einer Reihe sich wiederholender Schritte eine optimale Lösung erreichen.
Es ist ein am weitesten verbreiteter Programmieralgorithmus. Theoretisch kann dieses Verfahren jedes Problem lösen, das aus einer beliebigen Anzahl von Variablen und Einschränkungen besteht. Wenn das Problem aus mehr als drei Variablen und drei Einschränkungen besteht, ist die Verwendung eines Computers erforderlich. Abb. 31.9 zeigt die schematische Darstellung des Simplex-Algorithmus.
Verschiedene Schritte im Simplex-Verfahren:
Die Schritte dieses Verfahrens sind nachfolgend aufgeführt:
1. Formulieren Sie das Problem, indem Sie die Zielfunktion und die Nebenbedingungen bestimmen.
2. Wandeln Sie die Ungleichungen in Gleichungen um, um die Standardform zu erhalten, indem Sie Slack-Überschuss und künstliche Variablen in die Zielfunktion einführen.
3. Bereiten Sie die anfängliche Simplex-Tabelle vor.
4. Berechnen Sie den Wert für z j (Nettoverlust pro Einheit) und c j - z j (Nettobeitrag) für diese Lösung.
5. Bestimmen Sie die Eingabevariable (Schlüsselspalte), indem Sie die Spalte mit der negativsten Spalte auswählen
( zj - cj ).
6. Bestimmen Sie die Abweichungsvariable (Schlüsselzeile), indem Sie die Verhältnisspalte aus Regel 5 berechnen und den kleinsten nicht negativen Wert auswählen.
7. Berechnen Sie die Ersetzungszeile der verbesserten Simplex-Tabelle nach Regel 6.
8. Berechnen Sie die verbleibenden Zeilen der neuen Tabelle nach Regel 7.
9. Berechnen Sie den Wert c j und z j für diese Lösung.
10. Wenn der Wert nicht negativ ist (c j - z j ), kehren Sie zu Schritt 5 zurück.
11. Wenn keine nicht negativen Werte ( cj - zj ) vorhanden sind, wurde die optimale Lösung erhalten.
Beispiel 1:
Ein Landwirt hat 1000 Hektar Land, auf dem er Mais, Weizen oder Sojabohne verzehren kann. Jeder Hektar Mais kostet Rs. 100 für die Vorbereitung, erfordert 7 Mann Arbeitstage und erzielt einen Gewinn von Rs. 30 Hektar Weizen kostet Rs. Um sich vorzubereiten, benötigen Sie 10 Mann Arbeitstage und erzielen einen Gewinn von Rs. 40
Ein Morgen Sojabohnen kostet 70 Rs für die Vorbereitung 8 Arbeitstage und bringt einen Gewinn von Rs. 20 Wenn der Landwirt Rs hat. 100.000 für die Vorbereitung und zählen auf 8000 Arbeitstage. Wie viele Hektar sollte jeder Ernte zugeordnet werden, um den Gewinn zu maximieren? (Gujarat MBA, 1989)
Lösung:
Lassen Sie x Morgen Land für Mais zugeteilt werden
y Morgen Land für Weizen zugeteilt werden
Z Morgen Land für Sojabohne zugeteilt werden
Da jeder Morgen Land für Mais einen Gewinn von Rs ergibt. 30, für Weizenerträge Rs. 40 und für Sojabohnen Rs. 20. Die mathematische Formulierung des LLP lautet
Max Z = 30x + 40y + 20z + 0S 1, + OS 2, + 0S 3
Vorbehaltlich an
100 x + 120y + 70z ≤ 100000
7x + 10y + 8z ≤ 8000
x + y + z ≤ 1000
x, y, z ≥ 0
Lassen Sie uns die Ungleichungen in Gleichungen umwandeln, indem Sie Slack-Variablen S 1, S 2 und S 3 einführen. Die Zielfunktion und die Einschränkung können als geschrieben werden
In der Spalte mit den grundlegenden Variablen sind die Vektoren für die Variablen S 1, (1, 0, 0), S 2, (1, 0, 1) und S 3 (0, 0, 1). Die anfänglich durchführbare Lösung ist durch die Variablen S gegeben 1, S 2 und S 3 sind beide insgesamt Gewinn = 0
Nun werden Z j und C j - Z j nach Regel 1, 2 und 3 berechnet. Die Schlüsselspalte wird mit der Startmarkierten Spalte bestimmt und die Simplex-Tabelle II wird wie folgt vorbereitet.
Tabelle II bietet keine optimale Lösung. Wir fahren fort, um die einfache Tabelle III zu erstellen und die Lösung wie folgt zu verbessern:
Minimierungsproblem von Big M. Methode:
In der Industrie gibt es möglicherweise Standorte, an denen das Ziel bestehen kann, die Produktionskosten oder die Herstellungsdauer zu minimieren, dh die Zielfunktion muss minimiert werden. In solchen Fällen können wir auf dieselbe Weise wie ein Maximierungsproblem vorgehen, indem wir einfach mit beiden Seiten multiplizieren der objektiven Funktion durch-1 In solchen Situationen wird die Minimierung von Z die Maximierung von (-Z) sein.
Da in solchen Fällen die Überschussvariablen einen negativen Wert annehmen, der gegen die Nicht-Negativitätsbeschränkung verstößt, führen wir zur Beseitigung dieser Schwierigkeit eine neue Variable ein, die als künstliche Variablen bezeichnet wird.
Jetzt weisen wir Überschussvariablen einen Koeffizienten von 3000 und + künstliche Variablen mit + M zu. Damit künstliche Variablen nicht die Basisvariablen in der optimalen Lösung sind, weisen wir ihnen sehr hohe Kosten zu, weshalb M als sehr große Zahl definiert wird, dh großes M oder Strafe
Diese Methode wird mit Hilfe von Folgendem veranschaulicht:
Beispiel 2
Operations Research: Tool # 2. Transportprobleme:
Die Transportprobleme sind eine der Arten von LPP, bei der das Ziel besteht, Güter / Produkte in verschiedenen Mengen eines einzigen homogenen Artikels / Ware zu verschiedenen Bestimmungsorten zu transportieren, um die Gesamttransportkosten im täglichen Leben der verschiedenen produzierenden Organisationen oder anderer Einrichtungen zu minimieren Um verschiedene Aspekte zu berücksichtigen, lagern Sie Ihre Endprodukte oder Artikel an verschiedenen Orten ab, die als Ursprung oder Ware bezeichnet werden. Wenn die Belieferung an Benutzer erfolgen soll, werden die Artikel vom Ursprung zu einem oder mehreren Bestimmungsorten transportiert. Der allgemeine Zweck dieses Prozesses besteht in der Festlegung einer Vertriebsrichtlinie so dass die gesamten Transportkosten minimal sind oder die Zeit, die für die Umladung benötigt wird, minimal ist.
Nachdem nativ fertige Produkte aus der Anlage auf wirtschaftlichste Art und Weise in Transportprobleme zu Lagerhäusern transportiert werden sollen, können hier verschiedene Merkmale der linearen Programmierung beobachtet werden, wobei die Verfügbarkeit sowie die Anforderungen verschiedener Zentren begrenzt sind und die begrenzten Ressourcen die Transportprobleme der Spezialfälle darstellen der Simplex-Methode.
Anwendung in Ventilen der Transport von Produkten aus verschiedenen Quellen zu verschiedenen Zielorten wie:
(i) Transport von Einheiten, die das Ziel aufgerissen haben. Ziel ist es, die Transportkosten zu minimieren.
(ii) Maximierung des Gewinns beim Transport der Einheiten zum Bestimmungsort.
Die wichtigsten Schritte sind :
Schritt 1:
Formulieren Sie das Problem und richten Sie es in Form einer Transportmatrix ein.
Schritt 2:
Erhalten Sie die realisierbare Lösung.
Schritt 3:
Testen Sie die optimale Lösung.
Schritt 4:
Aktualisieren Sie die Lösung durch Erfolgsverbesserungen, bis die Transportkosten nicht weiter gesenkt werden.
Häufig verwendete Methoden sind:
1. Nordwest-Eckmethode.
2. Methode der geringsten Kosten.
3. Vogelsche Approximationsmethode.
An der North West Corner-Methode beteiligte Schritte:
Schritt 1:
Beschränken Sie eine leere Maximalmatrix mit Zeilen und Spalten.
Schritt 2:
Geben Sie die Zeilensummen und Spaltensummen am Ende an.
Schritt 3:
Beginnen Sie mit (11) an der Northwest-Ecke der Matrix, und weisen Sie die maximal mögliche Menge / Anzahl zu, wobei darauf zu achten ist, dass die Zuweisung weder über der von den jeweiligen Lagerhäusern benötigten Menge noch über der in den Versorgungszentren verfügbaren Menge liegen kann.
Schritt 4:
Gehen Sie nach der Anpassung der Angebots- und Nachfragezahlen in den entsprechenden Zeilen- und Spaltenzuweisungen zur ersten Zelle und wiederholen Sie den Schritt 3.
Schritt 5:
Nachdem die Anforderung der ersten Spalte erfüllt ist, wird die nächste Zelle in der zweiten Spalte und der ersten Zeile erstellt und mit Schritt 3 fortgefahren.
Schritt 6:
Wenn für ein beliebiges Zellenangebot sie gleich sind, kann die nächste Zuweisung in den Zellen der nächsten Zeilen und Spalten erfolgen.
Schritt 7:
Setzen Sie den Prozess fort, bis die gesamte verfügbare Menge den Zellen je nach Bedarf vollständig zugeordnet ist
Beispiel 3:
Lösen Sie das folgende Problem von NWCM, um die minimalen Transportkosten zu berechnen:
Schritte bei der Methode der niedrigsten Kosten:
Dieses Verfahren berücksichtigt die geringsten Kosten und benötigt daher weniger Zeit, um das Problem zu lösen. Die verschiedenen Schritte lauten wie folgt:
Schritt 1:
Wählen Sie aus allen Zeilen und Spalten in der Matrix die Zelle mit den niedrigsten Transportkosten aus. Weisen Sie so viel wie möglich zu, um entweder die Zeile oder Spalte zu entfernen, die entweder die Quelle erschöpft oder die Anforderung vollständig erfüllt. Wenn beide zufriedenstellend sind, entfernen Sie beide. Wenn die Zelle mit den kleinsten Kosten nicht eindeutig ist, wählen Sie beliebig eine Zelle mit den niedrigsten Kosten aus.
Schritt 2:
Wiederholen Sie den Vorgang für alle ungekreuzten Zeilen und Spalten mit der nächstkleinsten Kostenzelle. Schritt 3: Wiederholen Sie den Vorgang, bis alle Quellen erschöpft sind oder die Anforderungen aller Ziele erfüllt sind.
Beispiel 4:
Lösen Sie das folgende Problem mit der kostengünstigsten Methode:
Vogel-Näherungsverfahren:
Diese Methode ist eine Straf- oder Bedauerungsmethode und wird gegenüber den beiden anderen Methoden bevorzugt, wobei die anfänglich realisierbare Grundlösung entweder optimal oder sehr nahe an der optimalen Lösung erhalten wird, weshalb die zur Berechnung der optimalen Lösung erforderliche Zeit verringert wird.
Bei diesem Verfahren ist die Zuteilungsgrundlage eine Einheitskostenstrafe, dh die Zeile oder Spalte, die die höchste Einheitskostenstrafe / die Differenz zwischen den niedrigsten und den nächsthöheren Kosten angibt, wird zuerst zum Zwecke der Zuteilung ausgewählt. Auf diese Weise werden auch die nachfolgenden Zuordnungen in den anderen Zellen vorgenommen, wobei die höchsten Kosten für die Einheitskosten berücksichtigt werden.
Die Zuteilung wird vorgenommen, um die Strafkosten zu minimieren. Folgende Schritte sind erforderlich:
Schritt 1:
Berechnen Sie die Strafe für jede Zeile und Spalte, indem Sie lediglich die Differenz zwischen den kleinsten und nächstkleinsten Transportkosten in derselben Zeile und Spalte berechnen, dh die Differenz gibt die Strafe an, die zu zahlen ist, wenn die Zuweisung nicht zu den Mindestkosten erfolgt Kriterium.
Schritt 2:
Wählen Sie eine Zeile oder Spalte mit der höchsten Strafe aus und weisen Sie der kostengünstigsten Zelle so viel wie möglich zu. Bei Gleichstand wird zuerst eine Zelle mit maximal möglicher Zuordnung ausgewählt
Schritt 3:
Nach dem Erfüllen der Anforderung oder dem Ausschöpfen des Angebots entweder die Zeile oder die Spalte streichen, wird der verbleibenden Zeile oder Spalte ein Angebot von null oder eine Null zugewiesen. Jede Zeile oder Spalte ohne Angebot oder Bedarf, die nicht für weitere Berechnungen verwendet wird.
Schritte 4:
Wiederholen Sie die Schritte 1 und 3, bis alle Quellen erschöpft sind oder alle Anforderungen erfüllt sind.
Beispiel 5
Ein Hersteller möchte 8 Ladungen seines Produkts von den Produktionszentren X, Y & Z an die Distributionszentren A, B und C versenden. Die Laufleistung vom Ursprung 0 zum Ziel D ist die folgende Matrix.
Beispiel 6:
Finden Sie die optimale Lösung für das folgende Transportproblem, indem Sie eine erste Lösung mit der Annäherungsmethode von Vogets erhalten:
Lösung:
Wenden wir die Annäherungsmethode von vogel an. Probleme ausgewogen als Angebot = Bedarf = 50 Einheiten. Wenden wir die Methode von vogel an, wie in der nachstehenden Tabelle angegeben.
Transportkosten = 2 x 15 + 9 x 15 + 20 x 10 + 4 x 5 + 18 x 5 x 475 Einheiten.
Prüfen Sie auf Optimal:
Der Optimalitätstest kann durchgeführt werden, wenn zwei Bedingungen erfüllt sind, d
1. Es gibt m + n - 1 Zuweisung, wobei m die Anzahl der Zeilen und n die Anzahl der Spalten ist. Hier ist m + n - = 6. Die Anzahl der Zuweisungen beträgt jedoch fünf.
2. Diese m + n-1-Zuweisungen sollten sich auf unabhängigen Positionen befinden, dh es sollte nicht möglich sein, die Zuweisung zu erhöhen oder zu verringern, ohne die Position der Zuweisungen zu ändern oder die Zeilen- oder Spalteneinschränkungen zu verletzen.
Eine einfache Regel für Zuordnungen, die sich in unabhängigen Positionen befinden, besteht darin, dass es nicht möglich ist, von einer Zuweisung zu einer Reihe von horizontalen und vertikalen Schritten von einer besetzten Zelle zu einer anderen zu gelangen, ohne eine direkte Umkehrung der Route. Es ist ersichtlich, dass in dem vorliegenden Beispiel die Zuordnung an unabhängigen Positionen erfolgt, da an den zugewiesenen Zellen keine geschlossene Schleife gebildet werden kann.
Daher ist die erste Bedingung nicht erfüllt, und um die erste Bedingung zu erfüllen, müssen wir eine kleine Menge E bei den leeren Zellen mit den niedrigsten Transportkosten zuordnen. Es ist ersichtlich, dass t in Zelle (2, 2) mit Kosten von 7 Einheiten zugewiesen werden kann, und die Zuweisungen bleiben immer noch auf einer unabhängigen Position, wie unten in Tabelle 2 beschrieben.
Nun ist die Anzahl der Zuordnungen m + n - 6 = 6 und sie befinden sich an unabhängigen Positionen. Notieren Sie die Kostenmatrix in den zugewiesenen Zellen. (Tisch 3)
Anfangskostenmatrix für zugeordnete Zellen. Schreiben Sie auch die Werte von u i und v j .
Aus Tabelle 5 ist ersichtlich, dass die Zellenbewertung bei Zelle (1, 4) negativ ist, dh -4, wodurch die Transportkosten durch die Zuordnung bei Zelle (1, 4) weiter verringert werden.
Lassen Sie uns die ursprünglichen Zuteilungen und die vorgeschlagene neue Zuteilung aufschreiben.
Aus Tabelle 6 ist ersichtlich, dass, wenn wir in Zelle (1, 4) zuweisen, eine Schleife wie gezeigt gebildet wird, und wir 10 Einheiten zuweisen, so dass die Zuordnung in Zelle (2, 4) wie in Tabelle 7 gezeigt verschwindet. Neu Zuordnungstabelle wird
Transportkosten = 5 x 2 + 10 x 1 1 + 10 x 7 + 15 x 9 + 5 x 4 + 18 + 5 = 435 Einheiten.
Die Transportkosten sind also von 475 auf 435 Einheiten gesunken.
Prüfen Sie auf Optimal:
Mal sehen, ob diese Lösung optimal ist oder nicht? Dafür müssen noch zwei Bedingungen geprüft werden
Zuordnungsnummer = m + n- 1 = 6 (erfüllt)
Zuweisung an unabhängiger Position (erfüllt, da geschlossene Schleife für zugewiesene Zellen nicht gebildet wird) Schreibkosten bei den zugewiesenen Alls und Werten von u i und v j .
Operation Research: Tool # 3. Zuordnungsproblem:
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. Das Problem kann 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.
Zuweisungsmodell:
Angenommen, es gibt n erleichtert und n Jobs. Es 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 Abtretung erfolgen sollte, um den Gewinn zu maximieren oder die Kosten oder Zeiten zu minimieren.
In der Tabelle ist Coij als die Kosten definiert, wenn der j- te Job dem Mitarbeiter zugewiesen wird. Es sei hier darauf hingewiesen, dass dies ein Sonderfall eines 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, deren (n - 1) Variablen Null sind; n ist die Anzahl der Arbeitsplätze oder die Anzahl der Einrichtungen.
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 ij ist eine Variable, die als definiert ist
Methode zur Lösung des Problems (ungarische Technik):
Betrachten Sie die Zielfunktion des Minimierungstyps.
Die Lösung dieses Zuordnungsproblems umfasst folgende Schritte:
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 abgezogen. Wir erhalten also in jeder Zeile dieser neuen Tabelle mindestens eine Null.
2. Nachdem Sie die Tabelle erstellt haben (wie in Schritt-1), werden die Spalten der Tabelle übernommen. 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 Zuordnungen 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 in diesem Stadium die Mindestanzahl von Zeilen (horizontal und vertikal), die erforderlich ist, um alle Nullen in der in Schritt 3 erhaltenen Matrix abzudecken.
Folgendes Verfahren wird angenommen:
(i) Häkchen (V) Alle Zeilen, die keine Zuordnung haben.
(ii) Markieren Sie nun (V) alle diese Spalten, die in den markierten Zeilen Null haben.
(iii) Haken markiert jetzt alle Zeilen, die noch nicht markiert sind und die in den markierten Spalten eine Zuordnung haben.
(iv) Alle Schritte, dh 4 (1), 4 (2), 4 (3), werden wiederholt, bis keine Zeilen oder Spalten mehr markiert werden können.
(v) Zeichnen Sie nun gerade Linien, die durch alle nicht markierten Zeilen und markierten Spalten gehen. 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.
