Lösen Sie den Simplex mit der folgenden zlp-Methode. Service zur Lösung linearer Programmierprobleme. Lösung des Simplex-Problems durch die Methode

Es wird ein Beispiel für die Lösung des Problems mit der Simplex-Methode sowie ein Beispiel für die Lösung des dualen Problems betrachtet.

Inhalt

Die Aufgabe

Für die Umsetzung von drei Gütergruppen verfügt ein Handelsunternehmen über drei Arten begrenzter materieller und monetärer Ressourcen in Höhe von b 1 = 240, b 2 = 200, b 3 = 160 Einheiten. Gleichzeitig für den Verkauf einer Warengruppe für 1.000 Rubel. Umsatz wird eine Ressource erster Art in Höhe von a 11 = 2 Einheiten verbraucht, eine Ressource zweiter Art in Höhe von a 21 = 4 Einheiten, eine Ressource dritter Art in Höhe von a 31 = 4 Einheiten. Für den Verkauf von 2 und 3 Warengruppen für 1 Tausend Rubel. Umsatz wird jeweils ausgegeben, die Ressource des ersten Typs in Höhe von a 12 = 3, a 13 = 6 Einheiten, die Ressource des zweiten Typs in Höhe von a 22 = 2, a 23 = 4 Einheiten, die Ressource vom dritten Typ in Höhe von a 32 = 6, a 33 = 8 Einheiten . Profitieren Sie vom Verkauf von drei Warengruppen für 1.000 Rubel. Der Umsatz beträgt jeweils c 1 \u003d 4, c 2 \u003d 5, c 3 \u003d 4 (tausend Rubel). Bestimmen Sie das geplante Volumen und die Struktur des Handelsumsatzes, damit der Gewinn des Handelsunternehmens maximiert wird.

Zum direkten Problem der Warenzirkulationsplanung: lösbare Simplex-Methode, komponieren Doppelproblem Lineares Programmieren.
Installieren konjugierte Variablenpaare direkte und duale Probleme.
Konjugierte Variablenpaare ergeben sich aus der Lösung des direkten Problems Duale Problemlösung, in welchem Ressourcenschätzung für den Verkauf von Waren ausgegeben.

Lösung des Simplex-Problems durch die Methode

Sei x 1, x 2, x 3 - die Anzahl der verkauften Waren in Tausend Rubel, jeweils 1, 2, 3 Gruppen. Dann hat das mathematische Modell des Problems die Form:

F = 4 x 1 + 5 x 2 + 4 x 3 ->max

0)))(~)" title="delim(lbrace)(matrix(4)(1)((2x_1 + 3x_2 + 6x_3= 0)))(~)">!}

Wir lösen den Simplex nach der Methode.

Wir führen zusätzliche Variablen x 4 ≥ 0, x 5 ≥ 0, x 6 ≥ 0 ein, um die Ungleichungen in Gleichheiten umzuwandeln.

Als Basis nehmen wir x 4 = 240; x5 = 200; x6 = 160.

Daten werden eingegeben Simplex-Tisch

Simplex-Tisch Nummer 1

Zielfunktion:

0 240 + 0 200 + 0 160 = 0

Wir berechnen die Punkte nach der Formel:

Δ 1 \u003d 0 2 + 0 4 + 0 4 - 4 \u003d - 4
Δ 2 \u003d 0 3 + 0 2 + 0 6 - 5 \u003d - 5
Δ 3 \u003d 0 6 + 0 4 + 0 8 - 4 \u003d - 4
Δ 4 \u003d 0 1 + 0 0 + 0 0 - 0 \u003d 0
Δ 5 \u003d 0 0 + 0 1 + 0 0 - 0 \u003d 0
Δ 6 \u003d 0 0 + 0 0 + 0 1 - 0 \u003d 0

Da es negative Schätzungen gibt, ist der Plan nicht optimal. Niedrigste Bewertung:

Wir führen die Variable x 2 in die Basis ein.

Wir definieren eine Variable, die die Basis verlässt. Dazu ermitteln wir das kleinste nichtnegative Verhältnis für die Spalte x 2 .

= 26.667

Das kleinste nicht negative Ergebnis: Q 3 = 26,667. Aus der Basis leiten wir die Variable x 6 ab

Teilen Sie Zeile 3 durch 6.
Von der 1. Reihe subtrahieren Sie die 3. Reihe multipliziert mit 3
Subtrahieren Sie von der 2. Zeile die 3. Zeile multipliziert mit 2


