Category

Viele bei Unternehmen natürlich auftretende Fragestellungen sind wohlbekannte mathematische Probleme, denen mit Methoden aus der linearen Optimierung begegnet werden kann. Die Problemstellungen sehen dabei zunächst sehr verschieden aus: Ein Unternehmen hat einen Fuhrpark von LKWs und möchte seine Kunden beliefern. Welcher LKW soll zu welchen Kunden geschickt werden? Ein Krankenhaus hat verschiedene Arten von Behandlungszimmern. Welches Personal soll zu welcher Zeit welchen Patienten in welchem Behandlungszimmer versorgen? Ein Unternehmen hat ein Hochregallager. Welche Artikel sollen in welchen Bereichen gelagert werden, sodass der Aufwand für Ein- und Auslagerung minimiert wird? Diese zunächst einmal leicht formulierten Probleme erweisen sich bei genauerem Hinsehen als schwierig. Der Grund dafür ist, dass viele Nebenbedingungen involviert sind oder dass man zukünftige Änderungen der Problemstellung nicht kennt. Beispielsweise stellen sich folgende Fragen: Welche Lieferungen können überhaupt zu einer LKW-Tour kombiniert werden? Wie darf eine Tour aussehen, sodass ein LKW-Fahrer sie während einer Schicht fahren kann, ohne dabei die längst mögliche zulässige Fahrtzeit zu überschreiten? Welcher Arzt ist auf welche Behandlungen spezialisiert? Welches sind die in Zukunft am häufigsten angefragten Artikel? Welche Artikel können in welchem Teil des Lagers abgelegt werden? All diese Probleme und viele weitere verwandte Fragestellungen insbesondere aus der Logistik, dem Management, der Personalplanung oder der Produktionsplanung lassen sich mittels mathematischer Optimierung lösen. Die bewährte Vorgehensweise ist es, zunächst ein mathematisches Modell des Problems zu formulieren. Das Modell hält dabei die einzuhaltenden Nebenbedingungen fest und gibt die zu optimierende Größe vor. Die Beschreibung des Modells geschieht durch ein lineares Programm. Die Nebenbedingungen werden durch ein Ungleichungssystem ausgedrückt, die zu optimierende Größe wird durch eine Zielfunktion festgelegt. Ein sogenannter Solver löst das lineare Programm. Die erhaltene Lösung kann von Software interpretiert werden und Entscheidungshilfen für Unternehmen bieten. Bei sehr komplexen Fragestellungen, insbesondere solchen, bei denen unbekannte Einflussfaktoren durch zukünftige Entwicklungen eine Rolle spielen, kann man die Güte des Modells daran messen, welchen Wert — beispielsweise welche Kostenersparnis — es für das Unternehmen erzielt. Für einfachere Fragestellungen ist der Nutzen unmittelbar sichtbar. So reduziert eine gute Produktionsplanungssoftware Überzeiten, ist flexibel gegenüber kurzfristigen manuellen Änderungen und nimmt dem Nutzer den Planungsaufwand ab, sodass dieser selbst mehr Zeit für andere Aufgaben hat.
Wir möchten auf ein vereinfachtes Beispiel in der Ressourcenplanung eingehen und dieses mit Hilfe der linearen Optimierung lösen. In einer Arztpraxis gibt es verschiedene Untersuchungsmethoden, z.B. Blutabnahme fürs Labor, Ultraschall, Röntgen, usw. Jedes Gerät kann zu einer Zeit nur von einem Patienten belegt werden. Zudem gibt es verschiedene Patienten. Für jeden der Patienten muss natürlich individuell nur ein Teil der Untersuchungen durchgeführt werden. Aufgabe ist es, einen Plan zu finden, sodass für alle Patienten die notwendigen Untersuchungen gemacht werden und zugleich die jeweiligen Verweilzeiten der Patienten im Krankenhaus minimiert werden.

Wir modellieren die Problemstellung wie folgt. Zunächst erstellen wir ein Zeitraster. Wir definieren Zeitpunkte 0,1,2,3, …, die einen Viertelstunden-Takt vorgeben, startend ab 12 Uhr mittags. So wird mit Zeitpunkt 2 die Uhrzeit 12:30 Uhr des aktuellen Tages bezeichnet. Zudem nummerieren wir die Patienten 1,2 … und die Untersuchungsmethoden ebenfalls 1,2,…

Wir können nun binäre Variablen x_i,j,k einführen. Die Semantik dieser sei wie folgt definiert. Es sei x_i,j,k = 1 genau dann, wenn die Behandlung des Typs k vom Patienten j zum Zeitpunkt i beginnt. Jetzt modellieren wir die Nebenbedingungen.

