Simplex-Methode-Zielfunktion. Lineares Programmieren. Simplex-Methode

Diese Methode ist ein Verfahren zur gezielten Wechselwirkung von Referenzlösungen eines linearen Programmierproblems. Es ermöglicht eine endliche Anzahl von Schritten oder finden Sie die optimale Lösung, oder um festzustellen, dass es keine optimale Lösung gibt.

Der Hauptinhalt der Simplex-Methode lautet wie folgt:

1. Geben Sie die Methode zur Festsetzung der optimalen Referenzlösung an.
2. Geben Sie das Verfahren des Übergangs von einer Referenzlösung an einen anderen an, auf der der Wert der Zielfunktion näher an der optimalen, d. H. Geben Sie einen Weg an, um die Referenzlösung zu verbessern.
3. Stellen Sie Kriterien fest, die es ermöglichen, die rohe Kraft der Referenzlösungen auf einer optimalen Lösung zu stoppen oder der Schlussfolgerung um das Fehlen einer optimalen Lösung zu folgen.

Algorithmus der Simplex-Methode Lösung von linearen Programmieraufgaben

Um die Aufgabe zu lösen simplex-Methode Sie müssen Folgendes tun:

1. Bringen Sie die Aufgabe an kanonisch
2. Finden Sie die anfängliche Referenzlösung mit einer "einzelnen Basis" (wenn keine Referenzlösung vorliegt, löst die Aufgabe aufgrund der Inkompatibilität des Restriktionssystems nicht ab.)
3. Berechnen Sie Schätzungen der Erweiterungen von Vektoren auf der Grundlage der Referenzlösung und füllen Sie die Tabelle der Simplex-Methode aus
4. Wenn ein Zeichen der Einzigartigkeit der optimalen Lösung durchgeführt wird, endet die Task-Lösung
5. Wenn die Bedingung für das Vorhandensein eines Satzes von optimalen Lösungen durchgeführt wird, werden alle optimalen Lösungen einfach gefunden

Ein Beispiel, um das Problem mit der Simplex-Methode zu lösen

Beispiel 26.1.

Lösen Sie die Simplex-Methode der Aufgabe:

Entscheidung:

Wir geben eine Aufgabe der kanonischen Form an.

Dazu führen wir im linken Teil der ersten Grenze der Ungleichheit eine zusätzliche Variable X 6 mit einem +1-Koeffizienten ein. In der Zielfunktion tritt die Variable X 6 in den Nullkoeffizienten ein (d. H. NICHT INBEGRIFFEN).

Wir bekommen:

Wir finden die anfängliche Referenzlösung. Hierfür gleichen (ungelöste) Variablen gleich Null X1 \u003d x2 \u003d x3 \u003d 0.

Erhalten referenzlösung X1 \u003d (0,0,024,30,6) mit einer einzigen Basis B1 \u003d (A4, A5, A6).

Berechnung abschätzung der Expansionsvektoren. Die Bedingungen auf der Grundlage der Referenzlösung durch die Formel:

Δ k \u003d c b x k - c k

• C b \u003d (c 1, c 2, ..., c m) - Vektor von Zielfunktionskoeffizienten mit Grundvariablen
• X k \u003d (x 1k, x 2k, ..., x mk) - Vektorzerlegung des entsprechenden Vektors A bis zur Grundlage der Referenzlösung
• C k - der Zielfunktionskoeffizient mit einer Variablen x bis.

Die Schätzungen der Vektoren des in der Basis enthaltenen Vektoren sind immer gleich Null. Die Referenzlösung, die Ausdehnungskoeffizienten und Auswertung der Erweiterungen der Vektoren der Referenzlösungen der Referenzlösung sind in geschrieben simplex-Tisch:

Oberteil über dem Tisch zur Bequemlichkeit von Auswertungsberechnungen werden die Zielfunktionskoeffizienten aufgezeichnet. Die erste Spalte "B" zeichnet Vektoren auf, die in Bezug auf die Basis enthalten sind. Die Reihenfolge der Aufzeichnung dieser Vektoren entspricht der Anzahl der zulässigen Nummern, die in den Ungleichungen von Beschränkungen unbekannt sind. In der zweiten Spalte der Tabelle "c b" werden die Zielfunktionskoeffizienten in derselben Reihenfolge mit Grundvariablen aufgezeichnet. Mit dem richtigen Ort der Zielfunktionskoeffizienten in der Spalte "C b" der Beurteilung der in der Basis enthaltenen einzelnen Vektoren in der Basis gleich Null.

In der letzten Reihe des Tisches mit Schätzungen Δ k in der Spalte "A 0" werden die Werte der Zielfunktion auf der Referenzlösung Z (x 1) aufgezeichnet.

Die anfängliche Referenzlösung ist nicht optimal, da in der Task an der maximalen Schätzung δ 1 \u003d -2 Δ 3 \u003d -9 für Vektoren A 1 und 3 negativ ist.

Durch den Satz beim Verbessern der Referenzlösung, wenn in einer maximalen Aufgabe mindestens ein Vektor eine negative Schätzung aufweist, können Sie eine neue Referenzlösung finden, auf der der Wert der Zielfunktion größer ist.

Wir definieren die Einführung, deren der beiden Vektoren zu größeren Schritten der Zielfunktion führen wird.

Das Inkrement der Zielfunktion erfolgt durch die Formel :.

Berechnen Sie die Werte des Parameters θ 01 für die erste und dritte Spalte durch die Formel:

Wir erhalten θ 01 \u003d 6 bei l \u003d 1, θ 03 \u003d 3 bei l \u003d 1 (Tabelle 26.1).

Wir finden das Inkrement der Zielfunktion, wenn sie in die Basis des ersten Vektors ΔZ 1 \u003d-6 * (- 2) \u003d 12 eingeführt werden, und der dritte Vektor ΔZ 3 \u003d - 3 * (- 9) \u003d 27.

