wiwiweb
online lernen

Besser lernen mit Online-Kursen

NEU! Jetzt online lernen:
Operations Research
Den Kurs kaufen für:
einmalig 29,00 €
Zur Kasse

Simplex-Austausch-Schritt

WebinarTerminankündigung aus unserem Online-Kurs Volks- und Betriebswirtschaft:
 Am 12.01.2017 (ab 18:00 Uhr) findet unser nächstes Webinar statt.
Gratis-Webinar Grundbegriffe der Bilanzierung
- In diesem 60-minütigen Gratis-Webinar gibt Daniel Lambert einen Überblick über die zentralen Begriffe der Bilanzierung - hier im Besonderen dem Bilanzausweis.
[weitere Informationen] [Terminübersicht]

Zunächst versuchen wir, das

  • Kalkül des Simplex-Algorithmus, danach

  • die Zahlen der Tableaus

zu verstehen.

Methode

KOCHREZEPT SIMPLEX-ALGORITHMUS: 


 
1. Bestimme die Pivot-Spalte
Suche hierzu die Spalte mit dem größten Zielfunktionskoeffizienten

2. Bestimme die Pivot-Zeile

•teile alle Elemente der rechten Seite durch die – streng positiven – Elemente der Pivot-Spalte

•nimm das Minimum der Zahlen aus a.

3. Bestimme das Pivot-Element

Dies befindet sich im Schnittpunkt aus Pivotspalte und Pivotzeile

4. Dividiere die Elemente der Pivotzeile durch das Pivotelement

Dadurch wird das Pivotelement zu eins

5. Mache alle Elemente der Pivotspalte – mit Ausnahme des Pivotelements selbst – zu null

Subtrahiere geeignete Vielfache der Pivotzeile von den jeweiligen Zeilen des Tableaus

In unserem ersten Beispiel aus dem Kapitel "Beste Lösung" ist die Pivotspalte bei x1, da der Zielfunktionswert mit 270 maximal ist.

Merke

x1 wird dadurch von einer Nichtbasisvariable (mit Wert null) zu einer Basisvariable (mit Wert größer null). Man spricht deshalb bei einem Simplex-Schritt auch von einem Basis-Tausch. Gut 1 wird produziert, Produkt 2 nicht (x1 = 60, x2 = 0 im Punkt (E)).

Dann sucht man die Pivotzeile. Die Elemente der rechten Seite, dividiert durch die Pivotspalte, liefern Quotienten, die ganz rechts eingetragen werden:

x1

x2

y1

y2

y3

y4

RS

Divisionen

y1

1

0

1

0

0

0

60

60 : 1 = 60

y2

0

1

0

1

0

0

150

-

y3

1

0,2

0

0

1

0

70

70 : 1

y4

150

50

0

0

0

1

12.500

12.500 : 150 = 83,33

ZF

270

45

0

0

0

0

0

Tab. 2: Suche nach der Pivotzeile und dem Pivotelement

Minimal ist die Zahl 60, so dass die erste Zeile zur Pivotzeile wird. Das Pivotelement liegt im Drehkreuz aus Pivotspalte und Pivotzeile und ist hier also 1. Der vierte Schritt des obigen Kochrezepts entfällt, da das Pivotelement bereits gleich 1 ist. Mache danach die einzelnen Elemente der Pivotspalte zu null. In der zweiten Zeile rechnet man nichts, da der Eintrag bereits null ist.

  • In der dritten Zeile

    • rechnet man III – I = IIIneu

  • Für die vierte Zeile

    • kalkuliert man –150·I + IV = IVneu

  • In der Zielfunktionszeile

    • rechnet man ZF – 270·I =ZFneu

Nach diesem Simplex-Schritt erhält man folgendes Tableau:

x1

x2

y1

y2

y3

y4

RS

x1

1

0

1

0

0

0

60

y2

0

1

0

1

0

0

150

y3

0

0,2

-1

0

1

0

10

y4

0

50

-150

0

0

1

3.500

0

45

-270

0

0

0

-16.200

Tab. 3: Simplextableau nach erstem Austauschschritt

Zum tiefergehenden Verständnis sind noch einige Erklärungen notwendig:

Wir befinden uns im Punkt (E) der Abb. 4, denn es ist x1= 60 und x2= 0.

x1 ist nun Basisvariable, nicht mehr Nichtbasisvariable wie vorher. Auf deutsch: Gut 1 wird produziert, das Gut 2 nicht (x2 ist also weiterhin Nichtbasisvariable). x1 steht deshalb nun am linken Rand des Tableaus, nicht mehr lediglich oben.

y1 ist nicht mehr Basis-, sondern Nichtbasisvariable. Es wird also der Wert y1 = 0 zugewiesen. Wenn x1 = 60 ist, dann ist die Absatzkapazität komplett ausgereizt. Mehr Absatz ist beim ersten Produkt nicht möglich.

Bei einer Menge von x1= 60 ME und x2= 0 ME ist der Gewinn G = 270·60 + 45·0 = 16.200 €. Der Wert in der rechten unteren Ecke des Tableaus ist also der Gewinn, der bei Betrachtung der jeweiligen Ecke entsteht.

Methode

Das Minus-Zeichen bedeutet nicht, dass der Gewinn negativ ist!

Zu den restlichen Werten der rechten Seite:

  • y2= 150

    • die zweite Absatzkapazität ist noch komplett unausgelastet,

    • es ist also noch Platz für 150 zu produzierende Mengeneinheiten

  • y3= 10

    • auf der Maschine beträgt die Restkapazität noch 10 Minuten

    • wegen 1·60 + 0,2·0 = 60, und dies liegt 10 Minuten unter der maximalen Kapazität von 70

  • y4= 3.500

    • es sind noch 3.500 Arbeitsstunden unausgenutzt

    • wegen 150.60 + 50·0 = 9.000,

    • und dies liegt 3.500 Stunden unter der maximalen Kapazität von 12.500.

Auch die restlichen Zahlen sind interpretierbar. Hierum kümmern wir uns jedoch erst im Optimaltableau (was allerdings in jedem anderen Tableau auch geht).

Multiple-Choice

Welche der folgenden Aussagen kommt der Wahrheit am nächsten?  

0/0
Lösen

Hinweis:

Bitte kreuzen Sie die richtigen Aussagen an. Es können auch mehrere Aussagen richtig oder alle falsch sein. Nur wenn alle richtigen Aussagen angekreuzt und alle falschen Aussagen nicht angekreuzt wurden, ist die Aufgabe erfolgreich gelöst.

Bild von Autor Daniel Lambert

Autor: Daniel Lambert

Dieses Dokument Simplex-Austausch-Schritt ist Teil eines interaktiven Online-Kurses zum Thema Operations Research.

Dipl.-Math. Dipl.-Kfm. Daniel Lambert gibt seit vielen Jahren Kurse zur Prüfungsvorbereitung. Er unterrichtet stets orientiert an alten Prüfungen und weiß aus langjähriger Erfahrung, wie sich komplexe Sachverhalte am besten aufbereiten und vermitteln lassen. Daniel Lambert ist Repetitor aus Leidenschaft seit nunmehr 20 Jahren.
Vorstellung des Online-Kurses Operations ResearchOperations Research
Dieser Inhalt ist Bestandteil des Online-Kurses

Operations Research

wiwiweb - Interaktive Online-Kurse (wiwiweb.de)
Diese Themen werden im Kurs behandelt:

[Bitte auf Kapitelüberschriften klicken, um Unterthemen anzuzeigen]

  • Lineare Programmierung
    • Einleitung zu Lineare Programmierung
  • Maximierungsprobleme
    • Einleitung zu Maximierungsprobleme
  • Beste Lösung, Graphische Lösung
    • Aufstellen des Problems
    • Graphische Darstellung des Maximierungsproblems
  • Analytische Lösung
    • Vorbereitung
    • Schlupfvariablen
    • Aufstellen des Ausgangstableaus
    • Der Simplex-Algorithmus
    • Simplex-Austausch-Schritt
    • Weiterer Simplex-Schritt und Interpretation des Optimaltableaus
  • Entartung
    • Mehrdeutigkeit
    • Degeneration
  • Sensitivitätsanalyse
    • Schwankungen Deckungsbeitragskoeffizienten
    • Änderungen der Restriktionen
  • Zweitbeste Lösung
    • Zweitbeste Lösung
  • Minimierungsprobleme
    • Einleitung zu Minimierungsprobleme
    • Zweiphasenmethode
      • Zweiphasenmethode
      • Beginn erste Phase
      • Beginn zweite Phase
      • Dualität
      • Dualer Simplex-Algorithmus
  • Transportproblem
    • Nordwest-Ecken-Methode
    • Matrix-Minimum-Methode
    • Stepping-Stone-Methode
  • 24
  • 18
  • 56
  • 6
einmalig 29,00
umsatzsteuerbefreit gem. § 4 Nr. 21 a bb) UStG
Online-Kurs Top AngebotTrusted Shop

Unsere Nutzer sagen:

  • Gute Bewertung für Operations Research

    Ein Kursnutzer am 16.03.2015:
    "alles top"

  • Gute Bewertung für Operations Research

    Ein Kursnutzer am 02.12.2014:
    "Super Erklärungen in den Videos!"

NEU! Sichere dir jetzt die perfekte Prüfungsvorbereitung und spare 10% bei deiner Kursbuchung!

10% Coupon: lernen10

Zu den Online-Kursen