Um das Beispiel übersichtlich zu halten, nehmen wir an, dass wir drei Patienten haben und nur den Zeitraum zwischen 12:00 Uhr und 13:00 Uhr betrachten. Wir formulieren die Nebenbedingungen für die Behandlungsmethode 3 (Ultraschall-Untersuchung). Wir reservieren für eine Ultraschall-Untersuchung einen Zeitschlitz von 15 Minuten.

Wenn für Patient 1 die Ultraschall-Untersuchung in der betrachteten Zeitspanne durchgeführt werden muss, so definieren wir die Bedingung

x_0,1,3 + x_1,1,3 + x_2,1,3 + x_3,1,3 = 1.

Auf analoge Weise können wir nun formulieren, welche Untersuchen für andere Patienten notwendig sind.

Nehmen wir an, dass es nur ein Ultra-Schallgerät gebe. Dann benötigen wir ausserdem die Bedingungen

x_0,1,3 + x_0,2,3 + x_0,3,3 <= 1

x_1,1,3 + x_1,2,3 + x_1,3,3 <= 1

x_2,1,3 + x_2,2,3 + x_2,3,3 <= 1

x_3,1,3 + x_3,2,3 + x_3,3,3 <= 1,

die erzwingen, dass zu jedem Zeitpunkt nur ein Patient eine Ultraschall-Untersuchung erhalten kann. Ebenso muss für andere Untersuchungen die begrenzte Kapazität der Räumlichkeiten berücksichtigt werden.

Um dafür zu sorgen, dass die Verweilzeit minimiert wird, gewichten wir die Behandlungsbeginne, sodass spätere Behandlungsbeginne „teurer“ als frühere sind und fügen diese in die Zielfunktion ein. In unserem Beispiel enthält die Zielfunktion die Terme 1*x_0,1,3 + 2*x_1,1,3 + 3*x_2,1,3 + 4*x_3,1,3. Hierbei nehmen wir an, dass alle Patienten um 12 Uhr in der Praxis ankommen. In einer tatsächlichen Software müsste man u.a. in der Gewichtung noch die Ankunftszeit der Patienten berücksichtigen.

Das so entstandene Modell kann dann an einen Solver gegeben werden, der eine Lösung für die Problemstellung findet. Aus dem Resultat kann ein Behandlungsplan abgelesen werden.

Da schon bei diesem Minimalbeispiel erkennbar einige Bedingungen notwendig sind, ist in einer Planungssoftware die Formulierung sinnvollerweise zu automatisieren, sodass eine Praxisassistentin mit einer grafischen Benutzeroberfläche aus einer Auswahlliste nur die Menge der notwendigen Behandlungen auswählen müsste. Die Formulierung des linearen Programms kann dann durch die Software geschehen. Die Lösung kann ebenfalls automatisch ausgewertet und entsprechend optisch aufbereitet werden, sodass die Assistentin einen Raumbelegungsplan oder einen individuellen Behandlungsplan leicht aus einem Kalender ablesen kann.

Obschon das Thema Optimierung für heutige Unternehmen hochaktuell ist, ist Optimierung ein seit Jahrhunderten bekanntes Teilgebiet der angewandten Mathematik. Bereits im 17. Jahrhundert beschreibt Sir Isaac Newton ein Verfahren zum Lösen eines nicht-linearen Optimierungsproblems. Im Jahre 1939 betrachtet Kantorowitsch den Spezialfall der linearen Optimierung. In den 1940er Jahren erkennt George Danzig den praktischen Nutzen der linearen Optimierung. Er stellt fest, dass sich viele natürliche Fragestellungen aus der Wirtschaft mit Hilfe linearer Optimierung beschreiben lassen. Wiederum Danzig legt 1947 den ersten Algorithmus vor, mit Hilfe dessen viele Probleme durch Computer gelöst werden können.

Mit dem Aufkommen der Computertechnik und weiterer numerischer Methoden gewann das Verfahren noch an Bedeutung. Danzigs Algorithmus ist noch heute Bestandteil vieler moderner, hochleistungsfähiger Solver. Die aus der Wirtschaftswissenschaft stammende Disziplin, bessere Entscheidungen durch mathematische Optimierung zu treffen, wird als Operations Research bezeichnet. Durch die Verbesserung der Algorithmen und die Fortschritte in der Leistungsfähigkeit heutiger Rechner erhalten Operations Research und Optimierung Einzug in Unternehmen.