1. Einführung in Operations Research

Untersuchungsgegenstand von OR ist die quantitative Optimierung von Entscheidungen. Konkret geht es um Probleme, bei denen eine oder mehrere Zielgrößen (z. B. Kosten, Gewinn, Zeit) unter Einhaltung bestimmter Nebenbedingungen (Ressourcen, Kapazitäten, gesetzliche Vorgaben) bestmöglich – also maximal oder minimal – gewählt werden sollen.

OR untersucht also, wie man aus einer Menge zulässiger Handlungsalternativen die beste Alternative bestimmen kann, und welche mathematischen Methoden dafür geeignet sind (Lineare Optimierung, Ganzzahlige Optimierung, Graphenalgorithmen, Heuristiken).

Die drei Aspekte sind Eingrenzen, Nähern und Vereinfachen:

• Eingrenzen – Entscheidung, welche Aspekte der Realität ins Modell aufgenommen werden. Beispiel: Bei einer Tourenplanung fließen Straßenlängen ein, aber nicht das Wetter jeder einzelnen Fahrt.
• Nähern – Übertragung von realen Größen in eine mathematisch handhabbare Form. Beispiel: Nichtlineare Kostenverläufe werden linear approximiert.
• Vereinfachen – Reduktion auf die entscheidungsrelevanten Größen; Details, die das Ergebnis nicht wesentlich beeinflussen, werden weggelassen.

Die drei Schritte zusammen sorgen dafür, dass ein Modell überhaupt lösbar wird, ohne dass die Aussagekraft für die Realität verloren geht.

Variablen $\vec{x} = (x_1, \dots, x_n)$ sind die Stellgrößen, über die der Entscheider verfügt (z. B. Produktionsmengen, Investitionsanteile, Zuordnungsindikatoren).

Zielfunktion $z = f(\vec{x})$ ist die Kennzahl, die optimiert werden soll – entweder maximiert (Gewinn, Nutzen) oder minimiert (Kosten, Zeit, Distanz).

Nebenbedingungen $g_i(\vec{x}) \le 0$ sind Einschränkungen, die eingehalten werden müssen: Kapazitätsgrenzen, Mindestmengen, Bilanzgleichungen. Häufig kommen Nicht-Negativität ($x_i \ge 0$) oder Ganzzahligkeit ($x_i \in \mathbb{Z}$) hinzu.

Kurzformel: Variablen wählen, sodass die Zielfunktion optimal wird, ohne eine Nebenbedingung zu verletzen.

Beim TSP soll ein Handlungsreisender $n$ Städte genau einmal besuchen und am Ende zum Startort zurückkehren. Zwischen je zwei Städten sind die Distanzen (oder Kosten/Zeiten) gegeben. Gesucht ist diejenige Rundreise, die die Gesamtdistanz minimiert.

Das Problem ist NP-hart: die Anzahl möglicher Rundreisen wächst wie $(n-1)!/2$. Schon bei 20 Städten sind es rund $6 \cdot 10^{16}$ Reihenfolgen – exakte Lösung ist praktisch nicht mehr möglich, deshalb kommen Heuristiken (z. B. Nearest Neighbor, 2-Opt) zum Einsatz.

Beim Rucksackproblem hat man $n$ Gegenstände, jeder mit einem Nutzen $u_i$ und einem Gewicht $w_i$. Der Rucksack hat ein Höchstgewicht $W$. Gesucht ist die Auswahl $x_i \in \{0,1\}$, die den Gesamtnutzen maximiert, ohne die Gewichtsgrenze zu überschreiten.

Es ist kein triviales Auswahlproblem, weil Gegenstände mit hohem Nutzen oft auch schwer sind. Man muss deshalb Nutzen und Gewicht abwägen – ein Gegenstand mit mittlerem Nutzen aber sehr geringem Gewicht kann sinnvoller sein als der wertvollste, wenn dieser den ganzen Rucksack blockiert.

Formal: $\max \sum u_i x_i$ unter $\sum w_i x_i \le W$, $x_i \in \{0,1\}$. Das Problem ist NP-hart.

