Ein Beispiel für die Lösung von direkten und dualen Problemen durch die Simplex-Methode. Lösen von Problemen der linearen Programmierung mit der Simplex-Methode

Hier ist eine manuelle (kein Applet) Lösung von zwei Problemen durch die Simplex-Methode (ähnlich der Lösung durch ein Applet) mit detaillierten Erklärungen, um den Algorithmus zur Lösung von Problemen mit der Simplex-Methode zu verstehen. Das erste Problem enthält nur Ungleichungszeichen "≤" (ein Problem mit einer Anfangsbasis), das zweite kann die Zeichen "≥", "≤" oder "=" (ein Problem mit einer künstlichen Basis) enthalten, sie werden auf unterschiedliche Weise gelöst .

Simplex-Methode, ein Problem mit einer Ausgangsbasis lösen

1)Simplex-Methode für ein Problem mit einer Ausgangsbasis (alle Anzeichen von Ungleichheitsbeschränkungen "≤").

Schreiben wir die Aufgabe in kanonisch bilden, d.h. Ungleichheitsbeschränkungen können durch Hinzufügen von in Gleichheit umgeschrieben werden Bilanz Variablen:

Dieses System ist ein System mit einer Basis (Basis s 1, s 2, s 3, jede davon ist in nur einer Gleichung des Systems mit Koeffizient 1 enthalten), x 1 und x 2 sind freie Variablen. Probleme, bei deren Lösung die Simplex-Methode verwendet wird, müssen die folgenden zwei Eigenschaften haben: - das Zwangsbedingungssystem muss ein Gleichungssystem mit einer Basis sein; - freie Terme aller Gleichungen im System müssen nicht negativ sein.

Das resultierende System ist ein System mit einer Basis und seine freien Terme sind nichtnegativ; daher können wir anwenden Simplex-Methode... Lassen Sie uns die erste Simplex-Tabelle (Iteration 0) erstellen, um das Problem auf . zu lösen Simplex-Methode, d.h. eine Tabelle mit Zielfunktionskoeffizienten und ein Gleichungssystem für die entsprechenden Variablen. Hier bedeutet "BP" die Spalte der Basisvariablen, "Lösung" - die Spalte der rechten Seiten der Gleichungen des Systems. Die Lösung ist nicht optimal, weil es gibt negative Koeffizienten in der z - Zeile.

Simplex-Methoden-Iteration 0

							Attitüde

Um die Lösung zu verbessern, fahren wir mit der nächsten Iteration fort Simplex-Methode, erhalten wir die folgende Simplex-Tabelle. Dazu müssen Sie wählen zulässige Spalte, d.h. eine Variable, die bei der nächsten Iteration der Simplex-Methode in die Basis aufgenommen wird. Es wird durch den größten negativen Modulo-Koeffizienten in der z-Reihe (im Maximum-Problem) ausgewählt - in der anfänglichen Iteration des Simplex-Verfahrens ist dies Spalte x 2 (Koeffizient -6).

Ist dann ausgewählt zulässige Zeichenfolge, d.h. die Variable, die die Basis bei der nächsten Iteration der Simplex-Methode verlässt. Es wird durch das kleinste Verhältnis der Spalte "Entscheidung" zu den entsprechenden positiven Elementen der Auflösungsspalte (der Spalte "Verhältnis") ausgewählt - in der anfänglichen Iteration ist dies Zeile s 3 (Koeffizient 20).

Zulässiges Element befindet sich am Schnittpunkt der auflösenden Spalte und der auflösenden Zeile, ihre Zelle ist hervorgehoben, sie ist gleich 1. Daher wird bei der nächsten Iteration der Simplex-Methode die Variable x 2 s 1 in der Basis ersetzen. Beachten Sie, dass in der Z-Linie nicht nach der Beziehung gesucht wird, sondern dort ein Bindestrich "-" eingefügt wird. Wenn die gleichen minimalen Relationen vorhanden sind, wird eine von ihnen ausgewählt. Wenn alle Koeffizienten in der Auflösungsspalte kleiner oder gleich 0 sind, ist die Lösung des Problems unendlich.

