Wirtschaftswissenschaften Mathematik – Lineare Optimierung
Karteikarten zum Thema „Wirtschaftswissenschaften“ · 13 Karten · von atrio. Beispiele: Was ist ein lineares Optimierungsproblem in Standardform? · Welche Bed…
Karten
13 KartenWas ist ein lineares Optimierungsproblem in Standardform?
Rückseite
Maximiere c^T x unter Ax ≤ b, x ≥ 0 mit Zielvektor c, Restriktionsmatrix A, Ressourcenvektor b und Entscheidungsvariablen x.
Welche Bedingungen müssen für eine zulässige Basislösung erfüllt sein?
Rückseite
Genau m linear unabhängige Spalten von A bilden Basis B, nichtbasisvariablen sind null, Basislösung x_B = B^{-1}b ≥ 0 ergibt sich eindeutig.
Was besagt das Optimalitätskriterium im Simplex-Algorithmus?
Rückseite
Eine zulässige Basislösung ist optimal, falls alle reduzierten Kosten c̄_N = c_N - c_B^T B^{-1} N ≤ 0 (Maximierung) sind.
Wie wird die eintrittende Variable im Simplex-Schritt gewählt?
Rückseite
Bei Maximierung: Variable mit größtem positivem reduzierten Kostenkoeffizienten (Bland-Regel oder Dantzig-Regel zur Verhinderung von Zyklen).
Wie bestimmt man die austretende Variable beim Pivot-Schritt?
Rückseite
Minimales-Quotienten-Kriterium: min {b_i / a_ij | a_ij > 0} über alle Zeilen der Basismatrix – sichert Zulässigkeit der neuen Lösung.
Was ist das duale Problem zu einem Primalmaximierungsproblem in Standardform?
Rückseite
Minimiere b^T y unter A^T y ≥ c, y ≥ 0. Jede Primalrestriktion entspricht einer Dualvariablen (Schattenpreis).
Was besagt der starke Dualitätssatz der linearen Optimierung?
Rückseite
Falls das Primalproblem eine optimale Lösung besitzt, besitzt auch das Dualproblem eine optimale Lösung und beide Optimalwerte stimmen überein.
Wie interpretiert man ökonomisch die optimalen Dualvariablen (Schattenpreise)?
Rückseite
Ein Schattenpreis y_i gibt die Änderung des Optimalwerts bei marginaler Erhöhung der i-ten Ressource b_i an (Grenznutzen).
Was untersuchen Sensitivitätsanalysen bei linearen Optimierungsproblemen?
Rückseite
Stabilität der optimalen Basis bei Änderungen von Zielfunktionskoeffizienten, Restriktionsrechten Seiten oder Hinzufügen neuer Restriktionen/Variablen.
Wann liegt Entartung (Degenerierung) im Simplex-Algorithmus vor?
Rückseite
Mindestens eine Basivariable ist null in der Basislösung. Kann zu Zyklen führen, bei gleicher Zielfunktion aber verschiedenen Basen.
Wie erkennt man alternative Optimallösungen im Simplex-Tableau?
Rückseite
Mindestens eine nichtbasisvariable hat reduzierte Kosten null bei optimaler Lösung – Konvexkombinationen erzeugen unendlich viele Optima.
Wodurch unterscheidet sich das Transportproblem von allgemeinen LPs?
Rückseite
Spezielle Struktur: Angebots- und Nachfragerestriktionen, Gesamtangebot = Gesamtnachfrage. Lösbar mit Nordwest-Ecken-Regel, Vogel-Verfahren oder MODI-Methode.
Warum sind ganzzahlige lineare Programme (ILP) schwieriger als LPs?
Rückseite
Ganzzahligkeitsrestriktionen machen das Problem NP-schwer; LP-Relaxation liefert untere Schranke, Branch-and-Bound oder Cutting Planes nötig für Exaktheit.