Folglich ist es für eine schnellere Annäherung an die optimale Lösung erforderlich, anstelle des ersten Vektors der Basis A6 einen Vektor A3 in der Basislösungsgrundlage einzuführen, da das Minimum des Parameters θ 03 in der ersten Zeile erreicht ist (l \u003d 1).

Wir produzieren die Transformation von Jordanien mit dem X13 \u003d 2-Element, wir erhalten die zweite Referenzlösung X2 \u003d (0,0,3, 21.42.0) mit der Basis B2 \u003d (A3, A4, A5). (Tabelle 26.2)

Diese Lösung ist nicht optimal, da der Vektor A2 eine negative Schätzung Δ2 \u003d - 6. Um die Lösung zu verbessern, müssen Sie den Vektor A2 in Bezug auf Referenzlösung eingeben.

Wir definieren die Anzahl der Vektorausgabe von der Basis. Berechnen Sie dazu den Parameter θ 02 für die zweite Säule, er ist 7 bei L \u003d 2. Folglich leiten wir aus der Basis den zweiten Vektor der Basis von A4 von der Basis ab. Wir produzieren die Transformation von Jordanien mit dem X 22 \u003d 3-Element, wir erhalten die dritte Referenzlösung X3 \u003d (0,7,10,0,63,0) B2 \u003d (A3, A2, A5) (Tabelle 26.3).

Diese Lösung ist die einzige optimale, da für alle Vektoren, die nicht in der Beurteilung des positiven enthalten sind

Δ 1 \u003d 7/2, δ 4 \u003d 2, δ 6 \u003d 7/2.

Antworten: Max Z (x) \u003d 201 bei x \u003d (0,7,10,0,63).

Lineare Programmiermethode in der wirtschaftlichen Analyse

Lineare Programmiermethode. Es ermöglicht es, die optimalste wirtschaftliche Entscheidung angesichts schwerwiegender Beschränkungen in Bezug auf Ressourcen in der Produktion (Anlagevermögen, Materialien, Arbeitsressourcen) zu begründen. Die Verwendung dieser Methode in der wirtschaftlichen Analyse ermöglicht es uns, Probleme zu lösen, die sich hauptsächlich auf die Planung der Aktivitäten der Organisation beziehen. Diese Methode hilft, die optimalen Ausgabewerte sowie die Richtungen der meisten zu bestimmen effektive Nutzung. Die Organisation von Produktionsressourcen verfügbar.

Mit dieser Methode lösen sich die sogenannten extremen Aufgaben, dh extremen Werten, dh das Maximum und das Minimum der Funktionen von Variablen.

Diese Zeit basiert auf der Systemlösungen lineare Gleichungen In Fällen, in denen die analysierten wirtschaftlichen Phänomene miteinander verbunden sind, ist strikt funktionale Abhängigkeit. Das lineare Programmierverfahren wird verwendet, um Variablen in Gegenwart bestimmter Grenzfaktoren zu analysieren.

Die Lösung der sogenannten Transportaufgabe mit der linearen Programmiermethode ist sehr üblich. Der Inhalt dieser Aufgabe besteht darin, die Kosten zu minimieren, die im Zusammenhang mit dem Betrieb von Fahrzeugen unter den Bedingungen bestehender Beschränkungen auf die Anzahl der Fahrzeuge, deren Tragfähigkeit, der Dauer ihrer Arbeit durchgeführt werden, minimiert werden, wenn das Maximum erforderlich ist Anzahl der Kunden.

Neben, diese Methode Es wird weit verbreitet, wenn Sie die Aufgabe, einen Zeitplan zu zeichnen, weit verbreitet. Diese Aufgabe besteht darin, sicherzustellen, dass die Funktionszeit des Personals dieser Organisation, die für beide Mitglieder dieses Personals und für die Kunden der Organisation am akzeptabelsten ist.

Diese Herausforderung besteht darin, die Anzahl der Kunden zu maximieren, die im Rahmen von Einschränkungen auf die Anzahl der verfügbaren Personalmitglieder sowie der Arbeitszeitfonds bedient werden.

Somit ist das lineare Programmierverfahren sehr häufig in der Analyse der Analyse und Verwendung verschiedene Arten Ressourcen sowie in der Planungs- und Prognoseprozess von Organisationen.

Trotzdem kann die mathematische Programmierung in Bezug auf diese wirtschaftlichen Phänomene angewendet werden, die Beziehung zwischen dem nicht linear ist. Zu diesem Zweck können Methoden der nichtlinearen, dynamischen und konvexen Programmierung verwendet werden.

Die nichtlineare Programmierung basiert auf der nichtlinearen Natur der Zielfunktion oder der Einschränkungen oder beides. Formen der Zielfunktion und Ungleichheiten von Einschränkungen unter diesen Bedingungen können unterschiedlich sein.

Die nichtlineare Programmierung wird insbesondere in der wirtschaftlichen Analyse angewendet, wenn sie die Beziehung zwischen den Indikatoren, die die Wirksamkeit der Organisation und das Volumen dieser Tätigkeit, die Struktur der Produktion, den Marktbedingungen und anderen ausdrücken, eingesetzt werden.

Die dynamische Programmierung basiert auf dem Bau von Holzlösungen. Jede Tiere dieses Baumes dient als Bühne, um die Folgen der vorherigen Lösung zu bestimmen und die ineffizienten Optionen für diese Lösung zu beseitigen. Auf diese Weise, dynamische Programmierung. Es hat ein mehrstufiges, mehrstufiges Zeichen. Diese Art der Programmierung wird in der wirtschaftlichen Analyse angewendet, um optimale Optionen für die Entwicklung der Organisation zu finden, sowohl derzeit als auch in der Zukunft.