Lassen Sie uns die folgende Tabelle "Iteration 1" ausfüllen. Wir erhalten es aus der Tabelle "Iteration 0". Das Ziel weiterer Transformationen ist es, aus der auflösenden Spalte x 2 eins zu machen (mit eins anstelle des auflösenden Elements und Nullen anstelle anderer Elemente).

1) Berechnung von Zeile x 2 der Tabelle "Iteration 1". Zuerst dividieren wir alle Mitglieder der auflösenden Zeile s 3 der Tabelle "Iteration 0" durch das auflösende Element (es ist gleich 1 in in diesem Fall) dieser Tabelle erhalten wir Zeile x 2 in der Tabelle "Iterations 1". Weil das auflösende Element in diesem Fall gleich 1 ist, dann fällt Zeile s 3 der Tabelle "Iteration 0" mit Zeile x 2 der Tabelle "Iteration 1" zusammen. Wir haben Zeile x 2 der Tabelle "Iteration 1" 0 1 0 0 1 20 erhalten, die restlichen Zeilen der Tabelle "Iteration 1" werden aus dieser Zeile und den Zeilen der Tabelle "Iteration 0" wie folgt erhalten:

2) Berechnung der z-Zeile der Tabelle "Iteration 1". Anstelle von -6 in der ersten Zeile (Z-Zeile) in Spalte x 2 der Tabelle Iteration 0 sollte 0 in der ersten Zeile der Tabelle Iteration 1 stehen. Dazu multiplizieren wir alle Elemente der Zeile x 2 der Tabelle "Iteration 1" 0 1 0 0 1 20 mit 6, wir erhalten 0 6 0 0 6 120 und addieren diese Zeile mit der ersten Zeile (z - Zeile) von die Tabelle "Iteration 0" -4 -6 0 0 0 0 erhalten wir -4 0 0 0 6 120. In der Spalte x 2 erscheint null 0, das Ziel ist erreicht. Elemente der Auflösungsspalte x 2 sind rot hervorgehoben.

3) Berechnung der Zeile s 1 der Tabelle "Iteration 1". An Stelle 1 in s 1 Zeile der Tabelle "Iteration 0" muss 0 in der Tabelle "Iteration 1" stehen. Dazu multiplizieren wir alle Elemente der Zeile x 2 der Tabelle "Iteration 1" 0 1 0 0 1 20 mit -1, wir erhalten 0 -1 0 0 -1 -20 und addieren diese Zeile mit s 1 - the Zeile der Tabelle "Iteration 0" 2 1 1 0 0 64 erhalten wir Zeile 2 0 1 0 -1 44. In Spalte x 2 erhalten wir die erforderliche 0.

4) Berechnung von Zeile s 2 der Tabelle "Iteration 1". An Platz 3 in s 2 Zeile der "Iteration 0"-Tabelle muss 0 in der "Iteration 1"-Tabelle stehen. Dazu multiplizieren wir alle Elemente der Zeile x 2 der Tabelle "Iteration 1" 0 1 0 0 1 20 mit -3, wir erhalten 0 -3 0 0 -3 -60 und addieren diese Zeile mit s 1 - the Zeile der Tabelle "Iteration 0" 1 3 0 1 0 72 erhalten wir Zeile 1 0 0 1 -3 12. In Spalte x 2 ergibt sich die erforderliche 0. Spalte x 2 in der Tabelle "Iteration 1" ist eins geworden , es enthält eine 1 und den Rest 0.

Die Zeilen der Tabelle "Iteration 1" erhält man nach folgender Regel:

Neue Zeile = Alte Zeile - (Auflösungsspaltenfaktor der alten Zeile) * (Neue Auflösungszeile).

Für die Z-Linie haben wir zum Beispiel:

Alte Z-Linie (-4 -6 0 0 0 0) - (- 6) * Neue Auflösungslinie - (0 -6 0 0 -6 -120) = Neue Z-Linie (-4 0 0 0 6 120).

Für die folgenden Tabellen erfolgt die Neuberechnung von Tabellenelementen auf die gleiche Weise, sodass wir sie weglassen.

Simplex-Methoden-Iteration 1

							Attitüde

Wenn Spalte x 1 zugelassen wird, wird Zeile s 2 aufgelöst, s 2 verlässt die Basis, x 1 tritt in die Basis ein. Genauso erhalten wir den Rest der Simplex-Tabellen, bis wir eine Tabelle mit allen positiven Koeffizienten in der z-Zeile erhalten. Dies ist ein Zeichen für eine optimale Tabelle.