Wir berechnen:

Wir bekommen eine neue Tabelle:

Simplex-Tisch Nummer 2

Zielfunktion:

0 160 + 0 440/3 + 5 80/3 = 400/3

Wir berechnen die Punkte nach der Formel:

Δ 1 \u003d 0 0 + 0 8/3 + 5 2/3 - 4 \u003d - 2/3
Δ 2 \u003d 0 0 + 0 0 + 5 1 - 5 \u003d 0
Δ 3 \u003d 0 2 + 0 4/3 + 5 4/3 - 4 \u003d 8/3
Δ 4 \u003d 0 1 + 0 0 + 5 0 - 0 \u003d 0
Δ 5 \u003d 0 0 + 0 1 + 5 0 - 0 \u003d 0
Δ 6 \u003d 0 (-1) / 2 + 0 (-1) / 3 + 5 1/6 - 0 \u003d 5/6

Da es eine negative Schätzung Δ 1 = - 2/3 gibt, ist der Plan nicht optimal.

Wir führen die Variable x 1 in die Basis ein.

Wir definieren eine Variable, die die Basis verlässt. Dazu ermitteln wir das kleinste nichtnegative Verhältnis für Spalte x 1 .

Das kleinste nicht negative Ergebnis: Q 3 \u003d 40. Wir leiten die Variable x 2 aus der Basis ab

Teilen Sie die 3. Reihe durch 2/3.
Von der 2. Reihe subtrahieren Sie die 3. Reihe multipliziert mit 8/3


Wir berechnen:

Wir bekommen eine neue Tabelle:

Simplex-Tisch Nummer 3

Zielfunktion:

0 160 + 0 40 + 4 40 = 160

Wir berechnen die Punkte nach der Formel:

Δ 1 \u003d 0 0 + 0 0 + 4 1 - 4 \u003d 0
Δ 2 \u003d 0 0 + 0 (-4) + 4 3/2 - 5 \u003d 1
Δ 3 \u003d 0 2 + 0 (-4) + 4 2 - 4 \u003d 4
Δ 4 \u003d 0 1 + 0 0 + 4 0 - 0 \u003d 0
Δ 5 \u003d 0 0 + 0 1 + 4 0 - 0 \u003d 0
Δ 6 \u003d 0 (-1) / 2 + 0 (-1) + 4 1/4 - 0 \u003d 1

Da es keine negativen Schätzungen gibt, ist der Plan optimal.

Die Lösung des Problems:

x 1 = 40; x2 = 0; x 3 \u003d 0; x 4 = 160; x5 = 40; x6 = 0; Fmax = 160

Das heißt, es ist notwendig, Waren der ersten Art im Wert von 40.000 Rubel zu verkaufen. Waren der 2. und 3. Art müssen nicht verkauft werden. In diesem Fall beträgt der maximale Gewinn F max = 160.000 Rubel.

Lösung des dualen Problems

Das duale Problem sieht so aus:

Z = 240 y 1 + 200 y 2 + 160 y 3 ->min

Title="delim(lbrace)(matrix(4)(1)((2y_1 + 4y_2 + 4y_3>=4) (3y_1 + 2y_2 + 6y_3>=5) (6y_1 + 4y_2 + 8y_3>=4) (y_1, y_2, y_3>= 0)))(~)">!}

Wir führen zusätzliche Variablen y 4 ≥ 0, y 5 ≥ 0, y 6 ≥ 0 ein, um die Ungleichungen in Gleichheiten umzuwandeln.

Konjugierte Variablenpaare des direkten und des dualen Problems haben die Form:

Aus der letzten Simplex-Tabelle Nr. 3 des direkten Problems finden wir die Lösung des dualen Problems:

Zmin = Fmax = 160;
y 1 \u003d Δ 4 \u003d 0; y 2 \u003d Δ 5 \u003d 0; y 3 \u003d Δ 6 \u003d 1; y 4 \u003d Δ 1 \u003d 0; y 5 \u003d Δ 2 \u003d 1; y 6 \u003d Δ 3 \u003d 4;

Y1=0; y2 = 0; y 3 = 1; Zmin = 160;

