ingenieurkurse
online lernen

Besser lernen mit Online-Kursen

NEU! Jetzt online lernen:
Operations Research 1
Den Kurs kaufen für:
einmalig 39,00 €
Zur Kasse
Lineare Programmierung > Standardform: Maximierungsproblem > Simlpex-Algorithmus: Einführung > Primales Simlpexverfahren:

Primales Simplexverfahren: Pivotspalte/-zeile/-element

WebinarTerminankündigung aus unserem Online-Kurs Thermodynamik:
 Am 13.12.2016 (ab 16:00 Uhr) findet unser nächstes Webinar statt.
Gratis-Webinar (Thermodynamik) Innere Energie, Wärme, Arbeit
- Innerhalb dieses 60-minütigen Webinares wird der 1. Hauptsatz der Thermodynamik für geschlossene Systeme behandelt und auf die innere Energie, Wärme und Arbeit eingegangen.
[weitere Informationen] [Terminübersicht]

Nachdem das Tableau für das lineare Optimierungsproblem im vorherigen Abschnitt aufgestellt worden ist, soll nun die erste Iteration für das primale Simplexverfahren durchgeführt werden. Für jede Iteration müssen die folgenden Schritte durchgeführt werden:

  1. Wahl der Pivotspalte t: Enthält die untere Zeile, in welche die Werte aus der Zielfunktion eingetragen werden, nur nicht-negative Werte, so ist die optimale Lösung gefunden. Ansonsten wird diejenige Spalte mit dem kleinsten negativen Wert ausgewählt. Sind mehrere Spalten mit kleinstem negativen Wert gegeben, so kann unter diesen eine beliebige Spalte ausgewählt werden. 

  2. Wahl der Pivotzeile s: Sind in der Pivotspalte aus 1. alle $a_{it} \le 0$, so exsitiert für das Problem keine optimale Lösung. Das Verfahren muss abgebrochen werden. Ansonsten wird die rechte Seite für alle Elemente $a_{it} \ge 0$ der Pivotspalte betrachtet und diejenige Pivotzeile ausgewählt, für die gilt $min\frac{bi}{a_{it}} = min$. Dort wo sich die Pivotspalte und die Pivotzeile schneiden, liegt das Pivotelement $a_{st}$.

  3. Nachdem die Pivotspalte $t$ und die Pivotzeile $s$ sowie das Pivotelement $a_{st}$ bestimmt worden sind, wird nun in einem nächsten Schritt die Basisvariable der Pivotzeile mit der Nichtbasisvarbiablen der Pivotspalte getauscht und ein neues Tableau aufgestellt.

Merke

Die Optimallösung des Maximierungsproblems liegt nach dem primalen Simplexverfahren dann vor, wenn alle Werte der Zielfunktionszeile positiv sind.


Zum besseren Verständnis der ersten drei Schritte, wird nun das Beispiel aus dem vorherigen Abschnitt herangezogen und ausführlich gezeigt, wie diese Schritte durchgeführt werden:

1. Schritt: Wahl der Pivotspalte

Primales Simplexverfahren - Wahl der Pivotspalte

Es wird diejenige Spalte als Pivotspalte ausgewählt, für welche der Zielfunktionswert den kleinsten negativen Wert annimmt. In dem obigen Beispiel sind beide Werte gleich (-1). Das bedeutet, es kann eine beliebige Spalte als Pivotspalte gewählt werden. In diesem Fall ist nun die erste Spalte gewählt worden.

2. Schritt: Wahl der Pivotzeile

Primales Simplexverfahren - Wahl der Pivotzeile

Als nächstes werden dann alle Werte innerhalb der Pivotspalte betrachtet (hier: 4, 2, 1). Es werden dann diejenigen Werte größer Null ausgewählt (die kleiner null bleiben unberücksichtigt) und mit den Werten der rechten Seiten verrechnet (Division der rechten Seiten durch die Werte). Dort wird der kleinste Wert ausgewählt und die Pivotzeile festgelegt. Das Pivotelement liegt dann dort, wo sich Pivotspalte und Pivotzeile schneiden:

Primales Simplexverfahren - Wahl des Pivotelements


3. Schritt: Aufstellen eines neuen Tableaus, wobei Basisvariable mit Nichtbasisvariable vertauscht werden:

Primales Simplexverfahren - Tausch der NBV und BV

Dies sind die ersten drei Schritte, die durchgeführt werden müssen. Es kann nun das neue Tableau aufgestellt werden, welches zunächst noch leer ist. Die Basisvariable der Pivotzeile $x_5$ und die Nichtbasisvariable der Pivotspalte $x_1$ sind vertauscht worden. Für die Bestimmung der neuen Werte des Tableaus müssen nun einige Rechenschritte durchgeführt werden, die im folgenden Abschnitt erläutert werden.

Multiple-Choice
Welche Aussagen zum primalen Simplex-Algorithmus sind richtig?
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.

Vorstellung des Online-Kurses Operations ResearchOperations Research
Dieser Inhalt ist Bestandteil des Online-Kurses

Operations Research 1

