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 > Obere und untere Schranken bei Variablen:

Obere Schranken

WebinarTerminankündigung aus unserem Online-Kurs Technische Mechanik 3: Dynamik:
 Am 06.12.2016 (ab 16:00 Uhr) findet unser nächstes Webinar statt.
Gratis-Webinar (Dynamik) Gradlinige Bewegung eines Massenpunktes
- Dieses 60-minütige Gratis-Webinar behandelt die geradlinige Bewegung eines Massenpunktes.
[weitere Informationen] [Terminübersicht]

Obere Schranken $\kappa_j$ werden im Gegensatz zu unteren Schranken $\lambda_j$ während des Simplexalgorithmus berücksichtigt. Dabei wird bei Erreichen der oberen Schranke $\kappa_j$ die Variable $x_j$ ersetzt durch:

Methode

$x_j = \kappa_t - \overline{x_j}$

Vorgehensweise:

Die Vorgehensweise bei der Berücksichtigung der oberen Schranken beim primalen Simplexalgorithmus wird im Folgenden aufgezeigt. Dabei müssen die folgenden Schritte vor jeder Iteration durchgeführt werden.

1. Wahl der Pivotspalte: Kleinsten negativen Wert wählen. Bei mehreren kleinsten negativen Werte ist einer zufällig auszuwählen. Liegen keine negativen Werte vor, so ist die Optimallösung erreicht. Die Nichtbasisvariable der Pivotspalte wird zu $x_t$ mit dem dazugehörigen $\kappa_t$ (obere Schranke der Nichtbasisvariable).

2. Wahl der Pivotzeile: Es wird nun die Pivotspalte und die dazugehörigen Werte der rechten Seite betrachtet und folgende Formeln angewandt:

Methode

$q_1 := \{ min \{\frac{b_i}{a_{it}} \}  \; \text{mit} \; a_{it} > 0 \; , \; \text{sonst} \; \infty \}$

$q_2 := \{ min \{-\frac{\kappa_i - b_i}{a_{it}} \}  \; \text{mit} \; a_{it} < 0 \; , \; \text{sonst} \; \infty \}$

Das in der Formel verwendete $\kappa_i$ ist die obere Schranke für die Basisvariable in der $i$-ten Zeile. Das in der Formel angesetzt $b_i$ ist zugleich der Wert der Basisvariable $x_i$.

Es gilt weiterhin

Methode

$q := min\{q_1, q_2, \kappa_t\}$

Nachdem nun $q$ bestimmt worden ist, müssen noch 3 Fälle unterschieden werden:

  • $q = q_1$:

Die Basisvariable $x_i$ für die $q_1 = \frac{b_s}{a_{st}}$ gilt, verlässt die Basis (wird zur Nichtbasisvariablen). Es wird wie üblich der Simplexalgorithmus angewandt. Danach geht es weiter bei 1. Wahl der Pivotspalte.

  • $q = q_2$

Die Basisvariable $x_i$ für die $q_2 = -\frac{\kappa_s - b_s}{a_{st}}$ gilt, wird in der betrachteten Pivotzeile durch $x_i = \kappa_i - \overline{x_i}$ ersetzt und verlässt die Basis (wird zur Nichtbasisvariablen). Es wird wie üblich der Simplexalgorithmus angewandt. Danach geht es weiter bei 1. Wahl der Pivotspalte.

  • $q = \kappa_t$

Die Nichtbasisvariable $x_t$ wird in der betrachteten Pivotspalte durch $x_t = \kappa_t - \overline{x_t}$ ersetzt. Sie erhält den Wert Null in der Zielfunktionszeile. Es erfolgt kein Basistausch und damit auch keine Tableautransformation. Es geht weiter bei 1.Wahl der Pivotspalte.

Anwendungsbeispiel: Obere Schranken

Gegeben sei das folgende Optimierungsproblem:

$f(x_1, x_2) = 2x_1 + 3x_2$    $\rightarrow$  max!

u.d.N.

$x_1 + 2x_2 \le 100$

$x_1 + x_2 \le 75$

$x_1          \le 45$

          $x_2 \le 30$

$x_1, x_2 \ge 0$

In dem obigen Optimierungsproblem (Standardform), sind die Variablen $x_1$ und $x_2$ nach oben beschränkt:

$x_1 \le 45$ und $x_2 \le 30$.

