ZU DEN KURSEN!

Operations Research 1 - Obere Schranken: Vielzahl an beschränkten Variablen

Kursangebot | Operations Research 1 | Obere Schranken: Vielzahl an beschränkten Variablen

Operations Research 1

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:

$f(x_1, x_2, x_3, x_4) = 4x_1 + 6x_2 + 3x_3 + x_4$   $\rightarrow$  max!

u.d.N.

$x_1 + 2x_2 + 4x_3 + x_4 \le 80$

$2x_1 + x_2 + x_3           \le 60$

$x_1 \le 20$

$x_2 \le 30$

$x_3 \le 10$

$x_4 \le 5$

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

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:

$f(x_1, x_2, x_3, x_4) = 4x_1 + 6x_2 + 3x_3 + x_4$   $\rightarrow$  max!

u.d.N.

$x_1 + 2x_2 + 4x_3 + x_4 + x_5           = 80$

$2x_1 + x_2 + x_3                    + x_6  = 60$

$x_1 \le 20$

$x_2 \le 30$

$x_3 \le 10$

$x_4 \le 5$

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

Eintragen in das Simplextableau ergibt:

Obere Schranken der Variablen im Simplex

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 $-6$. Setzen von $x_t = x_2$ mit der Beschränkung $\kappa_2 = 30$.

2. Schritt: Wahl der Pivotzeile. Es wird $q_1$ und $q_2$ bestimmt.

$q_1 = min \{\frac{80}{2}, \frac{60}{1} \} = 40$

$q_2 = \infty$ Kein negativer Koeffizient in der Pivotspalte vorhanden.

Bestimmung von $q = min \{q_1, q_2, \kappa_2 \} = 30$

Es gilt der Fall:

  • $q = \kappa_2$

Es wird nun die gesamte Spalte ersetzt durch $x_2 = \kappa_2 - \overline{x}_2 = 30 - \overline{x_2}$. Es wird das aktuelle lineare Optimierungsproblem (siehe Tableau) herangezogen. Die Spalte betrifft alle Nebenbedingungen und die Zielfunktion, weshalb das komplette Optimierungsmodell durch $x_2 = 30 - \overline{x_2}$ ersetzt werden muss. 

$f(x_1, x_2, x_3, x_4) = 4x_1 + 6(30 - \overline{x_2}) + 3x_3 + x_4$   $\rightarrow$  max!

u.d.N.

$x_1 + 2(30 - \overline{x_2}) + 4x_3 + x_4 + x_5           = 80$

$2x_1 + 30 - \overline{x_2} + x_3                    + x_6  = 60$

$x_1 \le 20$

$30 - \overline{x_2} \le 30$

$x_3 \le 10$

$x_4 \le 5$

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

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

$f(x_1, x_2, x_3, x_4) = 4x_1 - 6 \overline{x_2}) + 3x_3 + x_4 + 180$   $\rightarrow$  max!

u.d.N.

$x_1 - 2\overline{x_2}) + 4x_3 + x_4 + x_5           = 20$

$2x_1 - \overline{x_2} + x_3                     + x_6  = 30$

$x_1 \le 20$

$\overline{x_2} = 0$

$x_3 \le 10$

$x_4 \le 5$

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

Eintragen in das Tableau:

Obere Schranken der Variablen im Simplex

Der Zielfunktionswert von $180$ resultiert, weil $x_1 = \overline{x}_2 = x_3 = x_4 = 0$ (Nichtbasisvariablen) unter Berücksichtigung von $x_2 = 30 - \overline{x}_2 = 30 - 0 = 30$. Einsetzen in die Ausgangszielfunktion ergibt:

$f(x_1, x_2, x_3, x_4) = 4 \cdot 0 + 6 \cdot 30 + 3 \cdot 0 + 0 = 180$ 

Es wird nun wieder von vorne begonnen.

1. Schritt: Wahl der Pivotspalte. Der kleinste negative Wert ist $-4$. $x_t = x_1$ mit $\kappa_1 = 20$

2. Schritt: Wahl der Pivotzeile. Bestimmung von $q_1$ und $q_2$.

$q_1 = min \{\frac{20}{1}, \frac{30}{2} \} = 15$

$q_2 = \infty$  Kein negativer Koeffizient in der Pivotspalte.

Bestimmung von $q = min \{15, \infty, 20 \} = 15$

Es gilt der Fall:

  • $q = q_1$:

Es wird nun die Basisvariable betrachtet, für die $q_1 = 15$ gilt. Dies ist $x_6 = \frac{30}{2}$. Diese Basisvariable verlässt die Basis und wird zur Nichtbasisvariablen. Der Tausch erfolgt mit $x_t = x_1$. Es wird zudem ein Simplexschritt durchgeführt:

Obere Schranken der Variablen im Simplex

Der Zielfunktionswert ist berechnet worden durch: $x_1 = 15$, $\overline{x}_2 = 0$ mit $x_2 = 30 - \overline{x_2}$ also $x_2 = 30$ und $x_3 = x_4 = 0$:

$f(x_1, x_2, x_3, x_4) = 4 \cdot 15 + 6 \cdot 30 + 3 \cdot 0 + 0 = 240$ 

