Zusammenfassung von Grundlagen der Wirtschaftsmathematik

## Einführung Lineare Optimierung beschäftigt sich mit der Bestimmung optimaler Lösungen für Probleme, deren Ziel- und Nebenbedingungen linear in den Entscheidungsvariablen sind. Typische Anwendungen finden sich in Produktion, Logistik, Portfolio-Optimierung und Ressourcenplanung. > Definition: Lineares Optimierungsproblem (Standardform) > Ein maximierbares Problem in Standardform lautet: $$\text{maximiere } Z = \vec{c}^T\vec{x} \quad\text{unter } A\vec{x} = \vec{b},\; \vec{b}\ge 0,\; \vec{x}\ge 0.$$ ## Grundbegriffe und Struktur ### Entscheidungsvariablen - Entscheiden, was verändert werden kann; z.B. Produktionsmengen $x_1$, $x_2$. ### Zielfunktion - Lineare Funktion der Variablen: $$Z = c_1 x_1 + c_2 x_2 + \dots + c_n x_n.$$ - Ziel: Maximieren oder Minimieren von $Z$. ### Nebenbedingungen (Restriktionen) - Lineare Ungleichungen oder Gleichungen: $$a_{11}x_1 + a_{12}x_2 \le b_1,$$ $$a_{21}x_1 + a_{22}x_2 \le b_2,$$ usw. - Nichtnegativitätsbedingungen: $x_i \ge 0$ für alle $i$. > Definition: Zulässiger Lösungsbereich > Die Menge aller Vektoren $\vec{x}$, die alle Nebenbedingungen und $\vec{x}\ge 0$ erfüllen, nennt man zulässigen Lösungsbereich $B$. ### Eigenschaften des zulässigen Bereichs - $B$ ist konvex und (bei beschränkten Problemen) ein Vieleck in der Ebene für $n=2$. - Leerer $B$ bedeutet keine zulässige Lösung. Fun fact: Wusstest du, dass bei linearen Zielfunktionen das Optimum (falls endlich) immer in mindestens einem Eckpunkt des zulässigen Bereichs liegt? Dies ist die Grundlage sowohl der graphischen Lösung als auch des Simplexverfahrens. ## Graphische Lösung (für $n=2$) 1. Modell aufstellen: Zielfunktion und alle Restriktionen mit $x_1,x_2\ge 0$. 2. Jede Ungleichung als Gerade zeichnen und zulässige Halbebene markieren. 3. Schnitt der Halbebenen ergibt den zulässigen Bereich $B$. 4. Zielfunktionsgerade: Schreibe $x_2$ als Funktion von $x_1$: $$x_2 = -\frac{c_1}{c_2}x_1 + \frac{Z}{c_2}.$$ 5. Verschiebe diese Gerade parallel in Richtung wachsender $Z$ (bei Maximierung) oder sinkender $Z$ (bei Minimierung), bis sie den zulässigen Bereich in einem Eckpunkt berührt. - Ein eindeutiges Optimum liegt vor, wenn die Zielfunktionsgerade genau einen Eckpunkt teilt. - Unendlich viele Optima treten auf, wenn die Zielfunktionsgerade mit einer Restriktionskante zusammenfällt; dann sind alle Punkte auf diesem Segment optimal. - Keine endliche Lösung (unbeschränkt), wenn sich die Zielfunktionsgerade beliebig weit in „bessere“ Richtungen verschieben lässt, ohne $B$ zu verlassen. ### Beispiel (kurz) Gegeben: Produktionsmengen $x_1,x_2$; Kapazitätsrestriktionen und Absatzhöchstmengen. Vorgehen: Gleichungen aufstellen, Graph zeichnen, zulässigen Bereich finden, Eckpunkte prüfen und dasjenige mit maximalem Deckungsbeitrag auswählen. ## Simplexverfahren Das Simplexverfahren löst Probleme in Standardgleichungsform effizient. > Definition: Simplextableau > Ein Tableau fasst die Koeffizienten von $A$, die Basisvariablen, die rechte Seite $\vec{b}$ und die Zielfunktionszeile zusammen, um iterative Basiswechsel (Pivotschritte) durchzuführen. ### Wahl der Pivotspalte (Optimalitätskriterium) - Wenn in der Zielfunktionszeile noch negative Koeffizienten vorkommen (bei Maximierung), existiert Verbesserungspotential. - Wähle als Pivotspalte die Spalte mit dem kleinsten negativen Zielfunktionskoeffizienten. - Wenn alle Koeffizienten nichtnegativ sind, ist die aktuelle Basislösung optimal. ### Wahl der Pivotzeile (Zulässigkeits- / Engpassbedingung) - Berechne für jede Zeile mit positivem Pivotelement $a_{ik}>0$ den Quotienten $$\frac{b_i}{a_{ik}}.$$ - Wähle die Zeile mit dem kleinsten nichtnegativen Quotienten als Pivotzeile; das sichert, dass die neue Basislösung zulässig bleibt. ### Einschränkungen des Verfahrens - Das dargestellte Simplexverfahren benötigt die Standardform $A\vec{x}=\vec{b},\;\vec{b}\ge 0,\;\vec{x}\ge 0$. - Spezielle Fälle wie degenerierte Lösungen, unbeschränkte Probleme oder Mehrfachoptimalitäten erfordern be