Obere Schranken: Vielzahl an beschränkten Variablen

In diesem Abschnitt soll jetzt ein lineares Optimierungsproblem gegeben sein, bei welchem eine Vielzahl an Variablen vorliegen, die obere Schranken aufweisen. Hier ist es ratsam nach dem Verfahren der oberen Schranken vorzugehen (siehe Abschnitt: Obere Schranken).

Gegeben sei das folgende Optimierungsproblem:

   max!

u.d.N.

Das obige lineare Optimierungsproblem ist in Standardform gegeben. Die Werte der rechten Seite sind alle positiv (kanonische Form). Es kann demnach das aus dem Abschnitt Obere Schranken gezeigte Verfahren angewandt werden, um die optimale Lösung zu bestimmen. Es ist auch möglich das primale Simplexverfahren durchzuführen. Die Anzahl der Nebenbedingungen beträgt dann aber 6 und die Bestimmung der optimalen Lösung ist sehr rechenaufwendig. Es wird im weiteren das Verfahren der oberen Schranken angewandt.

Zunächst muss das Optimierungsprroblem in Normalform überführt werden. Dazu werden die Schlupfvariablen eingefügt. Die oberen Schranken bleiben hierbei bestehen:

   max!

u.d.N.

Eintragen in das Simplextableau ergibt:

Mittels der Iterationschritte für obere Schranken besitzt das Tableau nur 2 Nebenbedingungen. Die Berechnung wird wie folgt durchgeführt:

1. Schritt. Wahl der Pivotspalte. Kleinster negativer Wert in der Zielfunktionszeile. Hier . Setzen von mit der Beschränkung .

2. Schritt: Wahl der Pivotzeile. Es wird und bestimmt.

Kein negativer Koeffizient in der Pivotspalte vorhanden.

Bestimmung von

Es gilt der Fall:

Es wird nun die gesamte Spalte ersetzt durch . Es wird das aktuelle lineare Optimierungsproblem (siehe Tableau) herangezogen. Die Spalte betrifft alle Nebenbedingungen und die Zielfunktion, weshalb das komplette Optimierungsmodell durch  ersetzt werden muss. 

   max!

u.d.N.

Auflösen der Klammern und bei den Nebenbedingungen die Werte ohne Variablen auf die rechte Seite bringen:

   max!

u.d.N.

Eintragen in das Tableau:

Der Zielfunktionswert von resultiert, weil (Nichtbasisvariablen) unter Berücksichtigung von . Einsetzen in die Ausgangszielfunktion ergibt:

Es wird nun wieder von vorne begonnen.

1. Schritt: Wahl der Pivotspalte. Der kleinste negative Wert ist . mit

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

 Kein negativer Koeffizient in der Pivotspalte.

Bestimmung von

Es gilt der Fall:

• :

Es wird nun die Basisvariable betrachtet, für die gilt. Dies ist . Diese Basisvariable verlässt die Basis und wird zur Nichtbasisvariablen. Der Tausch erfolgt mit . Es wird zudem ein Simplexschritt durchgeführt:

Der Zielfunktionswert ist berechnet worden durch: , mit also und :

1. Schritt: Wahl der Pivotspalte. Es existieren zwei kleinste Werte. Es kann einer beliebig gewählt werden. Es wird der Wert gewählt für welchen gilt mit .

2. Schritt: Wahl der Pivotzeile. Es werden und berechnet.

 Es existieren keine negative Koeffizienten in der Pivotspalte.

Es wird bestimmt:

. 

Es gelten nun zwei Fälle. Gewählt wird der Fall 2.

Es wird nun für die Basisvariable die gesamte Spalte ausgetauscht durch . Dabei muss das aktuelle Optimierungsmodell herangezogen werden (siehe Tableau):

ZF:     (mit umkehrten Vorzeichen berücksichtigen)

NB:

Einsetzen von :

ZF:   

NB:

Zusammenfassen:

ZF:   

NB:

Einfügen in das Tableau:

Es ist deutlich zu erkennen, dass sich nur die Spalte verändert hat, in der sich vorher und jetzt befindet. Der neue Zielfunktionswert ergibt sich durch: , und wobei und . Einsetzen in die Ausgangszielfunktion ergibt:

1. Schritt: Wahl der Pivotspalte. Es existiert noch ein negativer Wert in der Zielfunktionszeile: mit und .

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

Bestimmung von :

Es gilt der Fall:

• :

Es wird nun die Basisvariable für die zur Basisvariablen. Hierbei handelt es sich um . Der Tausch findet mit der Nichtbasisvariablen der Pivotspalte statt, also mit . Es wird zudem ein Simplexschritt durchgeführt:

Es liegt die Optimallösung vor, da keine negative Werte mehr in der Zielfunktionszeile gegeben sind. Die Optimallösung beträgt:

, , und . Dabei gilt und . Einsetzen in die Ausgangszielfunktion ergibt:

Das Problem kann auch mittels primalen Simplex gelöst werden. Dann aber werden die oberen Schranken mit als Nebenbedingungen berücksichtigt. Es ergeben sich dann statt 2 ingesamt 6 Schlupfvariablen:

Es kann hier der primale Simplexalgorithmus angewandt werden. Am Ende resultiert das selbe Ergebnis. Es ist aber auch deutlich zu erkennen, dass durch die Anzahl der Nebenbedingungen ein hoher Rechenaufwand gegeben ist. Nach 4 Iterationen ist die optimale Lösung gegeben.