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

Revidierter Simplex-Algorithmus

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]

In diesem Abschnitt wird der revidierte Simplexalgorithmus aufgezeigt. Dieser wird angewandt, wenn die Anzahl der Variablen in einem linearen Optimierungsproblem wesentlich größer ist, als die Anzahl der Nebenbedingungen. Es wird im folgenden der revidierte Simplexalgorithmus für ein in kanonischer Form (Maximierungsproblem, kleiner/gleich-Nebenbedingungen, Nichtnegativitätsbedingung, positive Werte der rechten Seite) vorliegendes Problem aufgezeigt.

Gegeben sei das folgende lineare Maximierungsproblem in kanonischer Form:

$f(x_1, x_2, x_3) = 3x_1 + 5x_2 + 4x_3$  $\rightarrow$  max!


u.d.N.

$2x_1 + 2x_2 + x_3 \le 3$

$x_1 + 2x_2 + 4x_3 \le 5$

$x_1, x_2, x_3 \ge 0$

Das Problem wird zunächst auf die Normalform gebracht, indem die Schlupfvariablen eingefügt werden:

$f(x_1, x_2, x_3) = 3x_1 + 5x_2 + 4x_3$  $\rightarrow$  max!


u.d.N.

$2x_1 + 2x_2 + x_3 + x_4             = 3$

$x_1 + 2x_2 + 4x_3          + x_5    =  5$

$x_1, x_2, x_3, x_4, x_5 \ge 0$


Es liegt nun die folgende Form vor:

Methode

max  $c^T x$

        $Ax = b$

        $ x \ge 0$

Vorgehensweise revidierte Simplexmethode

Bevor mit der Berechnung begonnen wird, werden die Koeffizienten in Matrizen geschrieben und die Basis- und Nichtbasisvariablen wie folgt festgelegt:

$c^T = (3, 5, 4, 0, 0)$

$A = \begin{bmatrix} 2 & 2 & 1 & 1 & 0 \\ 1 & 2 & 4 & 0 & 1 \end{bmatrix}$ 

$b =  \begin{pmatrix} 3 \\ 5 \end{pmatrix}$

Es werden ebenfalls die Schlupfvariablen in den Matrizen mitberücksichtigt. In die Zielfunktion gehen diese mit dem Wert null ein, weshalb dort für beide am Ende eine Null steht.

Es wird als nächstes die Matrix $B$ (nur Werte der Basisvariablen plus Einheitsvektor) aufgestellt:

$B = \begin{bmatrix} 1 & 0 & 0 \\  0 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix}$ 

Zu Beginn sind die Basisvariablen die Schlupfvariablen $x_4$ und $x_5$. Es werden alle Werte der Nebenbedingungen für die Basisvariablen, ohne die rechte Seite berücksichtigt. Die Zielfunktion für die Basisvariablen wird die letzte Zeile der Matrix. Für die Basisvariablen sind die Zielfunktionswerte alle Null. Außerdem wird noch ein Einheitsvektor (mit der $1$ in der letzten Zeile) berücksichtigt.

Die Matrix $N$ (nur Werte der Nichtbasisvariablen) wird ebenfalls benötigt:

$N = \begin{bmatrix} 2 & 2 & 1 \\ 1 & 2 & 4 \\ -3 & -5 & -4 \end{bmatrix}$ 

Zu Beginn sind die Nichtbasisvariablen die Variablen der Zielfunktion $x_1$, $x_2$ und $x_3$. Es werden alle Werte der Nichtbasisvariablen, ohne die rechte Seite berücksichtigt.

Merke

Hinweis: Es ist sinnvoll sich die Variablen über die Matrix zu schreiben. Vor allem bei einem späteren Tausch der Variablen kann man sonst schnell den Überblick verlieren.

1. Iteration:

1. Schritt: Auswahl der Pivotspalte.

Bestimmung der Pivotspalte $a_s$, indem die Zielfunktion der Inversen von $B$ mit der Matrix $N$ mulipliziert wird.

Es muss also zunächst die Inverse Matrix $B^{-1}$ bestimmt werden:

$B^{-1} = B = \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix} = I$

