Suche

Drucken Drucken

Lineare Optimierung

Unter linearer Optimierung versteht man Optimierungsprobleme, bei denen

  1. die Zielfunktion linear ist und
  2. die (linearen) Nebenbeschränkungen zum Teil in Form von Ungleichungen vorliegen.

Wenn die Nebenbedingungen in Form von Gleichungen vorlägen, könnte das Problem mit Ersetzen von Variablen gelöst werden.

Um das Verfahren eines linearen Optimierungsproblems mit Ungleichungen als Nebenbedingungen kennen zu lernen. Sehen wir uns ein Beispiel an, das wir dann anschließend lösen:

Eine Unternehmung produziert zwei Produkte, deren Mengen wir mit x_1 und x_2 bezeichnen. Diese Produkte werden mit Hilfe von drei Maschinen A, B und C hergestellt. Die Maschinen habe unterschiedliche Laufzeiten:

  • Maschine A läuft 200 Stunden
  • Maschine B läuft 120 Stunden
  • Maschine C läuft 240 Stunden

Die beiden Produkte 1 und 2 benötigen unterschiedlich viel Zeit auf den Maschinen:

  • Produkt 1 benötigt zwei Stunden auf Maschine A und je eine Stunde auf Maschine B und C
  • Produkt 2 benötigt je eine Stunde auf den Maschinen A und B und drei Stunden auf Maschine C

Das Unternehmen erhält pro verkaufte Einheit des Produkts 1 zwei € und pro Einheit des Produkts 2 drei €.

Die Zielfunktion ist der Gewinn:

(1)   \begin{equation*}G(x_{1},x_{2})=2x_{1}+3x_{2}.\end{equation*}

Der Gewinn ist eine lineare Funktion in x_1 und x_2. Die Nebenbedingungen liegen alle als Ungleichungen vor:

    \begin{eqnarray*}2x_{1}+x_{2}&\leq&200\ (2)\\x_{1}+x_{2}&\leq&120\ (3)\\x_{1}+3x_{2}&\leq&240\ (4)\end{eqnarray*}

Dabei beschreiben die Gleichungen (2) bis (4), dass das Unternehmen Maschine 1 höchstens 200, Maschine 2 höchstens 120 und Maschine 3 höchstens 240 Stunden nutzen kann.{11}}[[1]]Sollte eine der Ungleichungen nicht in der Form „kleiner als“ vorliegen, müsste sie mit -1 multipliziert werden, um das Rechenzeichen zu verändern.[[11]]

Damit wir das sogenannte Simplexverfahren anwenden können, müssen alle Ungleichungen in Gleichungen verwandelt werden. Dies geschieht, indem pro Ungleichung eine sogenannte Schlupfvariable y_i eingeführt wird. Das System der Nebenbedingungen hat dann folgendes Aussehen

    \begin{eqnarray*}2x_{1}+x_{2}+y_{1}&=&200\ (5)\\x_{1}+x_{2}+y_{2}&=&120\ (6)\\x_{1}+3x_{2}+y_{3}&=&240\ (7)\end{eqnarray*}

Der Sinn dieser Schlupfvariablen ist es einzig und allein, die Ungleichungen zu Gleichungen umzuwandeln. Ist eine der Schlupfvariablen gleich Null, so wird die ursprüngliche Ungleichung mit Gleichheit erfüllt. Ist sie größer Null, dann war die Ungleichung eine echte Ungleichung. Beispiel: Es sei y_1=0 und y_2=50. Dann wird Gleichung (2) zu einer Gleichung (2x_1+x_2=200) und Maschine 1 wird die gesamte zur Verfügung stehende Zeit genutzt. y_2=50 bedeutet, dass x_1+x_2 zusammen kleiner als 120 sind und Maschine 2 50 Stunden lang nicht genutzt wird.

Die Gleichungen (1), (5), (6) und (7) werden nun in ein Simplextableau geschrieben, Dazu werden nur die Koeffizienten benutzt. Die zu maximierende Funktion schreiben wir in die letzte Zeile, nachdem wir sie in G-2x_1-3x_2=0 umgeformt haben:

