Lösung von Simplextabellen online im Detail. Beispiel Problemlösung

11.4. DUALES SIMPLEX-VERFAHREN

Aus den Ergebnissen der vorherigen Abschnitte folgt, dass wir, um eine Lösung des ursprünglichen Problems zu erhalten, zum dualen übergehen und unter Verwendung von Schätzungen seines optimalen Designs die optimale Lösung des ursprünglichen Problems bestimmen können.

Der Übergang zum dualen Problem ist nicht notwendig, denn wenn wir das erste Simplex-Tableau mit einer Einheitszusatzbasis betrachten, dann ist leicht zu erkennen, dass die Spalten das ursprüngliche Problem enthalten und das duale Problem in die Zeilen geschrieben wird.

Wie gezeigt wurde, ist beim Lösen des direkten Problems bei jeder Iteration der Unterschied, d.h. Größe -Koeffizient mit einer Variablen, ist gleich der Differenz zwischen der rechten und linken Seite der entsprechenden Nebenbedingung des dualen Problems. Wenn bei der Lösung eines direkten Problems mit maximierbarer Zielfunktion die Iteration nicht zu einer optimalen Lösung führt, dann für mindestens eine Variable und nur im Optimum für alle Unterschied .

Unter Berücksichtigung dieser Bedingung mit Berücksichtigung der Dualität können wir schreiben

.

Also wenn, dann . Das heißt, wenn die Lösung des primalen Problems nicht optimal ist, ist die Lösung des dualen Problems ungültig. Andererseits bei . Dies impliziert, dass die optimale Lösung des primalen Problems einer zulässigen Lösung des dualen Problems entspricht.

Dadurch konnte ein neues Verfahren zur Lösung von linearen Programmierproblemen entwickelt werden, bei dessen Anwendung zunächst eine nicht akzeptable, aber „besser als optimale“ Lösung erzielt wird (bei der üblichen Simplex-Methode zunächst zulässig, aber suboptimal Lösung). Eine neue Methode namens Dual-Simplex-Verfahren, sorgt für die Erfüllung der Lösungsoptimalitätsbedingung und deren systematische „Annäherung“ an den Bereich zulässiger Lösungen. Wenn sich die erhaltene Lösung als zulässig herausstellt, endet der iterative Berechnungsprozess, da auch diese Lösung optimal ist.

Das Dual-Simplex-Verfahren ermöglicht das Lösen linearer Programmierprobleme, deren Constraint-Systeme mit positiver Basis freie Terme beliebigen Vorzeichens enthalten. Dieses Verfahren macht es möglich, die Anzahl der Transformationen des Constraint-Systems sowie die Größe der Simplex-Tabelle zu reduzieren. Betrachten Sie die Anwendung des Dual-Simplex-Verfahrens anhand eines Beispiels.

Beispiel. Finden Sie das Minimum einer Funktion

unter Einschränkungen

.

Kommen wir zur kanonischen Form:

unter Einschränkungen

Das anfängliche Simplex-Tableau hat die Form

Basic Variablen	x 1	x 2	x 3	x 4	x 5	Lösung
x 3 x 4 x 5	–3 –4	–1 –3				–3 –6
	–2	–1

Erste Basislösungoptimal, aber nicht akzeptabel.

Das betrachtete Lösungsverfahren basiert wie das übliche Simplexverfahren auf der Verwendung von Zulässigkeits- und Optimalitätsbedingungen.

Zulässigkeitsvoraussetzung. Als ausgeschlossene Variable wird die betragsmäßig größte negative Basisvariable gewählt (falls es Alternativen gibt, erfolgt die Wahl willkürlich). Wenn alle Basisvariablen nicht negativ sind, endet der Berechnungsprozess, da die resultierende Lösung zulässig und optimal ist.

Bedingung Optimalität. Die in die Basis aufgenommene Variable wird wie folgt aus den Nichtbasisvariablen ausgewählt. Die Verhältnisse der Koeffizienten der linken Seite werden berechnet-Gleichungen zu den entsprechenden Koeffizienten der Gleichung, die der ausgeschlossenen Variablen zugeordnet ist. Beziehungen mit positivem oder Null-Nenner werden nicht berücksichtigt. Beim Problem der Minimierung der Eingangsgröße muss das kleinste der angegebenen Verhältnisse übereinstimmen, beim Problem der Maximierung das Verhältnis mit dem kleinsten Betrag (wenn es Alternativen gibt, erfolgt die Wahl willkürlich). Wenn die Nenner aller Verhältnisse Null oder positiv sind, hat das Problem keine zulässigen Lösungen.

Nach Auswahl der Variablen, die in die Basis aufgenommen und ausgeschlossen werden sollen, um die nächste Lösung zu erhalten, wird die übliche Operation des Transformierens der Zeilen der Simplex-Tabelle ausgeführt.

In diesem Beispiel ist die ausgeschlossene Variable. Die zur Bestimmung der neuen Basisvariablen berechneten Verhältnisse sind in der folgenden Tabelle dargestellt:

Variablen	x 1	x 2	x 3	x 4	x 5
Die gleichung x 4 - Gleichung	–2 –4	–1 –3
Attitüde

Die aufzunehmende Variable ist x 2. Die anschließende Zeichenfolgenkonvertierung führt zu einer neuen Simplex-Tabelle:

Basic Variablen	x 1	x 2	x 3	x 4	x 5	Lösung
x 3 x 2 x 5						–1 –1

Neue Lösung auch optimal, aber immer noch ungültig. Als neue ausgeschlossene Variable wählen wir (willkürlich) x 3 . Lassen Sie uns eine eingeschlossene Variable definieren.

Variablen	x 1	x 2	x 3	x 4	x 5
Die gleichung x 4 - Gleichung
Attitüde

Simplex-Verfahren - Dies ist eine Methode des sukzessiven Übergangs von einer Basislösung (dem Scheitelpunkt des Lösungspolyeders) des Systems von Beschränkungen eines linearen Programmierproblems zu einer anderen Basislösung, bis die Zielfunktion den optimalen Wert (Maximum oder Minimum) annimmt.

Die Simplex-Methode ist eine universelle Methode, die jede lösen kann Problem der linearen Programmierung, während die grafische Methode nur für ein Beschränkungssystem mit zwei Variablen geeignet ist.

