Optimierung für Ingenieure - Cheatsheet

Mathematische Modellierung linearer Probleme

Definition:

Formulierung realer Probleme als lineare Modelle durch mathematische Gleichungen und Ungleichungen.

Details:

• Zielfunktion: \( \text{max/min } c^T x \)
• Lineare Nebenbedingungen: \[ Ax \leq b, Ax \geq b, Ax = b \]
• Entscheidungsvariablen: \( x \in \mathbb{R}^n \)
• Beispielanwendungen: Produktionsplanung, Transportprobleme, Netzwerkoptimierung

Simplex-Algorithmus

Definition:

Algorithmus zur Lösung linearer Optimierungsprobleme in der kanonischen Form.

Details:

• Findet optimale Lösungen für LP-Problem über Basislösungen.
• Start in Ecke des zulässigen Bereichs, iteriert entlang der Kanten.
• Wählt Iterationsrichtung, die Kostenfunktion am meisten verbessert.
• Endet, wenn kein Verbesserungsschritt mehr möglich ist (Optimallösung gefunden).
• Normalerweise effizient in der Praxis, trotz exponentieller Worst-Case-Komplexität.

Karush-Kuhn-Tucker-Bedingungen

Definition:

KKT-Bedingungen stellen notwendige und hinreichende Optimalitätsbedingungen für Optimierungsprobleme mit Gleichungs- und Ungleichungsnebenbedingungen dar.

Details:

• Formuliert für nichtlineare Optimierungsprobleme
• Setzt Lagrange-Funktion ein
• Voraussetzung: Differenzierbarkeit und konvexe Funktionen
• KKT-Bedingungen umfassen: Primal und duale Durchführbarkeit, Komplementäre Schlupfbedingung, Stationaritätsbedingung
• Lagrange-Multiplikatoren lösen Gleichungssysteme
• Für Ungleichungen: Aktivitätsbedingungen notwendig

Bellman-Gleichung

Definition:

Bellman-Gleichung für dynamische Programmierung und Optimierung.

Details:

• Grundlage für optimale Entscheidungsfindung in stochastischen und deterministischen Systemen
• Rekursive Beziehung zur Berechnung des Wertes eines Zustands:
• Deterministisch: \( V(x) = \min_u \{ L(x, u) + V(f(x, u)) \} \)
• Stochastisch: \( V(x) = \min_u \{ L(x, u) + \sum_{x'} P(x'|x,u) V(x') \} \)
• \(V(x)\): Wertfunktion
• \(L(x, u)\): Kosten- oder Nutzenfunktion
• \(P(x'|x,u)\): Übergangswahrscheinlichkeit
• \(f(x, u)\): Zustandsübergangsfunktion
• Wird iterativ verwendet in Algorithmen wie Value Iteration oder Policy Iteration

Genetische Algorithmen

Definition:

Stochastischer Optimierungsalgorithmus, der Prinzipien der natürlichen Evolution anwendet.

Details:

• Population von Individuen, die mögliche Lösungen repräsentieren
• Jedem Individuum wird eine Fitness-Funktion zugewiesen
• Selektion: Auswahl der besten Individuen
• Kreuzung (Crossover): Austausch von Genen zwischen Individuen
• Mutation: Zufällige Änderungen von Genen
• Genetischer Algorithmus durchläuft mehrere Iterationen (Generationen)
• Konvergenzkriterium: Stopp, wenn eine Lösung ausreichend gut ist oder eine maximale Anzahl von Generationen erreicht wurde

Lagrange-Multiplier

Definition:

Methode zur Lösung von Optimierungsproblemen mit Nebenbedingungen.

Details:

• Hauptidee: Einführung zusätzlicher Variablen (\textit{Lagrange-Multiplikatoren})
• Problemformulierung: Maximiere/Minimiere Funktion, wobei dies durch Nebenbedingungen eingeschränkt ist
• Lagrange-Funktion: \textbf{L}(x_1, x_2, \ldots, \lambda) = f(x_1, x_2, \ldots) + \lambda (g(x_1, x_2, \ldots) - c)
• Schritte zur Lösung:
• 1. Bilde die Lagrange-Funktion
• 2. Setze die partiellen Ableitungen der Lagrange-Funktion gleich Null
• 3. Löse das Gleichungssystem

Stochastische dynamische Programmierung

Definition:

Methode zur Lösung von Optimierungsproblemen mit Unsicherheit, verwendet stochastische Prozesse und dynamische Programmiertechniken

Details:

• Teilproblemformulierung, die sukzessiv gelöst wird
• Übergangs- und Ertragsfunktionen berücksichtigen Unsicherheit
• Bellman-Gleichung als zentral

Sensitivitätsanalyse

Definition:

Untersuchung der Auswirkungen von Änderungen der Eingabeparameter auf die optimale Lösung.

Details:

• Wichtige Methode bei der Evaluierung von Optimierungsmodellen.
• Berechnung der Ableitung der Zielfunktion oder der Nebenbedingungen bezüglich der Eingabeparameter.
• Normale Fragestellungen: Wie ändert sich die optimale Lösung, wenn Parameter variiert werden?
• Mathematisch: Betrachtung der partiellen Ableitungen \(\frac{\partial f}{\partial x_i}\).