x_{1} x_{2} y_{1} y_2 y_3 G
2 1 1 0 0 0 200
1 1 0 1 0 0 120
1 3 0 0 1 0 240
-2 -3 0 0 0 1 0
Ziel des Simplexverfahrens, ist es, drei Einheitsvektoren in den ersten fünf Spalten herzustellen und in der letzten Zeile keinen negativen Wert mehr zu haben.{{2}}[[2]]Dass es drei Einheitsvektoren sind, hängt mit der Anzahl der Nebenbedingungen zusammen; bei vier Nebenbedingungen wären es vier Einheitsvektoren.[[2]] Momentan sind die drei Einheitsvektoren bei den Variablen y_1=200, y_2=120 und y_3=240, so dass in diesem Zustand nichts produziert würde und ein Gewinn von Null anfällt. Der Gewinn steht ganz unten rechts in der Tabelle.

Um das Optimierungsproblem zu lösen, wird in der unteren Zeile der negativste (kleinste) Wert gesucht. Dies führt uns in diesem Beispiel in die zweite Spalte mit der -3. Jetzt werden in dieser Spalte die Quotienten aus Ergebnisvektor (Letzte Spalte) und aktueller Spalte gebildet. Hier ergibt sich:

    \begin{eqnarray*}\frac{200}{1}&=&200\\\frac{120}{1}&=&120\\\frac{240}{3}&=&80\end{eqnarray*}

Das kleinste dieser Ergebnisse signalisiert das Pivotelement, in diesem Fall also das Element in der dritten Zeile der zweiten Spalte. Die Auswahl dieses Elements hat folgenden Hintergrund:

  1. Die Wahl des negativsten Wertes in der unteren Zeile lässt uns die Variable finden, die den größten Einfluss auf den Gewinn hat – in unserem Beispiel bringt eine Einheit von Produkt 2 3 €.
  2. Mit dem zweiten Schritt wird die stärkste Beschränkung dieser Variablen gefunden. Es ist nicht möglich, mehr als 80 Einheiten von Produkt 2 auf Maschine C zu produzieren, weil dann die Maschinenzeit verbraucht ist. Dass auf den Maschinen A und B noch Platz wäre, spielt keine Rolle – mehr als 80 Einheiten können nicht produziert werden.

Mit diesem Vorgehen wird also der stärkste Einfluss auf den Gewinn ermittelt.

Um die Auswirkungen dieser Entscheidung zu sehen, wird das die zweite Spalte zu einem Einheitsvektor mit einem Element ungleich Null in der dritten Spalte umgeformt. Dazu wird

  • ein Drittel der dritten Zeile von der ersten Zeile subtrahiert, um in der ersten Zeile eine Null in der zweiten Spalte zu bekommen
  • ebenfalls ein Drittel der dritten Zeile von der zweiten Zeile subtrahiert, um auch dort in der zweiten Spalte eine Null zu bekommen
  • die dritte Zeile zur vierten Zeile addiert, um dort in der zweiten Spalte ebenfalls eine Null zu bekommen.

Nach diesen Umformungen sieht das Simplextableau wie folgt aus:

x_1 x_2 y_1 y_2 y_3 G
\frac{5}{3} 0 1 0 -\frac{1}{3} 0 120
\frac{2}{3} 0 0 1 -\frac{1}{3} 0 40
1 3 0 0 1 0 240
-1 0 0 0 1 1 240

Bei dem jetzigen Stand würden 80 Einheiten von Produkt 2 produziert und 240 € Gewinn gemacht. Das Verfahren ist aber noch nicht beendet, da in der letzten Zeile noch ein negativer Wert steht. Nun muss in der ersten Spalte das Pivotelement gesucht werden. Dazu wird jeweils wieder der Wert in der letzten Spalte durch den Wert in der ersten Spalte dividiert. Das ergibt:

    \begin{eqnarray*}120:\frac{5}{3}&=&72\\40:\frac{2}{3}&=&60\\240:1&=&240\end{eqnarray*}