Beim Zuordnungsproblem müssen $n$ Aufgaben genau $n$ Ressourcen (z. B. Mitarbeitern, Maschinen) bijektiv zugeordnet werden – jede Aufgabe genau einer Ressource und umgekehrt. Für jede Kombination $(i,j)$ ist ein Kostenwert $c_{ij}$ gegeben. Ziel: Minimierung der Gesamtkosten.

Praxisbeispiele:

• Personaleinsatzplanung: Welche Mitarbeiter bearbeiten welche Projekte?
• Maschinenbelegung: Welcher Auftrag läuft auf welcher Maschine?
• Transport: Welcher LKW fährt welche Route?

Wichtig: Anders als TSP und Rucksack ist das reine Zuordnungsproblem polynomiell lösbar (z. B. mit der Ungarischen Methode) – es ist also ein P-Problem.

P-Probleme lassen sich mit einem Algorithmus lösen, dessen Laufzeit sich als Polynom in der Problemgröße $n$ darstellen lässt (z. B. $n^2$, $n^3$). Auch für große $n$ bleiben sie praktisch lösbar.

NP-harte Probleme haben (nach aktuellem Wissensstand) keine polynomiellen Algorithmen. Die Laufzeit wächst exponentiell ($2^n$) oder fakultativ ($n!$).

$n!$ ist besonders problematisch, weil es schneller als jede Exponentialfunktion wächst. Konkret: $20! \approx 2{,}4 \cdot 10^{18}$ – bei einer Milliarde Operationen pro Sekunde bräuchte man ca. 77 Jahre. Bei $n=25$ steigt das schon auf hunderttausende Jahre. Deshalb ist die reine Aufzählung aller Permutationen (Brute Force) für $n \gtrsim 15$–$20$ nicht mehr sinnvoll.

Laut Tabelle wird ein $n!$-Algorithmus bereits bei $n = 20$ praktisch unlösbar: Die Laufzeit beträgt hier ca. 77 Jahre (bei einer Elementaroperation pro Mikrosekunde). Bei $n=50$ oder $n=100$ liegt die Rechenzeit in astronomischen Größenordnungen, die selbst das Alter des Universums überschreiten.

Zum Vergleich: Ein polynomieller $n^3$-Algorithmus benötigt bei $n=100$ nur etwa 1 Sekunde. Der Unterschied zwischen Polynom und Fakultät ist also nicht graduell, sondern qualitativ – es entscheidet darüber, ob ein Problem praktisch lösbar ist oder nicht.

Ein OR-Modell ist immer eine Vereinfachung der Realität. Nach dem ersten Durchlauf (Realität → Modell → Lösung → Realität) zeigt sich oft:

• Die Lösung ist zwar mathematisch optimal, aber praktisch nicht umsetzbar (z. B. weil wichtige Nebenbedingungen fehlten).
• Die getroffenen Näherungen waren zu grob und liefern verzerrte Ergebnisse.
• Neue Erkenntnisse aus der Umsetzung erfordern eine Anpassung des Modells.

Deshalb ist Modellierung keine Einbahnstraße: das Modell wird verfeinert, die Lösung neu berechnet, wieder getestet – bis ein akzeptabler Kompromiss zwischen Modellkomplexität und Realitätsnähe erreicht ist.

Fehlt eine relevante Nebenbedingung, ist der zulässige Bereich im Modell größer als in der Realität. Der Optimierer findet dann Lösungen, die formal optimal sind, aber real gar nicht umsetzbar.

Beispiel: In einem Produktionsmodell wird die Maschinenkapazität vergessen. Der Optimierer schlägt vor, doppelt so viel zu produzieren wie möglich – die Lösung ist mathematisch korrekt, aber unbrauchbar.

Konsequenz: Modellvalidierung ist Pflicht. Man muss immer prüfen, ob die berechnete Lösung tatsächlich in der Realität funktioniert. Wenn nicht, muss die fehlende Nebenbedingung ergänzt und neu gerechnet werden.

