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\le b,Ax\ge 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)=\underset{u}{min}\{L(x,u)+V(f(x,u))\}$
• Stochastisch: $V(x)=\underset{u}{min}\{L(x,u)+\sum _{x^{\prime }}P(x^{\prime }|x,u)V(x^{\prime })\}$
• $V(x)$: Wertfunktion
• $L(x,u)$: Kosten- oder Nutzenfunktion
• $P(x^{\prime }|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}$.