Kurs:Algorithmen und Datenstrukturen/Vorlesung/Lineare Optimierung




Lineare OptimierungBearbeiten

Auf dieser Seite wird die lineare Optimierung behandelt. Eine lineare Optimierungsaufgabe ist: Maximiere eine lineare Funktion in mehreren Variablen

 .

Die lineare Nebenbedingung sind gegeben als lineare Gleichungen:

 

...

 

 

Dies entspricht dem Gleichungssystem:

 

Doch ist das ausdrucksstark genug für unsere Probleme?

Umformung von GleichungssystemenBearbeiten

Beliebige Systeme lassen sich in die Standardform übertragen.

  • Minimieren ist wie maximieren:  
  •   Bedingungen statt   Bedingungen:  
  • Gleichung zu Ungleichung:  
  • Ungleichung zu Gleichung (Schlupfvariablen einführen):  
  •   kann negativ sein:  

Beispiel GewinnmaximierungBearbeiten

Eine Firma produziert zwei verschiedene Waren. Ware   erbringt einen Gewinn von einem Euro. Ware   erbringt einen Gewinn von 6 Euro. Die Frage hierzu lautet, welches Verhältnis von   und   führt zum größten Gewinn? Dazu gibt es zwei Nebenbedingungen:

  • Die Firma kann täglich maximal 200 Einheiten der Ware   produzieren und maximal 300 Einheiten der Ware  
  • Insgesamt kann die Firma maximal 400 Einheiten pro Tag produzieren

Die Firma beschließt eine weitere Ware zu produzieren.

  • Die Ware   bringt einen Gewinn von 13 Euro.
  • Die maximale Tagesproduktion liegt weiterhin bei 400 Einheiten.
  • Für die Produktion von Ware   und Ware   wird dieselbe Maschine verwendet, allerdings ist der Produktionsaufwand für   dreimal höher. Insgesamt kann die Maschine 600 Arbeitsschritte leisten.

Formuliere, die Zielfunktion:  .

Anschließend formuliere die Nebenbedingungen:

 

 

 

 

 



Die Nebenbedingungen definieren ein drei-dimensionales Polyeder, in dem die optimale Lösung liegt.

Nun formen wir in die Normalform um:

 

 

 

 

 

 




Die Nebenbedingungen definieren nun ein Polyeder, in dem die optimale Lösung liegt.







Die Zielfunktion   ist eine Gerade. Nun wird die Gerade verschoben, bis das Maximum erreicht ist.




Die Linearen Optimierungsprobleme der Form

 

 

 

besitzen genau dann eine endliche Optimallösung, wenn sie eine optimale Ecklösung (= „Ecke“ des zugehörigen Polyeders) besitzen. D.h. man muss zur Lösungsfindung nur die Ecken des Polyeders betrachten.