Auch wenn ein Problem NP-hart ist, hat die Modellierung mehrere Vorteile:

• Klarheit: Das Modell zwingt zu einer präzisen Formulierung von Variablen, Ziel und Nebenbedingungen.
• Heuristiken: Auf Basis des Modells lassen sich Näherungsverfahren entwickeln, die in vertretbarer Zeit gute (wenn auch nicht garantiert optimale) Lösungen liefern.
• Untere/obere Schranken: Relaxierungen (z. B. Weglassen der Ganzzahligkeit) liefern Schranken, die die Qualität einer Heuristik-Lösung bewerten helfen.
• Kleine Instanzen exakt lösbar: Bei $n \le 15$–$20$ funktioniert oft auch der exakte Ansatz.

Kurz: Das Modell ist das Fundament – die Lösungstechnik kann später gewählt werden.

OR unterscheidet sich in mehreren Punkten grundlegend von einer normalen Tabellenkalkulation:

• Systematische Suche: OR sucht mit mathematisch fundierten Algorithmen (Simplex, Branch-and-Bound, Dijkstra, Heuristiken) das Optimum in einem oft riesigen Lösungsraum – nicht nur eine einzelne Was-wäre-wenn-Rechnung.
• Restriktionen: Nebenbedingungen sind fester Bestandteil des Modells, nicht nachträgliche Filter.
• Beweisbare Optimalität: Bei P-Problemen liefert OR nachweislich das Optimum – nicht nur eine plausible Lösung.
• Skalierbarkeit: OR-Methoden funktionieren auch bei hunderten oder tausenden Variablen, wo eine Excel-Rechnung scheitert.

Excel kann ein Ergebnis berechnen. OR beantwortet die Frage: Ist das das beste Ergebnis überhaupt?

Bei $n^2$: Verdopplung von $n$ führt zu einer Vervierfachung der Laufzeit (denn $(2n)^2 = 4n^2$). Bei $n=100$ dauert es 10 ms, bei $n=200$ dann 40 ms – gut beherrschbar.

Bei $2^n$: Verdopplung von $n$ führt zu einer Quadrierung der Laufzeit (denn $2^{2n} = (2^n)^2$). Bei $n=50$ dauert es 36 Jahre, bei $n=100$ bereits $\approx 10^{15}$ Jahre – mehr als das Alter des Universums.

Diese Rechnung zeigt: Polynome sind gutmütig, Exponentialfunktionen und Fakultäten explodieren. Der Unterschied wird bei jeder Verdopplung dramatischer.

Das klassische Zuordnungsproblem ist polynomiell (P) – die Ungarische Methode löst es in $O(n^3)$.

Das TSP ist NP-hart. Der Unterschied liegt in der Struktur:

• Beim Zuordnungsproblem müssen nur Paare gebildet werden – die Reihenfolge der Paare ist irrelevant. Die kombinatorische Struktur ist "flach".
• Beim TSP muss zusätzlich eine Reihenfolge (Zyklus) bestimmt werden. Dadurch entsteht eine Fakultäts-Explosion und die Struktur wird "tief".

Kurz: Zuordnung = wer-mit-wem. TSP = wer-mit-wem-in-welcher-Reihenfolge. Das zusätzliche "in welcher Reihenfolge" macht das Problem qualitativ schwerer.

Die historischen Wurzeln zeigen zwei zentrale Punkte:

• OR ist entstanden, um knappe Ressourcen unter Zeitdruck optimal einzusetzen – also aus einer echten Notlage heraus. Genau dieses Muster (knappe Kapazitäten, mehrere Anforderungen, klare Zielgröße) findet sich heute in jedem Unternehmen wieder.
• OR ist von Anfang an interdisziplinär: Mathematiker, Statistiker, Militär und Ingenieure haben zusammengearbeitet. Diese Kultur des "quantitativ + praxisnah" prägt OR bis heute.

Für die Klausur reicht die Kernaussage: OR = Kriegs-Ursprung → quantitative BWL → heute breite Anwendung in Logistik, Produktion, Finanzen.