Es wird nun gezeigt, wie man diese oberen Schranken berücksichtigen kann. Es ist auch möglich das LP durch Einfügen von Schlupfvariablen zu lösen, indem die oberen Schranken ebenfalls als Nebenbedingungen eingehen (so wie in den vorangegangenen Kapiteln erlernt). Allerdings gibt es häufig LP's mit mehreren Variablen, wenn diese alle obere Schranken aufweisen, dann müssen eine Menge an Nebenbedingungen berücksichtigt werden und der Rechenaufwand ist dann sehr hoch (siehe folgenden Abschnitt).

Das Problem wird nun mittels der Vorgehensweise der oberen Schranken bestimmt. Dabei werden die oberen Schranken nicht als Nebenbedingungen in das Tableau eingehen. Zunächst wird die Normalform benötigt (Einfügen von Schlupfvariablen):

$f(x_1, x_2) = 2x_1 + 3x_2$    $\rightarrow$  max!

u.d.N.

$x_1 + 2x_2 + x_3            = 100$

$x_1 + x_2            + x_4   = 75$

$x_1          \le 45$

          $x_2 \le 30$

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

Es existieren bei dieser Vorgehensweise zwei Nebenbedingungen (die oberen Schranken werden nicht als Nebenbedingung berücksichtigt). Das Tableau sieht wie folgt aus:

Obere Schranken primales Simplexverfahren

1. Schritt:  Auswahl der Pivotspalte (wie beim primalen Simplexverfahren), indem der kleinste negative Wert in der Zielfunktionszeile ausgewählt wird, hier: $-3$. Die zur Pivotspalte zugehörige Variable wird $x_t$. Diese Variable ist $x_2 = x_t$. Die zugehörige obere Schranken ist $\kappa_2 = 30$ (siehe Optimierungsproblem).

2. Schritt: Auswahl der Pivotspalte wie folgt (nicht mehr wie beim primalen Simplexverfahren):

$q_1 := \{ min \{\frac{b_i}{a_{it}} \}  \; \text{mit} \; a_{it} > 0 \; , \; \text{sonst} \; \infty \}$

$q_2 := \{ min \{-\frac{\kappa_i - b_i}{a_{it}} \}  \; \text{mit} \; a_{it} < 0 \; , \; \text{sonst} \; \infty \}$.

Dabei werden für $q_1$ alle Koeffizienten größer als Null der Pivotspalte betrachtet. Es werden dann die zugehörigen Werte der rechten Seite durch diese Koeffizienten geteilt und das Minimum dieser Quotienten gewählt. Exsitiert kein Koeffizient größer als Null, so wird $q_1 = \infty$ gesetzt.

Methode

$q_1 = min \{\frac{100}{2}, \frac{75}{1} \} = 50$


Für $q_2$ werden alle Koeffizienten kleiner als Null der Pivotspalte betrachtet. Existiert kein Koeffizient kleiner als Null, so wird $q_2 = \infty$ gesetzt.

Methode

$q_2 = \infty$.


3. Schritt: Es wird dann das Minimum aus $q_1, q_2$ und $\kappa_2$ gewählt:

$q = min \{q_1, q_2, \kappa_2 \} = min \{50, \infty, 30 \} = 30$

Das bedeutet, dass $q = \kappa_2 = 30$ ist. Es gilt also der Fall 

  • $q = \kappa_2$

Die Nichtbasisvariable $x_t = x_2$ wird durch $x_2 = \kappa_2 - \overline{x_t} = 30 - \overline{x}_2$ in der betrachten Spalte ersetzt. Sie erhält den Wert Null (bleibt also Nichtbasisvariable). Dazu wird das aktuelle lineare Optimierungsmodell herangezogen und für $x_2$ überall $30 - \overline{x}_2$ eingesetzt. Die Pivotspalte im Tableau betrifft die Zielfunktion und die Nebenbedingungen. Für $x_2$ muss also im gesamten Optimierungsproblem $30 - \overline{x}_2$ ersetzt werden. Das aktuelle Optimierungsproblem wird aus dem letzten Tableau abgelesen:

$f(x_1, \overline{x_2}) = 2x_1 + 3 (30 - \overline{x}_2)$    $\rightarrow$  max!

u.d.N.

$x_1 + 2 (30 - \overline{x}_2) + x_3            = 100$

