Kurs:Algorithmen und Datenstrukturen/Vorlesung/Opimierung Grundlagen




Grundlagen der OptimierungBearbeiten

Auf dieser Seite gibt es eine Einführung in das Thema Optimierung.

Die (Mathematische) Optimierung beschreibt eine Familie von Lösungsstrategien zur Maximierung/Minimierung einer Zielfunktion unter Nebenbedingungen. Viele der bisher untersuchten Probleme können als Optimierungsproblem modelliert werden. Zum Beispiel das Kürzeste Wege Problem: Minimiere die Länge eines Pfades unter der Nebenbedingung, dass der Pfad zwei gegebene Knoten verbindet. Oder das Rucksackproblem: Maximiere den Gesamtnutzen der Gegenstände unter der Nebenbedingung, dass die Kapazität des Rucksacks eingehalten wird. Oder das Flussprobleme: Maximiere den Fluss unter der Nebenbedingung, dass Kantenkapazitäten eingehalten werden.

Algorithmen wie Djikstra und Ford-Fulkerson sind domänenspezifische Algorithmen zur Lösung ihrer jeweiligen Optimierungsprobleme. Mathematische Optimierungsverfahren sind allgemeine Verfahren, die auf eine Vielzahl von Problemen anwendbar sind, dabei aber eventuell nicht immer so effizient wie speziellere Algorithmen sind.

Optimierung ist eine weites Feld, wir werden uns in dieser Vorlesung auf einen kleinen Ausschnitt konzentrieren:

  • Grundlagen der Optimierung
  • Kombinatorische Optimierung
  • Lineare Optimierung
  • Das Simplex‐Verfahren

BegriffeBearbeiten

Ein allgemeines (reelles) Optimierungsproblem ist gegeben durch P: Minimiere f(x)unter der Nebenbedingung  . f ist dabei die Zielfunktion.   heißt zulässig für P, falls  . X ist die zulässige Menge und   heißt globales Minimum von P, falls  . Äquivalent gilt P: Minimiere f(x) unter der Nebenbedingung   und P': Maximiere -f(x) unter der Nebenbedingung  .

Beispiel GewinnmaximierungBearbeiten

Eine Firma produziert zwei verschiedene Waren. Ware x1 erbringt einen Gewinn von einem Euro. Ware x2 erbringt einen Gewinn von 6 Euro.

Frage: Welches Verhältnis von x1 und x2 führt zum größten Gewinn?

Nebenbedingungen:

Die Firma kann täglich maximal 200 Einheiten der Ware x1 produzieren und maximal 300 Einheiten der Ware x2 .

Insgesamt kann die Firma maximal 400 Einheiten pro Tag produzieren.

Zuerst wird nun die Zielfunktion formuliert: Maximiere Gewinn (1 Euro pro  , 6 Euro pro  ) :  .

Anschließend werden die Nebenbedingungen formuliert.

Maximal 200 Exemplare von x1  

Maximal 300 Exemplare von x2  

Insgesamt maximal 400 Exemplare  

Es müssen Waren produziert werden  

Der Punkt   ist zulässig mit Funktionswert 0  

Der Punkt   ist zulässig mit Funktionswert 1400  

Der Punkt   ist zulässig mit Funktionswert 1900 und globales Maximum  

Der Punkt   ist unzulässig  

Dieses Beispiel ist ein lineares Optimierungsproblem.

Beispiel Kürzester WegBearbeiten

Es soll die Distanz von s nach y bestimmt werden. Dafür sollen folgende Variablen und Bezeichner betrachtet werden.

  •  : die Kante von a nach b ist Teil des kürzesten Pfades von s nach y für alle Kanten (a,b)
  •   : Das Gewicht der Kante von a nach b, zum Beispiel  
  • Die Zielfunktion ist  

Es gelten folgende Nebenbedingungen:

  1. Die Gewichte müssen wie im Graph sein  
  2. Alle Kanten (a,b) mit   müssen einen Pfad von s nach y bilden:
    1. Es gibt genau eine Kante mit Startpunkt s:  
    2. Es gibt genau eine Kante mit Zielpunkt y:  
    3. Für jeden anderen Knoten gilt, falls eine Kante in diesen Knoten reinführt, muss er auch wieder eine rausführen, zum Beispiel für  

Beachte durch die Minimierung werden Kreise auf dem Pfad automatisch verhindert.

Vollständiges Optimierungsproblem für ein kleines Beispiel von u nach x:


 

 

 

 

 

 

 

 

 

 

Das Problem der Kürzesten-Wegfindung ist ein ganzzahliges Optimierungsproblem, allgemeiner ein kombinatorisches Optimierungsproblem.

ProblemklassenBearbeiten

Optimierungsprobleme sind unterschiedlich schwer lösbar  

  • lineare Probleme: f,h sind linear, z.B. f/x,y)=3x+4y. Diese sind einfach zu lösen  
  • Quadratische Probleme: z.B.   sind auch noch einfach zu lösen.  
  • Konvexe Probleme: z.B. min   sind schon schwerer zu lösen.  
  • Nicht-konvexe Probleme: z.B.   sind ziemlich schwer zu lösen.  
  • Ganzzahlige Probleme:   sind überraschenderweise schwerer zu lösen als reelle Probleme. Etwa allgemeiner handelt es sich hier um kombinatorische Probleme (diskrete Elemente, nicht notwendigerweise Zahlen)
  • Weitere Parameter
    • Restringierte Probleme: zulässige Menge ist beschränkt
    • Unrestringierte Probleme: zulässige Menge ist unbeschränkt

Hier werden wir uns aber nur mit linearer Optimierung befassen.