Da die Matrix $B$ der Einheitsmatrix $I$ entspricht, ist diese zu Beginn gleich der Inversen.

Es wird nun die Zielfunktionszeile der Inversen $B^{-1}$ mit $N$ multipliziert:

$c_{B^{-1}} \cdot N = ( 0, 0, 1) \cdot \begin{bmatrix} 2 & 2 & 1 \\ 1 & 2 & 4 \\ -3 & -5 & -4 \end{bmatrix} = (-3, -5, -4)$

Es wird der kleinste negative Wert ausgewählt, hier: $-5$. Dieser gehört zur Nichtbasisvariablen $x_2$. Die Nichtbasisvariable $x_2$ besitzt die Pivotspalte

$a_2 = \begin{pmatrix} 2 \\ 2 \\ -5 \end{pmatrix}$


2. Schritt: Auswahl der Pivotzeile.

Die Pivotzeile wird bestimmt, indem die Inverse $B^{-1}$ mit der aktuell ausgewählte Pivotspalte $a_s$ und der rechten Seite $b$ mulipliziert wird. Dabei werden $a_s$ und $b$ in eine Matrix geschrieben:

$\begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix} \cdot \begin{bmatrix} 2 & 3 \\ 2 & 5 \\ -5 & 0 \end{bmatrix} = \begin{bmatrix} 2 & 3 \\ 2 & 5 \\ -5 & 0 \end{bmatrix} $

Die Ergebnismatrix wird dann verwendet, um die Pivtozeile zu bestimmen. Es werden die Werte der 2. Spalte durch die zugehörigen Werte der 1. Spalte geteilt. Hierbei dürfen für die 1. Spalte nur Werte größer als Null verwendet werden. Existieren keine Werte größer als Null, so existiert keine optimale Lösung. Es wird der kleinste Quotient ausgewählt:

$min \{ \frac{3}{2}, \frac{5}{2} \} = \frac{3}{2}$.

Die Pivotzeile wird also für $x_4$ ausgewählt. 

Schritt 3: Neuberechnung der Inversen

Es wird nun in der Ausgangsmatrix $B$ die Spalte von $x_4$ ersetzt durch die Spalte von $x_2$. Denn $x_2$ verlässt nun die Nichtbasis und wechselt in die Basis. Hingegen wechselt $x_4$ nun in die Nichtbasis. Das bedeutet auch $N$ muss angepasst werden:

$B = \begin{bmatrix} 2 & 0 & 0 \\ 2 & 1 & 0 \\ -5 & 0 & 1 \end{bmatrix}$

$N = \begin{bmatrix} 2 & 1 & 1 \\ 1 & 0 & 4 \\ -3 & 0 & -4 \end{bmatrix}$ 

Die Inverse muss nun neu berechnet werden, da sich $B$ geändert hat. Diesemal entspricht die Inverse $B^{-1}$ nicht der Matrix $B$. Diese muss also nun mittels Gauß-Jordan-Algorithmus bestimmt werden:

$B^{-1} = \begin{bmatrix} \frac{1}{2} & 0 & 0 \\ -1 & 1 & 0 \\ \frac{5}{2} & 0 & 1 \end{bmatrix}$

2. Iteration

Es kann als nächstes mit der 2. Iteration begonnen werden. 

1. Schritt: Auswahl der Pivotspalte.

Bestimmung der Pivotspalte $a_s$, indem die Zielfunktion von $B^{-1}$ mit der Matrix $N$ mulipliziert wird:

$c_{B^{-1}} \cdot N = ( \frac{5}{2}, 0, 1) \cdot \begin{bmatrix} 2 & 1 & 1 \\ 1 & 0 & 4 \\ -3 & 0 & -4 \end{bmatrix} = (2, \frac{5}{2} , -\frac{3}{2})$

Es wird der kleinste negative Wert ausgewählt, hier: $-\frac{3}{2}$. Dieser gehört zur Nichtbasisvariablen $x_3$. Die Nichtbasisvariable $x_3$ besitzt die Pivotspalte

$a_3 = \begin{pmatrix} 1 \\ 4 \\ -4 \end{pmatrix}$

2. Schritt: Auswahl der Pivotzeile.

