Simplex-Methode der linearen Programmierung
Simplex-Methode der linearen Programmierung!
Jedes lineare Programmierproblem, das zwei Variablen umfasst, kann leicht mit Hilfe einer grafischen Methode gelöst werden, da es einfacher ist, mit einem zweidimensionalen Graphen umzugehen. Alle durchführbaren Lösungen in der grafischen Methode liegen innerhalb des möglichen Bereichs in der Grafik, und wir haben die Eckpunkte des möglichen Bereichs auf die optimale Lösung getestet, dh einer der Eckpunkte des möglichen Bereichs war die optimale Lösung. Wir haben alle Eckpunkte getestet, indem wir diese Werte in die Zielfunktion stellen.
Wenn jedoch die Anzahl der Variablen von zwei ansteigt, wird es sehr schwierig, das Problem durch Zeichnen des Graphen zu lösen, da das Problem zu komplex wird. Die Simplex-Methode wurde von GB Dantzig, einem amerikanischen Mathematiker, entwickelt.
Diese Methode ist eine mathematische Behandlung der grafischen Methode. Hier werden auch verschiedene Eckpunkte des realisierbaren Bereichs auf Optimalität geprüft. Es ist jedoch nicht möglich, alle Eckpunkte zu testen, da die Anzahl der Eckpunkte mit der Anzahl der Gleichungen und Variablen die Mannigfaltigkeit erhöht. Die maximale Anzahl dieser Punkte kann getestet werden
m + n m = m + 1! / m! n!
wobei m die Anzahl von und n die Anzahl der Variablen ist.
Bei der Simplex-Methode wird daher die Anzahl der zu testenden Eckpunkte erheblich reduziert, indem ein sehr effektiver Algorithmus verwendet wird, der uns in nur wenigen Iterationen zum optimalen Lösungseckpunkt führt. Nehmen wir ein Beispiel und gehen Sie Schritt für Schritt vor.
Die Zielfunktion besteht darin, Z = 12 × 1 + 15 × 2 + 14 × 3 zu maximieren
Vorbehaltlich der Bedingungen
Schritt 1:
(a) Die rechte Seite aller Einschränkungen muss entweder Null oder + ve sein. Wenn sie -ve sind, müssen sie + ve gemacht werden, indem beide Seiten mit (-1) multipliziert werden, und das Zeichen der Ungleichung wäre umgekehrt. In diesem Beispiel ist RHS bereits + ve oder null.
(b) Alle Ungleichungen werden in Gleichungen umgewandelt, indem Slack- oder Überschussvariablen addiert oder subtrahiert werden. Diese Slack- oder Überschussvariablen werden eingeführt, weil es einfacher ist, mit Gleichungen umzugehen als Ungleichheiten in der mathematischen Behandlung.
Wenn die Einschränkung ≤ Typ ist, werden die Spielvariablen hinzugefügt, wenn die Einschränkung ≥ Typ ist, dann wird die Überschussvariable abgezogen. Hier werden Slack-Variablen s, s 2 und s 3 in drei Gleichungen (i), (ii) und (iii) addiert.
Und objektive Funktion wird
Maximiere Z = 12 x 1 + 15 x 2 + 14 x 3 + os 1 + os 2 + os 3
Schritt 2:
Erste mögliche Lösung finden:
Wir beginnen mit einer realisierbaren Lösung und gehen dann in den nächsten Iterationen auf die optimale Lösung zu. Die anfängliche durchführbare Lösung wird vorzugsweise als Ursprung gewählt, dh wenn die regulären Variablen, z. B. in diesem Fall x v x 2, x 3, Nullwerte annehmen. dh x 1 x 2, x 3 = 0
und wir erhalten s 1 = 0, s 2 = 0 und s 3 = 100 aus Ungleichungen (i), (ii) und (iii)
Basisvariablen sind die Variablen, die sich in der Lösung befinden, z. B. S v S 2 und S 3 sind die Basisvariablen in der Ausgangslösung.
Nicht-Basisvariablen sind die Variablen, die gleich Null gesetzt sind und sich nicht in der aktuellen Lösung befinden, z. B. sind x 1 und x 2 und x 3 die nicht-Basisvariablen in der Ausgangslösung.
Die obigen Informationen können in der Tabelle 1 ausgedrückt werden
In der Tabelle stellt die erste Zeile Koeffizienten der Zielfunktion dar, die zweite Zeile stellt verschiedene Variablen dar (zuerst reguläre Variablen dann Slack- / Überschussvariablen). Dritte, vierte und fünfte Zeile stehen für Koeffizienten von Variablen in allen Einschränkungen.
Die erste Spalte repräsentiert die Koeffizienten der Basisvariablen (aktuelle Lösungsvariablen) in der Zielsetzung (e i ). Die zweite Spalte repräsentiert die Basisvariablen (aktuelle Lösungsvariablen) und die letzte Spalte repräsentiert die rechte Seite der Einschränkungen in Standardform. Das heißt, nachdem alle Ungleichungen in Gleichungen überlastet wurden, werden in jeder Tabelle die aktuellen Werte der aktuellen Lösungsvariablen (Basisvariablen) durch RHS angegeben
In Tabelle 1 ist die derzeitige Lösung:
S 1 = 0, S 2 = 0, S 3 = 100
Natürlich sind auch die nicht grundlegenden Variablen X v X 2 und X 3 gleich Null
Entartung, wann immer eine Basisvariable Nullwerte annimmt, die aktuelle Lösung wird als entartet bezeichnet, da in dem vorliegenden Problem S 1 = 0 und S 2 = 0 das Problem weiter gelöst werden kann, indem S 1 = t und S 2 = t, wo t ist, ersetzt wird sehr kleine + ve Anzahl.
Schritt 3:
Optimalitätstest.
Der Optimalitätstest kann durchgeführt werden, um festzustellen, ob die aktuelle Lösung optimal ist oder nicht. Für diese erste schreiben Sie die letzte Zeile in der Form von (E j ) wo
Ej = Σ ei. Ein ij.
Wobei a ij Koeffizienten in der Body-Identity-Matrix für die i-te Zeile & j-te Spalte darstellt, dh die erste Spalte der Tabelle darstellt. Schreiben Sie in die letzte Zeile den Wert von (Cj - Ej), wobei c ; repräsentiert die Werte der ersten Zeile und E j repräsentiert die Werte der letzten Zeile. (Cj - Ej) stellt den Vorteil dar, jede nicht grundlegende Variable an die aktuelle Lösung heranzuführen, dh sie als grundlegend zu machen.
In der Tabelle 2 sind die Werte von Cj - Ej 12, 15 und 14 für X v X 2 und X 3 . Wenn einer der Werte von Cj - Ej + ve ist, bedeutet dies, dass die meisten positiven Werte die Variable darstellen, die in die aktuelle Lösung gebracht wird, die Zielfunktion maximal erhöhen würden. Im vorliegenden Fall ist X 2 die potentielle Variable, die für die nächste Iteration in die Lösung kommen kann. Wenn alle Werte in der Zeile (Cj - Ej) negativ sind, bedeutet dies, dass die optimale Lösung erreicht wurde.
Schritt 4:
Iterieren Sie in Richtung optimale Lösung:
Der maximale Wert von Cj - Ej gibt die in der Tabelle markierte Schlüsselspalte an
Daher ist X 2 die Eingabevariable, dh es wird grundlegend und würde in die Lösung eintreten. Aus der vorhandenen nicht grundlegenden Variable heraus, und man muss ausgehen und nicht einfach werden. Um herauszufinden, welche Variable herausgetrieben werden soll, dividieren Sie die Koeffizienten in der Spalte RHS durch die entsprechenden Koeffizienten in der Schlüsselspalte, um die Ratio-Spalte zu erhalten. Suchen Sie nun nach dem am wenigsten positiven Wert in der Ratiospalte und dies würde die Schlüsselzeile ergeben. Im vorliegenden Problem haben wir drei Werte, dh t, µ und 100, und davon ist t das kleinste + ve. Daher wäre die Zeile, die t in der Ratio-Spalte entspricht, die Schlüsselzeile. Und S. wäre die Abgangsvariable. Das Element am Schnittpunkt von Schlüsselzeile und Schlüsselspalte ist das Schlüsselelement.
Nun werden alle Elemente in der Schlüsselspalte außer dem Schlüsselelement zu Null und das Schlüsselelement zu Einheit gemacht. Dies geschieht mit Hilfe von Zeilenoperationen, wie dies bei den Matrizen der Fall ist. Hier ist das Schlüsselelement bereits unity und das andere Element in der Schlüsselspalte wird zu Null gemacht, indem Sie die erste Zeile -1 mal in der dritten Zeile hinzufügen und die nächste Tabelle erhalten.
Daher wird die zweite realisierbare Lösung
X 1 = 0, X 2 = t und X 3 = 0 dort um z = 15t
In der neuen Tabelle wurde s 1 in den Basisvariablen durch X 2 ersetzt und entsprechend wurde auch die ei-Spalte geändert.
Schritt 5:
Bei Betrachtung der Cj -Ej-Werte in Tabelle 3 finden wir, dass x 1 die meisten + ve-Werte von 27 hat, was darauf hinweist, dass die Lösung weiter verbessert werden kann, indem x 1 in die Lösung eingebracht wird, dh indem sie basisch wird. Daher ist die Spalte x 1 die Schlüsselspalte. Suchen Sie auch die Schlüsselzeile, wie oben erläutert, und schließen Sie Tabelle 5 ab.
Das Schlüsselelement in Tabelle 5 lautet "2", und es wird zu "unity". Alle anderen Elemente in der Schlüsselspalte werden mithilfe von Zeilenoperationen auf Null gesetzt, und schließlich wird Tabelle 6 angezeigt. Das erste Schlüsselelement wird durch das Teilen dieser Zeile durch "1" vereinheitlicht 2. Durch das Hinzufügen geeigneter Vielfachen dieser Zeile in eine andere Zeile erhalten Sie Tabelle 6.
Aus Tabelle 6 ist ersichtlich, dass die Lösung immer noch nicht optimal ist, da Cj-Ej immer noch + ve Werte ist. Dies ergibt die Schlüsselspalte und die entsprechende Schlüsselzeile wird gefunden. Das Schlüsselelement wird in Tabelle 7 angegeben
Jetzt machen wir durch geeignete Zeilenoperationen, dass andere Elemente in der Schlüsselspalte Null sind, wie in Tabelle 8 gezeigt.
Es ist ersichtlich, dass, da alle Werte in der Zeile Cj-Ej entweder -ve oder null sind, die optimale Lösung erreicht wurde.
Die Endlösung ist x 1 = 40 Tonnen
x 2 = 40 Tonnen
x 3 = 20 Tonnen
da t sehr klein ist, wird es vernachlässigt.
Beispiel 1:
Lösen Sie das folgende Problem mit der Simplex-Methode
Maximiere Z = 5 × 1 + 4 × 2
Vorbehaltlich 6x 1 + 4x 2 ≤ 24
x 1 + 2x 2 ≤ 6
-x 1 + x 2 ≤ 1
x 2 ≤ 2
und x 1 x 2 ≥ 0
Lösung:
Fügen Sie die Slack-Variablen S 1, S 2, S 3, S 4 in den vier Randbedingungen hinzu, um Ungleichungen zu beseitigen.
Wir erhalten 6x 1 + 4x 2 + s 1 = 24
x 1 + 2x 2 + s 2 = 6
-x 1 + x 2 + s 3 = 1
x 2 + s 4 = 2
Vorbehaltlich x 1, x 2, s 1, s 2, s 3 & s 4 > 0
Zielfunktion wird
Maximiere Z = 5x 1 + 4x 2 0s 1 + 0s 2 + 0s 3 + 0s 4
Die gebildete Tabelle 1 ist unten angegeben. Es ist ersichtlich, dass X 1 die Eintrittsvariable ist und S die Austrittsvariable ist. Schlüsselelement in Tabelle 1 wird zu unity und alle anderen Elemente in dieser Spalte werden zu null gemacht.
Aus Tabelle 2 kann hervorgehen, dass X 2 die Eintrittsvariable und S 2 die Austrittsvariable ist.
Aus Tabelle 5 ist ersichtlich, dass alle Werte der Zeile Cj-Ej entweder -ve oder Null sind. Daher wurde eine optimale Lösung erhalten.
Die Lösung ist x 1 = 3, x 2 = 3/2
Z max = 5 × 3 + 4x = 3/2
= 15 + 6 = 21 Ans.
Big M-Methode
Nehmen wir das folgende Problem, um die Big M-Methode zu veranschaulichen.
Minimiere Z = 2y 1 + 3y 2
unter Vorbehalt y 1 + y 2 ≥ 5
y 1 + 2y 2 ≥ 6
y 1, y 2 ≥ 0
Umwandlung in Standardform:
Maximieren Sie Z = -2y 1 - 3y 2 + Os, + 0s 2
Das Minimierungsproblem wird in ein Maximierungsproblem umgewandelt, indem die RHS der Zielfunktion mit -1 multipliziert wird.
Einschränkungen y 1 + y 2 - s 1 = 6… (i)
y, + y 2 - s 2 = 6… (ii)
y 1 y 2, s 1 s 2 ≥ 0
Hier werden die Überschussvariablen s1, s2 und jeweils von den Bedingungen (i) und (ii) abgezogen.
Nun können y 1, y 2 als nicht grundlegende Variablen genommen und gleich Null gesetzt werden, um s v s 2 als grundlegende Variablen mit s 1 = -5, s 2 = -6 zu erhalten.
Dies ist eine unlösbare Lösung, da die Überschussvariablen s 1 und s 2 get -ve-Werte haben. Um dieses Problem zu überwinden, fügen wir künstliche Variablen A 1 und A 2 in Gl. (i) und (ii) zu bekommen
y 1 + y 2 –s 1 + A 1 = 5… (iii)
y 1 + 2y 2 - s 2 + A 2 = 6… (iv)
Wo y 1 y 2, s 1, s 2, A 1, A 2 ≥ 0 ist
und objektive Funktion wird
Maximiere Z 1 = -2y 1 - 3y 2 + 0s 1 + 0s 2 - MA 1 - MA 2
Es ist zu beobachten, dass wir absichtlich sehr schwere Strafen auf künstliche Variablen in der Zielfunktion in Form von -MA1 und MA2 angewendet haben, wobei M eine sehr große Zahl v ist. Zweck ist, dass die künstlichen Variablen zunächst in der Ausgangslösung erscheinen.
Da künstliche Variablen die Zielfunktion im Falle von Strafen sehr stark herabsetzen, treibt der Simplex-Algorithmus die künstlichen Variablen in den anfänglichen Iterationen aus der Lösung heraus und daher erscheinen die künstlichen Variablen, die wir eingeführt haben, um das Problem zu lösen, nicht im Finale Lösung. Künstliche Variablen sind nur ein Rechengerät. Sie halten die Startgleichungen im Gleichgewicht und liefern einen mathematischen Trick, um eine Startlösung zu erhalten.
Ausgangstabelle wird
Da Cj-Ej unter einigen Spalten + ve ist, ist die in Tabelle 1 angegebene Lösung nicht optimal. Es ist ersichtlich, dass -3 + 3M aus -2 + 2M und -3 + 3M am meisten + ve ist, da M eine sehr große + ve Zahl ist. Das Schlüsselelement wird wie in Tabelle 1 gezeigt gefunden, es wird zu einer Einheit und alle anderen Elemente in dieser Spalte werden zu Null gemacht. Wir bekommen Tabelle 2.
Aus Tabelle 2 ist ersichtlich, dass die optimale Lösung immer noch nicht erreicht wird und eine bessere Lösung existiert. Y 1 ist die eingehende Variable und A 1 ist die ausgehende Variable. Wir bekommen Tabelle 3.
Aus Tabelle 3 ist ersichtlich, dass die optimale Lösung erreicht ist und die Lösung ist
Y 1 = 4, Y 2 = 1
Mindestwert von Z = 2x 4 + 3x 1 = 11 Einheiten Ans.
Nicht gebundene Lösung:
Ein lineares Programmierproblem hat eine unbeschränkte Lösung, wenn in der Ratio-Spalte alle Einträge entweder mit -ve oder mit Null abgerufen werden und es keinen + ve-Eintrag gibt. Dies zeigt an, dass der Wert der eingehenden Variablen, die aus einer Schlüsselspalte ausgewählt wird, beliebig groß sein kann, ohne die realisierbare Bedingung zu verletzen, und das Problem soll eine unbegrenzte Lösung haben.
Unendlich viele Lösungen:
Es wird gesagt, dass ein lineares Programmierproblem unendlich viele Lösungen hat, wenn wir während einer Iteration in der Zeile Cj-Ej alle Werte entweder null oder -ve haben. Es zeigt, dass der optimale Wert erreicht ist. Da jedoch eine der regulären Variablen in der Zeile Cj-Ej den Wert Null hat, kann gefolgert werden, dass es eine alternative optimale Lösung gibt.
Ein Beispiel für diese Art von Tabelle ist unten angegeben.
Es ist ersichtlich, dass eine optimale Lösung erreicht wurde, da alle Werte in der Zeile Cj-Ej Null oder -ve sind. X 1 ist jedoch keine Basisvariable und hat einen Wert von Null in der Zeile Cj-Ej. Dies bedeutet, dass X in den Wert gebracht werden kann Lösung, erhöht jedoch nicht den Wert der objektiven Funktion und Alternative ist optimal.
Fall von Nr. Machbare Lösung:
In einigen LPP ist zu erkennen, dass beim Lösen des Problems mit künstlichen Variablen die Zeile Cj-Ej zeigt, dass die optimale Lösung erreicht ist, während in der aktuellen Lösung immer noch künstliche Variablen mit einem + vp-Wert vorhanden sind. In solchen Situationen kann gefolgert werden, dass das Problem überhaupt keine machbare Lösung hat.
Beispiel 2
Lösung:
Um das Problem zu lösen, müssen künstliche Variablen in LHS hinzugefügt werden, um die anfängliche realisierbare Lösung zu erhalten. Lassen Sie uns künstliche Variablen A 1, A 2, A 3 einführen, unter denen die obigen Einschränkungen geschrieben werden können.
Wenn nun diese künstlichen Variablen in der endgültigen Lösung erscheinen, indem sie einige + ve-Werte haben, wird die Gleichheit von Gleichung (i), (ii) oder (iii) gestört. Daher möchten wir, dass künstliche Variablen nicht in der endgültigen Lösung erscheinen sollten. Daher wenden wir große Abzüge in der Zielfunktion an, die als geschrieben werden kann.
Maximiere Z = Y, + 2Y 2 + 3Y 3 - Y 4 - MA, - MA 2 - MA 3
Wenn wir nun y 1, Y 2, y 3 und y 4 als nicht grundlegende Variablen nehmen und Y 1 = Y 2 = y 4 = 0 setzen, dann erhalten wir die Anfangslösung als A 1 = 15, A 2 = 20 & A 3 = 10 und A 1, A 2, A 3 und A 4 sind grundlegende Variablen (Variablen in der aktuellen Lösung), um damit zu beginnen. Die obigen Informationen können in Tabelle 1 zusammengefasst werden.
AS Cj-Ej ist positiv, die derzeitige Lösung ist nicht optimal und daher gibt es eine bessere Lösung.
Iterieren Sie auf eine optimale Lösung
Durchführen von Iterationen, um eine optimale Lösung zu erhalten (siehe nachstehende Tabelle)
Da Cj-Ej in allen Spalten entweder null oder negativ ist, wurde die optimale, durchführbare Lösung erhalten. Optimale Werte sind
Y 1 = 5/2, Y 2 = 5/2, Y 3 = 5/2, Y4 = 0
Auch A 1 = A 2 = 0 und Z max = 15 Ans.