Simplex-Methode− Es handelt sich um eine Methode zur geordneten Aufzählung von Referenzplänen (die Reihenfolge wird durch eine monotone Änderung des Wertes 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. Aus Einschränkungen - Ungleichheiten müssen Einschränkungen - Gleichheiten gemacht werden. Dazu wird jede Einschränkung um eine weitere nichtnegative ergänzt Bilanzvariable mit dem „+“-Zeichen, wenn das Ungleichheitszeichen „£“ ist, und mit dem „–“-Zeichen, wenn das Ungleichheitszeichen „³“ ist.

In der 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 die Verfügbarkeit und den Verbrauch von Ressourcen widerspiegeln, dann numerischer Wert Eine zusätzliche Variable im Aufgabenplan, geschrieben in kanonischer Form, entspricht der Menge der ungenutzten Ressource.

Um das Problem mit der Simplex-Methode zu lösen, verwenden wir verkürzte Simplextabellen eines Systems linearer Gleichungen und die modifizierte Jordan-Eliminationsmethode.

1. Wir erstellen den ersten Grundplan

Die Aufgabe bleibt dieselbe. Überführen 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 ökonomischen Sinne die Werte zusätzlicher Variablen X 3 , X 4 , X 5 Bestimmen Sie die Rohstoffbilanz nach dem Verkauf der Produkte.

Die Matrix des resultierenden Gleichungssystems hat die Form:

Das ist in der Matrix zu erkennen A Die Basis Minor 4. Ordnung ist die Determinante, bestehend aus Einheitskoeffizienten für zusätzliche Variablen X 3 , X 4 , X 5 ,X 6 , da es ungleich Null und gleich 1 ist. Dies bedeutet, dass die Spaltenvektoren für diese Variablen linear unabhängig sind, d. h. form 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 Um unterschiedliche Werte festzulegen, erhalten wir bei der Lösung des Systems nach den Grundvariablen eine unendliche Menge bestimmter Lösungen. Wenn für freie Variablen nur Nullwerte festgelegt sind, dann gilt aus einer unendlichen Menge bestimmter Lösungen, grundlegende Lösungen- Grundpläne.

Um herauszufinden, ob die Variablen einfach sein können, muss die Determinante berechnet werden, die aus den Koeffizienten dieser Variablen besteht. Wenn diese Determinante ungleich Null ist, können diese Variablen einfach sein.


Die Anzahl der Basislösungen und die entsprechende Anzahl der Gruppen von Basisvariablen darf nicht mehr als betragen 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. Es sind 15 Gruppen zu je 4 Basisvariablen möglich (bzw. 15 Basislösungen).

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

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

Diese grundlegende Lösung ist inakzeptabel, Weil X 6 = –10 ≤ 0 und durch die Einschränkungsbedingung X 6 ≥ 0. Daher anstelle der Variablen X 6 als Basis müssen Sie eine weitere Variable aus den freien nehmen X 1 oder X 2 .

Die weitere Lösung führen wir mit verkürzten Simplex-Tabellen durch, indem wir die Zeilen der ersten Tabelle wie folgt mit den Koeffizienten des Systems füllen (Tabelle 1):

Tabelle 1

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

In der Spalte der freien 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 sein.

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 bestimmt, dass die Variable X 1 wird von „kostenlos“ auf „einfach“ umgestellt).

Wir teilen kostenlose Mitglieder b ich auf die relevanten Elemente a ist Auflösungsspalte erhalten wir evaluative BeziehungenΘ ich==(24, 15, 12, 10). Davon wählen wir das kleinste Positive (minΘ ich=10), was entspricht Berechtigungszeile. Berechtigungszeichenfolge definiert eine Variable xj, das im nächsten Schritt aus der Basis herausragt und frei wird. Deshalb X 6 -line ist eine permissive Zeile und das Element „-1“ ist es Freigabeelement. Wir umkreisen es. Variablen X 1 und X 6 werden getauscht.

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

1) Θ ich= wenn b ich Und a ist haben verschiedene Zeichen;

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

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

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

5) Θ ich= wenn b ich Und a ist habe die gleichen Vorzeichen.

Wir machen den Schritt der modifizierten jordanischen Eliminierung (MJJI) mit einem permissiven Element und erstellen eine neue Tabelle (Tabelle 2) gemäß der folgenden Regel:

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

2) die Elemente der permissiven Linie werden in RE unterteilt;

3) die Elemente der Auflösungsspalte werden in RE unterteilt und das Vorzeichen ändert sich;