Konvexe Programmierung ist eine Art nichtlinearer Programmierung. Diese Art der Programmierung drückt einen nichtlinearen Charakter der Abhängigkeit zwischen den Ergebnissen der durchgeführten Aktivitäten der Organisation und den Kosten aus. Konvexe (sonst konkave) Programmierung analysiert konvexe Zielfunktionen und konvexe Restriktionssysteme (Punkte zulässige Werte). Die konvexe Programmierung wird in der Analyse der wirtschaftlichen Tätigkeiten angewendet, um die Kosten zu minimieren und konkav zu minimieren, um den Umsatz unter den Bedingungen bestehender Einschränkungen der Aktion von Faktoren zu maximieren, die auf die analysierten Indikatoren auf die entgegengesetzte Weise beeinflussen. Folglich werden konvexe Zielfunktionen unter den Typen der Programmierarten minimiert und konkav - werden maximiert.

Kurze Theorie

Um lineare Programmieraufgaben zu lösen, gibt es viele verschiedene Methoden. Das effizienteste und universellste unter ihnen war jedoch die Simplex-Methode. Es sei darauf hingewiesen, dass bei der Lösung einiger Aufgaben andere Methoden effizienter sein können. Zum Beispiel, wenn der ZLP mit zwei Variablen optimal ist, und bei der Lösung des potenziellen Verfahrens. Die Simplex-Methode ist der Haupt- und anwendbar für jeden SAP in kanonischer Form.

In Verbindung mit dem Haupt-Linear-Programmier-Satz tritt natürlich die Idee des nächsten Weges auf entscheidung ZLP. Mit einer beliebigen Anzahl von Variablen. Um alle extremen Punkte der Polyederpläne (ihr nicht mehr als) zu finden, und vergleichen Sie die Werte der Zielfunktion in ihnen. Eine solche Art der Lösung, selbst mit einer relativ geringen Anzahl von Variablen und Einschränkungen, praktisch unmöglich, da der Prozess des Findens von Extrempunkten durch Schwierigkeiten mit der Lösung der anfänglichen Aufgabe vergleichbar ist, können außerdem die Anzahl der extremen Punkte der Polyederpläne sein sehr groß. In Verbindung mit diesen Schwierigkeiten entstand die Aufgabe der rationalen Integration von extremen Punkten.

Die Essenz der Simplex-Methode ist wie folgt. Wenn ein extremer Punkt bekannt ist und der Wert darin eine Zielfunktion ist, dann ist nicht unbedingt notwendig, in denen die Zielfunktion den schlechtesten Wert nimmt, nicht unbedingt erforderlich. Daher natürlich der Wunsch, einen Weg zum Übergang von diesem extremen Punkt auf die am besten angrenzende am Rande zu finden, von ihm bis zu einem besseren (nicht schlechter) usw., um dies zu tun, es ist notwendig, ein Zeichen dafür zu haben, dass das Die besten extremen Punkte als dieser extreme Punkt ist überhaupt nicht. Dies ist die allgemeine Idee der am häufigsten verwendeten Einfachheitmethode (Methode des konsistenten Verbesserungsplans), um die ZLL zu lösen. Also, in algebraischen Begriffen deuten die Simplex-Methode darauf hin:

1. die Fähigkeit, den ursprünglichen Referenzplan zu finden;
2. das Vorhandensein eines Anzeichens der Optimalität des Referenzplans;
3. die Fähigkeit, sich auf einen Nicht-Referenzplan zu bewegen.

Ein Beispiel, um das Problem zu lösen

Die Aufgabe

Für die Umsetzung von drei Warengruppen verfügt ein kommerzielles Unternehmen über drei Arten von begrenzten Materialien und Barressourcen in Menge, Anteile. Zur gleichen Zeit, zum Verkauf von 1 Gütergruppe pro tausend Rubel. Der Umsatz wird von der Ressource der ersten Spezies in der Anzahl der Einheiten, der Ressource des zweiten Typs in der Anzahl der Einheiten, der dritten Spezies-Ressource in der Anzahl der Einheiten verbraucht. Zu verkaufen 2 und 3 Warengruppen pro tausend Rubel. Der Umsatz wird entsprechend der Ressource der ersten Spezies in der Menge, Einheiten, den Ressourcen des zweiten Typs in der Menge, Einheiten, Drittressourcen des dritten Typs in der Menge, Einheiten, verbraucht. Profitieren Sie vom Verkauf von drei Warengruppen pro tausend Rubel. Ware ist bzw. Tausend Rubel.

• Bestimmen Sie das geplante Volumen und die Struktur des Umsatzes, so dass der Gewinn des Handelsunternehmens maximal ist.
• Die direkte Aufgabe der Planung des Umsatzes, der durch die Simplex-Methode gelöst wurde, ist eine doppelte Aufgabe der linearen Programmierung.
• Installieren Sie die konjugierten Paare variabler direkter und doppelter Aufgaben.
• Entsprechend den konjugierten Variablenpaaren aus der Lösung der direkten Aufgabe, um eine Entscheidung zu erhalten doppelaufgabewas Ressourcen erzeugt, die für den Verkauf von Waren ausgegeben werden.

Wenn Ihre Zulassung zur Sitzung von der Lösung der Aufgabeneinheit abhängt, und Sie haben keine Zeit noch der Wunsch, für die Berechnungen zu sitzen - verwenden Sie die Site-Site. Aufgabenordnung ist eine Frage von Minuten. Details (So hinterlassen Sie einen Antrag, Preise, Fristen, Zahlungsmethoden) können auf der Seite gelesen werden, um Lösungen für Aufgaben für lineare Programmierungen zu kaufen ...

Die Lösung des Problems

Baumodell

Durch den Umsatz der ersten, 2. und dritten Art von Waren.

