Lösung eines Produktionsproblems mit einem tabellarischen Simplexverfahren. Simplex-Methode zum Lösen von zlp
Wenn Sie ein Problem lösen müssen Lineares Programmieren mit Simplex-Tabellen, dann unsere Onlineservice wird dir eine große Hilfe sein. Die Simplex-Methode impliziert eine sequentielle Aufzählung aller Knoten der Region zulässige Werte um den Scheitelpunkt zu finden, an dem die Funktion einen Extremwert annimmt. In der ersten Stufe wird eine Lösung gefunden, die in jedem nachfolgenden Schritt verbessert wird. Diese Lösung wird als basisch bezeichnet. Hier ist eine Abfolge von Aktionen beim Lösen eines linearen Programmierproblems mit der Simplex-Methode:
Erster Schritt. In der kompilierten Tabelle müssen Sie sich zunächst die Spalte mit freien Elementen ansehen. Wenn es negative Elemente enthält, muss mit dem zweiten Schritt fortgefahren werden, wenn nicht, dann mit dem fünften.
Zweiter Schritt. Im zweiten Schritt muss entschieden werden, welche Variable von der Basis ausgeschlossen und welche aufgenommen werden soll, um die Simplex-Tabelle neu zu berechnen. Durchsuchen Sie dazu die Spalte mit freien Elementen und finden Sie ein negatives Element darin. Die Linie mit einem negativen Element wird als führende Linie bezeichnet. Darin finden wir das maximale negative Element in absoluten Werten, die entsprechende Spalte - den Follower. Wenn sich unter den freien Mitgliedern negative Werte befinden, aber nicht in der entsprechenden Zeile, dann hat eine solche Tabelle keine Lösungen. Durch die Änderung in der führenden Zeile wird die in der Spalte des freien Elements aus der Basis ausgeschlossen und die Variable, die der führenden Spalte entspricht, wird in die Basis aufgenommen.
Tabelle 1.
| Basisvariablen | Kostenlose Mitglieder in Einschränkungen | Nichtbasisvariablen | |||||
| x 1 | x 2 | ... | x l | ... | x nein | ||
| xn + 1 | b 1 | ein 11 | ein 12 | ... | ein 1l | ... | ein 1n |
| xn + 2 | b 2 | ein 21 | ein 22 | ... | ein 2l | ... | ein 2n |
| . | . | . | . | . | . | . | . |
| . | . | . | . | . | . | . | . |
| . | . | . | . | . | . | . | . |
| x n + r | b2 | ein r1 | ein r2 | ... | ein rl | ... | ein rn |
| . | . | . | . | . | . | . | . |
| . | . | . | . | . | . | . | . |
| . | . | . | . | . | . | . | . |
| x n + m | b m | ein m1 | ein m2 | ... | ein ml | ... | ein mn |
| F (x) max | F 0 | -c 1 | -c 2 | ... | -c 1 | ... | -c nein |
Dritter Schritt. Im dritten Schritt berechnen wir die gesamte Simplex-Tabelle mit speziellen Formeln neu, die man anhand dieser Formeln sehen kann.
Vierter Schritt. Wenn nach der Neuberechnung negative Elemente in der Spalte der freien Elemente verbleiben, fahren Sie mit dem ersten Schritt fort, wenn keine solchen vorhanden sind, dann mit dem fünften.
Fünfter Schritt. Wenn Sie den fünften Schritt erreicht haben, haben Sie eine akzeptable Lösung gefunden. Dies bedeutet jedoch nicht, dass es optimal ist. Es ist nur optimal, wenn alle Elemente in der F-Reihe positiv sind. Ist dies nicht der Fall, ist eine Verbesserung der Lösung erforderlich, für die wir nach folgendem Algorithmus die führende Zeile und Spalte für die nächste Neuberechnung finden. Zunächst finden wir die minimale negative Zahl in Zeile F, ohne den Funktionswert. Die Spalte mit dieser Nummer ist die führende. Um die führende Zeile zu finden, ermitteln wir das Verhältnis des entsprechenden freien Stabes und des Elements aus der führenden Spalte, sofern sie positiv sind. Die minimale Beziehung ermöglicht es Ihnen, die führende Zeile zu bestimmen. Wir berechnen die Tabelle erneut mit den Formeln, d.h. gehe zu Schritt 3.
Eine der Methoden zur Lösung von Optimierungsproblemen ( normalerweise mit der Suche nach einem Minimum oder Maximum verbunden associated) heißt lineare Programmierung. Simplex-Methode umfasst eine ganze Gruppe von Algorithmen und Methoden zur Lösung linearer Programmierprobleme. Eine dieser Methoden, die die Aufzeichnung von Anfangsdaten und deren Neuberechnung in einer speziellen Tabelle vorsieht, heißt tabellarische Simplex-Methode.
Betrachten Sie den Algorithmus der tabellarischen Simplex-Methode am Beispiel der Lösung Produktionsaufgabe , was darauf hinausläuft, einen Produktionsplan zu finden, der maximalen Gewinn bietet.
Ausgangsdaten des Problems für die Simplex-Methode
Das Unternehmen produziert 4 Arten von Produkten und verarbeitet sie auf 3 Maschinen.
Zeitsätze (min / Stück) für die Verarbeitung von Produkten auf Maschinen, festgelegt durch Matrix A:
Der Maschinenlaufzeitfonds (min.) ist in Matrix B angegeben:
Der Gewinn aus dem Verkauf jeder Produkteinheit (Rubel / Stück) wird durch die Matrix C angegeben:
Der Zweck der Produktionsaufgabe
Erstellen Sie einen Produktionsplan, in dem der Gewinn des Unternehmens maximal ist.
Lösung des Problems durch die tabellarische Simplex-Methode
(1) Nennen wir X1, X2, X3, X4 die geplante Menge der Produkte jedes Typs. Dann der gewünschte Plan: ( X1, X2, X3, X4)
(2) Schreiben wir die Randbedingungen des Plans in Form eines Gleichungssystems:
(3) Dann der Zielgewinn:
Das heißt, der Gewinn aus der Erfüllung des Produktionsplans sollte maximal sein.
(4) Um das resultierende Problem für ein bedingtes Extremum zu lösen, ersetzen wir das Ungleichungssystem durch ein lineares Gleichungssystem, indem wir zusätzliche nicht-negative Variablen einführen ( X5, X6, X7).
(5) Nehmen wir folgendes Basisplan:
X1 = 0, X2 = 0, X3 = 0, X4 = 0, X5 = 252, X6 = 144, X7 = 80
(6) Geben wir die Daten ein in Simplex-Tabelle:
In der letzten Zeile tragen wir die Koeffizienten der Zielfunktion und ihren Wert selbst mit umgekehrtem Vorzeichen ein;
(7) Wir wählen in der letzten Zeile der größte (modulo) eine negative Zahl.
Lass uns rechnen b = N / Selected_Column_Elements
Wählen Sie unter den berechneten Werten von b die wenigsten.
Der Schnittpunkt der ausgewählten Spalte und Zeile gibt uns ein zulassendes Element. Wir ändern die Basis in die Variable, die dem auflösenden Element entspricht ( X5 bis X1).
- Das auflösende Element selbst wird 1.
- Für die Elemente der Auflösungsgeraden - a ij (*) = a ij / RE ( das heißt, jedes Element wird durch den Wert des auflösenden Elements geteilt und wir erhalten neue Daten).
- Bei zulässigen Spaltenelementen werden sie einfach auf Null gesetzt.
- Die restlichen Tabellenelemente werden nach der Rechteckregel neu berechnet.
a ij (*) = a ij - (A * B / RE)
Wie Sie sehen, nehmen wir die aktuell neu zu berechnende Zelle und die Zelle mit dem Auflösungselement. Sie bilden gegenüberliegende Ecken des Rechtecks. Als nächstes multiplizieren wir die Werte aus den Zellen der anderen 2 Ecken dieses Rechtecks. Diese Arbeit ( EIN * B) wird durch das auflösende Element ( RE). Und subtrahiere von der aktuell neu berechneten Zelle ( ein ij) Was ist passiert. Wir bekommen einen neuen Wert - a ij (*).
(9) Überprüfen Sie die letzte Zeile erneut ( c) auf der Vorhandensein von negativen Zahlen... Wenn sie nicht da sind, wurde der optimale Plan gefunden, wir fahren mit der letzten Phase der Problemlösung fort. Ist dies der Fall, ist der Plan noch nicht optimal und die Simplex-Tabelle muss neu berechnet werden.
Da wir in der letzten Zeile wieder negative Zahlen haben, starten wir eine neue Iteration der Berechnungen.
(10) Da es in der letzten Zeile keine negativen Elemente gibt, haben wir den optimalen Produktionsplan gefunden! Nämlich: Wir werden diejenigen Produkte produzieren, die in die Spalte "Basis" - X1 und X2 - übergegangen sind. Wir kennen den Gewinn aus der Produktion jeder Produktionseinheit ( Matrix C). Es bleibt übrig, die gefundenen Produktionsmengen der Produkte 1 und 2 mit einem Gewinn mit 1 Stück zu multiplizieren, wir erhalten das endgültige ( maximal! ) Gewinn für einen bestimmten Produktionsplan.
ANTWORTEN:
X1 = 32 Stk., X2 = 20 Stk., X3 = 0 Stk., X4 = 0 Stk.
P = 48 * 32 + 33 * 20 = 2 196 Rubel.
Galyautdinov R. R.
© Das Kopieren des Materials ist nur zulässig, wenn ein direkter Hyperlink zu
| - | x 1 | + | x 2 | - | S 1 | = | 1 | ||||||||||
| x 1 | +3 | x 2 | + | S 2 | = | 15 | |||||||||||
| - | 2 | x 1 | + | x 2 | + | S 3 | = | 4 |
| - | x 1 | + | x 2 | - | S 1 | + | R 1 | = | 1 | |||||||||||
| x 1 | +3 | x 2 | + | S 2 | = | 15 | ||||||||||||||
| - | 2 | x 1 | + | x 2 | + | S 3 | = | 4 |
| x 1 = 0 x 2 = 0 S 1 = 0 S 2 = 15 S 3 = 4 R 1 = 1 |
=> W = 1 |
| x 1 | x 2 | S 1 | S 2 | S 3 | R 1 | st. Mitglied | Θ |
| -1 | 1 | -1 | 0 | 0 | 1 | 1 | 1: 1 = 1 |
| 1 | 3 | 0 | 1 | 0 | 0 | 15 | 15: 3 = 5 |
| -2 | 1 | 0 | 0 | 1 | 0 | 4 | 4: 1 = 4 |
| 1 | -1 | 1 | 0 | 0 | 0 | W - 1 | |
| -1 | 1 | -1 | 0 | 0 | 1 | 1 | |
| 4 | 0 | 3 | 1 | 0 | -3 | 12 | |
| -1 | 0 | 1 | 0 | 1 | -1 | 3 | |
| 0 | 0 | 0 | 0 | 0 | 1 | W - 0 |
| - | x 1 | + | x 2 | - | S 1 | = | 1 | ||||||||||
| 4 | x 1 | + | 3 | S 1 | + | S 2 | = | 12 | |||||||||
| - | x 1 | + | S 1 | + | S 3 | = | 3 |
| x 1 | x 2 | S 1 | S 2 | S 3 | st. Mitglied | Θ |
| -1 | 1 | -1 | 0 | 0 | 1 | |
| 4 | 0 | 3 | 1 | 0 | 12 | 12: 4 = 3 |
| -1 | 0 | 1 | 0 | 1 | 3 | |
| 4 | 0 | 1 | 0 | 0 | F - 1 | |
| -1 | 1 | -1 | 0 | 0 | 1 | |
| 1 | 0 | 3/4 | 1/4 | 0 | 3 | |
| -1 | 0 | 1 | 0 | 1 | 3 | |
| 4 | 0 | 1 | 0 | 0 | F - 1 | |
| 0 | 1 | -1/4 | 1/4 | 0 | 4 | |
| 1 | 0 | 3/4 | 1/4 | 0 | 3 | |
| 0 | 0 | 7/4 | 1/4 | 1 | 6 | |
| 0 | 0 | -2 | -1 | 0 | F - 13 |
| S1 = 0 S2 = 0 x 1 = 3 x 2 = 4 S 3 = 6 |
=> F - 13 = 0 => F = 13 |
Ein Beispiel für die Lösung des Problems durch die Simplex-Methode wird ebenso betrachtet wie ein Beispiel für die Lösung Doppelaufgabe.
Die Aufgabe
Für den Verkauf von drei Warengruppen verfügt ein Handelsunternehmen über drei Arten von begrenzten materiellen und monetären Mitteln in Höhe von b 1 = 240, b 2 = 200, b 3 = 160 Einheiten. Gleichzeitig für den Verkauf von 1 Warengruppe für 1 Tausend Rubel. Der Umsatz wird für die Ressource erster Art in Höhe von a 11 = 2 Einheiten ausgegeben, die Ressource zweiter Art in Höhe von 21 = 4 Einheiten, die 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. der Umsatz der Ressource erster Art in Höhe von a 12 = 3, a 13 = 6 Einheiten, der Ressource zweiter Art in Höhe von a 22 = 2, a 23 = 4 Einheiten, Ressource des dritten Typs in Höhe von 32 = 6, 33 = 8 Einheiten ... Profitieren Sie vom Verkauf von drei Warengruppen für 1 Tausend Rubel. Der Umsatz beträgt jeweils c 1 = 4, c 2 = 5, c 3 = 4 (Tausend Rubel). Bestimmen Sie das geplante Volumen und die Struktur des Umsatzes, damit der Gewinn des Handelsunternehmens maximal ist.
Zur direkten Aufgabe der Umsatzplanung, lösbar nach der Simplex-Methode, bilden Doppelaufgabe Lineares Programmieren.
Installieren konjugiere Variablenpaare direkte und doppelte Aufgaben.
Nach konjugierten Variablenpaaren erhält man aus der Lösung des direkten Problems Doppelproblemlösung in welchem Ressourcenbewertung für den Verkauf von Waren ausgegeben.
Lösung des Problems mit der Simplex-Methode
Seien x 1, x 2, x 3 - die Anzahl der verkauften Waren in Tausend Rubel, 1, 2, 3 - ihre Gruppen. Dann hat das mathematische Modell des Problems die Form:F = 4 x 1 + 5 x 2 + 4 x 3 -> max
0))) (~) "title =" (! LANG: delim (lbrace) (matrix (4) (1) ((2x_1 + 3x_2 + 6x_3 = 0))) (~)">!}
Wir lösen die Simplex-Methode.
Führe zusätzliche Variablen x 4 0, x 5 ≥ 0, x 6 ≥ 0 ein, um Ungleichungen in Gleichheiten umzuwandeln.
Nehmen Sie x 4 = 240 als Basis; x5 = 200; x6 = 160.
Wir geben die Daten ein in Simplex-Tabelle
Simplex-Tischnummer 1
Zielfunktion:
0 240 + 0 200 + 0 160 = 0
Wir berechnen die Scores mit der Formel:
Δ 1 = 0 2 + 0 4 + 0 4 - 4 = - 4
Δ 2 = 0 3 + 0 2 + 0 6 - 5 = - 5
Δ 3 = 0 6 + 0 4 + 0 8 - 4 = - 4
Δ 4 = 0 1 + 0 0 + 0 0 - 0 = 0
Δ 5 = 0 0 + 0 1 + 0 0 - 0 = 0
Δ 6 = 0 0 + 0 0 + 0 1 - 0 = 0
Da es negative Bewertungen gibt, ist der Plan nicht optimal. Niedrigste Note:
Wir führen die Variable x 2 in die Basis ein.
Wir definieren eine Variable, die die Basis verlässt. Finden Sie dazu das kleinste nicht-negative Verhältnis für die Spalte x 2.
= 26.667
Kleinstes nicht-negativ: Q 3 = 26,667. Wir leiten die Variable x 6 aus der Basis
Teilen Sie die dritte Reihe durch 6.
Von der 1. Zeile subtrahieren Sie die 3. Zeile, multipliziert mit 3
Von der 2. Reihe subtrahiere die 3. Reihe, multipliziert mit 2
Wir rechnen:
Wir bekommen neuer Tisch:
Simplex-Tischnummer 2
Zielfunktion:
0 160 + 0 440/3 + 5 80/3 = 400/3
Wir berechnen die Scores mit der Formel:
Δ 1 = 0 0 + 0 8/3 + 5 2/3 - 4 = - 2/3
Δ 2 = 0 0 + 0 0 + 5 1 - 5 = 0
Δ 3 = 0 2 + 0 4/3 + 5 4/3 - 4 = 8/3
Δ 4 = 0 1 + 0 0 + 5 0 - 0 = 0
Δ 5 = 0 0 + 0 1 + 5 0 - 0 = 0
Δ 6 = 0 (-1) / 2 + 0 (-1) / 3 + 5 1/6 - 0 = 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. Finden Sie dazu das kleinste nicht-negative Verhältnis für die Spalte x 1.
Das kleinste nicht-negativ: Q 3 = 40. Wir leiten die Variable x 2 aus der Basis
Teilen Sie die 3. Reihe durch 2/3.
Von der 2. Reihe subtrahiere die 3. Reihe, multipliziert mit 8/3
Wir rechnen:
Wir bekommen eine neue Tabelle:
Simplex-Tischnummer 3
Zielfunktion:
0 160 + 0 40 + 4 40 = 160
Wir berechnen die Scores mit der Formel:
Δ 1 = 0 0 + 0 0 + 4 1 - 4 = 0
Δ 2 = 0 0 + 0 (-4) + 4 3/2 - 5 = 1
Δ 3 = 0 2 + 0 (-4) + 4 2 - 4 = 4
Δ 4 = 0 1 + 0 0 + 4 0 - 0 = 0
Δ 5 = 0 0 + 0 1 + 4 0 - 0 = 0
Δ 6 = 0 (-1) / 2 + 0 (-1) + 4 1/4 - 0 = 1
Da es keine negativen Bewertungen gibt, ist der Plan optimal.
Die Lösung des Problems:
Antworten
x 1 = 40; x2 = 0; x3 = 0; x4 = 160; x5 = 40; x6 = 0; Fmax = 160Das heißt, es ist notwendig, die Waren des ersten Typs in Höhe von 40 Tausend Rubel zu verkaufen. Es ist nicht erforderlich, Waren der 2. und 3. Art zu verkaufen. In diesem Fall beträgt der maximale Gewinn F max = 160 Tausend Rubel.
Lösung des dualen Problems
Das Doppelproblem ist:
Z = 240 Jahre 1 + 200 Jahre 2 + 160 Jahre 3 -> min
Titel = "(! LANG: 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))) (~)">!}
Führe zusätzliche Variablen y 4 ≥ 0, y 5 ≥ 0, y 6 ≥ 0 ein, um Ungleichungen in Gleichheiten umzuwandeln.
Konjugierte Variablenpaare des direkten und dualen Problems haben die Form:
Aus dem letzten Simplex der Tabelle Nr. 3 des direkten Problems finden wir die Lösung des dualen Problems:
Zmin = Fmax = 160;
y 1 = 4 = 0; y 2 = 5 = 0; y 3 = 6 = 1; y 4 = Δ 1 = 0; y 5 = 2 = 1; y 6 = 3 = 4;
Erwägen Simplex-Methode zur Lösung von linearen Programmierproblemen (LP). Es basiert auf dem Übergang von einem Basisplan zu einem anderen, bei dem der Wert der Zielfunktion ansteigt.
Der Algorithmus der Simplex-Methode lautet wie folgt:
- Wir überführen das ursprüngliche Problem in kanonische Form, indem wir zusätzliche Variablen einführen. Bei Ungleichungen der Form ≤ werden zusätzliche Variablen mit dem Vorzeichen (+) eingeführt, bei der Form ≥ dann mit dem Vorzeichen (-). In die Zielfunktion werden zusätzliche Variablen mit entsprechenden Vorzeichen mit einem Koeffizienten gleich eingeführt 0 schon seit die Zielfunktion sollte ihre wirtschaftliche Bedeutung nicht ändern.
- Vektoren werden ausgeschrieben P i aus den Koeffizienten der Variablen und der Spalte der freien Terme. Diese Aktion bestimmt die Anzahl der Einheitsvektoren. Die Regel ist, dass es so viele Einheitsvektoren geben sollte, wie es Ungleichungen im System der Beschränkungen gibt.
- Danach werden die Originaldaten in eine Simplex-Tabelle eingetragen. Einheitsvektoren werden in die Basis eingeführt, und indem sie aus der Basis ausgeschlossen werden, wird eine optimale Lösung gefunden. Die Zielfunktionskoeffizienten werden mit dem umgekehrten Vorzeichen geschrieben.
- Das Optimalitätskriterium für das LP-Problem ist, dass die Lösung optimal ist, wenn in f- in Folge sind alle Koeffizienten positiv. Spaltensuchregel zulassen – Gesucht f- Die Reihe und die kleinste wird unter ihren negativen Elementen ausgewählt. Vektor P i sein Enthalten wird permissiv. Auswahlregel des Auflösungselements - das Verhältnis der positiven Elemente der Auflösungsspalte zu den Elementen des Vektors P 0 und die Zahl, die das kleinste Verhältnis ergibt, wird das auflösende Element, bezüglich dessen die Simplextabelle neu berechnet wird. Die Zeile, die dieses Element enthält, wird als Auflösungszeile bezeichnet. Wenn die Auflösungsspalte keine positiven Elemente enthält, hat das Problem keine Lösung. Nachdem das Auflösungselement bestimmt wurde, fährt man mit der Neuberechnung einer neuen Simplex-Tabelle fort.
- Regeln zum Ausfüllen einer neuen Simplex - Tabelle. Anstelle des auflösenden Elements wird eines abgelegt und die anderen Elemente werden als gleich angenommen 0 ... Der Auflösungsvektor wird in die Basis eingeführt, von der der entsprechende Nullvektor ausgeschlossen wird, und die restlichen Basisvektoren werden unverändert aufgezeichnet. Die Elemente der Auflösungslinie werden durch das Auflösungselement geteilt und die restlichen Elemente werden nach der Rechteckregel neu berechnet.
- Dies geschieht bis f- nacheinander werden nicht alle Elemente positiv.
Betrachten wir die Lösung des Problems mit dem obigen Algorithmus.
Gegeben:
Wir bringen das Problem in die kanonische Form:
Wir stellen Vektoren zusammen:
Wir füllen die Simplex - Tabelle aus:
:
Lassen Sie uns das erste Element des Vektors neu berechnen P 0, für die wir ein Rechteck aus Zahlen bilden: und wir erhalten: 
.
Für alle anderen Elemente der Simplex-Tabelle führen wir ähnliche Berechnungen durch:
Im resultierenden Plan f- die Zeile enthält ein negatives Element - (-5/3), Vektoren P 1... Es enthält in seiner Spalte ein einzelnes positives Element, das das auflösende Element ist. Lassen Sie uns die Tabelle relativ zu diesem Element neu berechnen:
Mangel an negativen Elementen in f- Linie bedeutet gefunden optimaler Plan:
F* = 36/5, X = (12/5, 14/5, 8, 0, 0).
- Ashmanov S.A. Lineare Programmierung, M: Nauka, 1998,
- Wentzel E.S. Operations Research, M: Sowjetischer Rundfunk, 2001,
- Kuznetsov Yu.N., Kuzubov V.I., Woloshenko A.B. Mathematische Programmierung, M: Höhere Schule, 1986.
Benutzerdefinierte lineare Programmierlösung
Alle Aufgaben in dieser Disziplin können Sie auf unserer Website bestellen. Sie können Dateien anhängen und Daten angeben unter
