Überprüfung auf Optimalität

Der Optimalitätstest kann durchgeführt werden, wenn zwei Bedingungen erfüllt sind, d

1. Es gibt m + n - 1 Zuordnungen, wobei m die Anzahl der Zeilen und n die Anzahl der Spalten ist. Hier ist m + n - 1 = 6. Aber die Zuteilung ist fünf.

2. Diese m + n - 1-Zuweisungen sollten an unabhängigen Positionen liegen. Dh es sollte nicht möglich sein, die Zuordnung zu erhöhen oder zu verringern, ohne die Position der Zuweisungen zu ändern oder die Zeilen- oder Spaltenbeschränkungen zu verletzen.

Eine einfache Regel für Zuordnungen, die sich in unabhängigen Positionen befinden, besteht darin, dass es nicht möglich ist, eine Zuweisung durch eine Reihe horizontaler und vertikaler Schritte von einer belegten Zelle zu einer anderen zu sich selbst zu bringen, 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 dennoch auf einer unabhängigen Position, wie nachstehend beschrieben:

Nun ist die Anzahl der Zuweisungen m + n- = 6 und sie befinden sich an unabhängigen Positionen.

Notieren Sie die Kostenmatrix in den zugewiesenen Zellen.

Anfangskostenmatrix für zugeordnete Zellen.

Schreiben Sie auch die Werte von u i und v j, wie zuvor erläutert.

Zellbewertungsmatrix

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 zuordnen, so dass die Zuordnung in Zelle (2, 4) wie in Tabelle 7 gezeigt verschwindet.

Neue 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 Optimaiity:

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)

Zuteilung an unabhängiger Position (erfüllt, da keine geschlossene Schleife für zugewiesene Zellen gebildet wird)

Schreibkosten bei den zugewiesenen Alls und Werten von u i und v j

Beispiel 2

(Unausgeglichenes Angebot und Nachfrage). Lösen Sie das folgende Transportproblem

Gesamtangebot = 200 Einheiten, Nachfrage = 185 Einheiten.

Lösung:

Da Angebot und Nachfrage nicht gleich sind, ist das Problem unausgeglichen. Um das Problem auszugleichen, muss eine Dummy-Kolonne hinzugefügt werden (siehe unten). Die Nachfrage an dieser Dummy-Kolonne (Laden) beträgt 15 Einheiten.

Grundlegende mögliche Lösung:

Wir werden die Annäherungsmethode von Vogel verwenden, um die erste praktikable Lösung zu finden.

Die erste mögliche Lösung ist durch die folgende Matrix gegeben:

Optimalitätstest:

Aus der obigen Matrix finden wir folgendes:

(a) Anzahl der Zuordnungen = m + n - 1 = 4 + 5-1 = 8

(b) Diese Zuordnungen von m + n - 1 befinden sich in unabhängigen Positionen.

Daher kann ein Optimalitätstest durchgeführt werden. Dieser besteht aus den zuvor erläuterten Unterschritten, wie in den folgenden Tabellen gezeigt:

Da die Zellwerte + ve sind, ist die erste realisierbare Lösung optimal. Da Tabelle 6 keine Einträge enthält, gibt es alternative optimale Lösungen. Die praktische Bedeutung der Nachfrage um 15 Einheiten gegenüber dem Angebot besteht darin, dass das Unternehmen die Produktion von 15 Einheiten in der Fabrik einschränken kann, in der es unwirtschaftlich ist.

Der optimale (minimale) Transport plus Produktionskosten.

Z = Rs. (4 × 25 + 6 × 5 + 8 × 20 + 10 × 70 + 4 × 30 + 13 × 15 + 8 × 20 + 0 × 15)

= Rs. (100 + 30 + 160 + 170 + 120 + 195 + 160 + 0) = Rs. 1, 465.

Beispiel 3:

Lösen Sie das folgende Transportproblem, um den Gewinn zu maximieren. Aufgrund von Unterschieden bei den Rohstoffkosten und den Transportkosten unterscheidet sich der Gewinn für die Einheit in Rupien, der in der nachstehenden Tabelle angegeben ist:

Lösen Sie das Problem, um den Gewinn zu maximieren.

Lösung:

Das Problem ist unausgeglichen, daher muss eine Dummy-Zeile hinzugefügt werden, um es auszugleichen.

Finden Sie die erste grundlegende mögliche Lösung:

Wir werden die Annäherungsmethode von vogel verwenden, um die anfänglich mögliche Lösung zu bestimmen.

Beachten Sie, dass es sich um ein Problem der Maximierung handelt. Daher geben wir die Differenz zwischen dem höchsten und dem zweithöchsten Element in jeder Zeile rechts von der Zeile und die Differenz zwischen dem höchsten und dem zweithöchsten Element in jeder Spalte unter der entsprechenden Spalte ein.

Jede dieser Differenzen stellt den Gewinn dar, der für die Nichtzuweisung an die Zelle mit dem höchsten Gewinn verloren wurde. Während wir Zuordnungen vornehmen, wählen wir zuerst die Zelle (2, 3) mit dem höchsten Eintrag in Zeile 2 aus, der der größten Differenz von [45] entspricht.

Optimalitätstest:

Erforderliche Anzahl von Zuweisungen = m + n - 1 = 3 + 4 - 1 = 6

Tatsächliche Zuteilungszahl = 5.

Daher weisen wir der Zelle (1, 3) (Zelle mit maximalem Gewinn aus leeren Zellen) eine kleine positive Zahl zu, so dass die Anzahl der Zuordnungen 6 wird. Diese 6 Zuweisungen befinden sich in unabhängigen Positionen. Daher kann ein Optimalitätstest durchgeführt werden.

Da alle Zellwerte entweder negativ oder null sind (Maximierungsproblem), ist die anfänglich mögliche Grundlösung optimal. Die Nachfrage am ersten Ziel wird von 5 Einheiten nicht erfüllt. Der Gewinn ist

Z max = Rs. [90 x 70 + 90 x 100 + 110 x 30 + 130 x 100 + 0 x 5]

= Rs. 31.600.