Operations Research

Eino zunehmende Anzahl von Autoren (siehe z. B. Boothroyd, 1978; Müller-Merbaeh, 1979; Checkland, 1983) vertreten die Auffassung, dass es zwei verschiedene Begriffe des Operations Research (OR,) gibt: Ein Operations Research aus der Sicht des Praktikers und eins aus der Sicht des Mathematikers. Während das OR aus der Sicht des Praktikers „die modellgestützte Vorbereitung von Entscheidungen zur Gestaltung und Lenkung von Mensch-Maschine-Systemen zur Aufgabe hat“ (Müller-Merbach, 1979, S. 295), sieht der Mathematiker das OR „als Teilgebiet der angewandten Mathernatik“ (Gaede, 1974) an. Wie es zu dieser Situation kam, wird näher im Kapitel 1 dieses Buches beschrieben. Hier wird allerdings die Meinung vertreten, dass es zwar zwei Teile des Gebietes OR geben mag, dass sie jedoch beide wichtig und notwendig für das OR sind und sich aus der Geschiehte des OR erklären lassen. Um dies für den Leser leichter verständlich zu machen, ist es nützlich, zunächst auf den hier benutzten Begriff des „Problems“ etwas näher einzugehen.

Der Ursprung des Begriffes „Operational Research“ ist zweifellos in den Jahren 1937 bis 1939 in England zu suchen. Er entstand 1937 zur Bezeichnung einer Gruppe von Wissenschaftlern in der englischen Armee, die den Auftrag hatte, „Forschung bezüglich der operationalen Nutzung des Radars durchzuführen“ (Tomlinson, 1971, S. XI). Waddington (Waddington, 1973) berichtet in seinem 1946 geschriebenen, aber erst 1973 veröffentlichten Buch über zwei Quellen des Operations Research, nämlich eine innerhalb der britischen Wehrmacht kurz vor dem Ausbruch des 2. Weltkrieges und eine im zivilen Bereich in Großbritannien zu Beginn des 2. Weltkrieges. Die erste war primär mit der praktischen Erforschung der Funktion und der Einsatzmöglichkeiten des Radars befasst, die zweite waren britische Wissenschaftler, die ganz allgemein der Auffassung waren, dass viele naturwissenschaftliche Methoden, die zu dieser Zeit im militärischen Bereich nicht eingesetzt wurden, hier sehr nützliche Anwendungen finden könnten. Beide Ströme vereinigten sich jedoch sehr schnell: Im Jahre 1940 bestand bereits eine Gruppe, die den Namen „Operational Research“ trug, im britischen Luftfahrtministerium. Kurz danach verfügten bereits Marine und Heer ebenfalls über derartige Arbeitsgruppen. Diese Gruppen beschäftigten sich primär mit dem schon erwähnten Radar und mit optimalen Strategien im Luftkampf und der U-Boot-Abwehr.

Es wurde schon in der Einführung darauf hingewiesen, dass zum Operations Research nicht nur die mathematischen Methoden zur Lösung von Real- oder Rechenmodellen gehören, sondern auch das Modellieren von Problemen. Während sich die folgenden Kapitel 3 bis 7 primär mit den Lösungsmethoden beschäftigen, soll in diesem Kapitel das Gebiet des OR betrachtet werden, das sich primär mit der angemessenen Modellierung von Entscheidungsproblemen befasst. Die Formulierung angemessener Entscheidungsmodelle für zu lösende Problemstellungen ist eine Voraussetzung für das Finden optimaler oder befriedigender Problemlösungen.

Lineares Programmieren ist der am besten entwickelte Teil der „Mathematischen Programmierung“. Entsprechend dem angelsächsischen Gebrauch des Begriffs „mathematical programming“ soll unter Mathematischer Programmierung das Gebiet des OR verstanden werden, das sich mit der Optimierung von Funktionen unter Nebenbedingungen befasst. Die Grundproblemstellung ist also:

Die Nichtlineare Programmierung beschäftigt sich mit der Bestimmung optimaler Lösungen zu dem Grundmodell der mathematischen Programmierung wobei allerdings im Gegensatz zur Linearen Programmierung angenommen wird, dass mindestens die Zielfunktion f oder eine der Nebenbedingungen g _i eine nichtlineare Funktion ist. Führt man sich die Vielfalt möglicher mathematischer Funktionstypen und ihrer Kombinationen in Modellen vor Augen, so ist es nicht verwunderlich, dass es, wiederum im Gegensatz zur Linearen Programmierung, bis jetzt weder eine geschlossene „Theorie des Nichtlinearen Programmierens“ noch ein Lösungsverfahren, das alle nichtlinearen Programmierungsaufgaben löst, gibt oder je geben wird. Es können insbesondere folgende Beobachtungen gemacht werden:

In Abschnitt 2.4 wurde im Zusammenhang mit dem Begriff der „beschränkten Rationalität“ darauf hingewiesen, dass Menschen, wenn sie sich von der Komplexität eines zu lösenden Problems überfordert fühlen, dazu neigen, u. a. komplexe Probleme in kleinere Teilprobleme zu zerlegen. Hierfür gibt es wohl primär zwei Gründe: Das folgende Beispiel mag helfen, die Zusammenhänge zu visualisieren (in Anlehnung an Weinberg, 1968, S. 5).

Es wurde schon mehrmals erwähnt, dass im OR nicht nur die Güte einer berechneten Lösung relevant ist, sondern auch der Aufwand der zu treiben ist, eine bestimmte Lösung zu bestimmen. Bei optimierenden Verfahren ist die Optimalität der Lösung garantiert, so dass früher die wesentlichen Merkmale für den Vergleich von Algorithmen der benötigte Speicherplatz und die notwendige Rechenzeit bis zur Lösung des Modells waren. Bereits in Abschnitt 3.12 wurde darauf im Zusammenhang mit dem Linearen Programmieren hingewiesen. Bei dem Vergleich bestehender optimierender Algorithmen aufgrund von auf EDV-Anlagen durchgeführten Rechnungen gab es allerdings oft weitere Unsicherheiten, die z.B. in verschiedenen benutzten Rechenanlagen und in der Güte des verwandten Computercodes bestanden. Bei heuristischen Verfahren kommen dazu noch die Lösungsgüte und andere Kriterien. Speicherplatz ist inzwischen oft nicht mehr eine kritische Größe, die anderen Kriterien bleiben jedoch im Prinzip bestehen. Seit dem Entstehen der Komplexitätstheorie in den 70er Jahren kann man jedoch Aussagen über die Komplexität von Algorithmen, Modellen oder Problemen auch ohne „Proberechnungen“ machen. Ehe wir einige Grundlagen dieser Theorie darstellen, sei jedoch noch darauf hingewiesen, dass es sich hier um einen speziellen Komplexitätsbegriff handelt, der z.B. mit dem in der empirisch-kognitiven Entscheidungstheorie oder in anderen Gebieten verwandten nicht übereinstimmt.

In Abschnitt 3.6 war bereits darauf hingewiesen worden, dass die Forderung der Ganzzahligkeit der optimalen Lösung einige der Annahmen verletzt, die die Anwendung des Simplex-Verfahrens erlaubt. Für allgemeine gemischt-ganzzahlige Modelle wurde in Abschnitt 3.6 auch schon das „klassische“ Gomory Verfahren beschrieben. Dies ist zwar in der letzten Zeit in Verbindung mit anderen algorithmischen Ansätzen wieder sehr aktuell geworden, es ist trotzdem wenig dazu geeignet, Modelle zu lösen, die viele 0/1-Variable enthalten. Diese Art von Modellen erhalten jedoch immer größere Wichtigkeit und viele der algorithmischen Entwicklungen konzentrieren sich darauf. Daher soll, ehe in den danach folgenden Abschnitten Lösungsverfahren beschrieben werden, eine Übersicht über die wichtigsten Typen von 0/1-Modellen gegeben werden.

Der Begriff des Graphen sowie graphentheoretische Verfahren finden im Bereich des Operations Research verbreitet Anwendung. Spezielle Formen von Graphen — Bäume — haben wir schon bei den Entscheidungsbaumverfahren kennengelernt, ohne dass dafür Kenntnisse in der Graphentheorie notwendig waren. Nützlich sind solche Kenntnisse allerdings auf anderen Gebieten, so z.B. bei der Verwendung sogenannter Gozintographen in der Fertigungssteuerung und -planung und in der Netzplantechnik. Deshalb sollen im folgenden die für das OR wichtigsten Grundlagen der Graphentheorie dargestellt werden. Für ein tiefergehendes Studium sei auf die Spezialliteratur verwiesen (z.B. Neumann, 1975b; Noltemeier, 1976b; Sachs, 1971).

Jedes System, sei es ein organisatorisches, physikalisches, elektrisches oder ein Produktionssystem, in dem ankommende Elemente (Menschen, Aufträge, Autos, Telefonanrufe etc.) Anforderungen an knappe Ressourcen (Sitzplätze, Maschinen, freie Stellen, Zapfsäulen etc.) stellen, kann man als ein Warteschlangen- oder Stauungssystem bezeichnen. Abbildung 9.1 zeigt einige dieser Situationen oder Systeme zur Illustration: