Optimization in industry and economy - Cheatsheet

Formulierung linearer Optimierungsprobleme

Definition:

Formulierung eines Problems zur Maximierung oder Minimierung einer linearen Funktion unter Berücksichtigung linearer Gleichungen und Ungleichungen als Einschränkungen.

Details:

• Allgemeine Form: Maximiere/Minimiere \( c^T x \ )
• Einschränkungen: \( Ax \leq b \)
• Zusätzliche Bedingungen: \( x \geq 0 \)
• Variable \( x \): Parameters werden optimiert
• Koeffizientenmultiplikator: \( c \)
• Matrix der Einschränkungen: \( A \)
• Rechte-Seiten-Vektoren: \( b \)

Simplex Algorithmus zur Problemlösung

Definition:

Algorithmus zur Lösung von linearen Optimierungsproblemen (LP: Lineare Programme), insbesondere zur Maximierung oder Minimierung einer linearen Zielfunktion unter linearen Nebenbedingungen

Details:

• Starte an einer Ecke des zulässigen Bereichs (Basislösung)
• Iteriere zu benachbarten Ecken, um den Zielfunktionswert zu verbessern
• Suche wird über Pivot-Operationen durchgeführt
• Algorithmus endet, wenn keine Verbesserung mehr möglich ist oder unbeschränkte Lösung gefunden wird
• Komplexität hängt von der Anzahl der Variablen und Bedingungen ab
• Standard-Grundsatz: Wähle die Variable mit der höchsten Steigung (Kostenzuwachs pro Einheitszunahme) als nächste Pivot-Variable

Branch-and-Bound Verfahren

Definition:

Branch-and-Bound Verfahren: Kombinatorischer Optimierungsalgorithmus zur Suche nach optimalen Lösungen, typischerweise bei ganzzahligen Programmierungsproblemen.

Details:

• Teilt Problem in kleinere Teilprobleme (Branching).
• Berechnet obere und untere Schranken für Lösungen der Teilprobleme (Bounding).
• Verwirft Teilprobleme, deren Schranken optimale Lösung nicht verbessern können (Pruning).
• Iteriert, bis beste Lösung gefunden ist oder keine weiteren Teilprobleme verbleiben.
• Nutzbar für lineare und nichtlineare Optimierungsprobleme.

Bellmans Prinzip der optimalen Kontrolle

Definition:

Bellmans Prinzip der optimalen Kontrolle verwendet dynamische Programmierung zur Lösung von Entscheidungsproblemen, indem es komplexe Probleme in einfachere Teilprobleme zerlegt.

Details:

• Grundidee: Ein optimaler Entscheidungsprozess hat die Eigenschaft, dass unabhängig vom Anfangszustand und der Anfangsentscheidung, die verbleibenden Entscheidungen optimal sein müssen.
• Rekursionsformel: \[ V^*(s) = \text{max}_a \big( R(s,a) + \beta \text{E} [ V^*(s') | s, a ] \big)\]
• \( V^*(s) \) = optimaler Wert im Zustand \( s \)
• \( R(s, a) \) = Belohnung für Aktion \( a \) im Zustand \( s \)
• \( \beta \) = Diskontfaktor
• \( s' \) = nächster Zustand

Maximaler Fluss Algorithmus

Definition:

Algorithmus zur Bestimmung des maximalen Flusses in einem Netzwerkgraphen zwischen Quelle und Senke.

Details:

• Graph mit Kapazitäten auf den Kanten
• Maximalen Fluss berechnen: Ford-Fulkerson, Edmonds-Karp, Push-Relabel
• Flusserhaltungsbedingung: Summe eingehender Flüsse = Summe ausgehender Flüsse für jeden Knoten außer Quelle und Senke
• Kapazitätsbeschränkung: Fluss einer Kante darf deren Kapazität nicht überschreiten
• Residualnetzwerk: Gibt verbleibende Kapazitäten nach aktuellem Fluss an
• Maximales Flusssatz: Maximaler Fluss = Minimale Schnittkapazität

Metaheuristiken wie genetische Algorithmen und Simulated Annealing

Definition:

Metaheuristiken wie genetische Algorithmen und Simulated Annealing: Optimierungsverfahren, inspiriert von biologischen oder physikalischen Prozessen, um schwierige Probleme näherungsweise zu lösen.

Details:

• Genetische Algorithmen (GA): basieren auf Selektion, Kreuzung und Mutation, um Lösungen zu verbessern.
• Simulated Annealing (SA): nutzt Prinzipien der Thermodynamik, insbesondere das Abkühlen von Metallen, um globale Optima zu finden.
• GA Fitness-Funktion: bewertet Lösungsqualität.
• SA Abkühlplan: bestimmt Temperaturverlauf, z.B. \(\text{T}_{k+1} = \text{T}_k \times \text{alpha}\) mit \(\text{alpha} < 1\).
• Kombination aus Exploration (neue Lösungen finden) und Exploitation (bestehende Lösungen verbessern) entscheidend.
• Geeignet für große und komplexe Suchräume.

Dualität in der linearen Programmierung

Definition:

Dualität ist ein fundamentales Konzept in der linearen Programmierung, das besagt, dass jedem linearen Programm (Primärproblem) ein weiteres lineares Programm (Dualproblem) zugeordnet werden kann.

Details:

• Jedes Primärproblem hat ein zugehöriges Dualproblem.
• Optimallösungen der beiden Probleme liefern gleiche Zielfunktionswerte.
• Schwache Dualität: Der Zielfunktionswert des Dualproblems ist eine obere Schranke für das Minimum des Primärproblems.
• Starke Dualität: Bei optimalen Lösungen sind die Zielfunktionswerte von Primär- und Dualproblem identisch.
• Formel für das Primärproblem (Standardform): Maximiere: \(c^T x\) unter den Nebenbedingungen: \(Ax \leq b, \, x \geq 0\)
• Formel für das Dualproblem: Minimiere: \(b^T y\) unter den Nebenbedingungen: \(A^T y \geq c, \, y \geq 0\)

Gemischt-ganzzahlige lineare Programmierung

Definition:

Optimierungsproblem: linear, einige Variablen ganzzahlig.

Details:

• Zielfunktion: linear, z. B. \[ \text{maximiere } c^T x \]
• Nebenbedingungen: lineare Gleichungen/Ungleichungen, z. B. \[ Ax \leq b \]
• Variablen: teilweise ganzzahlig, z. B. \[ x_i \in \mathbb{Z} \]
• Schwieriger zu lösen als reine LP due to diskrete Variablen
• Methoden: Branch-and-Bound, Cutting Planes, Branch-and-Cut