Lineare und Kombinatorische Optimierung - Cheatsheet

Graphische Lösungsmethoden in der linearen Programmierung

Definition:

Graphische Lösungsmethoden werden verwendet, um lineare Optimierungsprobleme mit zwei Entscheidungsvariablen visuell zu lösen.

Details:

• Ziel: Maximiere oder minimiere eine Zielfunktion, z. B. \( z = c_1x_1 + c_2x_2 \).
• Schritte:
  • Zeichne alle Nebenbedingungen als Geraden im \(x_1x_2\)-Koordinatensystem.
  • Bestimme den zulässigen Bereich (Schnittbereich aller Nebenbedingungen).
  • Zielfunktion als Gerade im Koordinatensystem darstellen und diese entlang eines Vektors \(c = (c_1, c_2)\) verschieben.
  • Optimalen Punkt finden: Extremwert eines Eckenpunktes im zulässigen Bereich, wo die Zielfunktion maximiert bzw. minimiert wird.
• Anwendbar nur für Probleme mit genau zwei Variablen.

Pivot-Operationen und Tableau-Formen im Simplex-Algorithmus

Definition:

Pivot-Operationen ändern die Basislösung im Simplex-Algorithmus durch Austausch von Basisvariablen. Tableau-Formen sind Darstellungen des LOPs in tabellarischer Form zur Durchführung dieser Operationen.

Details:

• Pivot-Operation: Auswahl einer Ein- und Austrittsvariable zur Verbesserung der Zielfunktion.
• Eintrittsvariable: Die Nichtbasisvariable mit dem negativsten reduzierten Kostenkoeffizienten (c-Barj < 0).
• Ausgangsvariable: Bestimmt durch die minimale nichtnegative Quotientenregel.
• Tableau-Formen: Enthalten Basisvariable, Nichtbasisvariable, Zielfunktion und Einschränkungen.
• Umrechnung: Basis- und Nichtbasisvariablen werden durch Pivot-Operationen modifiziert.
• Ziel: Finden der optimalen Lösung durch schrittweise Verbesserung der Zielfunktion.

Primal-Dual-Beziehungen und deren ökonomische Interpretation

Definition:

Primal-Dual-Beziehungen: Zusammenhang zwischen einem Optimierungsproblem (Primal) und seinem dualen Problem (Dual), oft verwendet zur Überprüfung der Optimalität und zur Lösung von Optimierungsproblemen. Ökonomische Interpretation: Veranschaulichung von Ressourcen und Preisen im Kontext der Optimierungsprobleme.

Details:

• Primal problem: Ursprüngliches Optimierungsproblem (meist Minimierungsaufgabe).
• Dual problem: Abgeleitetes Problem basierend auf Lagrange-Multiplikatoren (meist Maximierungsaufgabe).
• Schwache Dualität: Der Wert der Zielfunktion des Dualen ist immer kleiner oder gleich dem Wert der Zielfunktion des Primals: \[ z_D \, \leq z_P \]
• Starke Dualität: Im Optimalfall sind die Werte der Zielfunktionen gleich: \[ z_P = z_D \]
• Komplementäre Schlupfbedingungen: Verknüpfung der Primal- und Dualvariablen: \[ x_i (b_i - A_i x) = 0 \quad \forall \, i \]
• Ökonomische Interpretation: Primal-Variable repräsentiert Ressourcennutzung, Dual-Variable repräsentiert Schattenpreise.

Branch-and-Bound Methode in der ganzzahligen Optimierung

Definition:

Branch-and-Bound (B&B) ist ein Algorithmus zur Lösung von ganzzahligen Optimierungsproblemen, der systematisch den Lösungsraum durch Suchen aufteilt und bewertet.

Details:

• Eingeschränkter Baum (Branch): Der Lösungsraum wird rekursiv in kleinere Teilprobleme gegliedert.
• Schranken (Bound): Für jedes Teilproblem werden Schranken aufgestellt, um unvorteilhafte Pfade frühzeitig abzubrechen.
• LP-Relaxation: Oft wird zunächst das entsprechende lineare Programm gelöst, um Bounds zu berechnen.
• Bounding: Vergleich der aktuellen Lösung mit der besten bekannten ganzzahligen Lösung zur Optimierung.
• Ausschlusskriterien: Wenn die Schranke eines Teilproblems schlechter als die bisher beste Lösung ist, wird der entsprechende Zweig verworfen.
• Ziel: Finden der optimalen ganzzahligen Lösung durch effiziente Reduktion des Suchraumes.