Simplex-Methode Iteration 2

							Attitüde

Die auflösende Spalte s 3, die auflösende Zeile s 1, verlässt s 1 die Basis, s 3 tritt in die Basis ein.

Simplex-Methoden-Iteration 3

							Attitüde

In der z-Reihe sind alle Koeffizienten nicht negativ, daher ist die optimale Lösung x 1 = 24, x 2 = 16, z max = 192.

Diese Methode ist eine Methode zur gezielten Aufzählung von unterstützenden Lösungen für das Problem Lineares Programmieren... Es erlaubt in endlich vielen Schritten, entweder die optimale Lösung zu finden oder festzustellen, dass es keine optimale Lösung gibt.

Der Hauptinhalt der Simplex-Methode ist wie folgt:

Geben Sie einen Weg an, um die optimale Support-Lösung zu finden
Geben Sie die Übergangsmethode von einer Trägerlösung zu einer anderen an, bei der der Wert der Zielfunktion näher am optimalen liegt, d. h. einen Weg zur Verbesserung der Supportlösung aufzeigen
Legen Sie Kriterien fest, die es Ihnen ermöglichen, die Suche nach Unterstützungslösungen zur optimalen Lösung rechtzeitig zu stoppen oder der Schlussfolgerung über das Fehlen einer optimalen Lösung zu folgen.

Algorithmus der Simplex-Methode zur Lösung linearer Programmierprobleme

Um das Problem zu lösen Simplex-Methode Sie müssen Folgendes tun:

Bringen Sie das Problem in die kanonische Form
Finden Sie die erste Support-Lösung mit einer "Einheitenbasis" (wenn es keine Support-Lösung gibt, dann hat das Problem keine Lösung aufgrund der Inkompatibilität des Systems der Randbedingungen)
Berechnen Sie die Schätzungen der Vektorentwicklungen in der Basis der Stützlösung und füllen Sie die Tabelle der Simplexmethode aus
Ist das Kriterium für die Eindeutigkeit der optimalen Lösung erfüllt, dann endet die Lösung des Problems
Ist die Bedingung für die Existenz einer Menge optimaler Lösungen erfüllt, so werden durch einfache Aufzählung alle optimalen Lösungen gefunden

Ein Beispiel für die Lösung eines Problems mit der Simplex-Methode

Beispiel 26.1

Lösen Sie das Problem mit der Simplex-Methode:

Lösung:

Wir bringen das Problem in eine kanonische Form.

Dazu führen wir auf der linken Seite der ersten Ungleichungsbedingung eine zusätzliche Variable x 6 mit einem Koeffizienten von +1 ein. Die Variable x 6 ist in der Zielfunktion mit einem Koeffizienten von Null enthalten (dh sie ist nicht enthalten).

Wir bekommen:

Finden Sie die erste Support-Lösung. Dazu werden freie (unaufgelöste) Variablen mit Null x1 = x2 = x3 = 0 gleichgesetzt.

Wir bekommen Referenzlösung X1 = (0,0,0,24,30,6) mit Einheitsbasis B1 = (A4, A5, A6).

Wir berechnen Vektorexpansionsschätzungen Bedingungen auf Basis der Referenzlösung nach der Formel:

k = CbXk - ck

C b = (c 1, c 2, ..., cm) ist der Koeffizientenvektor der Zielfunktion für die Basisvariablen
X k = (x 1k, x 2k, ..., x mk) ist der Expansionsvektor des entsprechenden Vektors A k in der Basis der Stützlösung
C k - Koeffizient der Zielfunktion bei der Variablen x k.

Die Schätzungen der in der Basis enthaltenen Vektoren sind immer Null. Die Stützlösung, die Expansionskoeffizienten und die Schätzungen der Entwicklungen der Bedingungsvektoren in der Basis der Stützlösung werden in geschrieben Simplex-Tabelle:

Oberhalb der Tabelle sind die Koeffizienten der Zielfunktion zur Vereinfachung der Berechnung von Schätzungen angegeben. Die erste Spalte "B" enthält die Vektoren, die in der Basis der Referenzlösung enthalten sind. Die Schreibreihenfolge dieser Vektoren entspricht der Anzahl der zulässigen Unbekannten in den Beschränkungsgleichungen. In der zweiten Spalte der Tabelle "C b" sind die Koeffizienten der Zielfunktion mit den Basisvariablen in derselben Reihenfolge aufgeführt. Bei korrekter Anordnung der Zielfunktionskoeffizienten in der Spalte "C b" sind die Schätzungen der in der Basis enthaltenen Einheitsvektoren immer gleich Null.

Die letzte Zeile der Tabelle mit Schätzungen Δ k in der Spalte "A 0" zeichnet die Werte der Zielfunktion auf die Referenzlösung Z (X 1) auf.

Die initiale Supportlösung ist nicht optimal, da im Maximumproblem die Abschätzungen Δ 1 = -2, Δ 3 = -9 für die Vektoren А 1 und А 3 negativ sind.

Nach dem Theorem über die Verbesserung der Stützlösung kann, wenn im Maximumproblem mindestens ein Vektor eine negative Schätzung hat, eine neue Stützlösung gefunden werden, auf der der Wert der Zielfunktion größer ist.

Lassen Sie uns bestimmen, welcher der beiden Vektoren zu einem größeren Inkrement der Zielfunktion führt.

Das Inkrement der Zielfunktion ergibt sich aus der Formel:.

Wir berechnen die Werte des Parameters θ 01 für die erste und dritte Spalte mit der Formel:

Wir erhalten θ 01 = 6 mit l = 1, θ 03 = 3 mit l = 1 (Tabelle 26.1).

Das Inkrement der Zielfunktion ermitteln wir, indem wir den ersten Vektor ΔZ 1 = - 6 * (- 2) = 12 in die Basis einführen und den dritten Vektor ΔZ 3 = - 3 * (- 9) = 27.

Für eine schnellere Annäherung an die optimale Lösung ist es daher erforderlich, anstelle des ersten Vektors der Basis A6 den Vektor A3 in die Basis der Stützlösung einzuführen, da das Minimum des Parameters θ 03 in der ersten Zeile erreicht wird (l = 1).

Wir führen die Jordan-Transformation mit dem Element X13 = 2 durch, wir erhalten die zweite Stützlösung X2 = (0,0,3,21,42,0) mit der Basis B2 = (A3, A4, A5). (Tabelle 26.2)

Diese Lösung ist nicht optimal, da der Vektor A2 eine negative Schätzung Δ2 = - 6 hat. Um die Lösung zu verbessern, ist es notwendig, den Vektor A2 in die Basis der Stützlösung einzuführen.

Bestimmen Sie die Nummer des von der Basis abgeleiteten Vektors. Berechnen Sie dazu den Parameter θ 02 für die zweite Spalte, er ist gleich 7 für l = 2. Daher leiten wir aus der Basis den zweiten Basisvektor A4 ab. Führen wir die Jordan-Transformation mit dem Element x 22 = 3 durch, erhalten wir die dritte Stützlösung X3 = (0.7,10,0.63.0) B2 = (A3, A2, A5) (Tabelle 26.3).

Diese Lösung ist die einzig optimale, da für alle Vektoren, die nicht in der Schätzungsbasis enthalten sind, positiv

1 = 7/2, 4 = 2, Δ 6 = 7/2.

Antworten: max Z (X) = 201 bei X = (0.7,10,0.63).

Lineare Programmiermethode in der Wirtschaftsanalyse

Lineare Programmiermethode ermöglicht es, die optimale wirtschaftliche Lösung unter Bedingungen strenger Einschränkungen in Bezug auf die in der Produktion verwendeten Ressourcen (Sachanlagen, Materialien, Arbeitsressourcen) zu begründen. Die Verwendung dieser Methode in der Wirtschaftsanalyse ermöglicht es Ihnen, Probleme zu lösen, die hauptsächlich mit der Planung der Aktivitäten der Organisation zusammenhängen. Diese Methode hilft, die optimalen Werte der Produktionsleistung sowie die Richtungen der meisten zu bestimmen effektiver Einsatz der Organisation der Produktionsmittel zur Verfügung stehen.

Mit Hilfe dieser Methode wird die Lösung der sogenannten Extremprobleme durchgeführt, die darin besteht, die Extremwerte, dh die maximalen und minimalen Funktionen variabler Größen, zu finden.

