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:
max!
u.d.N.
Das Problem ist in Standardform gegeben. Es wird nun in die Normalform umgeformt und dann in das Simplextableau eingetragen:
max!
u.d.N.
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:
für
für .
Merke
Hier klicken zum AusklappenNicht vergessen. Die Zielfunktionskoeffizienten sind im Ausgangstableau mit ihren umgekehrten Vorzeichen eingetragen. Es werden aber immer die Ausgangszielfunktionskoeffizienten gesucht, wie sie im linearen Optimierungsproblem gegeben sind.
2. Danach wird geschaut wo sich die Variablen im Optimaltableau befinden. und sind im Optimaltableau Basisvariablen. Die Berechnung wird wie folgt durchgeführt:
Für werden alle Koeffizienten in dem Optimaltableau betrachtet, welche sich in der Zeile von befinden (Zeile ). Es werden dabei nur Koeffizienten größer als Null betrachtet. Der dazugehörige Zielfunktionswert (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 gesetzt.
Für werden alle Koeffizienten in dem Optimaltableau betrachtet, welche sich in der Zeile von befinden (Zeile ). Es werden dabei nur Koeffizienten kleiner als Null betrachtet. Der dazugehörige Zielfunktionswert (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 gesetzt.
Der Schwankungsbereich wird dann mittels folgendem Intervall bestimmt:
Einsetzen der Werte, wobei der Zielfunktionswert im Ausgangstableau darstellt (hier: ):
Methode
Hier klicken zum Ausklappen
Der Zielfunktionswert 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.
Es existieren keine Koeffizienten kleiner als Null () in der Zeile, wo sich befindet.
Der Schwankungsbereich ergibt sich durch:
Methode
Hier klicken zum Ausklappen
Der Zielfunktionswert 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.
Der Schwankungsbereich ergibt sich durch:
Methode
Hier klicken zum Ausklappen
Der Zielfunktionswert einer Schlupfvariable geht immer mit dem Wert Null in die Zielfunktion ein. Der Zielfunktionswert der Schlupfvariable kann aber zwischen - 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 herangezogen:
Es kann nun ein Wert von 0 bis 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 . 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 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 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 . Würde man den Zielfunktionswert also noch weiter erhöhen, so würde 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 mit dem Schwankungsbereich 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 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 betrachtet, deren Zielfunktionswert ebenfalls einem Schwankungsbereich unterliegt. In diesem Beispiel . Es wird die obere Schranke von 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 der Zielfunktionswert im Endtableau von negativ werden würde (für würde beim Simplexschritt dann aus der bei 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.
Merke
Hier klicken zum AusklappenEs wurde gezeigt, dass die Variation des Zielfunktionswertes
im Ausgangstableau zu keiner Änderung der rechten Seiten und keiner Änderung der Position der Basisvariablen führt. Bei der Berechnung der Schwankungen, werden diese immer für das Ausgangstableau bestimmt. Das lineare Optimierungsmodell selber wird nicht verändert. Es soll mithilfe der Sensitivitätsanalyse nur gezeigt werden, dass die Struktur des Optimaltableaus durch Variation der Koeffizienten im Ausgangstableau erhalten bleibt (wenn ein bestimmter Bereich eingehalten wird). Wird dieser Bereich unterschritten oder überschritten, so ist das Optimaltableau nicht mehr gegeben, weil die Zielfunktionswerte im Endtableau dann negative Werte annehmen und ein erneuter Simplexschritt notwendig wäre, um die Optimalitätseigenschaft wieder herzustellen.