Dann drückt die Zielfunktion den resultierenden Gewinn aus:

Einschränkungen für materielle und monetäre Ressourcen:

Außerdem im Sinne des Problems

Wir erhalten die folgende lineare Programmieraufgabe:

Zum kanonischen Typ ZLP bringen

Wir geben der Aufgabe der kanonischen Form an. Um Ungleichheiten in Gleichstellung umzuwandeln, führen wir zusätzliche Variablen ein. Variablen sind in Einschränkungen mit dem Koeffizienten 1. In der Zielfunktion sind alle zusätzlichen Variableneinsatz mit einem Koeffizienten mit einem Koeffizienten gleich Null.

Die Einschränkung hat eine bevorzugte Form, wenn der linke Teil mit Nicht-Negativität des rechten Teils eine Variable aufweist, die mit dem Koeffizienten eingeschlossen ist, und die verbleibenden Gleichheitsbeschränkungen - mit einem Koeffizienten gleich Null gleich. In unserem Fall haben die 1., 2., die dritten Einschränkungen eine bevorzugte Form mit den entsprechenden Basisgrößen.

Lösung Symptom.

Füllen Sie den Simplex-Tisch der 0-jährigen Iteration aus.

BP.

Simplex beziehungen

8

6

4

0

0

0

0

520

16

18

9

1

0

0

65/2

0

140

7

7

2

0

1

0

20

0

810

9

2

1

0

0

1

90

0

-8

-6

-4

0

0

0

Da wir die Aufgabe desto maximal lösen - die Anwesenheit in der Indexzeile der negativen Nummern, wenn das Problem mit einem Maximum der Lösung angibt, weist wir an, dass wir die optimale Lösung nicht erhalten haben, und dass Sie aus dem Tisch der 0. -er Iteration zum nächsten gehen müssen .

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

Die Presenter-Spalte entspricht.

Die Schlüsselzeile wird auf mindestens den Verhältnissen von freien Elementen und Elementen der Bleisäule (Simplex-Beziehungen) bestimmt:

An der Kreuzung der Schlüsselspalte und der Schlüsselzeile finden wir das zulässige Element, d. H. 7.

Fahren Sie nun zur Herstellung der ersten Iteration fort. Anstelle eines einzelnen Vektors betreten wir den Vektor.

In der neuen Tabelle auf der Website des Auflösungselements schreiben wir 1, alle anderen Elemente der Schlüsselsäule -n. Die Schlüsselzeilenelemente sind in ein Auflösungselement unterteilt. Alle anderen Elemente des Tisches werden entsprechend der Regel des Rechtecks \u200b\u200bberechnet.

Wir erhalten einen Tisch der 1. Iteration:

BP.

Simplex Beziehungen

8

6

4

0

0

0

0

200

0

2

31/7

1

-16/7

0

1400/31

8

20

1

1

2/7

0

1/7

0

70

0

630

0

-7

-11/7

0

-9/7

1

-

160

0

2

-12/7

0

8/7

0

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

Wir finden eine Schlüsselzeichenfolge, denn das bestimmt wir:

An der Kreuzung der Tastenspalte und der Schlüsselzeile finden wir den Zulassungsgegenstand, d. H. 31/7.

Der Vektor wird von der Basis angezeigt und betreten den Vektor.

Wir erhalten eine Tabelle der 2. Iteration:

BP.

Simplex beziehungen

8

6

4

0

0

0

4

1400/31

0

14/31

1

7/31

-16/31

0

8

220/31

1

27/31

0

-2/31

9/31

0

0

21730/31

0

-195/31

0

11/31

-65/31

1

7360/31

0

86/31

0

12/31

8/31

0

In der Indexzeile sind alle Mitglieder nicht negativ, so dass die folgende Lösung des linearen Programmierproblems erhalten wird (wir schreibt aus der Freiliedsäule):

So ist es notwendig, 7,1 tausend Rubel zu verkaufen. Produkte des 1. Typs und 45,2 Tausend Rubel Waren der dritten Ansicht. Das Produkt der 2. Art des Verkaufs ist unrentabel. Gleichzeitig ist der Gewinn maximal und wird 237,4 Tausend Rubel sein. Bei der Umsetzung des optimalen Plans beträgt der Rückstand der dritten Ansicht 701 Einheiten.

Dual Task LP.

Wir schreiben das Modell der doppelten Aufgabe.

Um eine duale Aufgabe zu erstellen, müssen Sie die folgenden Regeln verwenden:

1) Wenn die direkte Aufgabe maximal gelöst wird, dann doppelt - zumindest und umgekehrt;

2) Bei dem Problem bei maximaler Grenze der Ungleichheit ist es sinnvoll ≤ und im Problem der Minimierung - Bedeutung ≥;

3) Jede Einschränkung eines direkten Problems entspricht einer Variablen des doppelten Problems, und umgekehrt entspricht jede Einschränkung des dualen Problems einer Direktaufgabenvariablen;

4) Die Matrix des Systems von Einschränkungen des doppelten Problems wird von der Matrix des Restriktionssystems des anfänglichen Problems mit der Umsetzung erhalten;

5) Die freien Mitglieder des Direct-Problem-Einschränkungssystems sind Koeffizienten mit den entsprechenden Variablen der Zielfunktion der doppelten Aufgabe und umgekehrt;

6) Wenn die Variable der direkten Aufgabe mit einer nicht-Negativitätsbedingung überlagert ist, wird die entsprechende Einschränkung des doppelten Problems als Begrenzungsgleichung, falls nicht, als Gleichheitsgrenze geschrieben;

7) Wenn eine Einschränkung der direkten Aufgabe als Gleichheit erfasst wird, wird die relevante Variable des dualen Problems nicht auferlegt.

Transpoin-Matrics der Support-Aufgabe:

Wir geben der Aufgabe der kanonischen Form an. Wir führen zusätzliche Variablen ein. In der Zielfunktion werden wir alle zusätzlichen Variablen, die wir mit einem Koeffizienten einführen, gleich Null. Zusätzliche Variablen erhöhen den linken Teilen von Einschränkungen, die nicht die bevorzugte Spezies haben und gleich sein.

Lösung der doppelten Aufgabe von LP

Compliance zwischen den Variablen der ursprünglichen und dualen Aufgabe:

Basierend auf der Simplex-Tabelle wird die folgende Lösung der doppelten linearen Programmieraufgabe erhalten (Austritt aus der Unterleitung):

Somit ist die Ressource des ersten Typs das Defizit. Seine Schätzung ist maximal und gleich. Die dritte Formularressource ist eine redundante Dual-Score gleich Null. Jede zusätzlich verkaufte Wareneinheit der 2. Gruppe wird optimale Gewinne reduzieren
Das grafische Verfahren zur Lösung eines linearen Programmierproblems (ZLP) mit zwei Variablen wird berücksichtigt. Im Beispiel ist die Aufgabe angegeben detaillierte Beschreibung Gebäudezeichnung und Finden einer Lösung.

Lösung der Transportaufgabe
Das Transportproblem gilt im Detail, sein mathematisches Modell- und Lösungsmethoden, das den Referenzplan durch das Verfahren des Mindestelements und die Suche nach der optimalen Lösung durch das Verfahren der Potentialmethode ermittelt.

Entscheidungsfindung in Unsicherheit
Die Entscheidung des statistischen Matrixspiels bei Unsicherheitsbedingungen mit Hilfe von Waldkriterien, Wilde, Gurvitsa, Laplas, Bayes wird berücksichtigt. Mit dem Aufbau der Task-Beispiel wird der Aufbau einer Zahlungsmatrix und der Risikomatrix detailliert dargestellt.

Wenn in der Bedingung des Problems ein Einschränkungen mit einem Schild ≥ gibt, können sie dem Formular ΣA ji B J verabreicht werden, wobei beide Teile der Ungleichmäßigkeit auf -1 multiplizieren. Wir führen M zusätzliche Variablen x n + j ≥0 (j \u003d 1, m) ein, und wir transformieren die Einschränkungen in die Art der Gleichungen

(2)

Angenommen, alle ursprünglichen Variablen der Aufgabe x 1, x 2, ..., x n sind nicht-bacon. Dann sind zusätzliche Variablen basisch und die besondere Lösung des Restriktionssystems hat das Formular

x 1 \u003d x 2 \u003d ... \u003d x n \u003d 0, x n + j \u003d B j, j \u003d 1, m. (3)

Da der Wert der Funktionsfunktion F 0 \u003d 0 ist, kann f (x) wie folgt eingereicht werden:

F (x) \u003d Σc i x i + f 0 \u003d 0 (4)

Die anfängliche Simplex-Tabelle (Simplex-Tabelle. 1) ist anhand von Gleichungen (2) und (4) zusammengestellt. Wenn vor zusätzlichen Variablen x n + j ein Zeichen "+", wie in (2), gibt alle Koeffizienten, bevor die Variablen X i und das freie Element B j in der Simplex-Tabelle ohne Änderung aufgenommen werden. Die Koeffizienten der Zielfunktion, wenn sie maximiert ist, wird in die untere Linie des Simplex-Tischs mit entgegengesetzten Zeichen eingegeben. Kostenlose Mitglieder in der Simplex-Tabelle bestimmt die Lösung des Problems.

Der Problemlösungsalgorithmus ist wie folgt:

1. Schritt. Wir sind Elemente der Spalte freier Mitglieder. Wenn alle positiv sind, wird die zulässige Basislösung gefunden und zu Schritt 5 des Algorithmus entspricht, der der optimalen Lösung entspricht. Wenn in der anfänglichen Simplex-Tabelle negative freie Mitglieder vorhanden sind, ist die Lösung nicht zulässig und geht zu Schritt 2.

2. Schritt. Um eine zulässige Lösung zu finden, ist es notwendig, zu entscheiden, welche von nicht-Trennen-Variablen auf der Basis aktiviert ist und welche Variable, um sich von der Basis zurückzutreten.

Tabelle 1.

X n.

Grundlegende Variablen	Kostenlose Mitglieder in Einschränkungen	Nebase-Variablen
		x 1.	x 2.	...	x L.	...
x n + 1	b 1.	ein 11	a 12.	...	ein 1l.	...	ein 1n.
x n + 2	b 2.	a 21	a 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 n.

Wählen Sie dazu eine der negativen Elemente einer Spalte freier Elemente (lässt es B 2 vorführen oder zulässig sein. Wenn keine negativen Elemente in einer Reihe mit einem negativen freien Element vorhanden sind, dann ist das System der Einschränkungen unverständlich und Die Aufgabe hat keine Lösung.

Gleichzeitig wird die Variable von BP eliminiert, wodurch das Zeichen das Zeichen mit einer Erhöhung des ausgewählten NP X L ändert. Es wird x n + r sein, deren Index r aus dem Zustand bestimmt wird

jene. Die Variable, die dem kleinsten Verhältnis eines freien Elements an das Element der ausgewählten Bleisäule entspricht. Diese Beziehung wird aufgerufen simplex Haltung. Es sollten nur positive Simplex-Beziehungen berücksichtigt werden.

Die entsprechende Zeichenfolge, die der Variablen x n + r entspricht, wird aufgerufen führen oder erlauben. Das Element des Simplex-Tisches A RL, der an der Kreuzung der Host-Zeichenfolge und der Master-Säule steht, wird als führendes oder zulässige Element bezeichnet. Das Finden des Master-Elements endet mit jedem nächsten Simplex-Tisch.

3. Schritt. Der neue Simplex-Tisch wird berechnet, deren Elemente von den Elementen des Simplex-Tisches des vorherigen Schritts neu berechnet werden und mit einem Hub markiert sind, d. H. b "j, a" ji, c "i, f" 0. Die Neuberechnung von Elementen wird gemäß den folgenden Formeln hergestellt:

Zunächst wird der neue Simplex-Tisch mit einer Zeichenfolge und einer Spalte gefüllt, die in der vorherigen Simplex-Tabelle führte. Der Ausdruck (5) bedeutet, dass das Element A "RL an der Stelle des Meisters gleich der inversen Größe des Elements des vorherigen Simplex-Tisches ist. Die Elemente der RI-Reihe sind in das Leitungselement unterteilt, und die Elemente von Die A JL-Säule ist ebenfalls in ein führendes Element unterteilt, werden jedoch mit dem entgegengesetzten Zeichen aufgenommen. Elemente B "R und C" l wird nach demselben Prinzip berechnet.

Die restlichen Formeln sind einfach aufzunehmen.

Das Rechteck ist gemäß der alten Simplex-Tabelle derart gebaut, dass eine seiner Diagonalen bildet, die (A ji) und die Blei (A RL) -Elemente neu berechnet werden (Fig. 1). Die zweite Diagonale ist einzigartig definiert. Um ein neues Element A "JI aus dem JI-Element zu finden, wird er abgezogen (das" - "-Zeichen der Zelle ist dafür angegeben) das Produkt der Elemente der entgegengesetzten Diagonale geteilt, die durch das Leitelement geteilt wird. Ähnlich, Elemente B" J, (j ≠ r) und c "i, (i ≠ l).

4. Schritt. Eine Analyse der neuen Simplex-Tabelle beginnt mit dem ersten Schritt des Algorithmus. Die Aktion wird fortgesetzt, bis eine gültige Basislösung gefunden wird, d. H. Alle Elemente der Spalte freier Mitglieder müssen positiv sein.

5er Schritt Wir glauben, dass die zulässige Basislösung gefunden wird. Wir sehen die Zeilenkoeffizienten F (x) -Funktion. Ein Zeichen der Optimalität des Simplex-Tischs ist die Nicht-Negativität von Koeffizienten mit Nicht-Trennen von Variablen in der F-Line.

Feige. 1. Rechteckregel

Wenn es negativ ist (mit Ausnahme eines freien Mitglieds) zwischen den F-Zeilen-Koeffizienten), müssen Sie dann in eine andere grundlegende Lösung ziehen. Bei der Maximierung der Zielfunktion umfasst die Basis, dass die von nicht bindenden Variablen (beispielsweise x l) der Säule dem maximalen Absolutwert des negativen Koeffizienten C l an der Unterleitung des Simplex-Tischs entspricht. Auf diese Weise können Sie diese Variable auswählen, wobei der Anstieg zu einer Verbesserung der Funktionsfunktion führt. Eine Spalte, die der Variablen x l entspricht, wird als führend bezeichnet. Gleichzeitig ist die Variable x n + r von der Basis ausgeschlossen, deren Index R durch das minimale Simplex-Verhältnis bestimmt wird:

Die entsprechende String, die X n + R entspricht, wird als Master bezeichnet, und das Element der Simplex-Tabelle A RL, das an der Kreuzung der Host-Zeichenfolge und der Hostsäule steht, wird aufgerufen das führende Element.

6. Schritt. Entsprechend den im 3. Schritt angegebenen Regeln. Die Prozedur setzt sich fort, bis die optimale Lösung gefunden wird, oder es ist der Schluss, dass es nicht existiert.

Wenn bei der Optimierung der Lösung in der Master-Spalte alle Elemente nicht positiv sind, kann die Führungsleitung nicht ausgewählt werden. In diesem Fall ist die Funktion im Bereich der zulässigen Lösungen des Problems nicht von oben und f max -\u003e & ∞ begrenzt.

Wenn bei dem nächsten Schritt der Extremum-Suche eine der Grundvariablen null wird, wird die entsprechende Basislösung degeneriert. In diesem Fall tritt die sogenannte Schleife auf, dadurch gekennzeichnet, dass mit einer bestimmten Frequenz die gleiche Kombination von BP beginnt zu wiederholen (die Funktion der Funktion f ist aufbewahrt) und es ist unmöglich, zu einer neuen zulässigen Basis zu gehen Lösung. Die Schleife ist eine der wichtigsten Mängel der Simplex-Methode, aber es ist relativ selten. In der Praxis weigern sich in solchen Fällen in der Regel, die Variable auf die Basis einzugeben, deren Säule dem maximalen Absolutwert des negativen Koeffizienten in der Funktionsfunktion entspricht, und eine zufällige Auswahl einer neuen Basislösung vornehmen.

Beispiel 1. Lösen Sie die Aufgabe

max (f (x) \u003d -2x 1 + 5x 2 | 2x 1 + x 2 ≤ 7; x 1 + 4x 2 ≥8; x 2 ≤ 4; x 1,2 ≥0)

Simplex-Methode und geben die geometrische Interpretation des Lösungsprozesses an.

Die grafische Interpretation der Lösung des Problems ist in Fig. 2 dargestellt. 2. Der Maximalwert der Zielfunktion wird an der Oberseite des OTWP mit Koordinaten erreicht. Wir lösen die Aufgabe mit Simplex-Tabellen. Ich werde die zweite Grenze auf (-1) multiplizieren, und wir führen zusätzliche Variablen ein, so dass Ungleichheiten zur Art der Gleichungen führen, dann

Die anfänglichen Variablen X 1 und X 2 werden als Nichtmissbrauch genommen, und zusätzlich X 3, X 4 und X 5 betrachten die Basis und bilden einen Simplex-Tisch (Simplex-Tabelle. 2). Die Lösung, die der Simplex-Tabelle entspricht. 2 ist nicht zulässig; Das Antriebselement ist mit einer Schaltung umkreist und entsprechend dem Schritt 2 des früher angegebenen Algorithmus ausgewählt. Nächster Simplex-Tisch. 3 definiert eine zulässige Basislösung, es entspricht dem Scheitelpunkt von OCP in Fig. 3. 2 Das führende Element ist mit einer Kreislauf eingekreist und entsprechend dem 5. Schritt des Problemlösungsalgorithmus ausgewählt. Tabelle. 4 entspricht der optimalen Lösung des Problems, daher: x 1 \u003d x 5 \u003d 0; x 2 \u003d 4; x 3 \u003d 3; x 4 \u003d 8; F max \u003d 20.

Feige. 2. Grafiklösungsproblem

Gefallen? Zu Lesezeichen hinzufügen

Lösung von Aufgaben Simplex Method: Beispiele online

Aufgabe 1. Das Unternehmen produziert Regale für Badezimmer von zwei Größen - A und V. Vertriebsmaschinen glauben, dass bis zu 550 Regale eine Woche auf dem Markt umgesetzt werden können. Für jede Regale von Typ A ist 2 m2 des Materials erforderlich, und für den Regalb - 3 m2 des Materials. Das Unternehmen kann bis zu 1200 m2 Material pro Woche erhalten. Zur Herstellung eines Regal-Typs A ist 12 Minuten Maschinenzeit erforderlich, und für die Herstellung eines Regalsystems B - 30 min; Maschine kann 160 Stunden pro Woche verwendet werden. Wenn der Gewinn aus dem Verkauf von Typ A-Regal 3-Währungseinheiten ist, und aus der Reihe des Typs B - 4 DEN. UN., Wie viele Regale jedes Typs sollten pro Woche veröffentlicht werden?

Aufgabe 2. Lösen Sie die Aufgabe der linearen Programmierung Simplex-Methode.

Aufgabe 3. Das Unternehmen produziert 3 Arten von Produkten: A1, A2, A3, mit den Rohstoffen von zwei Typen. Die Kosten für Rohstoffe jedes Typs pro Produktionseinheit, Reserven von Rohstoffen für den geplanten Zeitraum sowie Gewinne der Produkteinheit jedes Typs.

1. Wie viele Produkte jeder Art müssen produzieren, um einen maximalen Gewinn zu erhalten?
2. Bestimmen Sie den Status jeder Art von Rohstoffen und seinen spezifischen Wert.
3. Bestimmen Sie den maximalen Bereich der Änderungen in den Reserven jeder Rohstoffart, in der die Struktur des optimalen Planes, d. H. Die Nomenklatur der Freigabe ändert sich nicht.
4. Bestimmen Sie die Menge der hergestellten Produkte und profitieren Sie aus dem Thema mit einer Erhöhung der Reserve eines der seltenen Rohstofftypen auf das maximal mögliche (in dieser Nomenklatur der Freigabe) der Größe.
5. Bestimmen Sie die Reichweitenintervalle der Gewinne aus der Produkteinheit jeder Art, in der sich der erhaltene optimale Plan nicht ändert.

Aufgabe 4. Lösen Sie die Aufgabe der linearen Programmierung mit einer Simplex-Methode:

Aufgabe 5. Lösen Sie die Aufgabe der linearen Programmierung Simplex-Methode:

Aufgabe 6. Lösen Sie die Aufgabe der Simplex-Methode, wenn man den in der Bedingung angegebenen Plan als anfänglicher Referenzplan berücksichtigt:

Aufgabe 7. Lösen Sie die Aufgabe einer modifizierten Simplex-Methode.
Zur Herstellung von zwei Arten von Produkten A und B werden drei Arten von technologischen Geräten verwendet. Zur Herstellung einer Einheit eines Produkts A wird das Gerät des ersten Typs A1 \u003d 4 Stunden, das Gerät des zweiten Typs A2 \u003d 8 Stunden und das Gerät des dritten Typs A3 \u003d 9 Stunden verwendet. Zur Herstellung einer Einheit der verwendeten Produkteinheit des verwendeten Produkts des ersten Typs B1 \u003d 7 Stunden, der Ausrüstung des zweiten Typs B2 \u003d 3 Stunden und das Gerät des dritten Typs B3 \u003d 5 Stunden.
Für die Herstellung dieser Produkte kann die Ausrüstung des ersten Typs nicht mehr als t1 \u003d 49 Stunden arbeiten, das Gerät des zweiten Typs ist nicht mehr als T2 \u003d 51 Stunden, das Gerät des dritten Typs ist nichts mehr als t3 \u003d 45 Stunden.
Gewinn aus dem Verkauf einer Einheit des fertigen Produkts A ist Alpha \u003d 6 Rubel und B - Betta-Produkte \u003d 5 Rubel.
Planen Sie einen Plan für die Produktion von Produkten A und B, wodurch maximale Gewinne von ihrer Implementierung bereitgestellt werden.

Aufgabe 8. Finden Sie die optimale Lösung für die Dual-Simplex-Methode

Ein Beispiel für das Lösen des Problems des Simplex-Problems sowie eines Beispiels, um eine duale Aufgabe zu lösen.

Die Aufgabe