Dieser Zeitraum basiert auf der Lösung des Systems lineare Gleichungen in Fällen, in denen die analysierten Wirtschaftsphänomene durch lineare, streng funktionale Abhängigkeiten verbunden sind. Die Methode der linearen Programmierung wird verwendet, um Variablen beim Vorhandensein bestimmter einschränkender Faktoren zu analysieren.

Die Lösung des sogenannten Transportproblems mit der Methode der linearen Programmierung ist weit verbreitet. Inhalt dieser Aufgabe ist es, die Kosten im Zusammenhang mit dem Betrieb von Fahrzeugen unter den Bedingungen der bestehenden Beschränkungen der Anzahl der Fahrzeuge, ihrer Tragfähigkeit, der Dauer ihres Betriebs zu minimieren, wenn ein maximaler Wartungsbedarf besteht Anzahl der Kunden.

Neben, diese Methode findet breite Anwendung bei der Lösung des Scheduling-Problems. Diese Aufgabe besteht in einer solchen Verteilung der Arbeitszeit des Personals einer bestimmten Organisation, die sowohl für die Mitglieder dieses Personals als auch für die Kunden der Organisation am annehmbarsten wäre.

Diese Aufgabe besteht darin, die Zahl der Kunden zu maximieren, die angesichts der Beschränkungen der Zahl der verfügbaren Mitarbeiter sowie des Arbeitszeitbudgets bedient werden.

Daher ist die lineare Programmierungsmethode bei der Analyse von Platzierung und Verwendung weit verbreitet. verschiedene Typen Ressourcen sowie bei der Planung und Prognose der Aktivitäten von Organisationen.

Dennoch kann die mathematische Programmierung auf solche ökonomischen Phänomene angewendet werden, deren Beziehung nicht linear ist. Dazu können nichtlineare, dynamische und konvexe Programmiermethoden verwendet werden.

Die nichtlineare Programmierung beruht auf der nichtlinearen Natur der Zielfunktion oder der Nebenbedingungen oder auf beidem. Die Formen der Zielfunktion und Ungleichungen von Nebenbedingungen können unter diesen Bedingungen unterschiedlich sein.

Die nichtlineare Programmierung wird in der Wirtschaftsanalyse verwendet, insbesondere wenn die Beziehung zwischen Indikatoren, die die Wirksamkeit der Aktivitäten einer Organisation ausdrücken, und dem Umfang dieser Aktivitäten, der Struktur der Produktionskosten, der Marktbedingungen usw.

Die dynamische Programmierung basiert auf der Konstruktion eines Entscheidungsbaums. Jede Stufe dieses Baums dient als Stufe, um die Konsequenzen der vorherigen Entscheidung zu bestimmen und ineffektive Optionen für diese Entscheidung zu eliminieren. Somit hat die dynamische Programmierung eine mehrstufige, mehrstufige Natur. Diese Art der Programmierung wird in der Wirtschaftsanalyse verwendet, um die besten Optionen für die Entwicklung einer Organisation jetzt und in Zukunft zu finden.

Die konvexe Programmierung ist eine Form der nichtlinearen Programmierung. Diese Art der Programmierung drückt die nichtlineare Natur der Beziehung zwischen den Ergebnissen der Aktivitäten einer Organisation und den dadurch verursachten Kosten aus. Die konvexe (auch konkave) Programmierung analysiert konvexe Zielfunktionen und konvexe Zwangssysteme (Punkte akzeptable Werte). Die konvexe Programmierung wird bei der Analyse der Wirtschaftstätigkeit verwendet, um die Kosten zu minimieren, und die konkave Programmierung wird verwendet, um das Einkommen unter den Bedingungen bestehender Beschränkungen der Wirkung von Faktoren zu maximieren, die die analysierten Indikatoren in entgegengesetzter Weise beeinflussen. Folglich werden bei den betrachteten Programmierarten konvexe Zielfunktionen minimiert und konkave maximiert.

Wenn Sie ein lineares Programmierproblem mit Simplex-Tabellen lösen müssen, dann ist unser Onlineservice wird dir eine große Hilfe sein. Die Simplex-Methode impliziert eine sequentielle Aufzählung aller Scheitelpunkte des zulässigen Wertebereichs, 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. Bei einer Änderung in der führenden Zeile wird diejenige 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
Basisvariablen	Kostenlose Mitglieder in Einschränkungen	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