Die Simplex-Methode wurde 1947 vom amerikanischen Mathematiker R. Danzig vorgeschlagen, seitdem löst diese Methode für die Bedürfnisse der Industrie häufig Probleme der linearen Programmierung mit Tausenden von Variablen und Nebenbedingungen.

Bevor wir zum Algorithmus der Simplex-Methode übergehen, einige Definitionen.

Jede nicht negative Lösung eines Systems von Nebenbedingungen wird aufgerufen akzeptable Lösung .

Lass es ein System geben m Einschränkungen ab n Variablen ( m n).

Zulässige Basislösung ist eine Lösung mit m nicht negativ Haupt (Basic ) Variablen und n - m Nicht-Kern . (nicht basisch bzw frei ) Variablen. Nicht-Basisvariablen in der Basislösung sind gleich Null, während die Hauptvariablen in der Regel nicht Null sind, dh positive Zahlen sind.

Irgendein m Systemvariablen m lineare Gleichungen mit n Variablen aufgerufen werden hauptsächlich , wenn die Determinante der Koeffizienten an ihnen von Null verschieden ist. Dann der Rest n - m Variablen aufgerufen werden Nicht-Kern (oder frei ).

Algorithmus der Simplex-Methode

• Schritt 1. Bringen Sie das Problem der linearen Programmierung in die kanonische Form. Verschieben Sie dazu die freien Terme auf die rechte Seite (wenn unter diesen freien Termen negativ sind, dann multiplizieren Sie die entsprechende Gleichung oder Ungleichung mit -1) und führen Sie zusätzliche Variablen in jede Bedingung ein (mit einem Pluszeichen, falls in der ursprüngliche Ungleichung das Vorzeichen ist kleiner oder gleich ", und mit einem Minuszeichen, wenn "größer als oder gleich").
• Schritt 2. Wenn im resultierenden System m Gleichungen, dann m nimm die Variablen als die Hauptvariablen, drücke die Hauptvariablen durch die Nichtbasisvariablen aus und finde die entsprechende Basislösung. Erweist sich die gefundene Basislösung als zulässig, gehe zur zulässigen Basislösung.
• Schritt 3. Drücken Sie die Zielfunktion durch die Nebenvariablen der zulässigen Basislösung aus. Wenn das Maximum (Minimum) der linearen Form gefunden wird und es keine Nichtbasisvariablen mit negativen (positiven) Koeffizienten in ihrem Ausdruck gibt, ist das Optimalitätskriterium erfüllt und die resultierende Basislösung ist optimal - die Lösung ist beendet. Wenn beim Ermitteln des Maximums (Minimum) einer linearen Form deren Ausdruck eine oder mehrere nicht grundlegende Variablen mit negativen (positiven) Koeffizienten enthält, gehen Sie zu einer neuen grundlegenden Lösung.
• Schritt 4. Wählen Sie aus den nicht grundlegenden Variablen, die in der linearen Form mit negativen (positiven) Koeffizienten enthalten sind, diejenige aus, die dem größten (Modulo-) Koeffizienten entspricht, und übertragen Sie sie auf die Hauptvariablen. Weiter zu Schritt 2.

Wichtige Bedingungen

Einige Sonderfälle werden in separaten Artikeln behandelt: when maximale Zielfunktion - unendlich, Wenn Das System hat keine Lösung, und wann die optimale Lösung ist nicht die einzige .

Als nächstes werden wir ein typisches Beispiel analysieren, wenn das System der Beschränkungen konsistent ist und es ein endliches Optimum gibt, und zwar nur eines. Eine Variation der Simplex-Methode ist Verteilungsverfahren zur Lösung des Transportproblems .

Simplex-Verfahren mit Simplex-Tabellen

Durch das Erstellen von Simplex-Tabellen ist es viel einfacher, ein Problem der linearen Programmierung zu lösen als durch algebraische Transformationen, was im nächsten Abschnitt gezeigt wird. Simplex-Tabellen sind sehr visuell. Es gibt verschiedene Arten von Regeln für die Arbeit mit Simplex-Tabellen. Wir werden die Regel analysieren, die am häufigsten als Leitspalten- und Leitreihenregel bezeichnet wird.

Es wäre nützlich, die manuellen Aktionen mit Brüchen in einem neuen Fenster zu öffnen: Es gibt genug davon, Brüche in Problemen mit der Simplex-Methode, um es milde auszudrücken.

Beispiel.

Wir führen weitere nicht-negative Variablen ein und reduzieren dieses Ungleichungssystem auf ein äquivalentes Gleichungssystem

.

Dies wurde unter Einhaltung der folgenden Regel durchgeführt: Wenn das Vorzeichen in der ursprünglichen Beschränkung "kleiner oder gleich" ist, muss die zusätzliche Variable hinzugefügt werden, und wenn "größer als oder gleich", muss die zusätzliche Variable hinzugefügt werden abgezogen.

Die eingeführten zusätzlichen Variablen werden als Hauptvariablen (basic) betrachtet. Then und sind nicht grundlegende (freie) Variablen.

Wenn wir die wichtigsten (grundlegenden) Variablen in nicht-grundlegenden (freien) Variablen ausdrücken, erhalten wir

Wir drücken die Zielfunktion auch in Form von nicht grundlegenden (freien) Variablen aus:

Aus den Koeffizienten der Variablen (Unbekannten) konstruieren wir das erste Simplex-Tableau.

Tabelle 1
Grundlegende Unbekannte	Kostenlose Mitglieder	Lose Unbekannte		Hilfskoeffizienten
		X1	X2
X3	-2	1	-2
X4	-4	-1	-1
X5	2	1	-1
X6	6	0	1
F	0	-1	-2

Die letzte Zeile der Tabelle, die die Zielfunktion und die darin enthaltenen Koeffizienten freier Variablen enthält, wird als Indexzeile bezeichnet.

Die resultierende Lösung ist nicht optimal, da die Koeffizienten der freien Variablen in der Indexzeile negativ sind. Das heißt, die optimale Lösung ist diejenige, bei der die Koeffizienten der freien Variablen in der Indexzeile größer oder gleich Null sind.

Um zur nächsten Tabelle zu gelangen, suchen Sie die größte (Modulo) der Zahlen und . Diese Zahl ist 2. Daher ist die führende Spalte die Spalte, in der es geschrieben wird

Um die führende Reihe zu bestimmen, finden wir das Minimum der Verhältnisse der freien Elemente zu den Elementen der führenden Spalte, und wenn der Zähler eine positive Zahl und der Nenner eine negative Zahl hat, wird das Verhältnis als gleich unendlich betrachtet.

.

Daher ist die führende Zeile diejenige, in der es geschrieben wird

Das führende Element ist also -2.

Wir erstellen die zweite Simplextabelle.

Wir geben das neue Grundelement in die erste Zeile ein, und wir geben die Spalte ein, in der es stand, wir geben eine neue freie Variable ein

Füllen Sie die erste Zeile aus. Dazu dividieren wir alle Zahlen in der führenden Zeile von Tabelle 1 durch das führende Element und schreiben es in die entsprechende Spalte der ersten Zeile von Tabelle 2, mit Ausnahme der Zahl in der führenden Spalte, wo der Kehrwert der führenden ist -Element geschrieben wird (d. h. eins geteilt durch das führende Element).

Füllen Sie die Spalte der Hilfskoeffizienten aus. Für diese Nummer der führenden Spalte von Tabelle 1 schreiben wir zusätzlich zum führenden Element mit entgegengesetzten Vorzeichen in die Spalte der Hilfskoeffizienten von Tabelle 2.

Tabelle 2
Grundlegende Unbekannte	Kostenlose Mitglieder	Lose Unbekannte		Hilfskoeffizienten
		X1	X3
X2	1	-1/2	-1/2
X4	-3	-3/2	-1/2	1
X5	3	1/2	-1/2	1
X6	5	1/2	1/2	-1
F	2	-2	-1	2

Wer die manuellen Aktionen mit Brüchen noch nicht in einem neuen Fenster geöffnet hat, kann das jetzt tun, denn es ist soweit.

Um die restlichen Zeilen von Tabelle 2 zu erhalten, werden die Zahlen, die sich bereits in der ersten Zeile dieser Tabelle befinden, mit dem Hilfskoeffizienten in der zu füllenden Zeile multipliziert, und zum Ergebnis addieren wir die Zahl aus Tabelle 1, die in derselben Zeile mit steht die entsprechende Variable.

Um beispielsweise das freie Mitglied der zweiten Reihe zu erhalten, multiplizieren wir die Zahl 1 mit 1 und addieren die Zahl -4 aus Tabelle 1. Wir bekommen -3. Auf die gleiche Weise finden wir den Koeffizienten für in der zweiten Zeile: . Da es in der vorherigen Tabelle keine Spalte mit einer neuen freien Variablen gibt, wird der Koeffizient der zweiten Zeile in der Spalte der neuen freien Variablen sein (das heißt, wir fügen von Tabelle 1 0 hinzu, da es in Tabelle 1 keine Spalte c gibt).

Die Indexzeile wird auf die gleiche Weise gefüllt:

Die so erhaltene Lösung ist wieder nicht optimal, da die Koeffizienten der freien Variablen in der Indexzeile wieder negativ sind.

Um zur nächsten Simplex-Tabelle zu gelangen, suchen wir die größte (Modulo) der Zahlen und , das heißt, die Module der Koeffizienten in der Indexzeile. Diese Zahl ist 2. Daher ist die führende Spalte die Spalte, die enthält.

Um nach der führenden Reihe zu suchen, suchen wir das Mindestverhältnis von freien Mitgliedern zu den Elementen der führenden Reihe. Wir bekommen:

.

Daher ist die führende Zeile diejenige, in die geschrieben wird, und das führende Element ist -3/2.

Kompilieren der dritten Simplextabelle

Wir schreiben die neue Basisvariable in die erste Zeile. In die Spalte, in der es war, tragen wir eine neue freie Variable ein.

Erste Linie:

Hilfskoeffizienten:

Tisch 3
Grundlegende Unbekannte	Kostenlose Mitglieder	Lose Unbekannte		Hilfskoeffizienten
		X4	X3
X1	2	-2/3	1/3
X2	2	-1/3	-1/3	1/2
X5	2	1/3	-2/3	-1/2
X6	4	1/3	1/3	-1/2
F	6	-4/3	-1/3	2

Die resultierende Lösung ist wieder nicht optimal, da die Koeffizienten der freien Unbekannten in der Indexzeile wieder negativ sind.

Um zur vierten Simplex-Tabelle zu gelangen, suchen wir die größte der Zahlen und . Dies ist eine Zahl.

Daher ist die führende Spalte diejenige mit .

Mindestmodul der Beziehungen freier Stäbe zu Elementen der Leitsäule:

.

Daher ist die führende Zeile diejenige, in die geschrieben wird, und das führende Element ist 1/3.

In der vierten Simplextabelle schreiben wir die neue Basisvariable in die erste Zeile. In die Spalte, wo es war, schreiben wir eine neue freie Variable .

Erste Linie:

Hilfskoeffizienten:

Tabelle 4
Grundlegende Unbekannte	Kostenlose Mitglieder	Lose Unbekannte		Hilfskoeffizienten
		X5	X3
X4	6	3	-2
X1	6	2	-1	2/3
X2	4	1	-1	1/3
X6	2	-1	1	-1/3
F	14	4	-3	4/3

Berechnung der restlichen Reihen am Beispiel der zweiten Reihe:

Auch die resultierende Lösung ist nicht optimal, aber schon besser als die vorherigen, da einer der Koeffizienten für freie Variablen in der Indexzeile nicht negativ ist.

Um den Plan zu verbessern, gehen wir zum nächsten Simplex-Tableau über.

Finde die größte der Zahlen 4 und . Diese Zahl ist 4. Daher ist die führende Spalte .

Um die führende Zeile zu finden, suchen Sie

.

Daher ist die führende Zeile diejenige, die enthält . Aber sie waren schon zusammen unter den freien Variablen. Um die nächste Variable von free nach basic zu übertragen, wählen wir daher eine andere führende Spalte aus - diejenige, in die geschrieben wird.

Um die führende Zeile zu finden, suchen Sie

.

Daher ist die Schlüsselzeile diejenige, in die geschrieben wird, und das führende Element ist 1.

In der fünften Simplextabelle wird die neue Basisvariable in die erste Zeile geschrieben. In die Spalte, wo es war, schreiben wir eine neue freie Variable .

Erste Linie:

Hilfskoeffizienten:

Tabelle 5
Grundlegende Unbekannte	Kostenlose Mitglieder	Lose Unbekannte		Hilfskoeffizienten
		X5	X6
X3	2	-1	1
X4	10			2
X1	8			1
X2	6			1
F	20	1	3	3

Versuchen wir gleich herauszufinden, ob die Lösung nicht optimal ist. Daher berechnen wir für die verbleibenden Zeilen nur die freien Terme (um die Werte der Basisvariablen herauszufinden, wenn die freien Variablen gleich Null sind) und die Koeffizienten für die freien Variablen in der Indexzeile.

Kostenlose Mitglieder:

In der zweiten Zeile ;

In der dritten Zeile ;

In der vierten Zeile.

Indexzeile:

Wir betrachten die Simplextabelle 5. Wir sehen, dass die optimale Lösung erhalten wurde, da die Koeffizienten für freie Unbekannte in der Indexzeile nicht negativ sind.

Simplexverfahren mit algebraischen Transformationen

Lassen Sie uns dasselbe Beispiel wie im vorherigen Absatz durch algebraische Transformationen lösen. Es sollte beachtet werden, dass es beim Lösen dieser Art von Simplex-Verfahren besser ist, die Zielfunktion nicht in die Form zu schreiben , da man sich in den Zeichen leicht verwechseln kann. Aber in diesem Fall wird der Punkt des Algorithmus, der das Optimalitätskriterium bestimmt, wie folgt modifiziert.

Wenn das Maximum (Minimum) der linearen Form gefunden wird und es keine Nicht-Basisvariablen mit positiven (negativen) Koeffizienten in ihrem Ausdruck gibt, ist das Optimalitätskriterium erfüllt und die resultierende Basislösung ist optimal - die Lösung ist beendet. Wenn beim Finden des Maximums (Minimums) einer linearen Form deren Ausdruck eine oder mehrere Nicht-Basisvariablen mit positiven (negativen) Koeffizienten enthält, gehen Sie zu einer neuen Basislösung.

Beispiel. Finden Sie das Maximum einer Funktion unter Nebenbedingungen

Schritt I. Wir führen weitere nichtnegative Variablen ein und reduzieren dieses Ungleichungssystem auf ein äquivalentes Gleichungssystem

.

Die eingeführten zusätzlichen Variablen werden als Hauptvariablen angenommen, da in diesem Fall die Basislösung des Systems leicht gefunden wird. Dann und sind kleinere Variablen.

Wenn wir die Hauptvariablen durch die nicht-grundlegenden Variablen ausdrücken, erhalten wir

Folglich entspricht diese Aufteilung der Variablen in Basis und Nichtbasis der Basislösung , was ungültig ist (zwei Variablen sind negativ) und daher nicht optimal. Gehen wir von dieser einfachen Lösung zu einer verbesserten über.

Um zu entscheiden, welche Variable von Nicht-Hauptvariablen in Hauptvariablen konvertiert werden soll, betrachten Sie eine der beiden verfügbaren Gleichungen des letzten Systems mit negativen freien Termen, z. B. die zweite. Es zeigt das und kann in die Hauptvariablen übersetzt werden, da sie in dieser Gleichung positive Koeffizienten haben (wenn sie also zunehmen, und dies geschieht, wenn wir eine von ihnen in die Hauptvariablen übersetzen, wird die Variable zunehmen).

Lassen Sie uns versuchen, in die Hauptvariable zu übersetzen. Um festzulegen, welche Variable von der Haupt- auf die Nichtbasis übertragen werden soll, finden wir den absoluten Wert des kleinsten Verhältnisses der freien Mitglieder des Systems zu den Koeffizienten bei . Wir haben . Sie ergibt sich aus der dritten Gleichung, die zeigt, dass die Variable in nicht-basische umgewandelt werden muss, was in der ursprünglichen Basislösung positiv ist. Folglich enthält die resultierende Basislösung, wie die ursprüngliche, zwei negative Komponenten, d. h. es wird keine Verbesserung beim Übergang zu einer solchen Basislösung geben.

Simplex-Methode− dies ist eine Methode der geordneten Aufzählung von Referenzplänen (die Ordnung wird durch eine monotone Änderung des Werts der Zielfunktion beim Übergang zum nächsten Plan sichergestellt). Dabei ist der Grundsatz zu beachten: Jeder nächste Schritt soll den Wert der Zielfunktion verbessern oder im Extremfall nicht verschlechtern.

Um das LLP zu lösen Simplex-Methode es wird auf die kanonische Form reduziert, d.h. von Beschränkungen - Ungleichheiten muss man Beschränkungen - Gleichheiten machen. Dazu wird jede Bedingung um eine zusätzliche nicht negative ergänzt Bilanz variabel mit dem „+“-Zeichen, wenn das Ungleichheitszeichen „£“ ist, und mit dem „–“-Zeichen, wenn das Ungleichheitszeichen „³“ ist.

In die Zielfunktion gehen diese zusätzlichen Variablen mit Nullkoeffizienten ein, d.h. der Zielfunktionseintrag ändert sich nicht. Jede Variable, die nicht der Nicht-Negativitätsbedingung unterliegt, kann als Differenz zweier nicht-negativer Variablen dargestellt werden: .

Wenn die Aufgabenbeschränkungen das Vorhandensein und den Verbrauch von Ressourcen widerspiegeln, ist der numerische Wert der zusätzlichen Variablen im Aufgabenplan, der in kanonischer Form geschrieben ist, gleich der Menge der ungenutzten Ressource.

Um das Problem mit der Simplex-Methode zu lösen, werden wir verwenden verkürzte Simplextabellen eines linearen Gleichungssystems und das modifizierte Jordan-Eliminierungsverfahren.

1. Wir erstellen den ersten Basisplan

Die Aufgabenstellung bleibt gleich. Bringen wir die Standardform des Ungleichungssystems (1) in die kanonische Form des Gleichungssystems, indem wir zusätzliche Bilanzvariablen einführen x 3 , x 4 , x 5 ,x 6 .

Im wirtschaftlichen Sinne die Werte zusätzlicher Variablen x 3 , x 4 , x 5 bestimmen die Bilanz der Rohstoffe nach dem Verkauf von Produkten.

Die Matrix des resultierenden Gleichungssystems hat die Form:

Das sieht man in der Matrix EIN der Basisminor 4. Ordnung ist die Determinante, zusammengesetzt aus Einheitskoeffizienten für zusätzliche Variablen x 3 , x 4 , x 5 ,x 6 , da er ungleich Null und gleich 1 ist. Das bedeutet, dass die Spaltenvektoren für diese Variablen linear unabhängig sind, d.h. bilden Basis, und die entsprechenden Variablen x 3 , x 4 , x 5 ,x 6 sind Basic(Basic). Variablen x 1 , x 2 wird aufgerufen frei(unerheblich).

Wenn freie Variablen x 1 und x 2 verschiedene Werte zu setzen, dann erhalten wir, wenn wir das System in Bezug auf die Grundvariablen lösen, eine unendliche Menge von bestimmten Lösungen. Wenn für freie Variablen nur Nullwerte gesetzt werden, dann aus einer unendlichen Menge bestimmter Lösungen, grundlegende Lösungen- Grundpläne.

Um herauszufinden, ob die Variablen basisch sein können, ist es notwendig, die Determinante zu berechnen, die aus den Koeffizienten dieser Variablen besteht. Wenn diese Determinante ungleich Null ist, können diese Variablen basisch sein.

Die Anzahl der Basislösungen und die entsprechende Anzahl der Gruppen von Basisvariablen kann nicht größer sein als , wobei n ist die Gesamtzahl der Variablen, r ist die Anzahl der Basisvariablen, r≤ m≤ n.

Für unsere Aufgabe r = 4; n= 6. Dann, d.h. 15 Gruppen von 4 Basisvariablen sind möglich (oder 15 Basislösungen).

Lösen wir das Gleichungssystem nach den Grundvariablen x 3 , x 4 , x 5 ,x 6:

Angenommen, die freien Variablen x 1 = 0, x 2 = 0 erhalten wir die Werte der Basisvariablen: x 3 = 312; x 4 = 15; x 5 = 24;x 6 = -10, d.h. die Grundlösung ist = (0; 0; 312; 15; 24; -10).

Diese Grundlösung ist inakzeptabel, Weil x 6 = –10 ≤ 0 und durch die Nebenbedingung x 6 ≥ 0. Daher statt der Variablen x 6 als Basis, müssen Sie eine andere Variable aus den freien nehmen x 1 oder x 2 .

Wir führen die weitere Lösung mit verkürzten Simplextabellen durch und füllen die Zeilen der ersten Tabelle mit den Koeffizienten des Systems wie folgt aus (Tabelle 1):

Tabelle 1

F- Die Zeichenfolge wird aufgerufen Index. Es ist mit objektiven Funktionskoeffizienten gefüllt, die mit entgegengesetzten Vorzeichen genommen wurden, da die Gleichung der Funktion dargestellt werden kann als F = 0 – (– 4x 1 – 3x 2).

In der Spalte der kostenlosen Mitglieder b ich Es gibt ein negatives Element b 4 = -10, d.h. die Lösung des Systems ist ungültig. Um eine gültige Lösung (Basisplan) zu erhalten, muss das Element b 4 muss nicht-negativ gemacht werden.

Wählen x 6 - eine Zeile mit einem negativen freien Mitglied. Diese Zeile enthält negative Elemente. Wählen Sie eine davon aus, zum Beispiel "-1" in x 1 -Spalte, und x 1 - Spalte akzeptieren als Berechtigungsspalte(es wird feststellen, dass die variable x 1 wird von kostenlos zu einfach wechseln).

Wir teilen kostenlose Mitglieder b ich auf den relevanten Elementen ein ist Spalte auflösen, erhalten wir wertende BeziehungenΘ ich==(24, 15, 12, 10). Von diesen wählen wir das kleinste positive (minΘ ich=10), was entsprechen wird Erlaubniszeile. Berechtigungszeichenfolge definiert eine Variable xj, die im nächsten Schritt aus der Basis herausragt und frei wird. Deshalb x 6 -Zeile ist eine zulässige Zeile, und das Element "-1" ist ermöglichendes Element. Wir umrunden es. Variablen x 1 und x 6 sind vertauscht.

Geschätzte Verhältnisse Θ ich in jeder Zeile werden durch die Regeln bestimmt:

1) Θ ich= wenn b ich und ein ist haben unterschiedliche Vorzeichen;

