lineare Optimierung

Die Lineare Optimierung oder Lineare Programmierung ist eines der Hauptverfahren des Operations Research und beschäftigt sich mit der Optimierung linearer Zielfunktionen über einer Menge, die durch lineare Gleichungen und Ungleichungen eingeschränkt ist. Häufig lassen sich lineare Programme (LPs) zur Lösung von Problemen einsetzen, für die keine speziell entwickelten Lösungsverfahren bekannt sind.

Lösung von linearen Optimierungsaufgaben

Lösung mittels Simplex-Algorithmus

Die Strategie hinter der Simplexmethode ist folgendes:
  • Beginne an einer Ecke des Lösungspolyeders
  • Wandere entlang einer Kante zu einer nächsten Ecke, die den Ziefunktionswert verbessert
  • Wiederhole den Vorgang solange noch Verbesserungen möglich sind.
Angabe:


Schritt 1: für jede Ungleichung des linearen Programms wird eine sogenannte Schlupfvariable eingeführt und das <= Zeichen durch ein = ersetzt.


grafisch dargestellt sieht unser Optimierungsproblem folgendermaßen aus:

Als ersten Schritt schreibt man das lineare Gleichungssystem in die Matrixform, dem sogenannten Simplextableau. Dazu werden die Ungleichungen (Grenzen) mit jeweils einer eigenen Schlupfvariable (s) erweitert und das Vergleichzeichen (> <) durch ein Istgleichzeichen (=) ersetzt. Der zulässige Bereich lässt sich als Menge aller Lösungen des Gleichungssystems beschreiben für die folgende "Nichtnegativitätsbedingung" gilt: xi >=0 , Si >= 0. Der zulässige Bereich ist eine Konvexe Menge, woraus sich ergibt, dass das Optimum immer in einem Eckpunkt des zulässigen Bereichs liegt. Diese Eckpunkte sind die Schnittpunkte der Begrenzungsgeraden.



Schritt 2: Als nächster Schritt nimmt man die Pivotschritte vor:
  1. Wähle die Spalte mit dem kleinsten Eintrag in der Zielfunktionszeile => PIVOTSPALTE
  2. Dividiere die Spalte ganz rechts durch die Pivotspalte => Quotient
  3. Wähle die Zeile mit dem kleinsten nichtnegativen Quotienten => PIVOTZEILE
  4. Der Schnittpunkt der PIVOTSPALTE und PIVOTZEILE = PIVOTELEMENT


Schritt 3: Als nächstes Schritt muss man in der Pivotspalte alle Werte (in diesem Fall in der Spalte x1) auf 0 bringen, indem man davon ein vielfaches der anderen Zeilen subrahiert.

das bedeutet, dass für den Punkt P(40,0) die Zielfunktion einen Wert von 120 hat.

Die optimale zulässige Basislösung wäre erreicht, wenn in der Zielfunktionszeile alle Einträge nicht-negativ sind.
Wiederholung Schritt 2+3:
Daher wiederholt man die Pivotschritte ein weiteres mal:
  1. Wähle die Spalte mit dem kleinsten Eintrag in der Zielfunktionszeile => PIVOTSPALTE
  2. Dividiere die Spalte ganz rechts durch die Pivotspalte => Quotient
  3. Wähle die Zeile mit dem kleinsten nichtnegativen Quotienten => PIVOTZEILE
  4. Der Schnittpunkt der PIVOTSPALTE und PIVOTZEILE = PIVOTELEMENT

Interpretation:
Wiederholung Schritt 2+3: Da die Zielfunktion noch immer negative Werte enthält, muss dieser Schritt ein weiteres mal wiederholt werden.
  1. Wähle die Spalte mit dem kleinsten Eintrag in der Zielfunktionszeile => PIVOTSPALTE
  2. Dividiere die Spalte ganz rechts durch die Pivotspalte => Quotient
  3. Wähle die Zeile mit dem kleinsten nichtnegativen Quotienten => PIVOTZEILE
  4. Der Schnittpunkt der PIVOTSPALTE und PIVOTZEILE = PIVOTELEMENT
Erklärung:

Lösung:


Alternativen

alternativer Algorithmus
Ich muss zugeben, dass ich kein großer Freund des Simplex-Algorithmus bin, da dieser nur nach intensiver Beschäftigung logisch ist. Wenn man mal längere Zeit nichts damit zu tun gehabt hat, muss man sich erst wieder damit auseinandersetzen, damit man Optimierungsaufgaben damit lösen kann. 

Aber eigentlich muss man für solche Optimierungsaufgaben nur etwas wissen. Die LÖSUNG befindet sich auf einen der Schnittpunkte der Nebenbedingungen.

