Operations Research 2 - Cheatsheet

Simplex-Algorithmus

Definition:

Zur Lösung linearer Optimierungsprobleme.

Details:

• Voraussetzung: Lineare Programmierungssysteme in kanonischer Form. Zielfunktion maximieren: \( c^T x \). Nebenbedingungen: \( Ax = b \), \( x \geq 0 \).
• Wähle Basislösung \( \textbf{B} \rightarrow x = B^{-1}b \)
• Berechne reduzierten Kostenvektor \( \bar{c} = c_N - N^T B^{-T} c_B \)
• Finde nicht-basisvariablen mit \( \bar{c}_j < 0 \)
• Pivotisiere um neue Basis zu finden
• Iteration bis \( \bar{c}_j \geq 0 \) für alle \( j \)

Dualitätstheorie

Definition:

Theorie, die besagt, dass zu jedem linearen Optimierungsproblem ein duales Problem existiert, bei dem die optimalen Lösungen der beiden Probleme miteinander verknüpft sind.

Details:

• Primal Problem: Minimierung oder Maximierung einer linearen Zielfunktion unter Nebenbedingungen.
• Duales Problem: Besteht aus den Koeffizienten der Nebenbedingungen des primalen Problems als Zielfunktion und umgekehrt.
• Duale Variablen: Lagrange-Multiplikatoren der Nebenbedingungen des primalen Problems.
• Schwache Dualität: Für jede zulässige Lösung des primalen und dualen Problems gilt: Zielfunktion des dualen Problems ≤ Zielfunktion des primalen Problems (bei Minimierung).
• Starke Dualität: Wenn das primale Problem eine optimale Lösung hat, hat auch das duale Problem eine optimale Lösung und die Werte der Zielfunktionen sind gleich.
• Konvertierung: Dualitätstheorie hilft bei der Lösung des primalen Problems, indem man das duale Problem löst.

Branch-and-Bound-Verfahren

Definition:

Branch-and-Bound-Verfahren: Optimierungsalgorithmus zur Lösung diskreter und kombinatorischer Probleme durch systematische Aufteilung des Lösungsraums.

Details:

• Eignet sich besonders für Integer-Programme.
• Verwendet: Zerlegung, Abschätzungen und Schranken.
• Zerlegung des Problems in Teilprobleme (Branching).
• Berechnung und Vergleich von Schranken zur Bewertung der Teilprobleme (Bounding).
• Ignorieren von Teilproblemen, die keine bessere Lösung liefern können (Pruning).
• Fortsetzung bis zur optimalen Lösung oder akzeptablen Näherung.
• Z.B. zur Lösung von Traveling Salesman Problem (TSP), Knapsack Problem.

Bellman-Gleichung

Definition:

Fundamentales Prinzip in dynamischen Programmierungsproblemen, das die optimale Entscheidungsstrategie durch rekursive Zerlegung in Teilprobleme definiert.

Details:

• Zentrale mathematische Formulierung: \[ V(s) = \max_a \left\{ R(s, a) + \gamma \sum_{s'} P(s'|s, a) V(s') \right\} \]
• \(V(s)\): Wertfunktion im Zustand \(s\)
• \(R(s, a)\): Belohnung für Aktion \(a\) im Zustand \(s\)
• \(\gamma\): Diskontfaktor (\(0 \leq \gamma \leq 1\))
• \(P(s'|s, a)\): Übergangswahrscheinlichkeit zum Zustand \(s'\) bei Aktion \(a\)

Genetische Algorithmen

Definition:

Genetische Algorithmen (GA) sind heuristische Suchverfahren, die von biologischen Evolutionsprozessen inspiriert sind und verwendet werden, um Optimierungsprobleme zu lösen.

Details:

• Grundprinzipien: Selektion, Kreuzung, Mutation, Rekombination
• Selektion: Auswahl der besten Individuen basierend auf Fitness
• Kreuzung (Crossover): Austausch von Teilen zweier Individuen zur Bildung neuer
• Mutation: Zufällige Veränderung eines Individuums zur Erhöhung der genetischen Vielfalt
• Fitnessfunktion: Bewertet, wie gut ein Individuum das Problem löst
• Populationsgröße: Anzahl der gleichzeitig betrachteten Individuen
• Anwendung: Komplexe und nichlineare Optimierungsprobleme

Dekomposition von Optimierungsproblemen

Definition:

Zerlegung eines großen Optimierungsproblems in kleinere, leichter lösbare Teilprobleme.

Details:

• Ziel: Verbesserung der Lösungsfindung und Rechenzeit
• Einsatz von Zerlegungsverfahren wie Benders Dekomposition und Dantzig-Wolfe Dekomposition
• Benders Dekomposition: Trennung in Master- und Subprobleme
• Dantzig-Wolfe Dekomposition: Rekombination nach Zerlegung
• Nutzung in linearer Programmierung, gemischt-ganzzahliger Programmierung