2) Θ ich= ∞ wenn b ich= 0 und ein ist < 0;

3) Θ ich= ∞ wenn ein ist = 0;

4) Θ ich= 0 wenn b ich= 0 und ein ist > 0;

5) Θ ich= wenn b ich und ein ist haben die gleichen Vorzeichen.

Wir gehen den Schritt der modifizierten jordanischen Elimination (MJJI) mit einem permissiven Element und erstellen eine neue Tabelle (Tabelle 2) nach folgender Regel:

1) Anstelle des auflösenden Elements (RE) wird ein Wert gesetzt, dessen Inverses, d.h. ;

2) die Elemente der zulässigen Linie werden in RE unterteilt;

3) die Elemente der Auflösungsspalte werden in RE unterteilt und die Vorzeichen wechseln;

4) die restlichen Elemente werden nach der Rechteckregel gefunden:

Aus Tabelle. 2 zeigt, dass die kostenlosen Mitglieder in b ich-Spalte sind nicht negativ, daher erhält man die zulässige Anfangslösung - erster Basisplan= (10; 0; 182; 5; 4; 0). In diesem Fall der Wert der Funktion F() = 40. Geometrisch entspricht dies der Spitze F(10; 0) Lösungspolygon (Abb. 1).

Tabelle 2

2. Wir prüfen den Plan auf Optimalität. Der Basisplan ist nicht optimal, denn in F-Linie hat einen negativen Koeffizienten "-4". Wir verbessern den Plan.

3. Finden einer neuen Basislinie

Wir wählen das zulassende Element gemäß der Regel aus:

Wir wählen den kleinsten negativen Koeffizienten in F-Zeile "-4", die die Freigabespalte bestimmt - x 6; Variable x 6 übersetzen in einfach;

Wir finden die Verhältnisse Θ ich, darunter wählen wir den kleinsten positiven, der der zulässigen Zeichenfolge entspricht:

Mindest Θ ich = Mindest(14, 5, 2, ∞) = 2, also x 5 - Zeile - freizügig, variabel x 5 übersetzen wir in frei (Variablen x 5 und x 6 sind vertauscht).

Am Schnittpunkt der zulässigen Zeile und Spalte befindet sich das zulässige Element "2";

Wir führen den Schritt SHMZhI aus, wir bauen die Tabelle auf. 3 nach der obigen Regel und erhalten einen neuen Referenzplan = (12; 0; 156; 3; 0; 2).

Tisch 3

4. Überprüfung des neuen Grundplans auf Optimalität

Auch der Basisplan ist nicht optimal, da in F-Linie hat einen negativen Koeffizienten "-1". Funktionswert F() = 48, was geometrisch der Spitze entspricht E(12; 0) Lösungspolygon (Abb. 1). Wir verbessern den Plan.