Ingenieurkurse (ingenieurkurse.de)
Diese Themen werden im Kurs behandelt:

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

  • Kurs: Operations Research 1 - Lineare Optimierung, Graphentheorie und Netzplantechnik
    • Einleitung zu Kurs: Operations Research 1 - Lineare Optimierung, Graphentheorie und Netzplantechnik
  • Lineare Programmierung
    • Einleitung zu Lineare Programmierung
    • Definition: Lineares Programm
    • Standardform: Maximierungsproblem
      • Einleitung zu Standardform: Maximierungsproblem
      • Grafische Lösung eines Maximierungsproblems
        • Einleitung zu Grafische Lösung eines Maximierungsproblems
        • Beispiel: Grafische Lösung eines Maximierungsproblems
      • Umformung in die Standardform (Maximierungsproblem)
      • Umformung in die Normalform (Maximierungsproblem)
      • Simlpex-Algorithmus: Einführung
        • Einleitung zu Simlpex-Algorithmus: Einführung
        • Primales Simlpexverfahren
          • Einleitung zu Primales Simlpexverfahren
          • Primales Simplexverfahren: Anfangstableau aufstellen
          • Primales Simplexverfahren: Pivotspalte/-zeile/-element
          • Primales Simplexverfahren: 1. Simplexschritt
          • Primales Simplexverfahren: Weitere Simplexschritte (optimale Lösung)
          • Beispiel: Maximierungsproblem / grafische Lösung
          • Beispiel: Maximierungsproblem / Primales Simplexverfahren
        • Duales Simplexverfahren
          • Einleitung zu Duales Simplexverfahren
          • Duales Simplexverfahren: Pivotzeile/-spalte/-element
          • Duales Simplexverfahren: Simplexschritte
        • Die Big-M-Methode des primalen Simplexverfahrens
          • Einleitung zu Die Big-M-Methode des primalen Simplexverfahrens
          • Die Big-M-Methode: Einfügen von künstlichen Variablen
          • Die Big-M-Methode: Künstliche Variablen als Basisvariablen
          • Big-M-Methode: Simplexschritt durchführen
          • Big-M-Methode: Weiterer Simplexschritt (zulässige Lösung)
          • Big-M-Methode: Weitere Simplexschritte (optimale Lösung)
      • Kanonische Form, Standardform, Normalform
      • Zusammenfassung: Maximierungsproblem
    • Minimierungsproblem
      • Einleitung zu Minimierungsproblem
      • Dualität - Primalproblem als Maximierungsproblem
      • Dualität - Primalproblem als Minimierungsproblem
      • Dualität - Dualproblem in Primalproblem
      • Beispiel: Primalproblem als Minimierungsproblem
      • Minimierungsproblem- Big-M/dualer Simplex
      • Zusammenfassung: Minimierungsproblem
    • Sonderfälle bei Optimierungsmodellen
      • Einleitung zu Sonderfälle bei Optimierungsmodellen
      • Beispiel: Minimierungsproblem ohne optimal Lösung
    • Sensitivitätsanalyse
      • Einleitung zu Sensitivitätsanalyse
      • Änderung der Zielfunktionskoeffizienten
        • Einleitung zu Änderung der Zielfunktionskoeffizienten
        • Beispiel: Sensitivitätsanalyse Zielfunktionskoeffizienten
      • Änderung der Restriktionen
    • Obere und untere Schranken bei Variablen
      • Untere Schranken
      • Obere Schranken
        • Einleitung zu Obere Schranken
        • Beispiel: Primaler Simplexalgorithmus
        • Beispiel: Vielzahl an beschränkten Variablen
    • Revidierter Simplex-Algorithmus
      • Einleitung zu Revidierter Simplex-Algorithmus
      • Beispiel: Revidierter Simplex-Algorithmus
  • Transport- und Zuordnungsprobleme
    • Das klassische Transportproblem
      • Einleitung zu Das klassische Transportproblem
      • Ausgleichsprüfung
      • Reduktion der Kostenmatrix
      • Eröffnungsverfahren
        • Einleitung zu Eröffnungsverfahren
        • Nord-Westecken-Verfahren
        • Rangfolgeverfahren
          • Einleitung zu Rangfolgeverfahren
          • Spaltenfolgeverfahren
          • Zeilenfolgeverfahren
          • Matrixminimumverfahren
        • Vogelsches-Approximations-Verfahren
      • Optimierungsverfahren
        • Einleitung zu Optimierungsverfahren
        • Stepping-Stone-Methode
        • MODI-Methode
    • Lineare Zuordnungsprobleme
      • Definition: Zuordnungsprobleme
      • Ungarische Methode
  • Netzplantechnik
    • Einführung Netzplantechnik
    • Ablaufplanung
      • Einleitung zu Ablaufplanung
      • Strukturplanung
      • Netzplanerstellung
    • Zeitplanung
      • Einleitung zu Zeitplanung
      • Beispiel 1: Vorgangsknotennetzplan
      • Beispiel 2: Vorgangsknotennetzplan
    • Kostenplanung
    • Kapazitätsplanung
  • Graphentheorie
    • Einführung: Graphentheorie
    • Kürzeste Wege
      • Einleitung zu Kürzeste Wege
      • Dijkstra-Algorithmus
      • Fifo-Algorithmus
  • 74
  • 11
  • 42
  • 144
einmalig 39,00
umsatzsteuerbefreit gem. § 4 Nr. 21 a bb) UStG
Online-Kurs Top AngebotTrusted Shop

Unsere Nutzer sagen:

  • Gute Bewertung für Operations Research 1

    Ein Kursnutzer am 22.06.2016:
    "top!! ;)"

  • Gute Bewertung für Operations Research 1

    Ein Kursnutzer am 05.12.2015:
    "Super erklärt !! "

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

10% Coupon: lernen10

Zu den Online-Kursen