Vorgehensweise:
1. man formt die Nebenbedingungs-Ungleichungen in Gleichungen um
2. Berechnet die Schnittpunkte der Nebenbedingungs-Ungleichungen
3. Scheidet die Schnittpunkte außerhalb des zulässigen Bereiches logisch aus
4. Setzt die verbleibenden Punkte in die Zielfunktion ein

 Zettel 1    Zettel 2 
 
 

Zur Veranschaulichung der berechneten PUNKTE:


graphische Lösung von linearen Optimierungsaufgaben

manuelle graphische Optimierung


lineare Optimierung


graphische Optimierung mittels Excel

Ausgangspunkt der Betrachtung ist eine Zielfunktion mit mehreren Nebenbedingungen.
  • Zielfunktion: 3*x+4*y=>max
  • Nebenfunktionen
    • 4*x+8*y<=24
    • 2*x+y<=10
    • y>=0
    • x>=0
Grundüberlegung
Grundsätzlich geht es ja darum, dass innerhalb der Grenzen, die durch die Nebenbedingungen beschrieben werden, das Maximum oder Minimum der Zielfunktion bestimmt werden muss. Dh. man könnte für alle Kombinationspaare von x und y die Zielfunktion innerhalb dieser Grenzen berechnen und diese in einem dreidimensionalen Diagramm darstellen. Dort wo der höchste Punkt auf der z-Achse vorliegt, ist auch das Maximum. 

In einem ersten Schritt bestimmt man den Lösungsbereich.

Auf Basis des Lösungsbereiches ermittelt man nun alle zulässigen Kombinationen der Variablen x und y, die sich innerhalb des Lösungsbereiches befinden und setzt diese Kombinationen in die Zielfunktion ein. Die Kombination mit dem höchsten Zielwert entspricht der Lösung.


Auf diese Art müssen aber je nach Genauigkeit sehr viele Kombinationen ermittelt werden. 

schnelle Variante
Wenn man weiß, dass sich die Maxima und Minima immer auf den Schnittpunkten der Nebenbedingungen befinden, dann kann man diese Berechnung wesentlich vereinfachen.

Grundsatz: Maxima und Minima befinden sich auf den Schnittpunkten der Nebenbedingungen

graphische und mathematische lineare Optimierung mittels typischer Software

lineare Optimierung mittels MuPad

lineare Optimierung mittels MuPAD

  • Zielfunktion: 120*x+90*y=>max
  • Nebenfunktionen
    • x+y <= 1000
    • y <= 800
    • 3*x+2*y <= 2400
    • x,y >= 0

Eingabe: LP := [[1000 >= x + y, y <= 800, 2400 >= 3*x + 2*y ], 120*x + 90*y, NonNegative]:


Zum Zeichnen kann man folgendes eingeben: G:=linopt::plot_data(LP,[x,y]):plot(G):

lineare Optimierung mit Mathematica

Die lineare Optimierung mit Mathematica ist auch relativ einfach:

  • Zielfunktion: 17*x-20*y+18*z =>max
  • Nebenfunktionen
    • x-y+z < 10
    • x < 5
    • x + z > 20

Links:

lineare Optimierung mit MatLab

Mit MatLab ist das Lösen von linearen Optimierungsproblemen hingegen etwas komplizierter.

Dazu muss in einem ersten Schritt das Optimierungsproblem in eine andere Form gebracht werden.

welches folgendermaßen eingegeben wird:
> f = [-143 -60]
> A = [1 1; 110 30; 120 210;-1 0;0 -1]
> b = [75; 4000;15000;0;0]
> linprog(f,A,b)

Und um das Maximum auszurechnen:
> -f*ans

Links:

lineare Optimierung mit TI92,TI89 ua.

Damit habe ich mich bis dato noch nicht beschäftigt. 

Links:

spezielle Software zum Lösen lineare Optimierung

spezielle Software für das Lösen lineare Optimierungsaufgaben:
  • Software: Lino (TU-Darmstadt) - Beispiel [TENOR = Tutorial Environment for Operations Research]
  • Optimierungssoftware Xpress-MP - siehe Fico

Lösen von linearen Optimierungsaufgaben mit Excel Solver

Neben dem Lösen lineare Optimierungsaufgaben mittels spezieller Software oder spezieller Schreibweise, besteht auch die Möglichkeit mittels Excel Solver Optimierungsprobleme zu lösen.

Links

Untergeordnete Seiten (1): Tenor Lino
Ċ
Erhard Rainer,
06.01.2014, 14:20
Comments