5. Finden einer neuen Basislinie

x 2-spaltig ist zulässig, da in F-Zeile ist der kleinste negative Koeffizient "-1". x 2 Spalten (Δ 2 = –1). Suche nach dem kleinsten Θ ich: Mindest Θ ich = Mindest(≈ 9, 6, ∞, 24) = 6, also x 4. Zeile - freizügig. Zulässiges Element "1/2". Variablen tauschen x 2 und x vier . Wir führen den Schritt SHMZhI aus, wir bauen die Tabelle auf. 4 erhalten wir einen neuen Referenzplan = (9; 6; 51; 0; 0; 5).

6. Überprüfung des Grundplans auf Optimalität

BEI F-Linie, alle Koeffizienten sind nicht negativ, daher ist der Referenzplan optimal. Entspricht geometrisch einem Punkt D(9;6) (siehe Abb. 1). Der optimale Plan gibt den Maximalwert der Zielfunktion c.u.

Hauptsächlich die Idee einer Simplex-Methode zur Lösung des LLP besteht in der konsequenten Verbesserung der LLP-Unterstützungslösungen.

Es gibt mehrere Möglichkeiten, die Simplex-Methode zu schreiben.

1. Die Grundform des Simplex-Verfahrens;
2. Simplex-Verfahren in Form einer Simplex-Tabelle;
3. Modifiziertes Simplex-Verfahren;
4. Simplex-Verfahren in Säulenform;
5. Simplex-Verfahren in Reihenform.