$x_1 + 30 - \overline{x}_2            + x_4   = 75$

$x_1          \le 45$

$30 - \overline{x}_2 \le 30$

$x_1, \overline{x}_2, x_3, x_4 \ge 0$

Klammern auflösen und in den Nebenbedingungen die Werte ohne Variablen auf die rechte Seite bringen:

$f(x_1, \overline{x}_2) = 2x_1 - 3\overline{x}_2 + 90$    $\rightarrow$  max!

u.d.N.

$x_1 - 2\overline{x}_2 + x_3            = 40$

$x_1 - \overline{x}_2            + x_4   = 45$

$x_1          \le 45$

$\overline{x_2} =  0$

$x_1, x_3, x_4 \ge 0$

Das neue Problem wieder in ein Simplextableau eintragen:

Obere Schranken primales Simplexverfahren

Das neue Problem ist in das obige Tableau eingefügt worden. Es ist deutlich zu erkennen, dass sich nur die Pivotspalte verändert hat. Nicht vergessen, die Werte der Zielfunktion müssen mit umgekehrten Vorzeichen berücksichtigt werden. Die 90 Zielfunktionswert resultieren daher, dass für $x_1 = 0$ (Nichtbasisvariable) und für $\overline{x}_2 = 0$ (Nichtbasisvariable) mit $x_2 = 30 - \overline{x}_2 = 30 - 0 = 30$ in die Ausgangszielfunktion eingesetzt wird:

$f(x_1, x_2) = 2x_1 + 3 x_2  = 2 \cdot 0 + 3 \cdot 30 = 90$

Es wird nun wieder bei Schritt 1: Auswahl der Pivotspalte begonnen.

1. Schritt: Auswahl der Pivotspalte: Die Pivotspalte ist wieder diejenige mit dem kleinsten negativen Wert der Zielfunktionszeile. In diesem Fall nun $-2$. Die dazugehörige Variable ist $x_t = x_1$. Diese besitzt eine obere Schranke von $\kappa_1 = 45$.

2. Schritt: Auswahl der Pivotzeile: Berechnung von $q_1$ und $q_2$.

$q_1 = min \{\frac{40}{1}, \frac{45}{1} \} = 40$

$q_2 = \infty$  Keine negativen Koeffizienten in der Pivotspalte gegeben.

Bestimmung von $q$:

$q = min \{q_1, q_2, \kappa_1 \} = min \{40, \infty, 45 \} = 40$

Es gilt der Fall:

  • $q = q_1$:

Die Basisvariable für die $q_1 = \frac{40}{1} = 40$ gilt, verlässt die Basis (wird zur Nichtbasisvariablen). Es handelt sich hierbei um die Basisvariable $x_3$, die mit der Nichtbasisvariable $x_t = x_1$ getauscht wird (Pivotelement ist dabei $1$). Es wird wie üblich der Simplexalgorithmus angewandt. Danach geht es weiter bei 1. Wahl der Pivotspalte:

Obere Schranken primales Simplexverfahren

Nach Anwendung des Simplexalgorithmus ist noch ein negative Wert $-1$ in der Zielfunktionszeile vorhanden. Das bedeutet, dass hier noch ein weiterer Schritt der oberen Schranken durchgeführt werden muss. Der Zielfunktionswert von $170$ ergibt sich durch Einsetzen von $x_1 = 40$ und $\overline{x}_2 = 0$ mit $x_2 = 30 - \overline{x}_2 = 30 - 0 = 30$ in die Ausgangszielfunktion:

$f(x_1, x_2) = 2x_1 + 3 x_2  = 2 \cdot 40 + 3 \cdot 30 = 170$

1. Schritt: Wahl der Pivotspalte: Kleinster negativer Wert, hier $-1$. Die dazugehörige Variable ist $x_t = \overline{x}_2$. Die dazugehörige obere Schranke ist gleich der Schranke für $x_2$: $\kappa_2 = 35$.

2. Schritt: Wahl der Pivotspalte: Bestimmung von $q_1$ und $q_2$.

$q_1 = min \{\frac{5}{1} \} = 5$


