Kurs:Algorithmen und Datenstrukturen/Vorlesung/Opimierung Grundlagen

Grundlagen der Optimierung

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

Begriffe

Ein allgemeines (reelles) Optimierungsproblem ist gegeben durch P: Minimiere f(x)unter der Nebenbedingung $x\in XmitX\subseteq {ℝ}^{n}undf:X\to ℝ$. f ist dabei die Zielfunktion. $x\in {ℝ}^n$ heißt zulässig für P, falls $x\in X$. X ist die zulässige Menge und $x^{\prime }\in X$ heißt globales Minimum von P, falls $\mathrm{\forall }x\in X:f(x^{\prime })\le f(x)$. Äquivalent gilt P: Minimiere f(x) unter der Nebenbedingung $x\in X$ und P': Maximiere -f(x) unter der Nebenbedingung $x\in X$.

Beispiel Gewinnmaximierung

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 $x_1$, 6 Euro pro $x_2$) : $max{x}_1+6\cdot x_2$.

Anschließend werden die Nebenbedingungen formuliert.

Maximal 200 Exemplare von x1 $x_1\le 200$

Maximal 300 Exemplare von x2 $x_2\le 300$

Insgesamt maximal 400 Exemplare $x_1+x_2\le 400$

Es müssen Waren produziert werden $x_1,x_2\ge 0$

Der Punkt $(0,0)\in {ℝ}^2(x_1=0,x_2=0)$ ist zulässig mit Funktionswert 0 $max{x}_1+6\cdot x_2$

Der Punkt $(100,200)\in {ℝ}^2$ ist zulässig mit Funktionswert 1400 $x_2\le 200$

Der Punkt $(100,300)\in {ℝ}^2$ ist zulässig mit Funktionswert 1900 und globales Maximum $x_1+x_2\le 400$

Der Punkt $(200,300)\in {ℝ}^2$ ist unzulässig $x_1,x_2\ge 0$

Dieses Beispiel ist ein lineares Optimierungsproblem.

Beispiel Kürzester Weg

Beispielgraph

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

• $e_{a,b}\in \{0,1\}$: die Kante von a nach b ist Teil des kürzesten Pfades von s nach y für alle Kanten (a,b)
• $w_{a,b}$ : Das Gewicht der Kante von a nach b, zum Beispiel $w_{s,u}=10$
• Die Zielfunktion ist $min{e}_{s,u}{w}_{s,u}+e_{s,x}{w}_{s,x}+...+e_{v,y}{w}_{v,y}$

Es gelten folgende Nebenbedingungen:

1. Die Gewichte müssen wie im Graph sein $w_{s,u}=10,w_{s,u}=5,...$
2. Alle Kanten (a,b) mit $e_{a,b}=1$ müssen einen Pfad von s nach y bilden:
   1. Es gibt genau eine Kante mit Startpunkt s: $e_{s,u}+e_{s,x}=1$
   2. Es gibt genau eine Kante mit Zielpunkt y: $e_{v,y}+e_{x,y}=1$
   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 $x:e_{s,x}+e_{u,x}=e_{x,u}+e_{x,y}$

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

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

Kürzester Weg

$min{e}_{u,v}{w}_{u,v}+e_{u,w}{w}_{u,w}+e_{v,w}{w}_{v,w}+e_{w,x}{w}_{w,x}$

$w_{u,v}=4$

$w_{u,w}=6$

$w_{v,w}=1$

$w_{w,x}=2$

$e_{u,v}+e_{u,w}=1$

$e_{w,x}=1$

$e_{u,v}=e_{v,w}$

$e_{u,w}+e_{v,w}=e_{w,x}$

$e_{u,v},e_{u,w},e_{v,w},e_{w,x}\in \{0,1\}$

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

Problemklassen

Optimierungsprobleme sind unterschiedlich schwer lösbar $max,minf(x_1,...x_n)$

• lineare Probleme: f,h sind linear, z.B. f/x,y)=3x+4y. Diese sind einfach zu lösen $h_1(x_1,...,x_n)\le b_1$
• Quadratische Probleme: z.B. $f(x,y)=x^2+xy$ sind auch noch einfach zu lösen. $h_{m_1}(x_1,...,x_n)\le b_{m_1}$
• Konvexe Probleme: z.B. min $f(x,y)=log(x)+log(y)$ sind schon schwerer zu lösen. $i_1(x_1,...,x_n)<c_1$
• Nicht-konvexe Probleme: z.B. $f(x,y)=xsin(x)$ sind ziemlich schwer zu lösen. $i_{m-2}(x_1,...,x_n)<c_{m-2}$
• Ganzzahlige Probleme: $x_1,...,x_n\in \mathbb{Z}$ 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.