Schritt drei. 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. Mit der minimalen Beziehung können Sie die führende Zeile definieren. Wir berechnen die Tabelle erneut mit den Formeln, d.h. gehe zu Schritt 3.

Simplex-Methode ist ein iterativer Prozess der gerichteten Lösung eines Gleichungssystems Schritt für Schritt, der mit einer Referenzlösung beginnt und auf der Suche nach bessere Option bewegt sich entlang der Eckpunkte des zulässigen Lösungsbereichs, die den Wert der Zielfunktion verbessern, bis die Zielfunktion den optimalen Wert erreicht.

Servicezweck... Der Dienst richtet sich an Online-Lösungen lineare Programmierprobleme (LPP) nach der Simplex-Methode in den folgenden Notationsformen:

in Form einer Simplex-Tabelle (Methode der Jordan-Transformationen); Grundform der Aufzeichnung;
modifizierte Simplex-Methode; in Säulenform; in Linienform.

Anweisung. Wählen Sie die Anzahl der Variablen und die Anzahl der Zeilen (Anzahl der Einschränkungen). Die resultierende Lösung wird gespeichert in Word-Datei und Excel.

Berücksichtigen Sie in diesem Fall keine Beschränkungen vom Typ x i ≥ 0. Wenn es in der Aufgabe für einige x i keine Einschränkungen gibt, muss das LPP zum CLP gebracht werden oder diesen Dienst nutzen. Die Lösung erkennt automatisch die Verwendung von M-Methode(Simplex-Methode auf künstlicher Basis) und zweistufige Simplex-Methode.

Folgendes wird auch mit diesem Rechner verwendet:
Grafische Methode zur Lösung von LPP
Transportproblemlösung
Matrixspiellösung
Nutzung des Dienstes in Onlinemodus Sie können den Preis des Matrixspiels (untere und obere Grenze) bestimmen, die Verfügbarkeit prüfen Sattelpunkt, eine Lösung der gemischten Strategie mit den folgenden Methoden finden: Minimax, Simplex-Methode, grafische (geometrische) Methode, Brown-Methode.
Extremum einer Funktion zweier Variablen
Dynamische Programmierprobleme
Verteilen Sie 5 homogene Warenpartien auf drei Märkte, um das maximale Einkommen aus ihrem Verkauf zu erzielen. Die Einnahmen aus Verkäufen in jedem Markt G (X) hängen von der Anzahl der verkauften Warenpartien X ab und werden in der Tabelle dargestellt.

Warenmenge X (in Losen)	Einkommen G (X)
Warenmenge X (in Losen)	1	2	3
0	0	0	0
1	28	30	32
2	41	42	45
3	50	55	48
4	62	64	60
5	76	76	72

Algorithmus der Simplex-Methode beinhaltet folgende Schritte:

Erstellung des ersten Basisplans. Übergang zur kanonischen Form des linearen Programmierungsproblems durch Einführung nicht-negativer zusätzlicher Bilanzvariablen.
Den Plan auf Optimalität prüfen... Wenn mindestens ein Koeffizient der Indexzeile kleiner als Null ist, ist der Plan nicht optimal und muss verbessert werden.
Spalten- und Zeilenanfang definieren... Von den negativen Koeffizienten der Indexzeile wird der absolut größte Wert ausgewählt. Dann werden die Elemente der Spalte der freien Elemente der Simplextabelle in Elemente mit dem gleichen Vorzeichen der führenden Spalte unterteilt.
Erstellen eines neuen Referenzplans... Der Übergang zu einem neuen Plan erfolgt durch Neuberechnung der Simplex-Tabelle nach dem Jordan-Gauss-Verfahren.