Für $q_2$ wird nun wie folgt vorgegangen. Da negative Koeffizienten in der Pivotspalte vorhanden sind, muss das Minimum aus folgender Formel gebildet werden: $\frac{-\kappa_i - b_i}{a_{it}}$. Dabei ist $\kappa_i$ die obere Schranke der Basisvariable der gerade betrachteten Zeile. Und $b_i$ der Wert der rechten Seite der Basisvariable der gerade betrachteten Zeile. $a_{it}$ demnach der Koeffizient der gerade betrachteten Zeile in der Pivotspalte:

$q_2 = min \{ -\frac{45 - 40}{-2} \} = 2,5$

Die obere Schranke $\kappa_i = 45$ gehört zur Basisvariablen $x_1$. Denn der negative Koeffizient $a_{1t} = -2$ der Pivotspalte steht in der Zeile der Basisvariablen $x_1$. Demnach wird die obere Schranke von $x_1$ gewählt $\kappa_1 = 45$ und der Wert der rechten Seite $b_1 = 40$ der Basisvariablen $x_1$.

Es muss als nächstes $q$ bestimmt werden:

$q = min \{5, 2,5, 45 \} = 2,5$

Es gilt demnach der Fall:

  • $q = q_2$
  • $q = q_2$

Die Basisvariable $x_i$ für die $q_2 = -\frac{\kappa_i - b_i}{a_{it}}$ gilt, wird durch $x_i = \kappa_i - \overline{x_i}$ ersetzt und verlässt die Basis (wird zur Nichtbasisvariablen). Es wird wie üblich der Simplexalgorithmus angewandt. Danach geht es weiter bei 1. Wahl der Pivotspalte.

Die Basisvariable für die $q_2 =  -\frac{\kappa_i - b_i}{a_{it}} = 2,5$ gilt ist $x_1$. Diese wird in der betrachteten Zeile ersetzt durch: $x_1 = 45 - \overline{x}_1$ und wird zur Nichtbasisvariablen. Dafür geht dann $\overline{x}_2$ in die Basis und es wird wieder ein Simplexschritt durchgeführt. Zunächst muss nun aber in das aktuelle lineare Optimierungsproblem für $x_1 = 45 - \overline{x}_1$ eingesetzt werden, dieses mal muss aber nur die Zeile ersetzt werden. Diese entspricht der 1. Nebenbedingung im aktuellen Optimierungsproblem (dem Tableau zu entnehmen):

Methode

NB : $x_3 - 2x_2 + x_1 = 40$

Einsetzen von $x_1 = 45 - \overline{x}_1$ in diese Nebenbedingung:

$x_3 - 2x_2 + 45 - \overline{x}_1 = 40$

Umstellen:

$x_3 - 2x_2 - \overline{x}_1 = -5$

Mit $-1$ multiplizieren, damit die rechte Seite positiv wird:

$-x_3 + 2x_2 + \overline{x}_1 = 5$

Diese Zeile im obigen Tableau austauschen:

Obere Schranken primales Simplexverfahren

Die betrachtete Variable $\overline{x}_1$ wechselt aus der Basis in die Nichtbasis. Dafür geht dann die Nichtbasisvariable der Pivotspalte $\overline{x}_2$ in die Basis und es wird ein weiterer Simplexschritt durchgeführt (Pivotspalte bei $\overline{x}_2$ und Pivotzeile bei $\overline{x}_1$, Pivotelement bei $2$):

Obere Schranken primales Simplexverfahren

Es liegt die optimale Lösung vor, da keine negativen Werte in der Zielfunktionszeile mehr auftauchen. Es gilt $\overline{x}_1 = 0$ und $\overline{x}_2 = 2,5$ mit $x_1 = 45 - \overline{x}_1 = 45$ und $x_2 = 30 - \overline{x}_2 = 27,5$ ergibt sich demnach:

Methode

$f(x_1, x_2) = 2 \cdot 45 + 3 \cdot 27,5 = 172,5$

Die Vorgehensweise ist für zwei nach oben beschränkte Variablen nicht zu empfehlen, da diese sehr aufwendig ist. Bei zwei nach oben beschränkten Variablen sollte in jedem Fall noch der primale Simplexalgorithmus angewandt werden (siehe folgenden Abschnitt). Erst bei einer Vielzahl an beschränkten Variablen lohnt sich diese Vorgehensweise. 

Merke

Diese Vorgehensweise kann auch auf den dualen Simplexalgorithmus sowie auch die Big-M-Methode angewandt werden.

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