Für die Umsetzung von drei Warengruppen verfügt ein kommerzielles Unternehmen über drei Arten von begrenzten Material- und Geldressourcen in der Menge von B 1 \u003d 240, B 2 \u003d 200, B 3 \u003d 160-Einheiten. Zur gleichen Zeit, zum Verkauf von 1 Gütergruppe pro tausend Rubel. Der Umsatz wird von der Ressource der ersten Spezies in der Menge einer 11 \u003d 2-Einheiten verbraucht, wobei die Ressource des zweiten Typs in der Menge eine 21 \u003d 4-Einheiten, die Ressource der dritten Form in der Menge von 31 \u003d 4 ist Einheiten. Zu verkaufen 2 und 3 Warengruppen pro tausend Rubel. Der Umsatz wird gemäß der Ressource des ersten Typs in der Menge A 12 \u003d 3, A 13 \u003d 6-Einheiten, die Ressource des zweiten Typs in der Menge von 22 \u003d 2, a 23 \u003d 4-Einheiten, der Ressource von Die dritte Form in der Menge von 32 \u003d 6, einem 33 \u003d 8-Einheiten. Profitieren Sie vom Verkauf von drei Warengruppen pro tausend Rubel. Der Umsatz ist C 1 \u003d 4, C 2 \u003d 5, C 3 \u003d 4, jeweils (tausend Rubel). Bestimmen Sie das geplante Volumen und die Struktur des Umsatzes, so dass der Gewinn des Handelsunternehmens maximal ist.

Zur direkten Aufgabe des Planungsumsatzes, simplex-Methode gelöst, erstellen doppelaufgabe Lineares Programmieren.
einstellen konjugiere-Paare von Variablen direkte und doppelte Aufgabe.
Nach den konjugierten Variablenpaaren, um eine direkte Aufgabe zu lösen lösung der dualen Aufgabein dem produziert wird bewertungsressourcenfür den Verkauf von Waren ausgegeben.

Lösung des Problems der Simplex-Methode

Sei x 1, x 2, x 3 die Anzahl der verkauften Waren, die in tausend Rubel bzw. 1, 2, 3 - zu IT-Gruppen ist. Dann ist das mathematische Modell des Problems:

F \u003d 4 · x 1 + 5 · x 2 + 4 · x 3 -\u003e max

0))) (~) "title \u003d" (! Lang: delim (lbrace) (Matrix (4) (1) ((2x_1 + 3x_2 + 6x_3 \u003d 0))) (~)">!}

Wir lösen die Simplex-Methode.

Wir führen zusätzliche Variablen x 4 ≥ 0, x 5 ≥ 0, x 6 ≥ 0 ein, damit Ungleichheiten in Gleichstellung umgewandelt werden.

Als Basis nehmen Sie x 4 \u003d 240; x 5 \u003d 200; x 6 \u003d 160.

Daten Wir betreten B. simplex-Tisch

Simplex Tabelle Nr. 1

Zielfunktion:

0 · 240 + 0 · 200 + 0 · 160 \u003d 0

Berechnen Sie die Bewertungen durch die 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. Die kleinste Bewertung:

Wir geben die Variable X 2 auf die Basis ein.

Bestimmen Sie die von der Basis kommende Variable. Dazu finden wir die kleinste nicht negative Beziehung zur Säule X 2.

= 26.667

Das kleinste ist nicht negativ: q 3 \u003d 26.667. Nehmen Sie die Variable X 6 aus der Basis

3. Zeile delim bei 6.
Von der ersten Linie subtrahieren wir die 3. Zeile multipliziert mit 3
Aus den 2. Zeilen subtrahieren wir die 3. Linie multipliziert mit 2

Berechnung:

Erhalten neue Tabelle:

Simplex Tabelle Nr. 2

Zielfunktion:

0 · 160 + 0 · 440/3 + 5 · 80/3 \u003d 400/3

Berechnen Sie die Bewertungen durch die 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 \u003d - 2/3 gibt, ist der Plan nicht optimal.

Wir geben die Variable X 1 auf die Basis ein.

Bestimmen Sie die von der Basis kommende Variable. Dazu finden wir die kleinste nicht negative Beziehung zur Säule X 1.

Das kleinste ist nicht negativ: q 3 \u003d 40. Nehmen Sie die Variable X 2 aus der Basis

3. Zeile delim auf 2/3.
Aus den 2. Zeilen subtrahieren wir die dritte Linie multipliziert mit 8/3

Berechnung:

Wir bekommen einen neuen Tisch:

Simplex Tabelle Nr. 3

Zielfunktion:

0 · 160 + 0 · 40 + 4 · 40 \u003d 160

Berechnen Sie die Bewertungen durch die 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:

Antworten

x 1 \u003d 40; x 2 \u003d 0; x 3 \u003d 0; x 4 \u003d 160; x 5 \u003d 40; x 6 \u003d 0; F max \u003d 160

Das heißt, es ist notwendig, das Produkt des ersten Typs in Höhe von 40 Tausend Rubel umzusetzen. Das Produkt der 2. und 3. Spezies implementiert nicht. Gleichzeitig wird der maximale Gewinn f max \u003d 160 tausend Rubel sein.

Lösung der dualen Aufgabe

Die duale Aufgabe ist:

Z \u003d 240 · y 1 + 200 · y 2 + 160 · y 3 -\u003e min

TITEL \u003d "(! Lang: Delim (LBRACE) (Matrix (4) (1) (2Y_1 + 4Y_2 + 4Y_3\u003e \u003d 4) (3Y_1 + 2Y_2 + 6Y_3\u003e \u003d 5) (6Y_1 + 4Y_2 + 8Y_3\u003e \u003d 4) (y_1, y_2, y_3\u003e \u003d 0))) (~)">!}

Wir geben zusätzliche Variablen y 4 ≥ 0, y 5 ≥ 0, y 6 ≥ 0 ein, damit Ungleichheiten in Gleichstellung umgewandelt werden.

Die konjugierten Paare variabler direkter und doppelter Aufgaben sind:

Von der letzten Simplex-Tabelle Nr. 3 direkte Aufgaben finden wir die Lösung der doppelten Aufgabe:

Z min \u003d f max \u003d 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;