Lassen Sie uns den Maximalwert der Zielfunktion F(X) = 3x 1 +5x 2 +4x 3 unter den folgenden Randbedingungen definieren.
0,1x 1 +0,2x 2 +0,4x 3 ≤1100
0,05x 1 +0,02x 2 +0,02x 3 ≤120
3x1 +x2 +2x3 ≤8000

Zur Erstellung des ersten Referenzplans reduzieren wir das Ungleichungssystem auf ein Gleichungssystem, indem wir zusätzliche Variablen einführen (Übergang zur kanonischen Form).
0,1x1 + 0,2x2 + 0,4x3 + 1x4 + 0x5 + 0x6 = 1100
0,05 x 1 + 0,02 x 2 + 0,02 x 3 + 0 x 4 + 1 x 5 + 0 x 6 = 120
3x1 + 1x2 + 2x3 + 0x4 + 0x5 + 1x6 = 8000

Grundlegende Notation der Simplex-Methode

Die Lösung wird durchgeführt, indem die Basisvariablen durch Nichtbasisvariablen ausgedrückt werden: x0 = 3x1 +5x2 +4x3 x 4 = 1100 - 0,1 x 1 - 0,2 x 2 - 0,4 x 3 x 5 = 120 - 0,05 x 1 - 0,02 x 2 - 0,02 x 3 x 6 = 8000-3x 1 -x 2 -2x 3

Simplex-Verfahren in Form einer Simplex-Tabelle

Die Lösung erfolgt in Form einer Simplextabelle. Das Formular ist für die Berechnung auf einem Computer ausgelegt. Bei Verwendung einer künstlichen Basis wird eine spezielle Zahl M verwendet (normalerweise 10000).

Planen	Basis	BEI	x 1	x2	x 3	x4	x5	x6	Mindest
1	x4	1100	0.1	0.2	0.4	1	0	0	5500
	x5	120	0.05	0.02	0.02	0	1	0	6000
	x6	8000	3	1	2	0	0	1	8000
Indexzeile	F(X1)	0	-3	-5	-4	0	0	0	0
2	x2	5500	0.5	1	2	5	0	0	11000
	x5	10	0.04	0	-0.02	-0.1	1	0	250
	x6	2500	2.5	0	0	-5	0	1	1000
Indexzeile	F(X2)	27500	-0.5	0	6	25	0	0	0
3	x2	5375	0	1	2.25	6.25	-12.5	0	11000
	x1	250	1	0	-0.5	-2.5	25	0	250
	x6	1875	0	0	1.25	1.25	-62.5	1	1000
Indexzeile	F(X3)	27625	0	0	5.75	23.75	12.5	0	0

Modifiziertes Simplex-Verfahren

Koeffizientenmatrix A = a ij Matrix b. Iteration Nr. 1. = (4, 5, 6) Matrix c. c = (-3, -5, -4, 0, 0, 0) c B = (0, 0, 0) cN = (-3, -5, -4) Wir rechnen: Die Matrix B -1 wird durch algebraische Additionen berechnet. u = c B B -1 = (0, 0, 0)

Simplex-Verfahren in Säulenform

Wir gehen zur Säulenform des Simplexverfahrens über. Wir drücken jede Variable in Form von Nichtbasisvariablen aus. x 0 = 0-3(-x 1)-5(-x 2)-4(-x 3)+0(-x 4)+0(-x 5)+0(-x 6) x 1 = 0-1(-x 1)+0(-x 2)+0(-x 3)+0(-x 4)+0(-x 5)+0(-x 6) x 2 = 0+0(-x 1)-1(-x 2)+0(-x 3)+0(-x 4)+0(-x 5)+0(-x 6) x 3 = 0+0(-x 1)+0(-x 2)-1(-x 3)+0(-x 4)+0(-x 5)+0(-x 6) x 4 = 1100+0,1(-x 1)+0,2(-x 2)+0,4(-x 3)+1(-x 4)+0(-x 5)+0(-x 6) x 5 = 120+0,05(-x 1)+0,02(-x 2)+0,02(-x 3)+0(-x 4)+1(-x 5)+0(-x 6) x 6 = 8000+3(-x 1)+1(-x 2)+2(-x 3)+0(-x 4)+0(-x 5)+1(-x 6) Dieses System entspricht der Tabelle T 0 . 0 -1 0 0 0 0 -1 0 0 0 0 -1 1100 0.1 0.2 0.4 120 0.05 0.02 0.02 8000 3 1 2 0 -3 -5 -4

