Obere Schranken

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

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 mit dem dazugehörigen (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:

Das in der Formel verwendete ist die obere Schranke für die Basisvariable in der -ten Zeile. Das in der Formel angesetzt ist zugleich der Wert der Basisvariable .

Es gilt weiterhin

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

• :

Die Basisvariable für die gilt, 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 gilt, wird in der betrachteten Pivotzeile durch  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 Nichtbasisvariable wird in der betrachteten Pivotspalte durch  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:

     max!

u.d.N.

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

und .

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):

     max!

u.d.N.

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

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

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

.

Dabei werden für 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 gesetzt.

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

3. Schritt: Es wird dann das Minimum aus und gewählt:

Das bedeutet, dass ist. Es gilt also der Fall 

Die Nichtbasisvariable wird durch in der betrachten Spalte ersetzt. Sie erhält den Wert Null (bleibt also Nichtbasisvariable). Dazu wird das aktuelle lineare Optimierungsmodell herangezogen und für überall eingesetzt. Die Pivotspalte im Tableau betrifft die Zielfunktion und die Nebenbedingungen. Für muss also im gesamten Optimierungsproblem ersetzt werden. Das aktuelle Optimierungsproblem wird aus dem letzten Tableau abgelesen:

     max!

u.d.N.

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

     max!

u.d.N.

Das neue Problem wieder in ein Simplextableau eintragen:

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 (Nichtbasisvariable) und für (Nichtbasisvariable) mit in die Ausgangszielfunktion eingesetzt wird:

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 . Die dazugehörige Variable ist . Diese besitzt eine obere Schranke von .

2. Schritt: Auswahl der Pivotzeile: Berechnung von und .

 Keine negativen Koeffizienten in der Pivotspalte gegeben.

Bestimmung von :

Es gilt der Fall:

• :

Die Basisvariable für die gilt, verlässt die Basis (wird zur Nichtbasisvariablen). Es handelt sich hierbei um die Basisvariable , die mit der Nichtbasisvariable getauscht wird (Pivotelement ist dabei ). Es wird wie üblich der Simplexalgorithmus angewandt. Danach geht es weiter bei 1. Wahl der Pivotspalte:

Nach Anwendung des Simplexalgorithmus ist noch ein negative Wert in der Zielfunktionszeile vorhanden. Das bedeutet, dass hier noch ein weiterer Schritt der oberen Schranken durchgeführt werden muss. Der Zielfunktionswert von ergibt sich durch Einsetzen von und mit in die Ausgangszielfunktion:

1. Schritt: Wahl der Pivotspalte: Kleinster negativer Wert, hier . Die dazugehörige Variable ist . Die dazugehörige obere Schranke ist gleich der Schranke für : .

2. Schritt: Wahl der Pivotspalte: Bestimmung von und .

Für wird nun wie folgt vorgegangen. Da negative Koeffizienten in der Pivotspalte vorhanden sind, muss das Minimum aus folgender Formel gebildet werden: . Dabei ist die obere Schranke der Basisvariable der gerade betrachteten Zeile. Und der Wert der rechten Seite der Basisvariable der gerade betrachteten Zeile. demnach der Koeffizient der gerade betrachteten Zeile in der Pivotspalte:

Die obere Schranke gehört zur Basisvariablen . Denn der negative Koeffizient der Pivotspalte steht in der Zeile der Basisvariablen . Demnach wird die obere Schranke von gewählt und der Wert der rechten Seite der Basisvariablen .

Es muss als nächstes bestimmt werden:

Es gilt demnach der Fall:

Die Basisvariable für die gilt, wird durch  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 gilt ist . Diese wird in der betrachteten Zeile ersetzt durch: und wird zur Nichtbasisvariablen. Dafür geht dann in die Basis und es wird wieder ein Simplexschritt durchgeführt. Zunächst muss nun aber in das aktuelle lineare Optimierungsproblem für eingesetzt werden, dieses mal muss aber nur die Zeile ersetzt werden. Diese entspricht der 1. Nebenbedingung im aktuellen Optimierungsproblem (dem Tableau zu entnehmen):

Einsetzen von in diese Nebenbedingung:

Umstellen:

Mit multiplizieren, damit die rechte Seite positiv wird:

Diese Zeile im obigen Tableau austauschen:

Die betrachtete Variable wechselt aus der Basis in die Nichtbasis. Dafür geht dann die Nichtbasisvariable der Pivotspalte in die Basis und es wird ein weiterer Simplexschritt durchgeführt (Pivotspalte bei und Pivotzeile bei , Pivotelement bei ):

Es liegt die optimale Lösung vor, da keine negativen Werte in der Zielfunktionszeile mehr auftauchen. Es gilt und mit und ergibt sich demnach:

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.