Einführung in die Optimierung - Cheatsheet.pdf

Einführung in die lineare Programmierung

Definition:

Lineare Programmierung (LP) beschäftigt sich mit der Maximierung oder Minimierung einer linearen Zielfunktion unter linearen Nebenbedingungen.

Details:

• Standardform: Optimiere von c mit B≈
• Zielfunktion: Überprüfe Lösung eventuell durch Zeichnen.
• Basislösungen und Grundlösungen für Gleichungssysteme
• Simplex-Algorithmus zur Lösung von LP-Problemen
• Zweiphasenverfahren, wenn keine zulässige Ausgangslösung
• Duale lineare Programmierung: identifiziert die LP-Probleme
• Anwendung in Wirtschaft, Logistik, Produktion

Simplex-Verfahren

Definition:

Algorithmus zur Lösung von linearen Programmen.

Details:

• Ziel: Maximierung/Minimierung einer linearen Zielfunktion unter linearen Nebenbedingungen.
• Start an einer Basisecke des zulässigen Bereichs, Bewegung entlang der Kanten.
• Iteration bis optimale Lösung oder Unbeschränktheit gefunden wird.
• Eckpunktlösung und Erhöhung der Variablen für besseren Zielfunktionswert.
• Mathematische Form: Standardform mit Basislösungen.
• Komponenten: Tableau, Pivot-Operationen.
• Abbruchkriterien: Optimalität (alle Koeffizienten der Zielfunktion nicht-negativ) oder Unbeschränktheit.
• Konvergenz: Endliche Anzahl von Schritten bei finiten Lösungen.
• Dualitätstheorie: Zusammenhang mit dualem Problem.

Dualitätstheorie

Definition:

Dualitätstheorie bezieht sich auf das Konzept, dass jedem Optimierungsproblem ein Duales Problem zugeordnet ist. Lösungen des Dualen Problems liefern Grenzen für die Lösungen des Primärproblems.

Details:

• Für ein lineares Optimierungsproblem (Primärproblem) in Standardform gibt es ein entsprechendes Duales Problem.
• Primärproblem (Standardform): \[ \min c^Tx \quad \text{s.t.} \quad Ax \geq b, \quad x \geq 0 \]
• Entsprechendes Duales Problem: \[ \max b^Ty \quad \text{s.t.} \quad A^Ty \leq c, \quad y \geq 0 \]
• Schwache Dualität: Wenn \(x\) zulässige Lösung für das Primärproblem und \(y\) zulässige Lösung für das Dualproblem ist, dann gilt \(c^Tx \, \geq \, b^Ty\).
• Starke Dualität: Wenn \(x^*\) optimale Lösung für das Primärproblem und \(y^*\) optimale Lösung für das Dualproblem ist, dann gilt \(c^Tx^* \, = \, b^Ty^*\).
• Komplementäre Schlupfbedingungen: \[ y_i (a_i^T x - b_i) = 0 \quad \forall i \]

Gradientenabstiegsverfahren

Definition:

Iterative Methode zur Minimierung einer Funktion durch Bewegung in Richtung des negativen Gradienten.

Details:

• Funktionswert verbessert durch Schritt in Richtung
• Schrittweite: Schrittweite optimieren
• :
• Korrektur: Update-Regel,
• : für

Lagrange-Multiplikatoren

Definition:

Methode zur Lösung von Optimierungsproblemen mit Gleichungsrestriktionen.

Details:

• Zielfunktion: f(x,y,...)
• Restriktion(en): g(x,y,...) = 0
• Bildung der Lagrange-Funktion: \( \mathcal{L}(x,y,...,\lambda) = f(x,y,...) + \lambda \cdot g(x,y,...) \)
• Notwendige Bedingungen: \( \frac{\partial \mathcal{L}}{\partial x} = 0, \frac{\partial \mathcal{L}}{\partial y} = 0, ..., \frac{\partial \mathcal{L}}{\partial \lambda} = 0 \)

Traveling-Salesman-Problem (TSP)

Definition:

Optimierungsproblem, bei dem ein Handlungsreisender die kürzeste Rundreise finden muss, die alle gegebenen Städte genau einmal besucht und zum Ausgangspunkt zurückkehrt.

Details:

• Ziel: Finde einen Hamiltonkreis minimaler Länge.
• Kostenmatrix: \(c_{ij}\) gibt die Kosten von Stadt i nach Stadt j an
• Optimierungsfunktion: \[ \text{minimiere } \textstyle \sum_{i=1}^{n-1} c_{x_i x_{i+1}} + c_{x_n x_1} \text{ über alle Permutationen (x_1, x_2, \ldots, x_n) der Städte} \]
• NP-schwer
• Heuristiken und approximative Algorithmen verfügbar: z.B. Nearest-Neighbor, Christofides-Algorithmus

Dynamische Programmierung

Definition:

Dynamische Programmierung ist eine Methode zur Lösung von Optimierungsproblemen, die Probleme in Teilprobleme zerlegt und deren Lösungen speichert, um Überberechnungen zu vermeiden.

Details:

• Prinzip: Zerlegung in Teilprobleme und Speicherung der Zwischenlösungen (Memoisation).
• Typische Struktur: Rekursiver Ansatz mit Überprüfung gespeicherter Ergebnisse.
• Anwendungsbereiche: Kürzeste Wege (z.B. Bellman-Ford-Algorithmus), ganzzahlige Optimierungsprobleme, Sequenzalignierung.
• Definition der Zustandsvariablen und Übergangsfunktionen.
• Formel: Optimalitätsprinzip von Bellman: \( V(i) = \text{opt} \big( C(i,j) + V(j) \big) \) für geeignete Kostenfunktion \( C(i,j) \)

Greedy-Algorithmen

Definition:

Greedy-Algorithmen nutzen eine Vorgehensweise, bei der in jedem Schritt die lokal beste Lösung gewählt wird in der Hoffnung, eine globale optimale Lösung zu finden.

Details:

• Schrittweise Wahl der besten lokalen Option
• Kann nicht globale Optimallösung garantieren
• Einsatzgebiete: Huffman-Codierung, Prim's Algorithmus, Kruskal's Algorithmus, Interval Scheduling
• Geeignet für bestimmte Klassen von Optimierungsproblemen, besonders solche mit optimaler Substruktur und Greedy-Auswahl-Eigenschaft
• \textbf{Greedy-Choice Property}: Eine global optimale Lösung kann durch eine Folge von lokalen Optimierungen gefunden werden
• \textbf{Optimal Substructure}: Optimale Lösungen von Teilproblemen führen zu einer optimalen Lösung des Gesamtproblems