Linear optimization - Cheatsheet

Grundlagen linearer Algebra und Matrizenrechnung

Definition:

Grundlagen der linearen Algebra und Matrizenrechnung umfassen die Untersuchung von Vektorräumen, linearen Abbildungen und Matrizen, die zentrale Objekte in der linearen Optimierung sind.

Details:

• Vektoren: Geordnete Liste von Zahlen, z.B. \(\begin{bmatrix} x_1 \ x_2 \ \dots \ x_n \end{bmatrix}\)
• Matrizen: Rechteckige Anordnungen von Zahlen, z.B. \(\begin{bmatrix} a_{11} & a_{12} \ a_{21} & a_{22} \end{bmatrix}\)
• Matrixmultiplikation: Zeilen-Spalten-Multiplikation, z.B. \((AB)_{ij} = \sum_{k} a_{ik}b_{kj}\)
• Determinante: Eine Zahl, die eine Matrix charakterisiert und z.B. für das Lösen von Gleichungssystemen verwendet wird, \(|A|\)
• Inverse Matrix: Eine Matrix \(A^{-1}\), die die Eigenschaft erfüllt, dass \(AA^{-1} = I\)
• Lineare Gleichungssysteme: Systeme der Form \(Ax = b\), die Lösungen durch Invertierung oder andere Methoden finden.

Anwendung linearer Modelle in der Wirtschaft

Definition:

Verwendung linearer Gleichungen und Ungleichungen zur Modellierung wirtschaftlicher Probleme und Entscheidungsfindung.

Details:

• Optimierungsprobleme: Kostenminimierung, Gewinnmaximierung
• Lineares Gleichungssystem: \(Ax = b\)
• Zielfunktion: \(Z = c^T x\)
• Einschränkungen: \(Ax \leq b\)
• Beispiele: Produktionsplanung, Transportprobleme, Portfolio-Optimierung

Behandlung von Restriktionen mittels Ungleichungen

Definition:

Verwendung von Ungleichungen zum Modellieren von Einschränkungen in linearen Optimierungsproblemen.

Details:

• Restriktionen begrenzen Lösungsraum.
• Typische Formen: \(ax + by \leq c\), \(dx + ey \geq f\), \(gx + hy = j\).
• Formuliert als Matrix-Ungleichungen: \(Ax \leq b\).
• Nichtnegativitätsbedingungen: \(x \geq 0\).
• Linearität sicherstellen.

Einführung in Softwaretools (z.B. MATLAB, LINDO, Excel Solver)

Definition:

Einführung in verschiedene Softwarewerkzeuge zur Lösung von linearen Optimierungsproblemen.

Details:

• MATLAB: Synthax für LP-Formulierung, Funktion linprog.
• LINDO: Speziell für LP, einfach zu bedienende Oberfläche, umfangreiche Dokumentation.
• Excel Solver: Nutzt Excel-Tabellen zur Formulierung und Lösung von LP-Problemen, anwendungsfreundlich für Anfänger.

Simplex-Verfahren und Dualitätsprinzipien

Definition:

Charakterisierung von linearen Optimierungsproblemen durch Setzen und Lösen von Gleichungssystemen; ermöglicht die Ermittlung eines optimalen Lösungswegs und die Analyse dualer Beziehungen.

Details:

• Das Simplex-Verfahren nutzt eine schrittweise Wiederholung, um die optimale Lösung zu finden.
• Startpunkt: Basislösung, die meist an den Ursprung gebunden ist.
• Iterationen bewegen sich entlang der Kanten des zulässigen Bereichs.
• Emailiergleichungen: Primaler und dualer LP Lösungen stehen in Beziehung zueinander.
• Ziel: Maximierung oder Minimierung der Zielfunktion.
• Dualitätsprinzip: Jede lineare Optimierungsaufgabe hat ein duales Problem mit umgekehrtem Optimierungsziel aber gleicher optimaler Zielfunktionswert.
• Optimalitätsbedingungen: Eine Lösung ist dann optimal, wenn primale und duale Lösungen vorhanden sind und identische Zielfunktionswerte aufweisen.

Ganzzahlige Programmierung und Branch-and-Bound Methode

Definition:

Verfahren zur Lösung von ganzzahligen linearen Programmierungsproblemen, basierend auf der schrittweisen Zerlegung des Lösungsraums.

Details:

• Problemformulierung: Maximieren oder Minimieren einer linearen Zielfunktion c^Tx unter den Einschränkungen Ax ≤ b und x ∈ ℤ.
• Branch-and-Bound-Methode:
• 1. Baumstruktur: Aufteilung des Lösungsraums in Teilräume.
• 2. Branching: Auswahl einer Variablen und Festlegung eines neuen Bereichs (Verzweigung).
• 3. Bounding: Berechnung und Vergleich von Schranken zur Bestimmung vielversprechender Knoten.
• 4. Pruning: Ausschluss unwirtschaftlicher Teilräume zur Verringerung des Suchraums.
• Schlüsselbegriffe: Beschränkung, Relaxation, optimale Lösung.
• Relevanz in der Ökonomie: Anwendung in Produktionsplanung, Standortwahl, Kostenminimierung.

Sensitivitätsanalyse und Robustheit von Lösungen

Definition:

Analyse wie Änderungen in den Parametern eines Optimierungsproblems die optimale Lösung beeinflussen.

Details:

• Untersuchung der Stabilität und Verlässlichkeit der Lösung.
• Typische Sensitivitätsanalysen beinhalten Parameter wie Kostenkoeffizienten, Ressourcenkapazitäten und Randbedingungen.
• Robustheitsanalyse sieht vor, wie Lösungen auf unvorhergesehene Veränderungen in den Parametern reagieren.
• Mathematische Modelle: Untersuchung der zulässigen Änderungen in den Parameterwerten, z.B. Änderung der Kostenfunktion \(c_j\), Restriktionskoeffizienten \(a_{ij}\) oder Kapazitätsgrenzen \(b_i\)
• Ergebnismetriken: Zwischenwerte, Schattenpreise, zulässige Bereichsänderungen.