Kursangebot | Operations Research | Änderung der Restriktionen

Operations Research

Änderung der Restriktionen

In diesem Abschnitt geht es nun darum, die Koeffizienten $b_i$ der rechten Seite so zu variieren, dass die optimale Lösung ihre Optimalitätseigenschaft nicht verliert. Das bedeutet also, bei Variation der Werte der rechten Seite im Ausgangstableau, ergibt sich im Optimaltableau keine Änderung des Zielfunktionswertes. Die Werte der rechten Seite verändern sich zwar, aber Ende wird die Variation der Werte der rechten Seite keine Änderung des Zielfunktionswertes ergeben.

Es sei das Optimierungsproblem aus dem vorangegangenen Abschnitt gegeben:

$f(x_1, x_2, x_3) = -400x_1 + 780x_2 + 1.250 x_3 $   $\rightarrow $ max!


u.d.N.

$32 x_1 + 42 x_2 + 20 x_3   + x_4                       \le 1.300$

$-10 x_1 + 15 x_2 + 25 x_3           + x_5              \le 1.000$

$8x_1 + 8x_2 + 5 x_3                             + x_6    \le 300$

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

Vorgehensweise: Sensitivitätsanalyse rechte Seite

1. Es wird zunächst das Ausgangstableau betrachtet:

Sensitivitätsanalyse Restriktionen

Die Werte der rechten Seite im Ausgangstableau $b_i$ werden wie folgt definiert:

$b_1 = 1.300$   

$b_2 = 1.000$     

$b_3 = 300$.

Die zu den Werten der rechten Seite zugehörigen Variablen $x_j$ sind:

$x_4$ für $b_1$,

$x_5$ für $b_2$,

$x_5$ für $b_3$.

2. Danach wird das Optimaltableau herangezogen:

Sensitivitätsanalyse Restriktionen

Es wird nun geschaut, wo sich die im Ausgangstableau befindlichen Basisvariablen ($x_4, x_5, x_6$) im Optimaltableau befinden. Im Optimaltableau stellt $x_4$ eine Basisvariablen dar, $x_5$ und $x_6$ hingegen sind Nichtbasisvariable. Es muss nun bei der Berechnung unterschieden werden zwischen Basisvariablen und Nichtbasisvariablen:

Basisvariablen

Ist die im Ausgangstableau befindliche Basisvariable im Optimaltableau ebenfalls eine Basisvariable, so muss folgende Berechnung durchgeführt werden:

Methode

$b_i^- = b_i^*$

$b_i^+ = \infty$

Nichtbasisvariablen

Ist die im Ausgangstableau befindliche Basisvariable im Optimaltableau eine Nichtbasisvariable, so muss folgende Berechnung durchgeführt werden:

Methode

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

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

mit

$b_i^*$ Werte der rechten Seite im Optimaltableau 

$a_{ij}^* $ Koeffizient der Spalte, wo sich $x_j$ befindet (Optimaltableau)

Schwankungsbereich der Zielfunktionskoeffizienten

Den Schwankungsbereich ermittelt man dann mittels folgendem Intervall:

Methode

$[b_i - b_i^- \; , \; b_i + b_i^+]$               

Vorgehensweise

Die genaue Vorgehensweise wird im Weiteren ausführlich behandelt. Dazu sei das obige Ausgangs- und Optimaltableau gegeben.

1. Zunächst sind die Basisvariablen aus dem Ausgangstableau und die dazugehörigen Werte der rechten Seite $b_i$ zu bestimmen:

$b_1 = 1.300$   für $x_4$

$b_2 = 1.000$    für $x_5$

$b_3 = 300$   für $x_6$.

2. Danach wird geschaut wo sich die Variablen im Optimaltableau befinden. $x_5$ und $x_6$ sind Nichtbasisvariablen, $x_4$ ist eine Basisvariable. Es wird zunächst die Basisvariable betrachtet.

  • $x_4$ = Basisvariable:

Der Schwankungsbereich wird durch die folgenden zwei Formel bestimmt: 

$b_i^- = b_i^*$

$b_i^+ = \infty$