Die Pivotzeile wird bestimmt, indem die Inverse $B^{-1}$ mit der aktuell ausgewählte Pivotspalte $a_s$ und der rechten Seite $b$ mulipliziert wird. Dabei werden $a_s$ und $b$ in eine Matrix geschrieben:

$\begin{bmatrix} \frac{1}{2} & 0 & 0 \\ -1 & 1 & 0 \\ \frac{5}{2} & 0 & 1 \end{bmatrix} \cdot \begin{bmatrix} 1 & 3 \\ 4 & 5 \\ -4 & 0 \end{bmatrix} = \begin{bmatrix} \frac{1}{2} & \frac{3}{2} \\ 3 & 2 \\ -\frac{3}{2} & \frac{15}{2} \end{bmatrix} $

Die Ergebnismatrix wird dann verwendet, um die Pivotzeile zu bestimmen. Es werden die Werte der 2. Spalte durch die zugehörigen Werte der 1. Spalte geteilt. Hierbei dürfen für die 1. Spalte nur Werte größer als Null verwendet werden. Existieren keine Werte größer als Null, so existiert keine optimale Lösung. Es wird der kleinste Quotient ausgewählt:

$min \{ \frac{\frac{3}{2}}{\frac{1}{2}}, \frac{2}{3} \} = \frac{2}{3}$.

Die Pivotzeile wird also für $x_5$ ausgewählt. 

Schritt 3: Neuberechnung der Inversen

Es wird nun in der Ausgangsmatrix $B$ die Spalte von $x_5$ ersetzt durch die Spalte von $x_3$. Denn $x_3$ verlässt nun die Nichtbasis und wechselt in die Basis. Hingegen wechselt $x_5$ nun in die Nichtbasis. Das bedeutet auch $N$ muss angepasst werden:

$B = \begin{bmatrix} 2 & 1 & 0 \\ 2 & 4 & 0 \\ -5 & -4 & 1 \end{bmatrix}$

$N = \begin{bmatrix} 2 & 1 & 0 \\ 1 & 0 & 1 \\ -3 & 0 & 0 \end{bmatrix}$ 

Die Inverse muss nun neu berechnet werden, da sich $B$ geändert hat. Diese muss also nun mittels Gauß-Jordan-Algorithmus bestimmt werden:

$B^{-1} = \begin{bmatrix} \frac{2}{3} & -\frac{1}{6} & 0 \\ -\frac{1}{3} & \frac{1}{3} & 0 \\ 2 & \frac{1}{2} & 1 \end{bmatrix}$

3. Iteration

1. Schritt: Auswahl der Pivotspalte.

Bestimmung der Pivotspalte $a_s$, indem die Zielfunktion von $B^{-1}$ mit der Matrix $N$ mulipliziert wird:

$c_{B^{-1}} \cdot N = ( 2, \frac{1}{2}, 1) \cdot \begin{bmatrix} 2 & 1 & 0 \\ 1 & 0 & 1 \\ -3 & 0 & 0 \end{bmatrix} = (\frac{3}{2}, 2 , \frac{1}{2})$

Optimale Lösung

Da keine negativen Werte mehr vorhanden sind, liegt die optimale Lösung vor. Diese ergibt sich für die Basisvariablen $x_B = (x_2, x_3)$.

Die Werte für die Basisvariablen ergeben sich durch Multiplikation der Inversen $B^{-1}$ mit der rechten Seite $b$:

 $\begin{bmatrix} \frac{2}{3} & -\frac{1}{6} & 0 \\ -\frac{1}{3} & \frac{1}{3} & 0 \\ 2 & \frac{1}{2} & 1 \end{bmatrix} \cdot \begin{pmatrix} 3 \\ 5 \\ 0 \end{pmatrix} = \begin{bmatrix} \frac{7}{6} \\ \frac{2}{3} \\ 8,5 \end{bmatrix}$

Dabei gilt $x_2 = \frac{7}{6}$ und $x_3 = \frac{2}{3}$. Der Zielfunktionswert beträgt $f = 8,5$.

Multiple-Choice
Bei dem revidierte Simplexalgorithmus wird das Problem zunächst auf die Normalform gebracht, indem die Schlupfvariablen eingefügt werden.
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