Simplex-Methode in Stringform

Als anfänglich zulässige Basis können wir B 0 = nehmen<4, 5, 6>. Sie entspricht der folgenden Tabelle. 1100 0.1 0.2 0.4 1 0 0 120 0.05 0.02 0.02 0 1 0 8000 3 1 2 0 0 1 0 -3 -5 -4 0 0 0

Die aus den Koeffizienten des Systems zusammengesetzte Matrix Q wird aufgerufen Simplex-Tisch entsprechend Basis B. Ein Simplex-Tableau wird aufgerufen zulässig, oder direkt zulässig, falls q i0 ≥ 0. Die Elemente q i0 der letzten Zeile der Simplextabelle Q werden aufgerufen relative Schätzungen.

Lösungsformen nach der Methode der künstlichen Basis

Für die Verwendung von künstlichen Variablen, die in die Zielfunktion eingeführt werden, wird eine sogenannte Strafe von M auferlegt, eine sehr große positive Zahl, die normalerweise nicht angegeben wird.
Die resultierende Basis wird als künstlich bezeichnet, und die Lösungsmethode wird als künstliche Basismethode bezeichnet.
Darüber hinaus beziehen sich künstliche Variablen nicht auf den Inhalt der Aufgabe, sondern ermöglichen es Ihnen, einen Ausgangspunkt zu erstellen, und der Optimierungsprozess zwingt diese Variablen dazu, Nullwerte anzunehmen und die Zulässigkeit der optimalen Lösung sicherzustellen.

Lösungsformen nach der Methode der künstlichen Basis:

1. M-Methode (Simplex-Tabelle);
2. zweistufiges oder zweiphasiges Simplex-Verfahren (Grundlegende Notation, modifiziertes Simplex-Verfahren, Simplex-Verfahren in Spaltenform, Simplex-Verfahren in Zeilenform).

Sind Einschränkungen mit dem Zeichen ≥ in der Bedingung des Problems vorhanden, so können diese auf die Form ∑a ji b j reduziert werden, indem beide Teile der Ungleichung mit -1 multipliziert werden. Wir führen m zusätzliche Variablen x n+j ≥0(j =1,m ) ein und transformieren die Nebenbedingungen in die Form von Gleichheiten

(2)

Nehmen wir an, dass alle Anfangsvariablen des Problems x 1 , x 2 ,..., x n nichtbasisch sind. Dann sind die zusätzlichen Variablen grundlegend, und eine bestimmte Lösung des Systems von Beschränkungen hat die Form

x 1 = x 2 = ... = x n = 0, x n+ j = b j , j = 1,m . (3)

Da in diesem Fall der Wert der Zielfunktion F 0 = 0 ist, können wir F(x) wie folgt darstellen:

F(x)=∑c ich x ich + F 0 =0 (4)

Die anfängliche Simplex-Tabelle (Simplex-Tabelle 1) wird basierend auf den Gleichungen (2) und (4) kompiliert. Wird den zusätzlichen Variablen x n+j wie in (2) das „+“-Zeichen vorangestellt, so werden alle Koeffizienten vor den Variablen x i und dem freien Term b j unverändert in die Simplextabelle eingetragen. Die Koeffizienten der Zielfunktion bei ihrer Maximierung werden mit entgegengesetzten Vorzeichen in die unterste Zeile der Simplextabelle eingetragen. Freie Mitglieder in der Simplex-Tabelle bestimmen die Lösung des Problems.

Der Algorithmus zur Lösung des Problems lautet wie folgt:

1. Schritt. Die Elemente der Spalte freie Mitglieder werden nachgeschlagen. Wenn sie alle positiv sind, wurde eine akzeptable Basislösung gefunden, und man sollte mit Schritt 5 des Algorithmus fortfahren, der dem Finden der optimalen Lösung entspricht. Wenn das anfängliche Simplex-Tableau negative freie Terme enthält, ist die Lösung nicht gültig und Sie sollten mit Schritt 2 fortfahren.

2. Schritt. Um eine praktikable Lösung zu finden, wird durchgeführt, während es notwendig ist, zu entscheiden, welche der Nichtbasisvariablen in die Basis aufgenommen und welche Variable aus der Basis entfernt werden soll.

Tabelle 1.

x n

Basisvariablen	Kostenlose Mitglieder in Einschränkungen	Nicht grundlegende Variablen
		x 1	x2	...	xl	...
xn+1	b 1	eine 11	eine 12	...	ein 1l	...	ein 1n
xn+2	b 2	eine 21	eine 22	...	ein 2l	...	ein 2n
.	.	.	.	.	.	.	.
.	.	.	.	.	.	.	.
.	.	.	.	.	.	.	.
xn+r	b2	ein r1	ein r2	...	ein rl	...	ein rn
.	.	.	.	.	.	.	.
.	.	.	.	.	.	.	.
.	.	.	.	.	.	.	.
xn+m	b m	ein m1	ein m2	...	ein ml	...	amn
F(x)max	F0	-c 1	-c 2	...	-c 1	...	-c n

