Operations Research
Die Lösung komplexer, realer Probleme durch Mathematik hat Wissenschaftler bereits im 17. Jahrhundert beschäftigt. Daraus folgte die Entwicklung des Operations Reserch (OR). Heute sind die Methoden aus fast allen Wirtschaftszweigen nicht mehr weg zu denken. Denn viele Geschäftsprozesse gehen zurück auf grundlegende mathematische Probleme, die mit OR gelöst wurden und werden!
Gewusst?
Charles Babbage
Mitte des 19. Jahrhunderts führte der Engländer Charles Babbage - heute vor allem bekannt für die Erfindung des Vorläufers moderner Computer - eine Studie zu Transportkosten und Briefsortierung bei der Post durch. Anschließend modellierte er mathematisch ein Zustellnetzwerk und zeigte, dass bei ausreichendem Briefaufkommen die zurückgelegte Entfernung eines Briefs irrelevant für die Transportkosten ist. Seine Forschung führte 1840 zur Einführung der landesweiten Penny Post, bei der jeder Briefversand nur ein Penny kostete. Dies gilt heute als die erste praktische OR-Anwendung. Doch bereits im 17. und 18. Jahrhundert arbeiteten Mathematiker – u.a. Leibniz und Newton - an der Berechnung von Problemen mit komplexen Entscheidungen. Und der französische Mathematiker Jean Baptiste Joseph Fourier skizzierte schon 1827 die ersten Methoden der linearen Programmierung.
Gelöst!
Das Vier-Farben-Problem
Will man eine politische Landkarte so einfärben, dass die Grenzen zwischen benachbarten Ländern gut zu erkennen sind, benötigt man für Länder mit einer gemeinsamen Grenzlinie unterschiedliche Farben. Wie viele verschiedene Farben braucht man, um diese Aufgabe für jede Landkarte lösen zu können? Diese Frage beschäftigt seit 1852 Mathematiker und ist damit das älteste OR-Problem. Heute weiß man, dass vier Farben für jede Landkarte auf dem Globus genügen. Es dauerte jedoch mehr als ein Jahrhundert, bis man durch den Einsatz von Computern das Vierfarbenproblem lösen konnte. Und auch heute existiert kein Beweis des Vierfarbensatzes, der ohne Rechner auskommt.
Gewusst?
Operations Research
Der Ursprung des Begriff Operations Research geht auf das Jahr 1937 zurück. Er entstand in England zur Bezeichnung einer Gruppe von Wissenschaftlern, die im Auftrag des Militärs die Einsatzmöglichkeiten des Radars erforschte. Im Jahr 1940 hatte man das Aufgabengebiet und die Forschungsgruppen vergrößert. Im Luftfahrtministerium sowie in Marine und Heer beschäftigte die Forscher neben dem Radar vor allem die Entwicklung von optimalen Strategien im Luftkampf und der U-Boot-Abwehr.
Gelöst!
Das Briefträgerproblem
Um Post zu verteilen, muss ein Briefträger speziell in breiten Straßen jede Straßenseite einmal durchlaufen. Um weitere Bereiche seines Gebiets zu erreichen, muss er u.U. bereits belieferte Straßen erneut durchläufen - und zwar ohne Post zu verteilen. So erhöht sich die Streckenlänge, die er für seine Arbeit zurücklegen muss. Gewünscht ist jedoch eine optimale Rundreise, die bei minimaler Streckenlänge alle Straßen mindestens einmal enthält. Auch diese Aufgabe lösen OR-Algorithmen. Heute kommen Lösungen für das Briefträgerproblem bei der Planung von Müllentsorgungs-, Straßenreinigungs- oder Wartungsreisen zum Einsatz. Gleiches gilt für die Planung einer Rundreise zum Einsammeln von Waren in einem Hochregallager.
Gewusst?
Leonid Kantorowitsch
Er gilt als Begründer der mathematischen Optimierung und erhielt 1975 den Wirtschaftsnobelpreis. 1939 zeigte er in einer Studie zur Organisation- und Planung von Produktionsprozessen, dass sich viele der auf diesem Gebiet entstehenden Probleme mathematisch formulieren lassen. Als er die Produktion einer Furnierholzfabrik optimieren sollte, entwickelte er hierzu die Methode der linearen Programmierung. Diese ist bis heute einer der Grundlagen des OR.
Gelöst!
Handlungsreisenden-Problem
Wie kann man die Reihenfolge für den Besuch mehrerer Orte so wählen, dass keine Station außer der ersten mehr als einmal besucht wird, die gesamte Reisestrecke möglichst kurz und die erste Station gleich der letzten Station ist? Für die Planung einer Tour durch die 15 größten Städte Deutschlands existieren rechnerisch 43.589.145.600 Möglichkeiten. Mit OR lässt sich die optimale Route aus diesen schier unendlich vielen Möglichkeiten mathematisch exakt ermitteln. Dieser Klassiker des OR wurde 1930 erstmals erwähnt und tritt bei der Tourenplanung und der Warenverteilung auf. Als Reihenfolgenproblem, -unter der Fragestellung, was wann wo gemacht werden soll-, kennt man es außerdem in der Produktionsplanung.
Gewusst?
George B. Dantzig
Der US-Mathematiker entwickelte 1947 den ersten Algorithmus zur Lösung linearer Optimierungsprobleme. Das Simplex-Verfahren gilt bis heute als eine Standard-Methode, die vielfach weiterentwickelt wurde. Eine der ersten Anwendungen des neuen Algorithmus war eine militärische: das Diäten-Problem. Das Ziel war es, eine kostengünstige Nahrung für Soldaten herzustellen, die bestimmte Mindest- und Höchstmengen an Vitaminen und anderen Inhaltsstoffen enthielt. An der optimalen Lösung waren damals neun Personen beschäftigt, die zusammen etwa 120 Manntage Rechenarbeit benötigten.
Gelöst!
Das Rucksackproblem
Wie viele Gegenstände mit einem bestimmten Wert passen in einen Rucksack mit einer Gewichtsbeschränkung, sodass der Nutzwert maximal wird? Dieses Problem betrifft nicht nur Diebe, die nur einen kleinen Teil einer Beute mitnehmen können und den maximalen Profit erzielen wollen. In vielen Fällen steht nur eine begrenzte Kapazität zur Verfügung, welche nicht die gesamte Nachfrage befriedigen kann. So hat ein Spediteur bei seinen Lkws nur eine begrenzten Laderaum zur Verfügung, um verschiedene Güter mit maximalem Gewinn zu transportieren. Auch für dieses Problem lässt sich mit OR eine Lösung mathematisch genau bestimmen.
Gewusst?
Akademische Lehre
1948 wurde Operations Research erstmals als akademische Disziplin am Massachusetts Institute of Technology in Cambridge aufgenommen. Dort fand der erste Kurs in dieser jungen Disziplin statt, der sich ausschließlich mit wirtschaftlichen anstelle von militärischen Anwendungen auseinandersetzte. 1952 konnte man am Case Institute of Technology in Cleveland erstmals einen Master und Doktorgrad in OR errreichen. An der RWTH Aachen wurde 1975 der erste kontinentaleuropäische Studiengang eingerichtet, aus dem später der Lehrstuhl für Unternehmensforschung hervorging. Inhaber war der INFORM - Firmengründer Prof. Hans-Jürgen Zimmermann.
Gelöst!
Das Verschnittproblem
Ob Rohre, Holz- oder Textilien, beim Zuschnitt von Rohmaterialien soll möglichst wenig Verschnitt entstehen. Ein solches Problem entsteht auch bei der Beladung eines Frachtraums oder eines Containers. Hier gilt es, möglichst wenig freien Raum zu verschenken. Auch hier hilft Operations Reserach, eine möglichst optimale Lösung zu berechnen.
Gewusst?
INFORM GmbH
1969 gründete Prof. Hans-Jürgen Zimmermann die INFORM GmbH mit dem Ziel, zu beweisen, dass mathematische Optimierung keine reine Kopfgeburt ist. Vielmehr wollte er zeigen, dass Unternehmen durch pures Rechnen ihre Abläufe optimieren und so viel Geld sparen können. INFORM war damit eines der ersten Unternehmen, das Optimierungslösungen auf Basis von OR anbot und die Verfahren mit Hilfe von Softwaresystemen für wirtschaftliche Prozesse anwendbar machte.
Gelöst!
Das Warteschlangen-problem
Ob an der Supermarktkasse, am Bankautomaten oder am Ticketschalter - jeder kennt sie und keiner mag sie: die Warteschlange. Wo ein paar Minuten Warten im Privatleben verschmerzlich erscheint, können diese Minuten im Wirtschaftsleben große Folgen haben. Wenn Lkw mit Produktionsmaterial in einem Werk nicht pünktlich an den Laderampen entladen werden können, sind horrende Standgelder fällig. Und bei Flugzeugen, die nicht rechtzeitig abgefertigt werden, weil noch andere Flieger vorher an der Reihe sind, steigen nicht nur die Kosten, sondern auch die Unzufriedenheit der Passagiere. Die adäquate und effiziente Gestaltung solcher Systeme mittels OR hat also einen bedeutenden Effekt auf die Lebensqualität und die Produktivität.
ZUKUNFT
Leistungsfähigkeit
Seit den 1990er Jahren ist es gelungen, die Geschwindigkeit der Algorithmen um einen Faktor von mehr als 1,5 Millionen zu erhöhen, gemessen an der Rechenzeit, die zur Lösung großer OR-Probleme erforderlich war und ist. Im selben Zeitraum hat sich die Geschwindigkeit der Hardware nur um den Faktor 2000 erhöht. Probleme, deren Berechnung noch im Jahr 1990 bis zu 100 Jahre dauern konnte, lassen sich heute innerhalb von Sekunden lösen. Das heißt: Was vor 30 Jahren eher ein theoretisches Konzept war, ist jetzt in der Praxis anwendbar - vor allem bei der Optimierung komplexer Geschäftsprozesse. Daher hat OR in fast alle Bereiche von Industrie und Wirtschaft Einzug gehalten. Die Verknüpfung mit KI -Methoden wie Machine Learning wird die Leistungsfähigkeit von OR weiter steigern.