4) Die restlichen Elemente werden nach der Rechteckregel gefunden:

Vom Tisch. 2 zeigt, dass die freien Mitglieder in b ich-Spalte sind nicht negativ, daher wird die zunächst zulässige Lösung erhalten - 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, da in F-line hat einen negativen Koeffizienten „-4“. Wir verbessern den Plan.

3. Eine neue Grundlinie finden

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

Wir wählen den kleinsten negativen Koeffizienten in F-Zeile „-4“, die die Aktivierungsspalte bestimmt – X 6; Variable X 6 in Basic übersetzen;

Wir finden die Verhältnisse Θ ich, unter ihnen wählen wir das kleinste positive aus, das der permissiven Zeichenfolge entspricht:

Mindest Θ ich = Mindest(14, 5, 2, ∞) = 2, daher X 5 - Zeile - freizügig, variabel X 5 übersetzen wir in freie (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. 3 gemäß der obigen Regel und erhalten Sie einen neuen Referenzplan = (12; 0; 156; 3; 0; 2).

Tisch 3

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

Auch der Basisplan ist nicht optimal, da in F-line 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. Eine neue Grundlinie finden

X 2-spaltig ist zulässig, da in F-Zeile der kleinste negative Koeffizient „-1“ ist in X 2-spaltig (Δ 2 = -1). Finden des kleinsten Θ ich: Mindest Θ ich = Mindest(≈ 9, 6, ∞, 24) = 6, daher X 4. Zeile - freizügig. Zulässiges Element „1/2“. Variablen austauschen X 2 und X 4 . Wir führen den Schritt SHMZhI aus, wir bauen die Tabelle. 4 erhalten wir einen neuen Referenzplan = (9; 6; 51; 0; 0; 5).

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

IN 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 ergibt den Maximalwert der Zielfunktion c.u.

Für die Herstellung von drei Arten von Hemden werden Fäden, Knöpfe und Stoffe verwendet. Die Bestände an Fäden, Knöpfen und Stoffen sowie deren Verbrauchsraten zum Nähen eines Hemdes sind in der Tabelle angegeben. Finden Sie den maximalen Gewinn und den optimalen Produkt-Release-Plan, der ihn sicherstellt (finden).

Hemd 1 Hemd 2 Hemd 3 Aktien Fäden (m.) 1 9 3 96 Knöpfe (Stk.) 20 10 30 640 Textil ( 1 2 2 44 Gewinn (R.) 2 5 4

Die Lösung des Problems

Modellbau

Durch und die Anzahl der zur Veröffentlichung vorgesehenen Hemden des 1., 2. und 3. Typs.

Dann sehen die Ressourcengrenzen so aus:

Darüber hinaus je nach Sinn der Aufgabe

Zielfunktion, die den erhaltenen Gewinn ausdrückt:

Wir erhalten das folgende lineare Programmierproblem:

Reduktion eines linearen Programmierproblems auf kanonische Form

Bringen wir das Problem in die kanonische Form. Lassen Sie uns zusätzliche Variablen einführen. Wir führen alle zusätzlichen Variablen mit einem Koeffizienten gleich Null in die Zielfunktion ein. Wir fügen den linken Teilen der Einschränkungen zusätzliche Variablen hinzu, die nicht vorhanden sind bevorzugter Typ, und wir erhalten Gleichheiten.

Lösung des Problems durch die Simplex-Methode

Füllen Sie die Simplex-Tabelle aus:

Da wir das Problem für das Maximum lösen, weist das Vorhandensein negativer Zahlen in der Indexzeile beim Lösen des Problems für das Maximum darauf hin, dass wir nicht die optimale Lösung erhalten haben und dass wir von der Tabelle der 0. Iteration zu wechseln müssen der Nächste.

Der Übergang zur nächsten Iteration erfolgt wie folgt:

Übereinstimmungen in der führenden Spalte

Die Schlüsselzeile wird durch die Mindestverhältnisse von freien Elementen und Elementen der führenden Spalte (Simplex-Verhältnisse) bestimmt:

Am Schnittpunkt der Schlüsselspalte und der Schlüsselzeile finden wir das ermöglichende Element, d.h. 9.

Beginnen wir nun mit dem Kompilieren der 1. Iteration: Anstelle eines Einheitsvektors führen wir einen Vektor ein.

In der neuen Tabelle schreiben wir anstelle des erlaubenden Elements eine 1, alle anderen Elemente der Schlüsselspalte sind Nullen. Die Schlüsselzeichenfolgenelemente werden durch das permissive Element geteilt. Alle anderen Elemente der Tabelle werden nach der Rechteckregel berechnet.

Schlüsselspalte für Übereinstimmungen der ersten Iteration

Das auflösende Element ist die Zahl 4/3. Wir leiten den Vektor von der Basis ab und führen stattdessen den Vektor ein. Wir erhalten die Tabelle der 2. Iteration.

Die Schlüsselspalte für die 2. Iteration entspricht

Wir finden die Schlüsselzeile, dafür definieren wir:

Das auflösende Element ist die Zahl 10/3. Wir leiten den Vektor von der Basis ab und führen stattdessen den Vektor ein. Wir erhalten die Tabelle der 3. Iteration.

№ BP c B Ao x 1 x2 x 3 x4 x5 x6 Simplex 2 5 4 0 0 0 Beziehung 0 x4 0 96 1 9 3 1 0 0 32/3 x5 0 640 20 10 30 0 1 0 64 x6 0 44 1 2 2 0 0 1 22 F j - c j 0 -2 -5 -4 0 0 0 1 x2 5 32/3 1/9 1 1/3 1/9 0 0 32 x5 0 1600/3 170/9 0 80/3 -10/9 1 0 20 x6 0 68/3 7/9 0 4/3 -2/9 0 1 17 F j - c j 160/3 -13/9 0 -7/3 5/9 0 0 2 x2 5 5 -1/12 1 0 1/6 0 -1/4 -- x5 0 80 10/3 0 0 10/3 1 -20 24 x 3 4 17 7/12 0 1 -1/6 0 3/4 204/7 F j - c j 93 -1/12 0 0 1/6 0 7/4 3 x2 5 7 0 1 0 1/4 1/40 -3/4 x 1 2 24 1 0 0 1 3/10 -6 x 3 4 3 0 0 1 -3/4 -7/40 17/4 F j - c j 95 0 0 0 1/4 1/40 5/4

In der Indexzeile sind alle Mitglieder nicht negativ, daher erhält man die folgende Lösung des linearen Programmierproblems (wir schreiben sie aus der Spalte der freien Mitglieder heraus):

Es müssen 24 Hemden des 1. Typs, 7 Hemden des 2. Typs und 3 Hemden des 3. Typs genäht werden. In diesem Fall ist der erzielte Gewinn maximal und beträgt 95 Rubel.

Es ist notwendig, ein lineares Programmierproblem zu lösen.

Zielfunktion:

2x 1 +5x 2 +3x 3 +8x 4 →min

Randbedingungen:

3x 1 +6x 2 -4x 3 +x 4 ≤12
4x 1 -13x 2 +10x 3 +5x 4 ≥6
3x1 +7x2 +x3 ≥1

Bringen wir das Restriktionssystem in die kanonische Form. Dazu ist es notwendig, von Ungleichungen zu Gleichheiten überzugehen und zusätzliche Variablen hinzuzufügen.

Da es sich bei unserem Problem um ein Minimierungsproblem handelt, müssen wir es in ein Maximierungsproblem umwandeln. Dazu ändern wir die Vorzeichen der Koeffizienten der Zielfunktion in die entgegengesetzten Vorzeichen. Wir schreiben die Elemente der ersten Ungleichung unverändert, fügen eine zusätzliche Variable x 5 hinzu und ändern das Vorzeichen „≤“ in „=“. Da die zweite und dritte Ungleichung das Vorzeichen „≥“ haben, ist es notwendig, die Vorzeichen ihrer Koeffizienten umzukehren und zusätzliche Variablen x 6 bzw. x 7 in sie einzuführen. Als Ergebnis erhalten wir ein äquivalentes Problem:

3x 1 +6x 2 -4x 3 +x 4 +x 5 =12
-4x 1 +13x 2 -10x 3 -5x 4 +x 6 =-6
-3x 1 -7x 2 -x 3 +x 7 =-1

Wir fahren mit der Bildung der anfänglichen Simplex-Tabelle fort. Zeile F der Tabelle enthält Zielfunktionskoeffizienten mit umgekehrtem Vorzeichen.

Freies Mitglied
F
X5
X6
X7

In der von uns zusammengestellten Tabelle gibt es negative Elemente in der Spalte der freien Elemente, wir finden unter ihnen das maximale Modulo – das ist das Element: -6, es legt die führende Zeile fest – X6. In dieser Zeile finden wir auch das maximale negative Element Modulo: -10, es befindet sich in der Spalte X3, die die führende Spalte sein wird. Die Variable in der führenden Zeile wird aus der Basis ausgeschlossen und die Variable, die der führenden Spalte entspricht, wird in die Basis aufgenommen. Lassen Sie uns die Simplex-Tabelle neu berechnen:

X1 X2 X6 X4 Freies Mitglied
F 0.8 8.9 0.3 6.5 -1.8
X5 4.6 0.8 -0.4 3 14.4
X3 0.4 -1.3 -0.1 0.5 0.6
X7 -2.6 -8.3 -0.1 0.5 -0.4

In der von uns zusammengestellten Tabelle gibt es negative Elemente in der Spalte der freien Elemente, wir finden unter ihnen das maximale Modulo – das ist das Element: -0,4, es legt die führende Zeile fest – X7. In dieser Zeile finden wir auch das maximale negative Element Modulo: -8,3, es befindet sich in der Spalte X2, die die führende Spalte sein wird. Die Variable in der führenden Zeile wird aus der Basis ausgeschlossen und die Variable, die der führenden Spalte entspricht, wird in die Basis aufgenommen. Lassen Sie uns die Simplex-Tabelle neu berechnen:

X1 X7 X6 X4 Freies Mitglied
F -1.988 1.072 0.193 7.036 -2.229
X5 4.349 0.096 -0.41 3.048 14.361
X3 0.807 -0.157 -0.084 0.422 0.663
X2 0.313 -0.12 0.012 -0.06 0.048

Da in der Spalte der freien Terme keine negativen Elemente vorhanden sind, wurde eine zulässige Lösung gefunden. In der F-Zeile befinden sich negative Elemente, was bedeutet, dass die resultierende Lösung nicht optimal ist. Definieren wir eine führende Spalte. Dazu finden wir in der Zeile F das maximale negative Element im Absolutwert – das ist -1,988. Die führende Zeile ist diejenige, für die das Verhältnis des freien Elements zum entsprechenden Element der führenden Spalte minimal ist. Die führende Zeile ist X2 und das führende Element ist 0,313.

X2 X7 X6 X4 Freies Mitglied
F 6.351 0.31 0.269 6.655 -1.924
X5 -13.895 1.763 -0.577 3.882 13.694
X3 -2.578 0.152 -0.115 0.577 0.539
X1 3.195 -0.383 0.038 -0.192 0.153

Da es in der Zeile F keine negativen Elemente gibt
die optimale Lösung gefunden. Da die ursprüngliche Aufgabe darin bestand, das Minimum zu finden, ist die optimale Lösung der freie Term der Zeichenfolge F mit umgekehrtem Vorzeichen. F=1,924
mit den Werten der Variablen gleich: x 3 =0,539, x 1 =0,153. Die Variablen x 2 und x 4 sind nicht in der Basis enthalten, also x 2 =0 x 4 =0.

Beispiel #3. Lösung des Problems der linearen Programmierung mit der Simplex-Methode.
Den größten Wert einer Funktion ermitteln (künstliche Basis)

Diese Lösung ist ein Beispiel des auf der Website vorgestellten Programms.


Finden Sie den größten Wert einer Funktion

x 1 ≥ 0 x 2 ≥ 0

1. Die freien Mitglieder des Systems dürfen nicht negativ sein.

Diese Bedingung ist erfüllt.


2. Jede Einschränkung des Systems muss eine Gleichung sein.

x 1 - 2 x2 ≤ 4
x 1 - x2 ≥ 1
x 1 + x2 ≤ 8
x 1 - 2 x2 + S1 = 4
x 1 - x2 - S2 = 1
x 1 + x2 + S3 = 8

S 1 ≥ 0, S 2 ≥ 0, S 3 ≥ 0. Die eingeführten Variablen S 1 , S 2 , S 3 werden Bilanzvariablen genannt.


3. Finden der Anfangsbasis und des Wertes der Funktion F, der der gefundenen Anfangsbasis entspricht.


Was ist eine Basis?
Eine Variable heißt für eine gegebene Gleichung einfach, wenn sie mit in die gegebene Gleichung eingeht Faktor eins und ist in den übrigen Gleichungen nicht enthalten (vorausgesetzt, auf der rechten Seite der Gleichung steht eine positive Zahl).
Wenn jede Gleichung eine Basisvariable hat, dann heißt das System, dass es eine Basis hat.
Variablen, die nicht einfach sind, werden freie Variablen genannt.

Was ist die Idee hinter der Simplex-Methode?
Jede Basis entspricht einem einzelnen Wert der Funktion. Einer von ihnen ist Höchster Wert F-Funktionen.
Wir werden von einer Basis zur anderen übergehen und den Wert der Funktion F erhalten, der nicht kleiner als der vorhandene ist.
Offensichtlich ist die Anzahl möglicher Grundlagen für jedes Problem nicht sehr groß.
Daher wird die Antwort früher oder später eingehen.

Wie erfolgt der Übergang von einer Basis zur anderen?
Bequemer ist es, die Lösung in Tabellenform festzuhalten. Jede Zeile der Tabelle entspricht der Gleichung des Systems. Die hervorgehobene Zeile besteht aus den Koeffizienten der Funktion (siehe Tabelle unten). Dadurch können Sie Variablen nicht jedes Mal neu schreiben, was viel Zeit spart.
Wählen Sie in der ausgewählten Zeile den größten positiven Koeffizienten aus (Sie können jeden positiven Koeffizienten auswählen).
Dies ist notwendig, um den Wert der Funktion F zu erhalten, der nicht kleiner als der vorhandene ist.
Spalte ausgewählt.
Für positive Koeffizienten der ausgewählten Spalte berechnen wir das Verhältnis Θ und wählen kleinster Wert.
Dies ist notwendig, damit nach der Transformation die Spalte der freien Mitglieder positiv bleibt.
Zeile ausgewählt.
Das Element, das das Basiselement sein wird, ist definiert. Als nächstes zählen wir.

Hat unser System eine Grundlage?

x 1 - 2 x2 + S1 = 4
x 1 - x2 - S2 = 1
x 1 + x2 + S3 = 8

Es gibt keine Grundlage, d.h. Wir können keine Lösung finden.
Muss ihn finden. Dazu lösen wir ein Hilfsproblem.
Fügen wir der Gleichung eine künstliche Variable hinzu, bei der es keine Basisvariable gibt.

x 1 - 2 x2 + S1 = 4
x 1 - x2 - S2 + R1 = 1
x 1 + x2 + S3 = 8

R 1 ≥ 0. Die eingeführte Variable R 1 wird als künstliche Variable bezeichnet.

Wir betrachten die Funktion W und suchen nach ihrem kleinsten Wert.

Der Algorithmus zum Ermitteln des kleinsten Wertes der Funktion W unterscheidet sich nur in einem Punkt vom oben diskutierten Algorithmus.
Sie müssen es selbst herausfinden.


x 1x2S1S2S3R1St. Mitglied Θ
1 -2 1 0 0 0 4 4: 1 = 4
1 -1 0 -1 0 1 1 1: 1 = 1
1 1 0 0 1 0 8 8: 1 = 8
-1 1 0 1 0 0 W - 1
0 -1 1 1 0 -1 3
1 -1 0 -1 0 1 1
0 2 0 1 1 -1 7
0 0 0 0 0 1 W - 0

Wir setzen die freien Variablen mit Null gleich. Finden Sie verbal die Werte der Basisvariablen. (siehe Tabelle)
Die Funktion W wird durch freie Variablen ausgedrückt. Daher kann der Wert der Funktion W für eine gegebene Lösung sofort ermittelt werden. (siehe hervorgehobene Zeile der Tabelle)

x 2 = 0 S 2 = 0 R 1 = 0
x 1 = 1 S 1 = 3 S 3 = 7		 => W - 0 = 0 => W = 0

Unter den Koeffizienten der ausgewählten Linie gibt es keine negativen. Daher wird der kleinste Wert der Funktion W gefunden.
Eine Basis wird ohne Verwendung einer künstlichen Variablen erhalten. Genau das war erforderlich.
Die der künstlichen Variablen entsprechende Spalte kann durchgestrichen werden.
Im Ergebnis sieht unser System so aus:

- x2 + S1 + S2 = 3
x 1 - x2 - S2 = 1
2 x2 + S2 + S3 = 7
F = - x 1 + 3 x2
F = -
( 1 + x2 + S2)
+ 3 x2
= -1 + 2 x2 - S2