Wählen Sie dazu eines der negativen Elemente der Spalte der freien Mitglieder (es sei b 2 führend oder zulassend. Wenn in der Zeile mit einem negativen freien Mitglied keine negativen Elemente vorhanden sind, ist das Beschränkungssystem inkonsistent und das Problem hat keine Lösung.

Gleichzeitig wird die Variable, die bei einer Erhöhung des gewählten NP x l als erste das Vorzeichen wechselt, aus dem BP ausgeschlossen. Dies ist x n+r , dessen Index r aus der Bedingung bestimmt wird

diese. die Variable, die dem kleinsten Verhältnis des freien Terms zum Element der ausgewählten Leitspalte entspricht. Diese Beziehung heißt Simplex-Beziehung. Es sollten nur positive Simplexbeziehungen berücksichtigt werden.

Der der Variablen x n+r entsprechende String wird aufgerufen führen oder zulassen. Das Element der Simplextabelle a rl , das sich am Schnittpunkt der führenden Zeile und der führenden Spalte befindet, wird als führendes oder auflösendes Element bezeichnet. Das Finden des führenden Elements beendet die Arbeit mit jedem nächsten Simplex-Tableau.

3. Schritt. Es wird eine neue Simplextabelle berechnet, deren Elemente aus den Elementen der Simplextabelle des vorherigen Schritts neu berechnet und mit einem Apostroph gekennzeichnet werden, d.h. b" j , a" ji , c" ich , F" 0 . Die Elemente werden nach folgenden Formeln neu berechnet:

Zuerst werden die Zeilen und Spalten, die in der vorherigen Simplex-Tabelle führend waren, in die neue Simplex-Tabelle gefüllt. Ausdruck (5) bedeutet, dass das Element a "rl anstelle des führenden Elements gleich dem Kehrwert des Elements der vorherigen Simplextabelle ist. Die Elemente der Zeile a ri werden durch das führende Element und die Elemente von dividiert Spalte a jl werden ebenfalls durch das führende Element dividiert, aber mit umgekehrtem Vorzeichen genommen. Die Elemente b" r und c" l werden nach dem gleichen Prinzip berechnet.

Der Rest der Formeln kann einfach mit geschrieben werden.

Das Rechteck wird nach der alten Simplextabelle so aufgebaut, dass eine seiner Diagonalen durch die umgerechneten (a ji) und führenden (a rl) Elemente gebildet wird (Abb. 1). Die zweite Diagonale ist eindeutig bestimmt. Um ein neues Element a "ji" zu finden, wird das Produkt der Elemente der gegenüberliegenden Diagonalen dividiert durch das führende Element von Element a ji subtrahiert (dies wird durch das Zeichen" - "an der Zelle angezeigt). In ähnlicher Weise werden die Elemente b" j, (j≠r) und c" i werden neu berechnet, (i≠l).

4. Schritt. Die Analyse einer neuen Simplex-Tabelle beginnt mit dem 1. Schritt des Algorithmus. Die Aktion wird fortgesetzt, bis eine zulässige Grundlösung gefunden ist, d.h. alle Elemente der Spalte für freie Mitglieder müssen positiv sein.

5. Schritt. Wir glauben, dass eine akzeptable Grundlösung gefunden wurde. Wir betrachten die Koeffizienten der Geraden der Zielfunktion F(x) . Ein Zeichen für die Optimalität einer Simplex-Tabelle ist die Nicht-Negativität der Koeffizienten für Nichtbasisvariablen in der F-Zeile.

Reis. 1. Rechteckregel

Wenn unter den Koeffizienten der F-Reihe negativ ist (mit Ausnahme des freien Begriffs), müssen Sie zu einer anderen Grundlösung gehen. Bei der Maximierung der Zielfunktion umfasst die Basis die der Nichtbasisvariablen (z. B. x l), deren Spalte dem maximalen Absolutwert des negativen Koeffizienten c l in der untersten Zeile der Simplextabelle entspricht. Damit können Sie die Variable auswählen, deren Erhöhung zu einer Verbesserung der Zielfunktion führt. Die der Variablen x l entsprechende Spalte wird Leitspalte genannt. Gleichzeitig wird die Variable x n+r von der Basis ausgeschlossen, deren Index r durch das minimale Simplexverhältnis bestimmt wird:

Die Zeile, die x n+r entspricht, wird als führende Zeile bezeichnet, und das Element der Simplex-Tabelle a rl , das sich am Schnittpunkt der führenden Zeile und der führenden Spalte befindet, wird aufgerufen führendes Element.

6. Schritt. nach den im 3. Schritt festgelegten Regeln. Das Verfahren wird fortgesetzt, bis eine optimale Lösung gefunden ist oder gefolgert wird, dass sie nicht existiert.

Wenn bei der Optimierung der Lösung in der führenden Spalte alle Elemente nicht positiv sind, kann die führende Zeile nicht ausgewählt werden. In diesem Fall ist die Funktion im Bereich der zulässigen Lösungen des Problems nicht nach oben beschränkt und F max ->&∞.

Wenn beim nächsten Schritt der Suche nach einem Extremum eine der Basisvariablen gleich Null wird, dann heißt die entsprechende Basislösung entartet. In diesem Fall tritt das sogenannte Looping auf, das dadurch gekennzeichnet ist, dass sich dieselbe Kombination von BP mit einer bestimmten Frequenz zu wiederholen beginnt (der Wert der Funktion F bleibt in diesem Fall erhalten) und nicht umgeschaltet werden kann eine neue akzeptable Basislösung. Looping ist einer der Hauptnachteile der Simplex-Methode, aber es ist relativ selten. In der Praxis wird in solchen Fällen üblicherweise darauf verzichtet, die Variable in die Basis einzugeben, deren Spalte dem maximalen Absolutwert des negativen Koeffizienten in der Zielfunktion entspricht, und es wird zufällig eine neue Basislösung gewählt.

Beispiel 1. Lösen Sie ein Problem

max(F(x) = -2x 1 + 5x 2 | 2x 1 + x 2 ≤7; x 1 + 4x 2 ≥8; x 2 ≤4; x 1,2 ≥0)

Simplex-Methode und geben Sie eine geometrische Interpretation des Lösungsprozesses.

Die grafische Interpretation der Lösung des Problems ist in Abb. 1 dargestellt. 2. Der Maximalwert der Zielfunktion wird an der Spitze des ODZP mit den Koordinaten erreicht. Lassen Sie uns das Problem mit Simplex-Tabellen lösen. Wir multiplizieren die zweite Nebenbedingung mit (-1) und führen zusätzliche Variablen ein, um die Ungleichungen dann in die Form von Gleichheiten zu bringen

Die anfänglichen Variablen x 1 und x 2 werden als nicht basisch betrachtet, und die zusätzlichen x 3 , x 4 und x 5 werden als basisch betrachtet, und wir erstellen eine Simplex-Tabelle (Simplex-Tabelle 2). Die der Simplextabelle entsprechende Lösung. 2, ist nicht gültig; das führende Element wird umrissen und gemäß Schritt 2 des obigen Algorithmus ausgewählt. Der nächste Simplex-Tab. 3 definiert eine zulässige Basislösung; 2 Das Leitelement wird entsprechend dem 5. Schritt des Algorithmus zur Problemlösung skizziert und ausgewählt. Tab. 4 entspricht der optimalen Lösung des Problems, also: x 1 = x 5 = 0; x 2 \u003d 4; x 3 \u003d 3; x 4 = 8; Fmax = 20.

Reis. 2. Grafische Lösung des Problems