Lösung der Produktionsaufgabe auf eine tabellarische Simplex-Methode. Lösung von Systemen linearer Gleichungen von Jordan-Gauss
Betrachten Sie die Entscheidung der ZLP-Simplex-Methode und geben Sie sie in Bezug auf die Maximierungsaufgabe an.
1. Durch die Bedingung des Problems wird sein mathematisches Modell erstellt.
2. Das entworfene Modell wird in kanonische Form umgewandelt. Dies kann die Basis mit dem ursprünglichen Support-Plan auswählen.
3. Das kanonische Modell der Aufgabe ist in Form eines Simplex-Tisches geschrieben, so dass alle freien Mitglieder nicht negativ sind. Wenn der anfängliche Support-Plan zugewiesen wird, gehen Sie zu Abschnitt 5.
Simplex-Tabelle: Das System der restriktiven Gleichungen und der Zielfunktion in Form von Ausdrücken, die relativ zur ursprünglichen Basis erlaubt sind. Die Zeichenfolge, in die die Faktoren der Zielfunktion F in die F-String oder eine Zeile der Zielfunktion geschrieben sind.
4. Finden Sie einen anfänglichen Referenzplan, erzeugt Simplex-Transformationen mit positiven Auflösungselementen, die die Mindest-Simplex-Beziehungen erfüllen, und ohne Berücksichtigung der Anzeichen der Elemente der F-Zeichenfolge. Wenn während Transformationen eine 0-String erfüllt ist, davon alle Elemente zusätzlich zu einem freien Element, Nullen, dann ist das System der restriktiven Gleichungen des Problems unverständlich. Wenn ein 0-String erfüllt ist, in dem sich neben einem freien Element keine anderen positiven Elemente befinden, hat das System der restriktiven Gleichungen keine nicht negativen Lösungen.
Das System (2.55), (2.56) auf eine neue Basis bringen, wird Simplex Transformation bezeichnet. Wenn die Simplex-Transformation als formaler algebraischer Operation betrachtet wird, kann darauf hingewiesen werden, dass infolge dieses Vorgangs die Rollen zwischen zwei in einigen System enthaltenen Variablen umverteilt werden lineare Funktionen: Eine Variable von den abhängigen Änderungen an der unabhängigen und dem anderen im Gegenteil - von unabhängig vom abhängigen Abhängigen. Eine solche Operation ist in Algebra namens Schardans Ausnahme bekannt.
5. Fundierte den ersten Referenzplan wird auf Optimalität untersucht:
a) Wenn in der F-Leitung keine negativen Elemente vorhanden sind (nicht das kostenlose Element zählen), ist der Plan optimal. Wenn es keine Null gibt, ist der optimale Plan der einzige; Wenn es mindestens eine Null gibt, sind die optimalen Pläne unendlich eingestellt.
b) Wenn in der F-Line mindestens ein negatives Element vorhanden ist, an dem die Invasory-Elementsäule entspricht,<
c) Wenn sich mindestens ein negatives Element in der F-Leitung befindet, und in seiner Säule gibt es mindestens ein Positiv, dann können Sie zu einem neuen Referenzplan gehen, der nahe an der optimalen Seite ist. Dazu muss die angegebene Spalte einer Genehmigung durch minimale Simplex-Beziehung zugewiesen werden, um die Zulassungszeichenfolge zu finden und durchzuführen simplex-Konvertierung.. Der resultierende Referenzplan wird erneut auf Optimalität untersucht. Der beschriebene Prozess wird wiederholt, bis der optimale Plan erzielt wird oder vor der Festlegung einer Intractability des Problems.
Die Spalte von Koeffizienten mit einer in der Basis enthaltenen Variablen wird als permissiv bezeichnet. Wenn Sie also eine Variable, die in die Basis eingesetzt ist, in die Basis (oder die Auswahl der zulässigen Spalte an einem negativen Element der F-Leitung eingesetzt wird, sorgen wir für die zunehmende Funktion F.
Etwas schwieriger wird durch die Variable bestimmt, die von der Basis ausgeschlossen wird. Dazu werden die Beziehung freier Mitglieder an die positiven Elemente der Auflösungssäule (solche Beziehungen Simplex Simplex genannt) und unter ihnen das kleinste finden, das die Saite (Genehmigung) bestimmt, die die exklusive Variable enthält. Die Auswahl einer Variablen, die aus der Basis ausgeschlossen ist (oder die Auswahl der Auflösungslinie), wird durch ein minimales Simplex-Verhältnis, wie bereits festgelegt, die Positivität der Grundkomponenten in einem neuen Referenzplan gewährleistet.
In Absatz 3 des Algorithmus wird davon ausgegangen, dass alle Elemente der Spalte freier Elemente nicht negativ sind. Diese Anforderung ist nicht erforderlich, aber wenn es abgeschlossen ist, werden alle nachfolgenden Simplex-Transformationen nur mit positiven Auflösungselementen hergestellt, was beim Berechnen praktisch ist. Wenn in der Spalte freier Elemente negative Nummern vorhanden sind, wird das Auflösungselement wie folgt ausgewählt:
1) Zeigen Sie eine Zeichenfolge an, die ein negatives freies Element erfüllt, beispielsweise eine T-Line, und wählen Sie ein negatives Element darin aus, und die ihm entsprechende Säule wird für den Permissive genommen (wir gehen davon aus, dass die Aufgabenbeschränkungen gemeinsam sind);
2) Erstellen Sie die Beziehung zwischen Elementen der Kolonne freier Elemente an die entsprechenden Elemente der Auflösungssäule mit den gleichen Zeichen (Simplex-Beziehungen);
3) Wählen Sie aus Simplex-Beziehungen die kleinste. Es bestimmt die Zulassungszeichenfolge. Lass es zum Beispiel P-Hub sein;
4) Bei der Kreuzung der Auflösungsspalte und Linien sind das zulässige Element. Wenn ein I-Line-Element erlaubt ist, dann wird nach der Simplex-Umwandlung das freie Element dieser Zeile positiv. Andernfalls wenden Sie sich in der nächsten Schritte an die T-Zeile. Wenn die Aufgabe lösbar ist, bleibt eine bestimmte Anzahl von Schritten in der Spalte freier Elemente keine negativen Elemente.
Finden Sie den ursprünglichen Support-Plan, den kanonischen Typ ZLP
Die Idee einer konsistenten Verbesserungslösung basierte auf einem universellen Verfahren zur Lösung einer linearen Programmieraufgabe - Simplex-Methode oder einer konsistenten Verbesserungsmethode-Methode.
Die geometrische Bedeutung des SimplEX-Verfahrens besteht in einem sequentiellen Übergang von einem Scheitelpunkt von einem Scheitelpunkt der Polyeder-Grenzbeschränkungen (anfänglich) bis zum Nachbarn, in dem die lineare Funktion den besten (zumindest nicht nicht der schlimmste) Wert relativ zum Objektiv der Problem; Solange die optimale Lösung gefunden wird - der Scheitelpunkt, in dem der optimale Wert der Zielfunktion erreicht ist (wenn die Aufgabe das endgültige Optimum hat).
Zum ersten Mal wurde die Simplex-Methode 1949 vom amerikanischen Wissenschaftler J. Danzig vorgeschlagen, jedoch wurden 1939 die Ideen der Methode von russischen Wissenschaftlern L.v entwickelt. Kantorovich.
Simplex-Methode, mit der Sie jede Aufgabe der linearen Programmierung, Universal, lösen können. Derzeit wird es für Computerberechnungen verwendet, jedoch können einfache Beispiele unter Verwendung des Simplex-Verfahrens manuell gelöst werden.
Um die Simplex-Methode umzusetzen - eine konsistente Verbesserung der Lösung - müssen drei Hauptelemente beherrscht werden:
Ein Verfahren zum Bestimmen einer anfänglichen zulässigen Basislösung des Problems;
Übergangsregel zum Besseren (genauer, nicht die schlechteste) Lösung;
Kriterium für die Überprüfung der Optimalität der gefundenen Lösung.
Um die Simplex-Methode zu verwenden, muss das lineare Programmierproblem an kanonische Form gegeben werden, d. H. Das System von Einschränkungen muss in Form von Gleichungen dargestellt werden.
Die Literatur beschreibt detailliert: Finden des ursprünglichen Referenzplans (anfängliche gültige Basislösung), auch auf künstliche Methode, um den optimalen Referenzplan, der Aufgaben mit Simplex-Tischen zu löst.
58. Der Haupttheorem des Symbols der Methode.
???????????????????????????????????????????????????????????????????????
59. Alternative zum Optimum in ZLP, Degeneration in ZLP.
Degeneration von linearen Programmieraufgaben
In Anbetracht der Simplex-Methode gingen wir davon aus, dass das Problem der linearen Programmierung nicht entspricht, d. H. Jeder Referenzplan enthält glatte M-positive Komponenten, wobei M die Anzahl der Einschränkungen des Problems ist. In einem degenierenden Referenzplan erleidet die Anzahl der positiven Komponenten weniger als die Anzahl der Einschränkungen: Einige Basisgrößen, die diesem Referenzplan entsprechen, nehmen Nullwerte an. Verwenden der geometrischen Interpretation für den einfachsten Fall, wenn n - m \u003d 2 (die Anzahl der nicht-Trennungsvariablen 2 ist), kann es leicht durch eine degenerierte Aufgabe von Nondegenerate unterschieden werden. Bei dem entarteten Problem in einem Scheitelpunkt des Polyeders sind mehr als zwei direkte Gleichlinien, die durch die Gleichungen des Formulars Xi \u003d 0 beschrieben werden, schneiden. Dies bedeutet, dass eine oder mehrere Seiten der Polygonbedingungen an der Stelle angezogen sind. In ähnlicher Weise werden bei n - M \u003d 3 mehr als 3 Ebenen Xi \u003d 0 in dem degenerierten Problem in einem Scheitelpunkt gekreuzt. Unter der Annahme von nicht degenerierter Aufgabe
es gab nur einen Wert, der den Index der von der Basis des Vektors hinterlegten Bedingungen ermittelte (abgeleitet von der Grundvariablen). IM
die entartete Aufgabe kann auf mehreren Indizes gleichzeitig (für mehrere Zeilen) erreicht werden. In diesem Fall sind in einem Referenzplan mehrere grundlegende Variablen Null. Wenn sich das Problem der linearen Programmierung als degeneriert, kann mit einer schlechten Auswahl des Vektors der von der Basis abgeleiteten Bedingungen eine unendliche Bewegung auf den Basen desselben Referenzplanes auftreten. Dies ist das sogenannte Zinkioning-Phänomen. Obwohl in den praktischen Aufgaben der linearen Programmierung die Schleife eher selten ist, ist es nicht ausgeschlossen. Eine der Methoden zur Bekämpfung der Degeneration besteht darin, das Problem durch "unbedeutende" Änderungen in den richtigen Teilen des Systems der Einschränkungen durch Größenordnung so umzuwandeln, dass die Aufgabe nicht gleichzeitig geworden ist und gleichzeitig diese Änderung tut den optimalen Aufgabenplan nicht beeinträchtigen. Häufiger umfassen die implementierten Algorithmen einige einfache Regeln, die die Wahrscheinlichkeit der Schleifen der Schleifen oder Überwindung verringern. Lassen Sie die Variable XJ notwendig sein, um die Basis herzustellen. Erwägen
mehrere Indizes E0, bestehend aus denjenigen, für die er erreicht wird. Viele Indizes I, für die diese Bedingung durchgeführt wird, bedeuten wir von E0 ,. Wenn E0 aus einem Element besteht, ist die Grundlage der AI-Bedingungen von der Basis ausgeschlossen (die XI-Variable erfolgt nicht-Bacon). Wenn E0 aus mehr als einem Element besteht, wird der Satz von E1 zusammengestellt, der besteht, aus dem er erreicht wird. Wenn E1 aus einem Index K besteht, wird die XK-Variable aus der Basis angezeigt. Ansonsten sind viele E2 kompiliert usw. Praktisch ist es notwendig, wenn die Looping bereits entdeckt wurde.
Alternative zum Optimum in ZLP ?????????????????
60. Die Methode der künstlichen Base. M-Aufgabe. Der Verbindungssatz zwischen den Lösungen des ursprünglichen Problems und der M-Task.
Methode der künstlichen Basis.
Die künstliche Basismethode wird verwendet, um die zulässige Basislösung des linearen Programmierproblems zu finden, wenn die Bedingungen der Art der Gleichungen in der Bedingung vorhanden sind. Betrachten Sie die Aufgabe:
max (f (x) \u003d ΣCixi | ΣAjixi \u003d BJ, J \u003d 1, m; xi≥0).
In Einschränkungen sind die sogenannten "künstlichen Variablen" RJ wie folgt:
ΣAjix + rj \u003d bj, j \u003d 1, m; f (x) \u003d Σcixi-mσrj
Mit der Einführung künstlicher Variablen auf künstlicher Methode wird ein ausreichend großer Koeffizient M der Zielfunktion zugeschrieben, wodurch die Geldbuße für die Einführung künstlicher Variablen sinnvoll ist. Bei der Minimierung werden künstliche Variablen in die Zielfunktion mit dem Koeffizienten M aufgegeben. Die Einführung von künstlichen Variablen ist zulässig, wenn sie während des Problems der Lösung des Problems konsequent auf Null beziehen.
Der Simplex-Tisch, der in dem Lösungsprozess mit dem Verfahren der künstlichen Base kompiliert ist, wird erweitert genannt. Es unterscheidet sich von der üblichen dadurch, dass sie zwei Zeilen für die Funktion des Ziels enthält: eins - für die Komponente F \u003d ΣCIXI, und der andere ist für die Komponente m ΣRJ, wir berücksichtigen das Verfahren zum Lösen des Problems in einem bestimmten Beispiel.
Beispiel 1. Finden Sie die maximale Funktion f (x) \u003d -x1 + 2x2 - X3 mit Einschränkungen:
x1≥0, x2≥0, x3≥0.
Wenden Sie die künstliche Basismethode an. Wir führen künstliche Variablen in den Einschränkungen des Problems ein
2x1 + 3x2 + x3 + R1 \u003d 3;
x1 + 3x3 + R2 \u003d 2;
Die Funktion des Zwecks f (x) -m σrj \u003d -x1 + 2x2 - X3 - M (R1 + R2).
Drücken Sie die Summe R1 + R2 aus dem Limit-System aus: R1 + R2 \u003d 5 - 3x1 - 3x2 - 4x3, dann f (x) \u003d -x1 + 2x2 - x3 - m (5 - 3x1 - 3x2 - 4x3).
Beim Zeichnen des ersten Simplex-Tischs (Tabelle 1) gehen wir davon aus, dass die anfänglichen Variablen X1, X2, X3 nicht trennen, und die eingeführten künstlichen Variablen sind basisch. In den Aufgaben der Maximierung ändert sich das Anzeichen von Koeffizienten mit Nicht-Bacon-Variablen in F- und M-Linien auf das Gegenteil. Das konstante Wertschild in der M-Zeichenfolge ändert sich nicht. Die Optimierung wird zuerst von der M-Line durchgeführt. Die Auswahl der Host-Spalte und -leitungen, alle Simplex-Transformationen im Fortschritt der künstlichen Basismethode werden wie in der üblichen Simplex-Methode ausgeführt.
Der maximale Inklusivwert des negativen Koeffizienten (-4) bestimmt die Bleisäule und die Variable X3, die zur Grundlage geht. Das Mindest-Simplex-Verhältnis (2/3) entspricht der zweiten Linie des Tisches, daher muss die Variable R2 daher von der Basis ausgeschlossen sein. Das Leitungselement ist durch Kontur eingekreist.
In künstlicher Basis werden künstliche Variablen, aus der Basis ausgeschlossen, nicht mehr dazu zurückgegeben, daher werden die Säulen der Elemente solcher Variablen abgesenkt. Tabelle. 2. Reduziert auf 1 Spalte. Durch die Neuberechnung dieser Tabelle gehen Sie zum Tisch. 3. In dem die Zeile M zurückgesetzt wurde, kann es entfernt werden. Nach Ausschluss aus der Grundlage aller künstlichen Variablen erhalten wir eine zulässige grundlegende Lösung des ursprünglichen Problems, das in dem in Betracht gezogenen Beispiel optimal ist:
x1 \u003d 0; x2 \u003d 7/9; Fmax \u003d 8/9.
Wenn beim Entfernen der M-Line die Lösung nicht optimal ist, wird das Optimierungsvorgang fortgesetzt und wird von der üblichen Simplex-Methode durchgeführt. Betrachten Sie ein Beispiel, in dem es Einschränkungen aller Arten gibt: ≤, \u003d, ≥
Die Aufgabe
Finden Sie optimale Größen der Produktion von Arten A, B und B. Kosten für Rohstoffe pro Produktionseinheit: A - 5, B - 2, B - 4. Das Rohstoffvolumen beträgt 2000 Einheiten. Ausrüstungskosten pro Produktionseinheit: A - 4, B - 5, B - 4. Die Ausrüstungsvolume beträgt 1000 Einheiten. Gewinn aus dem Verkauf einer Produkteinheit: A - 10, B - 8, in - 12. Das Kriterium - der maximale Gewinn des Unternehmens. Produktherstellung A muss mindestens 100 Einheiten sein. Die Produktion von Produkten B sollte mindestens 50 Einheiten betragen.
Lösung des Problems der Simplex M-Methode
1) Bestimmen des optimalen Produktionsplans
Sei x1, x2, x3 die Menge der von der Form A, B bzw. b hergestellten Produkte. Dann ist das mathematische Modell des Problems:
F \u003d 10 · x1 + 8 · x2 + 12 · x3 -\u003e max
Wir führen zusätzliche Variablen X4 ≥ 0, x5 ≥ 0, x6 ≥ 0, x7 ≥ 0 ein, damit Ungleichheiten in Gleichungen umgewandelt werden.
Um eine ursprüngliche Basis auszuwählen, führen wir künstliche Variablen X8 ≥ 0, x9 ≥ 0 und eine sehr große Anzahl M (M -\u003e ∞) ein. Wir lösen M-Methode.
F \u003d 10 · x1 + 8 · x2 + 12 · x3 + 0 · x4 + 0 · x5 + 0 · x6 + 0 · x7- m · x8- m · x9 -\u003e max
Als Basis nehmen Sie x4 \u003d 2000; x5 \u003d 1000; x8 \u003d 100; x9 \u003d 50.
Daten, die wir in den Simplex-Tisch eingeben
Simplex Tabelle Nr. 1
Zielfunktion:
0 · 2000 + 0 · 1000 + (- m) · 100 + (- m) · 50 \u003d - 150m
Berechnen Sie die Bewertungen durch die Formel:
Δ1 \u003d 0 · 5 + 0 · 4 + (- m) · 1 + (- m) · 0 - 10 \u003d - M - 10
Δ2 \u003d 0 · 2 + 0 · 5 + (- m) · 0 + (- m) · 1 - 8 \u003d - M - 8
Δ3 \u003d 0 · 4 + 0 · 4 + (- m) · 0 + (- m) · 0 - 12 \u003d - 12
Δ4 \u003d 0 · 1 + 0 · 0 + (- m) · 0 + (- m) · 0 - 0 \u003d 0
Δ5 \u003d 0 · 0 + 0 · 1 + (- m) · 0 + (- m) · 0 - 0 \u003d 0
Δ6 \u003d 0 · 0 + 0 · 0 + (- m) · (-1) + (- m) · 0 - 0 \u003d m
Δ7 \u003d 0 · 0 + 0 · 0 + (- m) · 0 + (- m) · (-1) - 0 \u003d m
Δ2 \u003d 0 · 0 + 12 · 0 + 10 · 0 + 8 · 1 - 8 \u003d 0
Δ3 \u003d 0 · 0 + 12 · 1 + 10 · 0 + 8 · 0 - 12 \u003d 0
Δ4 \u003d 0 · 1 + 12 · 0 + 10 · 0 + 8 · 0 - 0 \u003d 0
Δ5 \u003d 0 · (-1) + 12 · 1/4 + 10 · 0 + 8 · 0 - 0 \u003d 3
Δ6 \u003d 0 · 1 + 12 · 1 + 10 · (-1) + 8 · 0 - 0 \u003d 2
Δ7 \u003d 0 · (-3) + 12 · 5/4 + 10 · 0 + 8 · (-1) - 0 \u003d 7
Da es keine negativen Schätzungen gibt, ist der Plan optimal.
Problem lösen: x1 \u003d 100; x2 \u003d 50; x3 \u003d 175/2 \u003d 87,5; x4 \u003d 1050; x5 \u003d 0; x6 \u003d 0; x7 \u003d 0; Fmax \u003d 2450.
Antwort: x1 \u003d 100; x2 \u003d 50; x3 \u003d 175/2 \u003d 87,5; x4 \u003d 1050; x5 \u003d 0; x6 \u003d 0; x7 \u003d 0; FMAX \u003d 2450TO Es ist notwendig, x1 \u003d 100-Einheiten von Produkten des Formulars A, X2 \u003d 50 Einheiten des Produkts des Formulars B und X3 \u003d 87.5 Produkte des Typs V herzustellen. V. Maximaler Gewinn werden fmax \u003d 2450-Einheiten sein .
Der Verbindungssatz zwischen den Lösungen des ursprünglichen Problems und der M-Task.
???????????????????????
Betrachten Sie im Detail, wie Simplex-Tabellen neu berechnet werden (im Beispiel einer Iteration). Angenommen, es gibt einen Simplex-Tisch, der auf dargestellt ist Abb. Die Aufgabe, die Zielfunktion zu maximieren, wird gelöst. Die zulässige Spalte entspricht der Variablen x 2.und eine variable Zeichenfolge auflösen x 3. (Rote Zahlen), an ihrer Kreuzung gibt es ein Auflösungselement (Zelle mit grauem Hintergrund). Das erste, was wir tun müssen, ist, es zu ersetzen. Die Zulassungszeichenfolge zeigt an, welche Variable aus der Basis entfernt werden muss (in unserem Fall x 3.), und die permissive Spalte zeigt an, welche Variable die Basis eingeben soll (in unserem Fall) x 2.). Auf der Abb.2. Die Austauschfakte konzentriert sich auf die blaue Linie.
Jetzt kalkulieren wir die Elemente neu in der Auflösungszeile. Um dies zu tun, teilen Sie jeden von ihnen einfach auf das Auflösungselement (in unserem Beispiel) 4 ). Alle Elemente des Auflösungsspaltenresetes, neben dem Element, das in der Auflösungszeile steht. (Sehen Abb.2.)
Bild 1
Der Rest der Tabellenzellen (außer der Säule "Haltung") werden von der sogenannten sogenannten neu berechnet rechtextregel.Die Bedeutung, deren Bedeutung am einfachsten ist, das Beispiel zu verstehen. Müssen Sie das aufgebaute Element neu berechnen Abb Rote Kontur. Wir verbringen geistig von einer vertikalen und horizontalen Linie zur Kreuzung, mit einer Auflösungszeichenfolge und einer Säule der Spalte. Elemente, die in den Kreuzungsplätzen stehen, die mit blauen Konturen eingekreist werden (siehe Abb). Der neue Wert des "roten" Elements ist der aktuelle Wert des Elements des Minus des Produkts des "Blau", das in das zulässige (graue ") Element aufgeteilt ist (siehe Abb). Also: 18 - (64 * -1) / 4 = 34
, hier ist ein Zeichen " *
Der Multiplikationsvorgang ist angezeigt.
Schreiben Sie Ihrem vorherigen Ort eine neue Bedeutung (siehe Abb.2. Rote Kontur).
Figur 2.
Füllen Sie mit dieser Regel alle leeren Elemente der Tabelle (außer der Säule "Haltung") Abb. 3.. Danach definieren wir eine neue zulässige Spalte. Analysieren Sie dazu die Zeichenfolge "Q" und da unsere Aufgabe maximal ist, werden wir dabei finden maximales positives Element.Er bestimmt die zulässige Spalte. In unserem Fall, es 3/2 . Alle Elemente der Auflösungsspalte werden in einer roten Schriftart angezeigt (siehe Abb. 3.). Wenn nach der nächsten Iteration in der Zeichenfolge "Q" Es ist nicht positive Elemente - das bedeutet, dass die optimale Lösung erreicht ist, iterationen sind abgeschlossen. Wenn unsere Aufgabe minimal war, würde die permissive Säule durch das minimale negative Element und wenn nach der nächsten Iteration in der Zeichenfolge bestimmt werden "Q" Negative Elemente werden nicht sein, es bedeutet, dass die optimale Lösung erreicht wird.
Figur 3.
Füllen Sie nun die Säule "Haltung". Dazu benötigen Sie die entsprechende (stehende in derselben Zeile) Das Spaltenelement "Lösung" ist in ein entsprechendes Element der Auflösungsspalte unterteilt (siehe Abb. 3.). beachten Siedass diese Operation ausgeführt wird nur für positiv. Permissive Spaltenelemente und Zeichenfolge "Q" Dieser Vorgang nimmt an diesem Vorgang nicht teil. Wenn nach einiger Iteration in der Auflösungsspalte keine positiven Elemente sind, dann ist diese Aufgabe aufgrund der unbegrenzten Zielfunktion unlöslich, iterationen sind abgeschlossen.
Nach dem Füllen der Spalte "Ratio" definieren wir eine neue Zulässige Zeichenfolge. Es wird durch das minimale Element aus der Säule "Haltung" bestimmt. In unserem Fall, es 32 Alle Elemente der zulässigen Zeichenfolge werden rot dargestellt (siehe Abb. 3.). Dies ist die nächste Iteration endet, die folgende Iterationsvariable x 2. wird aus der Basis zurückgezogen (das sagt uns eine neue Zulassungszeichenfolge an), deren Platz wird eine Variable annehmen x 1 (Wir sprechen über diese neue Zulässigkeitsspalte), und alle Berechnungen werden wiederholt.
Die obige Umwandlung wird zweckmäßigerweise in speziellen Tischen ausgeführt, die als Simplex-Tabellen bezeichnet werden.
Die folgenden Blöcke werden in der Simplex-Tabelle zugewiesen:
Wir schreiben die Lösung des Beispiels eines Beispiels aus Abschnitt 3.3 in Simplex-Tabellen:
Alle im mathematischen Zustand der Task enthaltenen Quelldaten werden an den ersten Simplex-Tisch übertragen. Bohrlosenfreie Variablen, erhalten einen Referenzplan
In der letzten Zeichenfolge des ersten Simplex-Tischs geben wir das Kriterium in impliziter Form ein
Wir schließen aus diesem Kriterium eine grundlegende Variable x 4 aus, die ein Kriterium in den Sinn führt
Für Optimalitätslösungen müssen alle Schätzungen nicht negativ sein
Die Entscheidung ist nicht optimal, weil Es gibt negative Schätzungen.
Schätzungen können durch Formeln berechnet werden. Das Produkt ist der Stromvektor der Matrix der Bedingungen, dann kann die Schätzung der freien Variablen als Skalarprodukt des Vektors von Koeffizienten mit Grundvariablen an den derzeitigen Vektor der Matrix der Bedingungen minus der Zielfunktionskoeffizient mit Basisgrößen berechnet werden Diese Variable. Um den Wert zu bekommen
Die Auflösungsspalte wird von derjenigen ausgewählt, in der die kleinste Schätzung (wenn die Aufgabe maximal ist). Um die Auflösungszeile auszuwählen, ist es notwendig, zwischen allen Zeilen zu finden, ausgedrückt, aus denen sich variabel abnimmt, was schneller zu null wird.
Infolgedessen erhalten wir, dass die Spalte der Auflösungsspalte ist, und die Auflösungszeichenfolge ist. Aus der Liste der Basis schaltet er die Variable aus und tritt in die Variable ein.
Die Entscheidung ist nicht optimal, weil Es gibt eine negative Punktzahl -2.
Die Lösung ist optimal, weil Alle Schätzungen sind mehr Null. Offensichtlich ist es unmöglich zu erhöhen.
Regeln für den Bau von Simplex-Tischen
Simplex-Tabelle ist für jede Referenzlösung erstellt.
Lassen Sie die Referenzlösung. Simplex-Tisch für diese Lösung hat das Formular
Basismatrix B \u003d (A 1, A 2, ... A m)
· Bei grundlegenden Variablen ist die aktuelle Matrix Single.
- · Jede Spalte.
- · Vektorrecht Teile von Einschränkungen.
- · Schätzungen für kostenlose Variablen sind nicht null
· In der rechten Zelle - der Wert des Kriteriums
Stufen des Simplex-Modus
- 1. Überprüfen Sie die Optimalität ()
- 2. Wenn es gibt, ist die Lösung nicht optimal. Wählen Sie dann eine Spalte mit einer Mindesteinschätzung aus. Ich werde es nennen, um es zu erleichtern.
- Die Auflösungsleitung wird in der Mindestverhältnisse von freien Elementen an positive lösliche Spaltenkoeffizienten ausgewählt. Die aus dieser Reihe ausgedrückte Basisvariable verlässt die Liste der grundlegenden Variablen. Jene. X k Blätter, aber X S gibt ein.
- 4. Die aktuelle Simplex-Tabelle wird in die folgende Regel umgewandelt:
- · Die Auflösungszeichenfolge ist in den zulässigen Element unterteilt:
- · Die Auflösungssäule wird durch einen einzelnen ersetzt.
- · Alle anderen Elemente der Simplex-Tabelle können entsprechend der Regel des Vierecks neu berechnet werden:
Das Viereck an der Diagonale, das das gewünschte Element verbindet, ist geistig gebaut. Dann ist der neue Elementwert gleich dem gleichen minus das Produkt der Elemente auf der entgegengesetzten Diagonale, das in den zulässigen Element unterteilt ist.
Oder der neue Wert des Elements ist gleich dem Produkt von Gegenständen auf der Hauptdiagonale abzüglich des Produkts der Elemente auf der gegenüberliegenden Diagonale, und das alles in das zulässige Element unterteilt ist.
Kommentar : Wenn in der Auflösungszeile ein Nullelement vorhanden war, ändert sich diese Spalte nicht; Wenn in der Spalte Auflösungsspalte ein Nullelement vorhanden ist, ändert sich die entsprechende Zeile nicht.
Die Gauß-Jordan-Methode ist so konzipiert, dass sie Systeme von linearen algebraischen Gleichungen (Slava) lösen. Es ist eine Änderung der Gauß-Methode. Wenn die Gauß-Methode in zwei Schritten (Direkthub und Rückwärtskehr) durchgeführt wird, können Sie mit der Gauß-Jordan-Methode das System in einem Schritt lösen. Details und direktes Schema der Anwendung der Methode von Gaus-Jordan sind in den Beispielen beschrieben.
In allen Beispielen von $ A $ bezeichnet die Systemmatrix, $ \\ Widetilde (A) $ $ ist eine erweiterte Systemmatrix. Sie können über die Matrixform des Schreibens eines Wortes lesen.
Beispiel №1.
Löse $ \\ Links \\ (\\ beginnend (ausgerichtet) & 4x_1-7x_2 + 8x_3 \u003d -23; \\\\ & 2x_1-4x_2 + 5x_3 \u003d -13; \\\\ & -3x_1 + 11x_2 + x_3 \u003d 16. \\ end (ausgerichtet) \\ RECHTS. $ Gaussa-Jordan-Methode.
Machen wir uns von der letzten Matrix weiter, die wir zum System erhalten haben:
$$ Links \\ (\\ beginnen (ausgerichtet) & 0 \\ cdot x_1 + 1 \\ cdot x_2 + 0 \\ cdot x_3 \u003d 1; \\\\ & 1 \\ cdot x_1 + 0 \\ cdot x_2 + 0 \\ cdot x_3 \u003d -2; \\\\ & 0 \\ cdot x_1 + 0 \\ cdot x_2 + 1 \\ cdot x_3 \u003d -1. \\ Enden (ausgerichtet) \\ richtig. $$
Vereinfachung des resultierenden Systems, wir haben:
$$ Links \\ (\\ Beginn (ausgerichtet) & x_2 \u003d 1; \\\\ & x_3 \u003d -2; \\\\ & x_3 \u003d -1; \\ ende (ausgerichtet) \\ richtig. $$
Die vollständige Lösung ohne Erklärung sieht aus wie folgt:
Zumindest ist dieses Verfahren zur Auswahl der Auflösungselemente ziemlich zulässig, wählen Sie jedoch vorzugsweise die diagonalen Elemente der Systemmatrix als Auflösungselemente aus. Wir werden uns diese Methode unten ansehen.
Die Wahl der Auflösungselemente auf der Hauptdiagonale der Systemmatrix.
Da diese Lösung dem vorherigen vollständig ähnlich ist (mit Ausnahme der Auswahl der Auflösungselemente), lassen Sie uns detaillierte Erklärungen verfehlen. Das Prinzip der Auswahl der Auflösungselemente ist einfach: Wählen Sie in der ersten Spalte das Element der ersten Zeile aus, in der zweiten Spalte wir das Element der zweiten Zeile in der dritten Spalte - das dritte Linienelement usw.
Erster Schritt
Wählen Sie in der ersten Spalte das erste Zeichenfolgenelement aus, d. H. Als Auflösung habe ich ein Element 4. Ich verstehe, dass die Wahl der Nummer 2 bevorzugter erscheint, da diese Zahl immer noch weniger als 4. ist, damit die Nummer 2 in der ersten Spalte an erster Stelle wechseln kann Die erste und zweite Linie, um die erste und zweite Linie zu ändern:
$$ Links (\\ Start (Anordnung) (CCC | C) 4 & -7 & 8 & -23 \\\\ 2 & -4 & 5 & -13 \\\\ 2 & -4 & 5 & -13 \\ ed (Array) \\ RECHTS) \\ RightsArrow \\ Left (\\ beginnen (Array) (CCC | C) 2 & -4 & 5 & -13 \\\\ 4 & -7 & 8 & -23 \\ End & 11 & 1 & 16 \\ ENDE (Array) \\ Right) $$
Das zulässige Element wird also durch Zahl 2 dargestellt. In gleicher Weise teilen wir wie zuvor die erste Zeile um 2 auf und setzen dann die Elemente der ersten Spalte zurück:
$$ \\ Left (\\ Start (Anschluss) (CCC | C) 2 & -4 & 5 & -13 \\\\ 4 & -7 & 8 & -23 \\ End & 11 & 1 & 16 & 16 \\ ENDE (Array) \\ Right ) \\ Begin (array) (l) i: 2 \\\\\\ phantom (0) \\\\ \\ phantom (0) \\ end (array) \\ rightarrow \\ linke (\\ begin (array) (ccc | c) 1 & - 2 & 5/2 & -13/2 \\\\ 4 & -7 & 11 & 1 & 16 \\ ENDE (Array) \\ Rechts) \\ Anfang (Array) (l) \\ Phantom (0) \\\\ II-4 \\ CDOT I \\\\ III + 3 \\ CDOT I \\ END (ARRAY) \\ RightArrow \\ Left (\\ Beginn (Array) (CCC | C) 1 & -2 & 5/2 & -13/2 \\ \\ 0 & 1 & -2 & 3 \\\\ 0 & 5 & 17/2 & -7/2 \\ end (array) \\ rechts). $$.
Zweiter Schritt
In dem zweiten Schritt ist es erforderlich, die Elemente der zweiten Spalte zurückzusetzen. Wählen Sie in der Qualität des Auflösungselements das Element der zweiten Zeile aus, d. H. 1. Das permissive Element ist bereits gleich, so dass wir keine Zeilen ändern. Wenn wir die Linien an Orten ändern wollten, würde die erste Zeile nicht berührt, da sie bereits im ersten Schritt verwendet wurde. Die zweite und dritte Linie können jedoch leicht an Orten geändert werden. Ich wiederhole jedoch, in dieser Situation ist es jedoch nicht erforderlich, die Zeichenfolge an einigen Stellen zu ändern, da das zulässige Element bereits optimal ist - es ist gleich einem.
$$ Links (\\ Beginn (Array) (CCC | C) 1 & -2 & 5/2 & -13/2 \\\\ 0 & 1 & -2 & 3 \\\\ 0 & 5 & 17/2 & -7 & 3 \\\\ 0 & 5 & 17/2 & -7 / 2 \\ End (Array) \\ RECHTS) \\ Start (Anordnung) (L) I + 2 \\ CDOT II \\\\ \\ Phantom (0) \\\\ III-5 \\ CDOT II \\ End (Array) \\ RightArrow \\ Left (\\ Beginnen (Array) (CCC | C) 1 & 0 & -3/2 & -1/2 \\\\ 0 & 1 & -2 & 3 \\\\ 0 & 0 & 37/2 & 37/2 \\ ENDE (Array) \\ Recht). $$.
Der zweite Schritt ist vorbei. Gehen Sie zum dritten Schritt.
Dritter Schritt
Im dritten Schritt muss die Elemente der dritten Spalte zurückgesetzt werden. Wählen Sie in der Qualität des Auflösungselements das Element der dritten Zeile aus, d. H. 37/2. Wir teilen die Elemente der dritten Zeile um 37/2 (so dass das Auflösungselement 1), und dann die entsprechenden Elemente der dritten Spalte zurücksetzen:
$$ \\ Left (\\ beginnend (Array) (CCC | C) 1 & 0 & -3/2 & -1/2 \\\\ 0 & -2 & -2 & 3 \\\\ 0 & 0 & 37/2 & -37 / 2 \\ End (Array) \\ RECHTS) \\ Anfang (Anordnung) (l) \\ phantom (0) \\\\ \\ phantom (0) \\\\ III: \\ frac (37) (2) \\ end (array) \\ rightarrow \\ Links (\\ beginnend (Array) (CCC | C) 1 & 0 & -3/2 & -1/2 \\\\ 0 & 1 & -2 & 3 \\ ed (Array) \\ RECHTS) \\ Start (Array) (l ) I + 2 \\ cdot iii \\\\ ii + 3/2 \\ cdot iii \\\\ \\ phantom (0) \\ end (array) \\ rightarrow \\ linke (\\ begin (array) (ccc | c) 1 & 0 & 0 & 1 \\\\ 0 & 0 & 1 & 1 \\ End (Array) \\ Right). $$.
Die Antwort wird erhalten: $ X_1 \u003d -2 $, $ X_2 \u003d 1 $, $ X_3 \u003d -1 $. Die vollständige Lösung ohne Erklärung sieht aus wie folgt:
Alle anderen Beispiele auf dieser Seite werden auf der zweiten Art und Weise gelöst: Als Auflösung wählen wir die diagonalen Elemente der Systemmatrix aus.
Antworten: $ X_1 \u003d -2 $, $ X_2 \u003d 1 $, $ X_3 \u003d -1 $.
Beispiel Nummer 2.
Löse $ \\ Links \\ (\\ Beginn (ausgerichtet) & 3x_1 + x_2 + 2x_3 + 5x_4 \u003d -6; \\\\ & 3x_1 + x_2 + 2x_4 \u003d -10; \\\\ & 6x_1 + 4x_2 + 11x_3 + 11x_4 \u003d -27; \\ \\ & -3x_1-2x_2-2x_3-10x_4 \u003d 1. \\ end (ausgerichtet) \\ rechts. $ Gaussa-Jordan-Methode.
Wir schreiben eine erweiterte Matrix dieses Systems: $ \\ widetilde (a) \u003d \\ linke (\\ beginn (array) (cccc | c) 3 & 1 & 2 & 5 & -6 & -6 \\\\ 3 & 1 & 0 & 2 & - 10 \\\\ 6 & 4 & 11 & 11 & -2 & -2 \\\\ -3 & -2 & -2 & -10 & 1 \\ End (Array) \\ Right) $.
In der Qualität der Auflösungselemente wählen Sie die Diagonalelemente der Systemmatrix aus: Im ersten Schritt nehmen wir das Element der ersten Zeichenfolge in den zweiten Schritt das Element der zweiten Zeile und so weiter.
Erster Schritt
Wir müssen die entsprechenden Elemente der ersten Spalte zurücksetzen. Nehmen Sie als Auflösungselement ein Element der ersten Zeile ein, d. H. Dementsprechend muss die erste Zeile in 3 unterteilt sein, so dass das Auflösungselement einem gleich ist. Und setzen Sie dann alle Elemente der ersten Spalte zurück, außer der Auflösung:
$$ Links (\\ Start (Anschluss) (CCCC | C) 3 & 1 & 2 & 5 & -6 \\\\ 3 & 1 & 0 & 2 & 2 & -2 & -27 & 4 & 11 & 11 & 28 & -27 & 4 & 11 & 11 & -2 & -27 \\ \\ 3 & -2 & -2 & -10 & 1 \\ End (Array) \\ RECHTS) \\ Anfang (Anordnung) (L) I: 3 \\\\ \\ phantom (0) \\\\\\ Phantom (0) \\\\\\ Phantom ( 0) \\ END (ARRAY) \\ RightArrow \\ Left (\\ Start (Anschluss) (CCCC | C) 1 & 1/3 & 2/3 & 5/3 & 2 & 2 & 2 & 2 & 2 & 2 & 2 & -10 \\\\ 6 & 4 & 11 & 11 & -27 \\\\ -3 & -2 & -2 & -2 & -10 & 1 \\ ENDE (ARRAY) \\ RECHTS) \\ Anfang (Array) (L) \\ Phantom (0) \\\\ II- 3 \\ CDOT I \\\\ III-6 \\ CDOT I \\\\ IV + 3 \\ CDOT I \\ END (ARRAY) \\ RightArrow \\\\\\\\\\ RightArrow \\ RightArrow \\\\\\\\\\ Rightsarrow \\ Left (\\ beginnen (Anschluss) (CCCC | C) 1 & 1 / 3 & 2/3 & 5/3 & -2 \\\\ 0 & 0 & -2 & -3 & 7 & -15 \\\\ 0 & -1 & 0 & - 5 & -5 \\ End (Array) \\ Recht). $$.
Zweiter Schritt
Gehen Sie zur Nullstellung der entsprechenden Elemente der zweiten Spalte. In der Qualität des Auflösungselements wurden wir aufgesteckt, um das Element der zweiten Zeile zu nehmen, aber wir tun dies nicht, da das gewünschte Element Null ist. Fazit: Wir werden die Linien an Orten ändern. Es ist unmöglich, die erste Zeichenfolge zu berühren, da sie bereits im ersten Schritt verwendet wurde. Die Wahl ist nicht hoch: Oder wir ändern an einigen Stellen die zweite und dritte Linie, oder wir ändern den vierten und zweiten und zweiten. Da in der vierten Linie (-1) gegossen wird, dann auch die vierte Linie beim "Austausch". Also ändern wir uns in den zweiten und vierten Linien:
$$ Links (\\ Beginn (Array) (CCCC | C) 1 & 1/3 & 2/3 & 5/3 & -2 \\\\ 0 & 0 & -2 & -3 & -3 & -4 \\\\ 0 & 2 & 7 & 1 & -15 \\ end (et -1 & 0 & -5 & -5 \\ end (array) \\ rechts) \\ rightarrow \\ linke (\\ beginn (array) (cccc | c) 1 & 1/3 & 2/3 & 5/3 & -2 \\\\ 0 & -1 & 0 & -5 & -5 \\\\ 0 & 2 & 7 & 1 & 1 & -15 \\\\ 0 & 0 & -2 & -2 & -3 & -3 \\ ENDE (ARRAY) \\ RECHTS) $$
Jetzt ist alles normal: Das Auflösungselement ist gleich (-1). Es passiert übrigens, dass sich die Linien ändern, nicht möglich, sie werden jedoch im folgenden Beispiel Nr. 3 diskutieren. Inzwischen teilen wir den zweiten String auf (-1) auf und setzen dann die Elemente der zweiten Spalte zurück. Bitte beachten Sie, dass das Element in der zweiten Spalte das in der vierten Zeile angeordnete Element bereits Null ist, also berühren wir die vierte Linie nicht.
$$ Links (Beginn (Anschluss) (CCCC | C) 1 & 1/3 & 2/3 & 5/3 & -2 \\\\ 0 & -1 & 0 & -2 & -5 & -5 \\\\ 0 & 2 & 7 & 1 & -15 \\ \\ 0 & 0 & -2 & -3 & -4 & -4 \\ End (Array) \\ RECHTS) \\ Start (Array) (l) \\ Phantom (0) \\\\ II: (- 1) \\\\\\ Phantom (0) \\\\\\ Phantom (0) \\ END (ARRAY) \\ Rightarrow \\ Left (\\ Beginn (Anschluss) (CCCC | C) 1 & 1/3 & 2/3 & 5/3 & -2 \\\\ 0 & 1 & 0 & 5 & 5 & 5 \\\\ 0 & 2 & 0 & -2 & -3 & -4 \\ End (Array) \\ RECHTS) \\ Anfang (Array) (L) I-1/3 \\ CDOT II \\\\ \\ phantom (0) \\\\ III-2 \\ CDOT II \\\\\\ phantom (0) \\ ENDE (Array) \\ Rightarrow \\\\ \\ RightArrow \\ Left (\\ beginnen (Anschluss) (CCCC | C) 1 & 0 & 2/3 & 0 & 0 & 0 & 5 & 5 & 0 & 0 & -7 & -9 & -25 \\\\ 0 & 0 & -2 & -3 & -4 \\ End (Array) \\ richtig). $$.
Dritter Schritt
Wir fahren mit der Verarbeitung der dritten Spalte fort. Als Auflösungselement haben wir uns darauf einverstanden, die diagonalen Elemente der Systemmatrix einzunehmen. Für den dritten Schritt bedeutet dies die Auswahl eines Elements in der dritten Zeile. Wenn jedoch das Element 7 einfach als Auflösung einnehmen, muss die gesamte dritte Zeile auf 7 aufgeteilt werden. Es scheint mir, dass es möglich ist, auf (-2) einfacher aufgeteilt zu werden. Daher ändern wir die dritte und vierte Linie an einigen Stellen, und dann wird das Auflösungselement (-2) sein:
$$ Links (\\ begin (array) (CCCC | C) 1 & 0 & 2/3 & 0 & 0 & 5 & 5 & 5 \\\\ 0 & 0 & 5 & 5 \\\\ 0 & 0 & 7 & 5 & 5 & 5 \\\\ 0 & 0 & 7 & 5 & - 25 \\\\ 0 & 0 & -2 & -3 & -4 \\ ENDE (ARRAY) \\ RECHTS) \\ RightArrow \\ Left (\\ Beginn (Array) (CCCC | C) 1 & 0 & 2/3 & 0 & -11 / 3 \\\\ 0 & 1 & 0 & 5 & 5 \\\\ 0 & 0 & 0 & -2 & -3 & -4 \\\\ 0 & 0 & 7 & -9 & -200 \\ End (Array) \\ Right) $$ .
Element zulassen - (-2). Wir teilen die dritte Zeile auf (-2) und setzen die entsprechenden Elemente der dritten Spalte zurück:
$$ \\ Left (\\ beginnend (Array) (CCCC | C) 1 & 0 & 2/3 & 0 & 0 & 5 & 5 \\\\ 0 & 0 & -2 & - 2 & - 3 & -4 \\\\ 0 & 0 & 7 & -9 & -200 \\ ENDE (Array) \\ RECHTS) \\ Start (ARRAY) (l) \\ Phantom (0) \\\\ \\ Phantom (0) \\\\ III: (-2) \\\\\\ Phantom (0) \\ END (ARRAY) \\ RightArrow \\ Left (\\ Start (Anschluss) (CCCC | C) 1 & 0 & 2/3 & 0 & -11/3 \\\\ 0 & 1 & 0 & 5 & 5 & 5 \\\\ 0 & 0 & 1 & 3/2 & 2 \\, 25 \\ End (Array) \\ Rechts) \\ Anfang (Array) (l) i-2/3 \\ cdot iii \\\\ \\ phantom (0) \\\\ \\ phantom ( 0) \\\\ IV-7 \\ CDOT III \\ END (ARRAY) \\ RightArrow \\\\\\\\ Rightarrow \\ Left (\\ Start (Anschluss) (CCCC | C) 1 & 0 & 0 & 0 & 5 & 5 \\\\ 0 & 0 & 1 & 3/2 & 2 & 0 & 0 & 0 & 0 & -39/2 & - 0 & 0 & 0 39 \\ End (Array) \\ Right). $$.
Vierter Schritt
Gehen Sie zur Nullstellung der vierten Spalte. Das zulässige Element befindet sich in der vierten Linie und entspricht der Zahl von $ - \\ frac (39) (2) $.
$$ \\ Left (\\ beginnend (Array) (CCCC | C) 1 & 0 & 0 & 0 & 5 & 5 & 5 \\\\ 0 & 0 & 1 & 3/2 & 2 \\\\ 0 & 0 & 0 ende (ordnung) \\ RECHTS) \\ Start (Array) (L) \\ Phantom (0) \\\\ \\ phantom (0) \\\\ \\ phantom (0) \\\\ IV: \\ links (- \\ frac (39) (2) \\ rechts) \\ Ende (Array) \\ RightArrow \\ Left (\\ beginnend (Array) (CCCC | C) 1 & 0 & 0 & -1 & -5 \\\\ 0 & 1 & 0 & 5 & 5 & 5 & 5 & 5 \\\\ 0 & 0 & 1 & 3 & 3 & 1 & 2 \\ ENDE (Array) \\ RECHTS) \\ Anfang (Array) (L) I + IV \\\\ II-5 \\ CDOT IV \\\\ III-3/2 \\ CDOT IV \\\\ \\ phantom (0) \\ end (ARRAY) \\ RightArrow \\\\ \\ Rightsarrow \\ Left (\\ beginnen (arry) (CCCC | C) 1 & 0 & 0 & 0 & 0 & --5 \\\\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 0 & 0 & 1 & 2 \\ End (Array) \\ RECHTS). $$.
Die Entscheidung ist vorbei. Die Antwort lautet: $ x_1 \u003d -3 $, $ X_2 \u003d -5 $, $ X_3 \u003d -1 $, $ X_4 \u003d $ 2. Komplette Lösung ohne Erklärung:
Antworten: $ X_1 \u003d -3 $, $ X_2 \u003d -5 $, $ X_3 \u003d -1 $, $ X_4 \u003d $ 2.
Beispielnummer 3.
Lösen Sie $ \\ Links \\ (\\ beginnend (ausgerichtet) & x_1-2x_2 + 3x_3 + 4x_5 \u003d -5; \\\\ & 2x_1 + x_2 + 5x_3 + 2x_4 + 9x_5 \u003d -3; \\\\ & 3x_1 + 4x_2 + 7x_3 + 4x_4 + 14x_5 \u003d -1; \\\\ & 2x_1-4x_2 + 6x_3 + 11x_5 \u003d 2; \\\\ & -2x_1 + 14x_2-8x_3 + 4x_4-7x_5 \u003d 20; \\\\ & -4x_1-7x_2-9x_3-6x_4-21x_5 \u003d - 9 . \\ Enden (ausgerichtet) \\ rechts. $ Gaussa-jordan. Wenn das System unsicher ist, geben Sie die grundlegende Lösung an.
Solche Beispiele werden mit dem Thema "Allgemeine und grundlegende Lösungen von Slava" behandelt. Im zweiten Teil des genannten Themas dieses Beispiel Mit der Gauß-Methode gelöst. Wir lösen es mit der Methode von Gaussa-jordan. Ein Schritt für Schritt ist keine Entscheidung, da es in den vorherigen Beispielen bereits durchgeführt wurde.
$$ \\ Left (\\ beginnend (Array) (CCCCC | C) 1 & -2 & 3 & 0 & 4 & 2 & 9 & 2 & -2 & 1 & 5 & 2 & 7 & 7 & 4 & 2 & 2 & 2 & 7 & 7 & 4 & 04 & 0 & 11 & 2 & 4 & 6 & 0 & 11 & 4 & -7 & 20 & -7 & -7 & -7 & -9 & -6 & -7 & -9 -9 -21 & -9 \\ End (Array) \\ richtig) \\ Anfang (Array) (l) \\ Phantom (0) \\\\ II-2 \\ CDOT I \\\\ III-3 \\ CDOT I \\\\ IV-2 \\ CDOT I \\\\ V + 2 \\ CDOT I \\\\ VI + 4 \\ CDOT I \\ END (ARRAY) \\ RightArrow \\ Left (\\ Start (Anschluss) (CCCCC | C) 1 & -2 & 3 & 0 & 4 & -5 \\ \\ 0 & 5 & -1 & 2 & 1 & 7 & 2 & 2 & 2) & 14 \\ 0 & 0 & 0 & 0 & 0 & 3 & 12 \\\\ 0 & -1 & -2 & 3 & 1 & 10 & 10 & -2 & -15 & 3 & -6 & -5 & -29 \\ ENDE (Array) ) \\ RECHTS) \\ begin (array) (l) \\ phantom (0) \\\\ II: 5 \\\\ \\ phantom (0) \\\\ \\ phantom (0) \\\\ \\ phantom (0) \\\\ \\ phantom (0) \\ END (ARRAY) \\ RightArrow \\\\ \\ Left (\\ Start (Anschluss) (CCCCC | C) 1 & - 2 & 3 & 1 & -1/5 & 2/5 & 1/5 & 7/5 & 2 & 2 1 & 10 & -2 & 4 & 2 & 14 & 14 & 0 & 0 & 0 & 3 & 3 & 12 & 1 & 10 & -10 \\ 0 & -15 & 3 & 10 & -5 & -29 \\ ENDE (Array) \\ RECHTS) \\ START (ARRAY) (L) I + 2 \\ CDOT II \\\\ \\ Phantom (0) \\\\ III-10 \\ CDOT II \\\\ II: 3 \\\\ V-10 \\ CDOT II \\\\ VI + 15 \\ CDOT II \\ ed (Array) \\ Righgarrow \\ Left (\\ Start (Anschluss) (CCCCC | C) 1 & 0 & 13/5 & 4/5 & 22/5 & -11/5 \\\\ 0 & 1 & -1/5 & 2/5 & 1 / 5 & \u200b\u200b7/5 \\\\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & -1 & -1 & -4 \\\\ 0 & -1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & -2 & -8 \\ End (Array) \\ RECHTS). $$.
Ich glaube, dass einer der Transformationen immer noch Erklärungen erfordert: $ IV: $ 3. Alle Elemente der vierten Linie wurden von drei geteilt, so ausschließlich zur Vereinfachung der Vereinfachung, wir teilten alle Elemente dieser Linie auf drei auf. Die dritte Zeile in der umgebauten Matrix ist Null geworden. Schlagen Sie die Nulllinie aus:
$$ \\ Left (\\ Beginn (Array) (CCCCC | C) 1 & 0 & 13/5 & 4/5 & 22/5 & -11/5 \\\\ 0 & 1 & -1/5 & 2/5 & 1/5 & 7/5 \\\\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & -2 & -8 \\ End (Array) \\ richtig) $$
Es ist Zeit für uns, in den dritten Schritt zu gehen, auf dem die Elemente der dritten Spalte zurückgesetzt werden müssen. Das Diagonalelement (dritte Zeile) ist jedoch Null. Und es gibt nichts, um die Orte der Reihen zu ändern. Wir haben bereits die erste und zweite Linie verwendet, sodass wir sie nicht berühren können. Und die vierte und fünfte Linie ist sinnvoll, denn das Problem der Gleichheit Null des Auflösungselements geht nirgendwo hin.
In dieser Situation wird das Problem extrem einfach gelöst. Wir können die dritte Spalte nicht behandeln? Nun, zum vierten. Vielleicht ist in der vierten Spalte das Element der dritten Zeile nicht Null. Die vierte Säule "krank" jedoch das gleiche Problem wie der dritte. Das dritte Zeilenelement in der vierten Spalte ist Null. Und die Wechsel der Sitze von Linien wieder, nichts wird alles geben. Die vierte Spalte kann auch nicht verarbeiten? Okay, wenden wir uns an den Fünften. In der fünften Säule ist jedoch das Element der dritten Linie nicht einmal gleich Null. Es ist gleich einem, was ziemlich gut ist. Daher ist das zulässige Element in der fünften Spalte 1. Das zulässige Element wird ausgewählt, sodass wir die am weitesten entfernten Transformationen der Gauß-Jordan-Methode durchführen:
$$ \\ Left (\\ Beginn (Array) (CCCCC | C) 1 & 0 & 13/5 & 4/5 & 22/5 & -11/5 \\\\ 0 & 1 & -1/5 & 2/5 & 1/5 & 7/5 \\\\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & -2 & -8 \\ End (Array) \\ richtig) \\ Anfang (Array) (L) I-22/5 \\ CDOT III \\\\ II-1/5 \\ CDOT III \\\\ \\ Phantom (0) \\\\ IIM + III \\\\ V + 2 \\ CDOT III \\ End (Array) \\ Rightsarrow \\ Left (\\ beginnend (Array) (CCCCC | C) 1 & 0 & 13/5 & 4/5 & 0 & -19/5 \\\\ 0 & 1 & -1 / 5 & 2/5 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ ENDE (Array) \\ RECHTS) \\ RightArrow \\ \\ \\ RightArrow \\ Left | \\ Text (Nullzeilen entfernen) \\ RECHTS | \\ RightArrow \\ Left (\\ beginn (Anschluss) (CCCCC | C) 1 & 0 & 13/5 & 4/5 & 0 & -9/5 \\ \\ 0 & 1 & 3/5 & 0 & 0 & 0 & 0 & 1 & 4 \\ ENDE (Array) \\ RECHTS) $$.
Wir haben die Systemmatrix und eine erweiterte Systemmatrix in eine gestufte Form geführt. Beide Matrizen sind gleich $ R \u003d 3 $, d. H. Es ist notwendig, 3 grundlegende Variablen zu wählen. Die Anzahl der unbekannten $ n \u003d $ 5, also müssen Sie $ n-r \u003d 2 $ kostenlose Variablen auswählen. Seit $ R.< n$, то согласно следствию из теоремы Кронекера-Капелли dieses System Es ist unsicher (d. H. Hat eine unendliche Anzahl von Lösungen). Um Lösungen des Systems zu finden, machen Sie eine "Schritte":
Auf den "Schritten" befinden sich Elemente aus den Säulen №1, №2, №5. Daher ist der Basic Variablen $ X_1 $, $ X_2 $, $ X_5 $. Kostenlose Variablen, werden $ X_3 $, $ X_4 $ betragen. Säulen №3 und №4, entsprechend freien Variablen, leiden als Linie, während natürlich vergessen, ihre Anzeichen zu ändern.
$$ \\ Left (\\ beginnend (Array) (CCCCC | C) 1 & 0 & 13/5 & 4/5 & 0 & -19/5 \\\\ 0 & 1 & -1/5 & 2/5 & 0 & 3/5 \\\\ 0 & 0 & 0 & 1 & 4 \\ ENDE (Array) \\ RECHTS) \\ Rightsarrow \\ Left (\\ beginnend (Array) (CCC | CCC) 1 & 0 & 0 & -9/9/5 & -13 / 5 & -4/5 \\\\ 0 & 1 & 0 & 3/5 & 1/5 & -2/5 \\\\ 0 & 0 & 1 & 4 & 0 & 0 \\ End (Array) \\ Right). $$.
Aus der letzten Matrix erhalten wir eine allgemeine Lösung: $ \\ Links \\ (\\ beginnend (ausgerichtet) & x_1 \u003d - \\ frac (99) (5) - \\ frac (13) (5) x_3- \\ frac (4) (5 ) x_4; \\\\ & x_2 \u003d frac (3) (5) + \\ frac (1) (5) x_3- \\ frac (2) (5) x_4; \\\\ & x_3 \\ in r; \\\\ & x_4 \\ In R; \\\\ & x_5 \u003d 4. \\ \\ \\\\ & x_5 \u003d \\ \\ \\ \\ endet (ausgerichtet) \\ rechts. $. Die Basislösung findet durch die Einnahme von freien Variablen mit Null, d. H. $ x_3 \u003d 0 $, $ x_4 \u003d 0 $:
$$ Links \\ (\\ beginnend (ausgerichtet) & x_1 \u003d - \\ frac (99) (5); \\\\ & x_2 \u003d \\ frac (3) (5); \\\\ & x_3 \u003d 0; \\\\ & x_4 \u003d 0; \\\\ & x_5 \u003d 4. \\ end (ausgerichtet) \\ richtig. $$
Die Aufgabe ist gelöst, es bleibt nur noch, um die Antwort aufzunehmen.
Antworten: Allgemeine Lösung: $ \\ Links \\ (Beginn (ausgerichtet) & x_1 \u003d - \\ frac (99) (5) - \\ frac (13) (5) x_3- \\ frac (4) (5) x_4; \\\\ & X_2 \u003d \\ frac (3) (5) + \\ frac (1) (5) x_3- \\ frac (2) (5) x_4; \\\\ & x_3 \\ in r; \\\\ & x_4 \\ in r; \\\\ & x_4 \\ in r; \\\\ & X_5 \u003d 4. \\ ENDE (AUSIGNT) \\ RECHTS. $, Basislösung: $ \\ Links \\ (\\ beginnen (ausgerichtet) & x_1 \u003d - \\ frac (99) (5); \\\\ & x_2 \u003d \\ frac (3) (5); \\\\ \\ x_3 \u003d 0; \\\\ & x_4 \u003d 0; \\ ed (ausgerichtet) \\ richtig. $.
Siehe auch:
|
Theorem (über die Wahl eines Auflösungselements)
Wenn in mehreren Z-Hub-Spalten negative Elemente vorhanden sind, müssen Sie die autorisierte Spalte auswählen, in der Sie eine Spalte auswählen müssen, in der das maximale Produkt des absoluten Werts des Koeffizienten in der Z-ten Zeile und des minimalen Simplex-Verhältnisses dieser Spalte ist.
Beweise:
Lassen Sie das erlaubte Element erlaubt sein. Infolge des Schrittes der modifizierten Jordan-Ausnahmen ist ein freies Element in der Z-Zeile die Zahl, die dem .POSCOLP entspricht, und die Halterung in diesem Ausdruck ist immer positiv. Da die Bedeutung der Funktionalität immer gleich einem freien Element ist, ist diese Halterung die Additive der Funktionalität, die als Ergebnis des aufgenommenen Schritts erhalten wird.
Je größer der Inkrement, um die Funktionalität in jedem Schritt zu empfangen, desto weniger Schritte sind erforderlich (d. H. Rechenrechnung), um Optima zu erreichen. Die Größe dieses Inkrements hängt vom absoluten Wert des Koeffizienten und der Größe der kleinsten Simplex-Beziehung ab. Das heißt, die autorisierte Spalte ist eine Spalte, die ein maximales Produkt hat.
Beispiel: lineare Programmierung:
Wir finden die maximale Funktion
mit Einschränkungen.
Lösung: Machen wir einen Tisch mit Jordanien.
Da es freie Mitglieder darin gibt, ist der Plan Referenz. Es ist jedoch nicht optimal, da die Z-Zeilen-Koeffizienten negativ sind. Wählen Sie aus ihnen, was das größte Produkt des absoluten Werts und der kleinsten Simplex-Beziehung hat. Die dritte Spalte betrachtet die Erlaubnis, da er den größten absoluten Wert von 8 und Simplex-Beziehungen hat: jeweils (daher wird das Element 1 in der dritten Spalte aufgelöst). Wir machen einen Schritt von modifizierten Jordan-Ausnahmen und kommen zur nächsten Tabelle.
Beurteilen durch die Z-Zeilen-Koeffizienten, wird die optimale Lösung in der Tabelle nicht erreicht. Nehmen Sie die zweite Spalte mit einem negativen Koeffizienten in der Z-Zeile für die zulässige Zeile (Auflösungszeichenfolge kann nur der erste sein). Mit dem gefundenen Punkt 5 machen wir den nächsten Schritt.
In der Z-Reihe sind alle Koeffizienten positiv, der Plan, der durch Gleichungen der oberen Variablen Null und die seitlich freien Mitglieder, ist optimal. Wir schreiben die Werte der wichtigsten Unbekannten aus der Tabelle: Wir berücksichtigen den Maximalwert der Funktionalität in der letzten Zelltabelle:
In der letzten Tabelle sind alle Determinanten nicht negativ. Dies legt nahe, dass mit den Werten der unbekannten Funktionalität ein Maximum erreicht
Es wird normalerweise davon ausgegangen, dass es keinen Platz für den Satz von Plänen des Problems gibt, in denen der Zielfunktion Nenner Null ist. Ohne die Begrenzung der Allgemeinheit können wir das annehmen.
Bei dem Problem der fraktionalen linearen Programmierung wird das Extremum der Zielfunktion in der Spitze der Polyederlösungen erreicht. Mit dieser Ähnlichkeit mit linearer Programmierung können Sie fraktionale lineare Aufgaben durch das Abstand durch das Verfahren lösen.
Berechnungen erfolgen in Form von Jordanien-Tischen. Gleichzeitig werden zwei untere Linien für das Funktional abgegeben: Schreiben Sie in der ersten von ihnen die Koeffizienten des Zählers und in den zweiten Nenner. Die Quellaufgabe entspricht Tabelle 1:
| –x. 1 | –x. 2 | … | –x J. | … | –x n. | ||
| y. 1 | eIN. 11 | eIN. 12 | … | eIN. 1 J. | … | eIN. 1 N. | eIN. 1 |
| … | ……………………………………… | … | |||||
| y I. | ein I. 1 | ein I. 2 | … | ein ij. | … | ein in. | ein I. |
| … | ……………………………………… | … | |||||
| y m. | ein M. 1 | ein M. 2 | … | ein mj. | … | ein mn. | ein M. |
| z. 1 | –p. 1 | –p. 2 | … | –p j. | … | –p n | |
| z. 2 | –q 1 | –q 2 | … | –q J. | … | –q N. |
Durch y I. Die Unterschiede zwischen den rechten und linken Teilen des Systems der Einschränkungen sind angegeben:
Y I.= ein I.– Ein I. 1 x. 1 – ein I. 2 x. 2 – Ein I. 3 x. 3 – … – a in x n ³ 0.
Mit kostenlosen Variablen nennen wir die Variablen in der oberen Titellinie des Jordanischen Tischs. Geben Sie eine kostenlose variable Null-Werte an, erhalten wir die ursprüngliche Basislösung :. Dieser Vektor kann kein Support-Plan sein, weil Der Zielfunktionelle Nenner ist null ( z. 2 \u003d 0). Daher unter den freien Mitgliedern des Systems der Einschränkungen eIN. 1 ,…, ein M. Achten Sie darauf, negative Zahlen zu haben (sonst wäre die Basislösung ein Unterstützungsplan).
Die Schritte der modifizierten JORDANA-Ausnahmen, genau wie beim Lösen eines linearen Programmierproblems (siehe), und findet den ersten Plan des Problems. Ergebend k. Schritte, die wir in Tabelle 2 erreichen:
| –y. 1 | … | –x J. | … | –x n. | ||
| x. 1 | b. 11 | … | b. 1 J. | … | b. 1 N. | b. 1 |
| .… | ……………………………………… | |||||
| y I. | b I. 1 | … | b ij. | … | behälter | b I. |
| …. | ……………………………………. | |||||
| y m. | b M. 1 | … | b mj. | … | b mn. | b M. |
| z. 1 | f. 1 | … | f J. | … | f n. | F. |
| z. 2 | g. 1 | … | g J. | … | g n. | G. |
Tabelle 2 Alle kostenlosen Mitglieder b I. Nicht negativ, was nicht dauerhafte grundlegende Variablen bietet x. 1 ,…, y m.. Darüber hinaus (aufgrund der Positivität des Nenners der Zielfunktion z. 2 auf dem Satz von Referenzplänen). Der anfängliche Trägerplan ist der Vektor mit Koordinaten. Der Wert der Zielfunktion auf dem anfänglichen Referenzplan ist gleich.
Beachten Sie, dass bei einem der Schritte von jordanischen Ausnahmen von einem der freien Mitglieder b. Ich werde negativ sein und alle anderen Elemente iCH.- Reihen werden nicht negativ, die Aufgabe wird aufgrund mangelnder Pläne keine Lösungen haben.
Befolgen Sie die Zielfunktion, wenn Sie von einem Referenzplan auf ein anderes wechseln. Es stellt sich heraus, dass die Differenzmarke zwischen den neuen und alten Werten der Funktion mit dem Zeichen des Determinanten zusammenfällt. Wenn ein. weil Die Lösung Polyhedron enthält nur eine endliche Anzahl von Unterstützungsplänen, dann für die endgültige Anzahl von Schritten, den wir zum optimalen Referenzplan kommen.
Dieser Prozess kann auch das unbegrenzte Polyhedra der Lösungen stören. In diesem Fall kann die Zielfunktion das sogenannte asymptotische Extremum (in diesem Fall das Maximum) aufweisen. Die asymptotische maximale Aufgabe der fraktionalen linearen Programmierung ist die genaue obere Facette der Zielfunktion auf einer Vielzahl von Plänen, die bei keiner der Pläne erreicht wird. In dem Fall, in dem die Aufgabe ein asymptotisches Maximum hat, können Sie im Bereich der Pläne immer einen solchen Plan (nicht Referenz) finden, auf dem die Zielfunktion den Wert eines willkürlich nahe dem asymptotischen Maximum annimmt.
Mit der Pistower-Methode können Sie nicht nur maximal, sondern auch asymptotisches maximales Problem der fraktionalen linearen Programmierung finden. Berücksichtigen Sie detaillierter den Übergang vom Plan, um zu planen und herauszufinden. Wählen Sie das zulässige Element in j.- Säule, wir müssen durch das Prinzip der Mindest-Simplex-Beziehung geleitet werden. Jene. Auflösungselement B. j.- Die Säule sollte in die Linie gelangen, für die die Simplex-Beziehung positiv und minimal ist.
weil Nachdem er den anfänglichen Unterstützungsplan gefunden hatte, alle richtigen Teile b I. sind nicht negativ geworden, dann ein Auflösungselement j.Die Spalte kann einer der positiven Elemente () sein. Wenn in jedem Schritt des Stadiums des Findens des optimalen Referenzplans in der ausgewählten Auflösungsspalte (mindestens ein) positives Element vorhanden ist, hat eine solche Aufgabe ein Maximum (es ist möglich, dass nicht eins).
Wenn jedoch auf einem der Schritte eine Einschätzung von weniger als Null ist, und mit allen Elementen j.-unterspalte. Dann kann in dieser Spalte nach dem Prinzip der Mindest-Simplex-Beziehung geleitet werden, kann der zulässige Element nicht ausgewählt werden. Erhöhen der Werte der freien Variablen x J. Von 0 und auf (siehe Tabelle 2) bleiben wir alle im Bereich der Pläne. Dies ist darauf zurückzuführen, dass die Zunahme der Variablen x J. Verursacht keine Änderungsmarke auf minus eines der grundlegenden Variablen.
Bezeichnen mit M. Die Grenze, an die monotonisch ist, strebt das Objekt nach der Zielfunktion an :. Diese Zahl ist ein asymptotisches Maximum.
| 2 |
