Einführung in die Optimierung - Cheatsheet.pdf

Grundlagen der Linearen Programmierung

Definition:

Grundlagen der Linearen Programmierung: Methode zur Lösung von Optimierungsproblemen mit einer linearen Zielfunktion und linearen Nebenbedingungen.

Details:

• Zielfunktion: \( \text{maximiere / minimiere } c^T x \)
• Nebenbedingungen: \( A x \leq b \) und \( x \geq 0 \)
• Machbare Menge: Polyeder \( P = \{ x \mid A x \leq b, x \geq 0 \} \)
• Optimale Lösung: Punkt in P, an dem die Zielfunktion ihr Optimum erreicht
• Simplex-Algorithmus, Dualitätstheorie grundlegend

Simplex-Algorithmus

Definition:

Algorithmus zur Lösung von linearen Programmen und zur Optimierung von Zielfunktionen in linearen Ungleichungen durch Bewegung entlang der Kanten des zulässigen Bereichs.

Details:

• Ziel: Maximierung/Minimierung einer Zielfunktion
• Standardform: \[ \text{maximiere } c^T x \text{ unter den Nebenbedingungen } Ax \leq b, x \geq 0 \]
• Grundlagen: Basislösungen, Eckpunkte des zulässigen Bereichs
• Schrittweise Bewegung zu besseren Lösungen
• Endet bei optimaler Lösung oder Feststellung der Unbeschränktheit/Unlösbarkeit

Dualitätstheorie und Sensitivitätsanalyse

Definition:

Dualitätstheorie behandelt die Beziehung zwischen einem Optimierungsproblem (Primärproblem) und einem zugehörigen Dualproblem. Sensitivitätsanalyse untersucht, wie sich Änderungen der Parameter des Modells auf die optimale Lösung auswirken.

Details:

• Primärproblem:\[\min c^T x \quad \text{u.d.B.} \quad Ax \geq b, \; x \geq 0\]
• Dualproblem:\[\max b^T y \quad \text{u.d.B.} \quad A^T y \leq c, \; y \geq 0\]
• Schwache Dualität: \[ \text{Optimalwert des Dualproblems} \leq \text{Optimalwert des Primärproblems} \]
• Starke Dualität: Wenn eine optimale Lösung existiert, dann sind die Optimalwerte gleich.
• Sensitivitätsanalyse: Untersucht die Auswirkungen von Variationen in \(c, b\) oder \(A\) auf die Lösung.
• Schattenpreise: Ableitungen der Zielfunktion bezüglich der Nebenbedingungen.
• Reduced Costs: Zusätzlicher Gewinn pro Einheit einer nicht-basisvariablen Variable.

Newton-Verfahren

Definition:

Iteratives Verfahren zur Lösung von nichtlinearen Gleichungen mittels Taylor-Approximation.

Details:

• Updateschritt: \[ x_{k+1} = x_k - \frac{f'(x_k)}{f''(x_k)} \]
• Benötigt 2. Ableitung (Hessematrix bei multivariaten Funktionen)
• Schnelle Konvergenz in der Nähe eines Optimums, quadratische Konvergenz
• Anfällig für schlechte Startwerte

Branch-and-Bound Techniken

Definition:

Methode zur Lösung von kombinatorischen Optimierungsproblemen, indem systematisch alle möglichen Lösungen durchsucht und durch Abschätzung von Schranken bestimmte Äste im Suchbaum ausgeschlossen werden.

Details:

• Ziel: Minimierung/Maximierung der Zielfunktion
• Besteht aus drei Hauptschritten: Branching (Aufteilung des Problems), Bounding (Bestimmung von Schranken), und Pruning (Entfernen von unbrauchbaren Zweigen)
• Nutzt Upper und Lower Bounds zur Abschätzung
• Eignung besonders für NP-schwere Probleme
• Häufig bei Problemen wie dem Traveling Salesman oder dem Knapsack-Problem verwendet

Metaheuristische Verfahren: Simulated Annealing, Tabu Search

Definition:

Metaheuristische Verfahren zur globalen Optimierung durch Heuristiken, um lokale Minima zu vermeiden.

Details:

• Simulated Annealing: Kombination aus Metropolis-Algorithmus und Abkühlplan
• Zufällige Lösungssuche; akzeptiert auch schlechtere Lösungen mit Wahrscheinlichkeit \( e^{-\frac{\Delta E}{T}} \)
• Temperatur (T) verringert sich gemäß Abkühlplan
• Tabu Search: Verwendet (dynamische) Liste von „verbotenen” Lösungen, um Zyklen zu vermeiden
• Nutzt lokale Suche und Erweiterung von Nachbarschaftslösungen
• Tabu-Liste: Speichert kürzlich besuchte Lösungen; Tabu-Kriterien
• Aspirationskriterien: Überschreiben Tabu, wenn Lösung besser ist