Wenn es notwendig ist, das Extremum der Zielfunktion zu finden, dann sprechen wir davon, den Minimalwert (F (x) → min, siehe das Beispiel zum Lösen der Funktionsminimierung) und den Maximalwert ((F (x) → max, siehe Beispiel zum Lösen der Funktionsmaximierung)

Die extreme Lösung wird an der Grenze des Bereichs zulässiger Lösungen an einem der Eckpunkte der Eckpunkte des Polygons oder an dem Segment zwischen zwei benachbarten Eckpunkten erreicht.

Grundsatz der linearen Programmierung... Erreicht die Zielfunktion des LPP an einem Punkt im Bereich zulässiger Lösungen einen Extremwert, dann nimmt sie diesen Wert am Eckpunkt an. Wenn die Zielfunktion des LPP an mehr als einem Eckpunkt ihren Extremwert erreicht, nimmt sie an jeder der konvexen Linearkombinationen dieser Punkte denselben Wert an.

Die Essenz der Simplex-Methode... Die Bewegung zum optimalen Punkt erfolgt durch Bewegung von einem Eckpunkt zum benachbarten, der näher und schneller an X opt liegt. Ein solches Schema zum Aufzählen von Punkten, als Simplex-Methode bezeichnet, vorgeschlagen von R. Danzig.
Die Eckpunkte sind durch m Basisvariablen gekennzeichnet, daher kann der Übergang von einem Eckpunkt zum benachbarten erfolgen, indem in der Basis nur eine Basisvariable in eine Variable aus der Nichtbasis geändert wird.
Die Implementierung des Simplex-Verfahrens weist aufgrund verschiedener Merkmale und Formulierungen von LP-Problemen verschiedene Modifikationen auf.

Die Konstruktion von Simplex-Tabellen wird fortgesetzt, bis eine optimale Lösung erreicht ist. Wie verwendet man eine Simplex-Tabelle, um zu bestimmen, ob die Lösung eines linearen Programmierproblems optimal ist?
Wenn die letzte Zeile (Werte der Zielfunktion) keine negativen Elemente enthält, wird der optimale Plan gefunden.

Bemerkung 1. Wenn eine der Basisvariablen gleich Null ist, dann ist der Extrempunkt, der einer solchen Basislösung entspricht, entartet. Entartung tritt auf, wenn die Wahl einer Linienführung nicht eindeutig ist. Möglicherweise bemerken Sie die Entartung des Problems überhaupt nicht, wenn Sie eine andere Linie als Richtlinie wählen. Wählen Sie bei Mehrdeutigkeiten die Zeile mit dem niedrigsten Index aus, um Schleifen zu vermeiden.

Bemerkung 2. Angenommen, alle Simplex-Differenzen sind an irgendeinem Extrempunkt nicht negativ D k ³ 0 (k = 1..n + m), d. h.. eine optimale Lösung erhalten wird und es einen А k - Nichtbasisvektor gibt, für den D k = 0 ist. Dann wird das Maximum an mindestens zwei Punkten erreicht, d.h. es gibt ein alternatives Optimum. Wenn wir diese Variable x k in die Basis einführen, ändert sich der Wert der Zielfunktion nicht.

Bemerkung 3. Die Lösung des dualen Problems findet sich in der letzten Simplextabelle. Die letzten m Komponenten des Vektors der Simplexdifferenzen (in den Spalten der Bilanzvariablen) sind die optimale Lösung des dualen Problems. Bedeutung Zielfunktionen das direkte und das duale Problem fallen an den optimalen Punkten zusammen.

Bemerkung 4. Bei der Lösung des Minimierungsproblems wird ein Vektor mit der größten positiven Simplexdifferenz in die Basis eingeführt. Weiterhin wird derselbe Algorithmus wie für das Maximierungsproblem angewendet.

Wenn die Bedingung „Es ist notwendig, dass der Rohstoff des Typs III vollständig verbraucht wurde“, dann ist die entsprechende Bedingung Gleichheit.

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

Hemd 1

Hemd 2

Hemd 3

Aktien

Faden (m)

Knöpfe (Stk.)

640

die Kleidung (

Gewinn (S.)

Die Lösung des Problems

Modell bauen

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

Dann sind die Ressourcenlimits wie folgt:

Außerdem im Sinne des Problems

Zielfunktion, die den erzielten Gewinn ausdrückt:

Wir erhalten das folgende lineare Programmierproblem:

Reduzieren eines linearen Programmierproblems auf die kanonische Form

Bringen wir das Problem in eine 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 auf der linken Seite der Beschränkungen zusätzliche Variablen hinzu, die keine bevorzugte Form haben, und wir erhalten Gleichheiten.

Lösung des Problems mit der Simplex-Methode

Wir füllen die Simplex-Tabelle aus:

Da wir das Maximumproblem lösen, zeigt das Vorhandensein negativer Zahlen in der Indexzeile beim Lösen des Maximumproblems an, dass wir nicht die optimale Lösung erhalten haben und dass es notwendig ist, von der Tabelle der 0. Iteration zur nächsten zu gehen.

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

führende Spaltenübereinstimmungen

Die Schlüsselzeile wird durch das Mindestverhältnis von freien Stäben und Stäben der führenden Spalte bestimmt (Simplex-Beziehungen):

Am Schnittpunkt der Schlüsselspalte und der Schlüsselzeile finden wir das auflösende Element, d.h. neun.

Nun beginnen wir mit der Erstellung der 1. Iteration: Anstelle eines Einheitsvektors geben wir einen Vektor ein.

V neuer Tisch anstelle des auflösenden Elements schreiben wir 1, alle anderen Elemente der Schlüsselspalte sind null. Schlüsselzeilenelemente werden in zulassende Elemente unterteilt. Alle anderen Elemente der Tabelle werden nach der Rechteckregel berechnet.

Schlüsselspalte für Übereinstimmungen der ersten Iteration

Zulässige Elemente sind die Zahl 4/3. Der Vektor wird aus der Basis abgeleitet und stattdessen der Vektor eingeführt. Wir erhalten die Tabelle der 2. Iteration.

Schlüsselspalte für Übereinstimmungen der 2. Iteration

Wir finden den Schlüsselstring, dafür definieren wir:

Das auflösende Element ist die Zahl 10/3. Der Vektor wird aus der Basis abgeleitet und stattdessen der Vektor eingeführt. Wir erhalten die Tabelle der 3. Iteration.

№

c b

Ein o

x 1

x 2

x 3

x 4

x 5

x 6

Simplex

Beziehung

x 4

32/3

x 5

640

x 6

Fj - cj

-2

-5

-4

x 2

32/3

1/9

1/3

1/9

x 5

1600/3

170/9

80/3

-10/9

x 6

68/3

7/9

4/3

-2/9

Fj - cj

160/3

-13/9

-7/3

5/9

x 2

-1/12

1/6

-1/4

x 5

10/3

-20

x 3

7/12

-1/6

3/4

204/7

Fj - cj

-1/12

1/6

7/4

x 2

1/4

1/40

-3/4

x 1

3/10

-6

x 3

-3/4

-7/40

17/4

Fj - cj

1/4

1/40

5/4

Alle Terme in der Indexzeile sind nichtnegativ, sodass die folgende Lösung des linearen Programmierproblems erhalten wird (wir schreiben sie aus der Spalte der freien Terme heraus):

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

Sie können Hilfe bei der Lösung Ihrer Probleme zu diesem Thema finden, indem Sie eine Nachricht auf VKontakte, auf Viber senden oder das Formular ausfüllen. Die Kosten für das Lösen von Hausaufgaben beginnen bei 7 BYN. pro Aufgabe (200 Rubel), jedoch nicht weniger als 10 belarussische Rubel. (RUB 300) für die gesamte Bestellung. Detailliertes Design. Die Kosten für die Online-Prüfungsunterstützung (in diesem Fall ist eine Vorauszahlung von 100% erforderlich) - ab 30 BYN. (1000 russische Rubel) für die Lösung des Tickets.

Siegel

Auch interessant:

So finden Sie Facebook-Gruppen

Möglichkeiten zur Optimierung kontextbezogener Werbung für CPA

Wer ist ein Verkehrsmanager

Wir empfehlen zu lesen:

2021-11-21 08:45:22

Berichte exportieren und per E-Mail senden Durchschnittliche Prüfung und URL-Konvertierung von Google Analytics herunterladen

2021-11-21 08:45:22

Statische und dynamische HTML-Seiten im Detail

2021-11-21 08:45:22

Vier Retargeting-Taktiken für Yandex-Weihnachtskampagnen

Fortsetzung des Themas:

Sonstig

Entwicklung sozialer Netzwerke

Soziale Netzwerke im Internet sind heute spezialisierte Sites, die Menschen auf einer bestimmten Basis in einem Netzwerk zusammenbringen. In ihrem Wachstum...