Cutting-Plane Verfahren zur Lösung ganzzahliger Optimierungsprobleme

Definition:

Ein iteratives Verfahren zur Lösung von ganzzahligen linearen Programmierungsproblemen (ILPs) durch Hinzufügen von Schnittebenen (zusätzlichen Ungleichungen), die die zulässige Region verkleinern, bis eine ganzzahlige Lösung gefunden wird.

Details:

• Startet mit der Lösung des Relaxierten Problems (ILP ohne Ganzzahligkeitsbedingungen).
• Findet Schnittebene, die die aktuelle nicht-ganzzahlige Lösung ausschließt, aber alle gültigen ganzzahligen Lösungen beibehält.
• Fügt die Schnittebene dem Modell hinzu und löst das modifizierte Problem erneut.
• Wiederholt den Prozess, bis eine ganzzahlige Lösung gefunden wird.
• Häufig verwendete Schnittebenen: Gomory-Cuts, Chvátal-Gomory-Schnitten.
• Formel für eine Gomory-Schnittebene (im Fraktionalbereich):

Optimierung auf Graphen: Algorithmen und Anwendungen

Definition:

Optimierung auf Graphen beschäftigt sich mit der Suche nach optimalen Lösungen für Probleme, die durch Graphen modelliert werden können. Dies umfasst die Verwendung von Algorithmen zur Lösung von Aufgaben wie dem kürzesten Weg, dem minimalen Spannbaum und dem maximalen Fluss.

Details:

• Kürzeste Weg: Dijkstra-Algorithmus, Bellman-Ford-Algorithmus
• Minimaler Spannbaum: Kruskal-Algorithmus, Prim-Algorithmus
• Maximaler Fluss: Ford-Fulkerson-Algorithmus, Edmonds-Karp-Algorithmus
• Komplexität: Zeit- und Platzkomplexität der einzelnen Algorithmen
• Anwendungen: Netzwerkanalyse, Transportplanung, Scheduling, Resource Allocation

Netzwerkflussprobleme und zugehörige Algorithmen

Definition:

Optimierungsprobleme in Netzwerken, bei denen der Fluss in Kanten maximiert oder Kosten minimiert werden sollen.

Details:

• Netzwerk: Graph G=(V,E) mit Knoten V und Kanten E.
• Fluss f: Zuordnung von Strömungen zu Kanten, unter Beachtung der Kapazitäten der Kanten.
• Ford-Fulkerson-Algorithmus: Findet den maximalen Fluss in einem Netzwerk.
• Edmonds-Karp-Algorithmus: Eine Implementierung des Ford-Fulkerson-Algorithmus mit BFS zur Pfadsuche.
• Max flow min cut: Theorem zur Flussmaximierung: Der maximale Fluss entspricht der minimalen Schnittkapazität.

Dualsimplex-Verfahren und Sensitivitätsanalysen

Definition:

Dualsimplex-Verfahren: Verfahren zur Lösung von LP-Problemen, startet von einer dualfeasible Lösung. Sensitivitätsanalysen: Untersucht die Auswirkungen von Änderungen an den Parametern eines LP-Problems auf die optimale Lösung.

Details:

• Voraussetzung: Initiallösung ist dual-feasible
• Gleiche Iterationsschritte wie beim Simplex-Verfahren, aber Modi ändern sich
• Optimalitätsbedingungen erreichen durch Rückwärtsbewegung
• Sensitivitätsanalyse: Analysiert Robustheit der optimalen Lösung
• Änderungen: Zielfunktionskoeffizienten, rechte Seite der Nebenbedingungen, Matrixkoeffizienten
• Berechnung der zulässigen Änderungsintervalle der Parameter
• Eigenwerte der Nebenbedingungen: Einflüsse und Übergänge zwischen Basislösungen