Die Wahl für das Pivotelement fällt also auf das Element in der ersten Spalte in der zweiten Reihe \left(\frac{3}{2}\right). Es wird wie oben verfahren, um in der ersten Spalte nur noch in der zweiten Zeile ein Element stehen zu haben, dass von Null verschieden ist. Es wird

  • das \frac{5}{2}-fache der zweite Zeile von der ersten subtrahiert,
  • das \frac{3}{2}-fache der zweiten Zeile von der dritten subtrahiert und
  • das \frac{3}{2}-fache der zweiten Zeile zur vierten addiert,

um nur in der zweiten Zeile noch einen von Null verschiedenen Wert stehen zu haben.

Das Ergebnis dieser Rechnungen sieht so aus:

x_1 x_2 y_1 y_2 y_3 G
0 0 1 -\frac{5}{2} \frac{1}{2} 0 20
\frac{2}{3} 0 0 1 -\frac{1}{3} 0 40
0 3 0 -\frac{3}{2} \frac{3}{2} 0 180
0 0 0 \frac{3}{2} \frac{1}{2} 1 300

Damit ist das Verfahren abgeschlossen, weil in der letzten Zeile kein negativer Wert mehr steht. Die drei Einheitsvektoren befinden sich in den ersten drei Spalten – je ein Element ist ungleich Null und alle anderen sind gleich Null. Um die Ergebniswerte ablesen zu können, wird die jeweilige Zeile so mit einem Wert multipliziert, dass das jeweilige Element 1 wird, also

  • Zeile eins bleibt erhalten,
  • Zeile zwei wird mit \frac{3}{2} multipliziert und
  • Zeile drei wird durch 3 dividiert.

Somit erhalten wir

x_1 x_2 y_1 y_2 y_3 G
0 0 1 -\frac{5}{2} \frac{1}{2} 0 20
1 0 0 \frac{3}{2} -\frac{1}{2} 0 60
0 1 0 -\frac{1}{2} \frac{1}{2} 0 60
0 0 0 \frac{3}{2} \frac{1}{2} 1 300

Die drei Einheitsvektoren sind in den ersten drei Spalten, sie betreffen also die Variablen x_1 , x_2 und y_1. Dies bedeutet, dass y_2 und y_3 gleich Null sind. Inhaltlich ergibt sich folgendes:

  • Aus Spalte eins folgt, dass x_1 60 ist; es werden also 60 Einheiten von Produkt 1 hergestellt,
  • aus Spalte zwei folgt, dass x_2 ebenfalls gleich 60 ist und damit auch 60 Einheiten von Produkt 2 hergestellt werden,
  • aus Spalte drei folgt, dass y_1 gleich 20 ist – damit wird Maschine A nicht vollständig genutzt, sondern es ist eine Restkapazität von 20 Stunden vorhanden,
  • aus den Spalten vier und fünf folgen y_2=y_3=0 – weil dort keine Einheitsvektoren sind – und damit, dass die Maschinen B und C voll genutzt werden,
  • aus Zeile vier folgt, das der Gewinn 300 ist.

Überprüfen wir die aus dem Simplextableau abgelesenen Werte mit Hilfe unserer Ziel- und Nebenbedingungen:Gewinn:

    \begin{eqnarray*}\mbox{Gewinn}&:&G(x_{1},x_{2})=2*60+3*60=300\\\mbox{Maschine A}&:&2*60+60+20=200\\\mbox{Maschine B}&:&60+60=120\\\mbox{Maschine C}&:&60+3*60=240\end{eqnarray*}

Die Nebenbedingungen sind alle mit Gleichheit erfüllt – wobei bei Maschine A die Schlupfvariable positiv ist. Der Gewinn erreicht eine Höhe von 300 – wie durch das Simplextableau berechnet.

 

Drucken Drucken

Schreibe einen Kommentar