Zu $x_4$ gehört der Wert $b_1$ der rechten Seite im Ausgangstableau:

$b_1^- = b_i^*$

$b_1^+ = \infty$.

Das bedeutet also, es wird hier der Schwankungsbereich für den Wert $b_1$ im Ausgangstableau gesucht, welcher zu $x_4$ gehört. $b_1^-$ nimmt den Wert an, den $x_4$ im Optimaltableau als Wert der rechten Seite besitzt. Hier befindet sich der Wert ebenfalls in der 1. Zeile $b_1^* = 100$. Es kann natürlich auch vorkommen, dass sich der Wert nun in der 3. Zeile befindet, dann wäre $b_3^*$.

Der zu $x_4$ zugehörige Wert $b_i^*$ im Optimaltableau ist: $b_1^* = 100$.

$b_1^- = b_1^* = 100$.

$b_1^+ = \infty$.

Der Schwankungsbereich ergibt sich durch:

$[b_i - b_i^- \; , \; b_i + b_i^+]$      

Einsetzen der Werte, wobei $b_i$ der Wert der rechten Seite im Ausgangstableau für $x_4$ darstellt ($b_1 = 1.300$):

$[b_1 - b_1^- \; , \; b_1 + b_1^+]$    

$[1.300 - 100 \; , \;1.300 + \infty]$    

Methode

$[1.200 \; , \; \infty] \in b_1$

Der Wert der rechten Seiten $b_1$ im Ausgangstableau darf im Intervalll 1.200 bis unendlich schwanken, ohne dass die Optimalitätseigenschaft verloren geht.

  • $x_5$: Nichtbasisvariable

Als nächstes wird $x_5$ betrachtet. Für $x_5$ gilt der Wert $b_2$ der rechten Seite im Ausgangstableau. Für diesen soll nun der Schwankungsbereich bestimmt werden. Dieser wird mittels der folgenden Formeln berechnet:

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

Es wird nun die Spalte im Optimaltableau betrachtet, in welcher sich $x_5$ befindet. Es werden dann alle Koeffizienten größer als Null gewählt. Die dazugehörigen Werte der rechten Seite werden dann durch diese Koeffizienten geteilt. Aus diesen Quotienten wird dann das Minimum gewählt. Existieren keine Koeffizienten größer als Null, so wird $b_2^- = \infty$ gesetzt.

$b_2^- =  min \{\frac{44}{\frac{8}{250}} \} = 1.375$

Es gilt außerdem die Formel:

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

Hier werden alle Koeffizienten in der Spalte von $x_5$ kleiner als Null betrachtet. Existieren keine Werte kleiner als Null, so wird $b_2^+ = \infty$ gesetzt.

$b_2^+ = min \{-\frac{10}{-\frac{1}{50}} \} = 500$.

Der Schwankungsbereich ergibt sich durch:

$[b_2 - b_2^- \; , \; b_2 + b_2^+]$   

$[1.000 - 1.375 \; ; \; 1.000 + 500]$

Methode

$[-375 \; ; \; 1.500]$

Der Wert der rechten Seiten $b_2$ im Ausgangstableau darf im Intervalll -375 bis 1.500 schwanken, ohne dass die Optimalitätseigenschaft verloren geht.

  • $x_6$: Nichtbasisvariable

Für $x_6$ werden dieselben Berechnung wie für $x_5$ angeführt. Diesmal wird aber der Wert $b_3$ der rechten Seite im Ausgangstableau betrachtet und für diesen der Schwankungsbereich gesucht.

$b_2^- = min \{\frac{44}{\frac{1}{25}}; \frac{10}{\frac{1}{10}} \} = 100$

$b_2^+ = min \{-\frac{100}{-4} \} = 25$

Der Schwankungsbereich ergibt sich durch:

$[300 - 100 \; ; \; 300 + 25]$

Methode

$[200 \; ; \; 325]$

Der Wert der rechten Seiten $b_3$ im Ausgangstableau darf im Intervalll 200 bis 325 schwanken, ohne dass die Optimalitätseigenschaft verloren geht.