Beispiel: Sensitivitätsanalyse Zielfunktionskoeffizienten

In diesem Abschnitt folgt ein Beispiel zur Sensitivitätsanalyse der Zielfunktionskoeffizienten. In welchem Bereich dürfen die Koeffizienten der Zielfunktion liegen, damit die optimale Basislösung ihre Optimalitätseigenschaft nicht verliert? Das bedeutet also, dass kein weiterer Basistausch bzw. Simplexschritt notwendig ist, um zur optimalen Lösung zu gelangen. Gegeben sei das folgende lineare Optimierungsproblem:

$f(x_1, x_2) = 15 x_1 + 25 x_2$     $\rightarrow $  max!

u.d.N.

$x_1 + x_2 \le 115$

$5x_1 + 8 x_2 \le 700$

                $x_2 \le 65$

$x_1, x_2 \ge 0$

Das Problem ist in Standardform gegeben. Es wird nun in die Normalform umgeformt und dann in das Simplextableau eingetragen:

$f(x_1, x_2) = 15 x_1 + 25 x_2$     $\rightarrow $  max!

u.d.N.

$x_1 + x_2  + x_3                     \le 115$

$5x_1 + 8 x_2       + x_4            \le 700$

                $x_2            + x_5    \le 65$

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

Es wird hier der primale Simplexalgorithmus angewandt (Werte der rechten Seite sind positiv). Nach zwei Simplexschritten steht das Optimaltableau (Werte der Zielfunktionszeile sind positiv):

Es wird als nächstes die Sensitivitätsanalyse für die Zielfunktionswerte durchgeführt. Zunächst werden die im Ausgangstableau befindlichen Nichtbasisvariablen untersucht. 

1. Zunächst sind die Nichtbasisvariablen aus dem Ausgangstableau und die dazugehörigen Zielfunktionskoeffizienten zu bestimmen:

$c_1 = 15$   für $x_1$

$c_2 = 25$    für $x_2$.

2. Danach wird geschaut wo sich die Variablen im Optimaltableau befinden. $x_1$ und $x_2$ sind im Optimaltableau Basisvariablen. Die Berechnung wird wie folgt durchgeführt:

$c_j^- := \{ min \{\frac{c_j^*}{a_{ij}^*} \} \; \text{mit} \; a_{ij}^* > 0 \; \text{sonst} \; \infty \}$

$c_j^+ := \{ min \{-\frac{c_j^*}{a_{ij}^*} \} \; \text{mit} \; a_{ij}^* < 0 \; \text{sonst} \; \infty \}$

• $x_1$:

$c_1^- := min \{\frac{3}{\frac{1}{5}} \} = 15$

Für $c_1^-$ werden alle Koeffizienten $a_{2j}^*$ in dem Optimaltableau betrachtet, welche sich in der Zeile von $x_1$ befinden (Zeile $i = 2$). Es werden dabei nur Koeffizienten größer als Null betrachtet. Der dazugehörige Zielfunktionswert $c_j^*$ (Optimaltableau) wird dann herangezogen und der Quotient gebildet. Bei mehreren Koeffizienten größer als Null wird das Minimum der Quotienten gewählt. Sind keine Koeffizienten größer als Null vorhanden, so wird $c_1^- = \infty$ gesetzt.
 

$c_2^+ = min \{-\frac{1}{-\frac{8}{5}} \} = \frac{5}{8}$

Für $c_1^+$ werden alle Koeffizienten $a_{2j}^*$ in dem Optimaltableau betrachtet, welche sich in der Zeile von $x_1$ befinden (Zeile $i = 2$). Es werden dabei nur Koeffizienten kleiner als Null betrachtet. Der dazugehörige Zielfunktionswert $c_j^*$ (Optimaltableau) wird dann herangezogen und der Quotient gebildet (mit negativen Vorzeichen, so dass ein positiver Quotient resultiert). Bei mehreren Koeffizienten kleiner als Null wird das Minimum der Quotienten gewählt. Sind keine Koeffizienten kleiner als Null vorhanden, so wird $c_1^+ = \infty$ gesetzt.

Der Schwankungsbereich wird dann mittels folgendem Intervall bestimmt:

$[c_j - c_k^- \; , \; c_j + c_k^+]$    

Einsetzen der Werte, wobei $c_j$ der Zielfunktionswert im Ausgangstableau darstellt (hier: $c_1 = 15$):

$[15 - 15\; , \; 15 + \frac{5}{8}]$    

Der Zielfunktionswert $c_1$ darf im Ausgangstableau die Werte von 0 bis 40 annehmen, ohne dass die Basislösung die Optimalitätseigenschaft verliert, d.h. also ohne dass ein Basistausch erforderlich wird.

• $x_2$:

$c_2^- := min \{\frac{1}{1} \} = 1$

