Management Science (MiM) - Cheatsheet

Einfachextraktion und Implementierung von Optimierungsproblemen

Definition:

Identifikation und Lösung von Optimierungsproblemen durch Extrahieren der relevanten Variablen und Parameter sowie Implementierung der Lösungsmethoden.

Details:

• Identifikation der Ziel- und Nebenbedingungen
• Formulierung des Optimierungsproblems in mathematischer Form
• Verwendung von Software-Tools (z.B. Python, MATLAB) zur Implementierung
• Beispiel für ein lineares Optimierungsproblem:

Simplexverfahren in der linearen Programmierung

Definition:

Das Simplexverfahren ist ein Algorithmus zur Lösung linearer Optimierungsprobleme.

Details:

• Funktioniert durch schrittweises Verschieben entlang der Kanten des zulässigen Bereichs.
• Ziel ist es, die Zielfunktion zu maximieren oder zu minimieren.
• Mathematisch ausgedrückt: Gegeben eine Zielfunktion \(Z = c_1x_1 + c_2x_2 + ... + c_nx_n\) unter Nebenbedingungen in der Form \(Ax \leq b\).
• Start bei einer Ecklösung und bewegen zu benachbarten Ecken, um beste Lösung zu finden.
• Nutze Pivot-Operationen zur Aktualisierung.
• Endet, wenn keine Verbesserung mehr möglich ist.

Dualität und Sensitivitätsanalyse bei linearen Programmen

Definition:

Dualität: Zu jedem LP existiert ein Dualproblem mit umgekehrter Zielfunktion und -bedingungen. Sensitivitätsanalyse: Untersuchung wie Änderungen der Koeffizienten des LP die Lösung beeinflussen.

Details:

• Primal <=> Dual: Zielfunktion und Bedingungen tauschen Rollen
• Dualitätssätze: Starke und schwache Dualität
• Sensitivitätsanalyse: Änderungen bei Kostenkoeffizienten, Kapazitätsrestriktionen
• Schattenpreise: Marginale Wertveränderung einer Ressource
• Berechnung: Simplex-Methode

Kürzester Weg und minimale Spannbaumprobleme in Netzwerken

Definition:

Minimaler Spannbaum: Baum, der alle Knoten eines Graphen mit minimaler Gesamtkantenlänge verbindet. Kürzester Weg: Pfad zwischen zwei Knoten, der die geringste Summe der Kantengewichte hat.

Details:

• Algorithmen für minimalen Spannbaum: Kruskal, Prim.
• Algorithmus für kürzesten Weg: Dijkstra, Bellman-Ford.
• Formel für Distanz: \(d(u, v) = \min( \Sigma \text{Kantengewicht})\).
• Minimaler Spannbaum: \(\text{min}\Sigma \text{Kantengewicht}\).

Nash-Gleichgewicht in der Spieltheorie

Definition:

Nash-Gleichgewicht, wo kein Spieler durch Änderung der eigenen Strategie verbessering erzielt, sofern die anderen gleich bleiben.

Details:

• Formel: \( s_i^* = arg \max_{s_i} u_i(s_i, s_{-i}^*) \)
• Jeder Spieler wählt beste Antwort auf Strategie der Anderen
• Kann in Reinform oder gemischter Form auftreten
• Bedeutend für strategische Entscheidungen in Management-Spielen
• Spielt besondere Rolle bei nicht-kooperativen Spielen

Bellman-Gleichungen in der dynamischen Programmierung

Definition:

Bellman-Gleichungen, grundlegend für die dynamische Programmierung, beschreiben die Rekursion zur Ermittlung optimaler Entscheidungen.

Details:

• Zentrale Formel: \[ V(s) = \text{max}_{a \,\text{in}\, A} \, \left( R(s,a) + \gamma \sum_{s'} P(s'|s,a) V(s') \right) \]
• \( V(s) \): Wertfunktion für Zustand \( s \)
• \( a \): Aktion
• \( A \): Menge möglicher Aktionen
• \( R(s,a) \): Belohnung für Aktion \( a \) in Zustand \( s \)
• \( \gamma \): Diskontfaktor
• \( P(s'|s,a) \): Übergangswahrscheinlichkeit zu Zustand \( s' \) nach Aktion \( a \) in Zustand \( s \)
• Hauptziel: Finde optimale Politik \( \pi(s) \)

Zeitabhängige Entscheidungsprozesse mit dynamischer Programmierung

Definition:

Zeitabhängige Entscheidungsprozesse (auch bekannt als stochastische Prozesse oder Markov-Entscheidungsprozesse) analysieren Entscheidungen, die über mehrere Zeitpunkte hinweg getroffen werden müssen. Dynamische Programmierung (DP) bietet einen systematischen Ansatz zur Lösung solcher Probleme, indem sie diese in einfachere Teilprobleme zerlegt.

Details:

• DP-Ansatz: Nutzung der Bellman-Gleichung Formel:
• Bellman'sche Optimierungsprinzip: Formel:
• Optimale Politik/Strategie (Policy): Folge der besten Entscheidungen
• Zeitlich diskrete Prozesse