ZU DEN KURSEN!

Operations Research 1 - Obere Schranken

Kursangebot | Operations Research 1 | Obere Schranken

Operations Research 1

Obere Schranken

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

Hier klicken zum Ausklappen

$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

Hier klicken zum Ausklappen

$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

Hier klicken zum Ausklappen

$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

Hier klicken zum Ausklappen

$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

Hier klicken zum Ausklappen

$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

Hier klicken zum Ausklappen

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

Hier klicken zum Ausklappen

$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

Hier klicken zum Ausklappen

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