1. Schritt: Wahl der Pivotspalte. Es existieren zwei kleinste Werte. Es kann einer beliebig gewählt werden. Es wird der Wert $-1$ gewählt für welchen gilt $x_t = x_4$ mit $\kappa_4 = 5$.

2. Schritt: Wahl der Pivotzeile. Es werden $q_1$ und $q_2$ berechnet.

$q_1 = min \{\frac{5}{1} \} = 5$

$q_2 = \infty$  Es existieren keine negative Koeffizienten in der Pivotspalte.

Es wird $q$ bestimmt:

$q = min \{5, \infty, 5 \}$. 

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

  • $q = \kappa_4$

Es wird nun für die Basisvariable $x_t = x_4$ die gesamte Spalte ausgetauscht durch $x_4 = 5 - \overline{x}_4$. Dabei muss das aktuelle Optimierungsmodell herangezogen werden (siehe Tableau):

ZF: $-2x_6 - 4 \overline{x}_2 + x_3 + x_4$     (mit umkehrten Vorzeichen berücksichtigen)

NB: $-\frac{1}{2} x_6 - \frac{3}{2} \overline{x}_2 + \frac{7}{2} x_3 +  x_4   = 5$

     $  \frac{1}{2} x_6 - \frac{1}{2} \overline{x}_2 + \frac{1}{2} x_3             = 15$

$x_1 \le 20$

$\overline{x_2} = 0$

$x_3 \le 10$

$x_4 \le 5$

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

Einsetzen von $x_4 = 5 - \overline{x}_2$:

ZF: $-2x_6 - 4 \overline{x}_2 + x_3 + 5 + \overline{x}_4$   

NB: $-\frac{1}{2} x_6 - \frac{3}{2} \overline{x}_2 + \frac{7}{2} x_3 +  5 - \overline{x}_4   = 5$

     $  \frac{1}{2} x_6 - \frac{1}{2} \overline{x}_2 + \frac{1}{2} x_3             = 15$

$x_1 \le 20$

$\overline{x_2} = 0$

$x_3 \le 10$

$5 - \overline{x}_4 \le 5$

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

Zusammenfassen:

ZF: $-2x_6 - 4 \overline{x}_2 + x_3 - \overline{x}_4 + 5$   

NB: $-\frac{1}{2} x_6 - \frac{3}{2} \overline{x}_2 + \frac{7}{2} x_3 - \overline{x}_4   = 0$

     $  \frac{1}{2} x_6 - \frac{1}{2} \overline{x}_2 + \frac{1}{2} x_3             = 15$

$x_1 \le 20$

$\overline{x_2} = 0$

$x_3 \le 10$

$\overline{x}_4 \le 0$

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

Einfügen in das Tableau:

Obere Schranken der Variablen im Simplex

Es ist deutlich zu erkennen, dass sich nur die Spalte verändert hat, in der sich vorher $x_4$ und jetzt $\overline{x}_4$ befindet. Der neue Zielfunktionswert ergibt sich durch: $x_1 = 15$, $x_6 = x_3 = 0$ und $\overline{x}_2 = \overline{x}_4 = 0$ wobei $x_2 = 30 - \overline{x}_2 = 30 - 0 = 30$ und $x_4 = 5 - \overline{x}_4 = 5 - 0 = 5$. Einsetzen in die Ausgangszielfunktion ergibt:

$f(x_1, x_2, x_3, x_4) = 4 \cdot 15 + 6 \cdot 30 + 3 \cdot 0 + 5 = 245$ 

1. Schritt: Wahl der Pivotspalte. Es existiert noch ein negativer Wert in der Zielfunktionszeile: $-1$ mit $x_t = x_3$ und $\kappa_3 = 10$.

2. Schritt: Wahl der Pivotspalte. Bestimmung von $q_1$ und $q_2$.

$q_1 = min \{\frac{0}{\frac{7}{2}}; \frac{15}{\frac{1}{2}} \} = 0$

$q_2 = \infty$

Bestimmung von $q$:

$q = min \{0, \infty, 10 \} = 0$

Es gilt der Fall:

  • $q = q_1$:

Es wird nun die Basisvariable für die $q_1 = \frac{0}{\frac{7}{2}}$ zur Basisvariablen. Hierbei handelt es sich um $x_5$. Der Tausch findet mit der Nichtbasisvariablen der Pivotspalte statt, also mit $x_3$. Es wird zudem ein Simplexschritt durchgeführt:

Obere Schranken der Variablen im Simplex

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

$x_1 = 15$, $\overline{x}_2 = 0$, $x_3 = 0$ und $\overline{x}_4 = 0$. Dabei gilt $x_2 = 30 - \overline{x}_2 = 30 - 0 = 30$ und $x_4 = 5 - \overline{x}_4 = 5 - 0 = 5$. Einsetzen in die Ausgangszielfunktion ergibt:

Methode

Hier klicken zum Ausklappen

$f(x_1, x_2, x_3, x_4) = 4 \cdot 15 + 6 \cdot 30 + 3 \cdot 0 + 5 = 245$ 


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:

Obere Schranken der Variablen im Simplex

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.