$c_2^+ = \infty$  Es existieren keine Koeffizienten kleiner als Null ($a_{3j}^* < 0$) in der Zeile, wo sich $x_2$ befindet.

Der Schwankungsbereich ergibt sich durch:

$[25 - 1\; , \; 25 + \infty]$    

Der Zielfunktionswert $c_1$ darf im Ausgangstableau die Werte ab 24 annehmen, ohne dass die Basislösung die Optimalitätseigenschaft verliert, d.h. also ohne dass ein Basistausch erforderlich wird.

Es befindet sich am Ende noch eine Schlupfvariable in der Basis. Auch für diese kann nun ein Schwankungsbereich ermittelt werden.

• $x_3$:

$c_3^- := min \{\frac{1}{\frac{3}{5}} \} = \frac{5}{3}$

$c_2^+ = min \{-\frac{3}{-\frac{1}{5}} \} = 15$

Der Schwankungsbereich ergibt sich durch:

$[0 - \frac{5}{3} \; , \; 0 + 15]$    

Der Zielfunktionswert einer Schlupfvariable geht immer mit dem Wert Null in die Zielfunktion ein. Der Zielfunktionswert der Schlupfvariable $x_3$ kann aber zwischen -$\frac{5}{3}$ und 15 schwanken,  ohne dass die Basislösung die Optimalitätseigenschaft verliert, d.h. also ohne dass ein Basistausch erforderlich wird.

Optimalitätseigenschaft

Es soll gezeigt werden, dass die Optimalitätseigenschaft nicht verletzt wird, bei Variation der Zielfunktionskoeffizienten in den oben bestimmten Bereichen. Hierzu wird zunächst $x_1$ herangezogen:

$[0 \; , \; \frac{125}{8}] \in c_1$    

Es kann nun ein Wert von 0 bis $\frac{125}{8}$ für das Ausgangstableau verwendet werden, ohne dass sich das Optimaltableau verändert und damit die optimale Lösung. Es wird nun hier die oberste Grenze gewählt $c_1 = \frac{125}{8}$. Das Anfangstableau sieht dann wie folgt aus:

Die Zielfunktionswerte gehen in das Ausgangstableau immer mit dem umgekehrten Vorzeichen ein. Es wird nun also der Zielfunktionswert $c_1$ variiert, wobei alle anderen Werte konstant gehalten werden. Es wird  nun das primale Simplexverfahren solange angewendet, bis die Werte der Zielfunktionszeile positiv sind. Dann ist die Optimallösung und das Optimaltableau gegeben:

Es ist deutlich zu erkennen, dass trotz Änderung des Zielfunktionswertes $c_1$ in der Zielfunktionszeile des Ausgangstableaus, die Werte der Basisvariablen, die Werte der Koeffizienten in der Mitte des Tableaus und die Position der Variablen keine Änderung erfahren haben. Das Optimaltableau hat dieselbe Form, wie das obige Optimaltableau (ohne Variation). Man sieht auch deutlich, dass $c_2^* = 0$. Würde man den Zielfunktionswert $c_1$ also noch weiter erhöhen, so würde $c_2^* < 0$ und damit wäre die Optimallösung nicht mehr gegeben (negativer Wert in der Zielfunktionszeile). Das bedeutet, es müsste ein erneuter Simplexschritt durchgeführt werden, um die Optimalitätseigenschaft wieder herzustellen. 

Im Weiteren wird $x_2$ mit dem Schwankungsbereich $[24 \; , \; \infty] \in c_2$  betrachtet. Hierbei können alle Werte ab 24 für das Ausgangstableau verwendet werden, ohne dass sich die Struktur des Optimaltableaus verändert. Es wird spontan der Wert $200$ gewählt. Das Tableau wird aufgestellt und die Simplexschritte durchgeführt. Es ergibt sich:

Auch hier entspricht das Optimaltableau wieder dem ohne Variation der Zielfunktionskoeffizienten. 

Es wird als letztes noch die Schlupfvariable $x_3$ betrachtet, deren Zielfunktionswert ebenfalls einem Schwankungsbereich unterliegt. In diesem Beispiel $[- \frac{5}{3} \; , \; 15] \in c_3$. Es wird die obere Schranke von $15$ gewählt:

Auch hier ist die Struktur des Optimaltableaus wieder gegeben. Die Basisvariablen und auch die Werte der Basisvariablen (rechte Seite) sind unverändert. Es ist auch deutlich zu erkennen, dass bei einer Erhöhung des Zielfunktionswertes im Ausgangstableaus von $c_3$ der Zielfunktionswert im Endtableau von $c_1^*$ negativ werden würde (für $c_3 = 16$ würde beim Simplexschritt dann aus der $0$ bei $c_1^*$ eine -1). Das würde bedeuten, dass die Optimalitätseigenschaft hier nicht mehr gegeben ist. Um ein Optimaltableau zu erhalten, müsste dann ein erneuter Simplexschritt durchgeführt werden.