Burger King will in einer gottverlassenen amerikanischen Kleinstadt eine Hamburger-Braterei errichten – aber McDonalds ist schon da, mit einer Filiale im Osten der Stadt. Wo soll sich das neue Schnellrestaurant ansiedeln: im Westen, weit weg vom Konkurrenten, oder vor dessen Haustür? Welches ist der beste Standort für die Rettungswagen in einer Stadt? In einem der Krankenhäuser, die angefahren werden müssen, oder lieber neben der Bar mit den meisten Messerstechereien oder der unfallträchtigsten Kreuzung?

Solche Fragen sind Gegenstand einer eigenen Theorie, der Standortoptimierung (location science). Und wie die meisten Theorien, hat auch diese eine militärische Anwendung: Wie stationiert man Truppen innerhalb eines großen Gebietes so, dass sie jeden potenziell bedrohten Punkt binnen kurzer Zeit erreichen können, ohne dabei ein anderes Teilgebiet ungeschützt zu lassen?

Während des Zweiten Weltkriegs hatte General Douglas MacArthur im Pazifik ein derartiges Problem zu lösen. Seine Strategie wurde als "Insel-Hüpfen" (island-hopping) bekannt: Er verlegte Truppen von einer Insel auf die andere, aber nur, wenn genug Truppen zur Sicherung auf der ersten Insel blieben. Diese Bedingung zwang ihn zu langen, komplizierten Manövern. Ähnlich erging es dem römischen Herrscher Konstantin im vierten nachchristlichen Jahrhundert, nur dass der ein ganzes Weltreich zu verteidigen hatte. Auch seine Lösung war ähnlich (Bild unten).

Hätte Konstantin seine Legionen geschickter stationieren können? Der Altmeister der Standort-Optimierungs-The-orie, Charles S. ReVelle von der Johns-Hopkins-Universität in Baltimore (Maryland), und Kenneth E. Rosing von der Erasmus-Universität in Rotterdam haben 1997 Konstantins Problem mit einer mathematischen Methodik analysiert. Ihre Arbeit ist ein hübsches Anwendungsbeispiel, einfach, aber lehrreich, und man kann ein vergnügliches Spiel daraus machen. Ihre Analyse wurde im April 1997 im Johns Hopkins Magazine abgedruckt (http://www.jhu.edu/~jhumag/0497web/locate3.html) und wird noch dieses Jahr im "American Mathematical Monthly" erscheinen.

Zum Aufwärmen betrachten wir eine vereinfachte Ansicht des römischen Reiches zur Zeit Konstantins (Bild unten). Das "Spielbrett" zeigt acht Gebiete (schwarze Kreise), von Kleinasien bis zu Britannien, sowie Verbindungswege (Linien) zwischen den Gebieten. Im dritten Jahrhundert beherrschten die Armeen des römischen Imperiums den größten Teil Europas, und es standen insgesamt 50 Legionen zur Verfügung. Im vierten Jahrhundert aber war die Zahl auf 25 Legionen halbiert worden. Konstantin bildete daraus vier Gruppen von je sechs Legionen; die überzählige Legion wurde in der Praxis einer der Gruppen zugeschlagen. Er entwickelte einige einfache Regeln zur Stationierung und Bewegung von Truppen, die hinreichende Sicherheit garantieren sollten, und arbeitete dann die logischen Konsequenzen dieser Regeln aus.

Denken Sie sich jede Gruppe von sechs (oder sieben) Legionen als einen einzigen Spielstein, der auf einen Kreis des Spielfeldes gelegt werden soll. Hier sind Konstantins Regeln:

- Ein Gebiet gilt als absicherbar, wenn ein Spielstein in einem einzigen Zug dorthin bewegt werden kann.

- Wenigstens zwei Spielsteine müssen auf einem Feld stehen, ehe ein Spielstein davon weggezogen werden kann. Es muss also wenigstens ein Stein zurückbleiben.

Wie können Sie nach diesen Regeln die Gruppen so platzieren, dass das ganze Weltreich gesichert ist, das heißt, dass jeder Aufruhr in einer der Provinzen spätestens nach einem Zug niedergeschlagen werden kann? Oder, falls das nicht möglich ist, welcher Teil des Reiches kann gesichert werden? Die Abbildung zeigt Konstantins Lösung: zwei Gruppen in Rom und zwei in seiner neugegründeten Hauptstadt Konstantinopel.

Wie Sie sehen, ist dabei ein Gebiet, nämlich Britannien, nicht absicherbar. Man braucht nämlich vier Züge, um eine Gruppe nach Britannien zu schaffen. Eine Möglichkeit ist: Zuerst eine Gruppe von Rom nach Gallien. (Nun ist Gallien gesichert, und das war den Römern sicher viel wichtiger als das entfernte, kalte und nasse Britannien.) Dann eine Gruppe von Konstantinopel nach Rom, dann nach Gallien und schließlich weiter nach Britannien.

Kann man Konstantins Verteilung noch verbessern? Allerdings, man kann die Truppen so stationieren, dass jedes Gebiet in nur einem Zug gesichert werden kann. Stellen Sie einfach zwei Gruppen in Rom auf und je eine in Britannien und Kleinasien.

Warum hat Konstantin nicht so gehandelt? Schließlich gibt diese Aufstellung Rom ebenso viel Schutz wie die von ihm bevorzugte Lösung: zwei Gruppen. Wahrscheinlich hat er sie verworfen, weil das Weltreich in eine prekäre Lage geraten wäre, wenn es an zwei verschiedenen Fronten zugleich Ärger gegeben hätte. Sobald eine Gruppe Rom verlassen hat, stecken alle anderen fest, es gibt keinen zweiten Zug mehr.

Das Bild oben zeigt eine komplexere Version des gleichen Problems. Es gibt darin zwei weitere Routen: eine zwischen Iberien und Britannien und eine zwischen Ägypten und Kleinasien. Auch in diesem Falle kann unsere verbesserte Aufstellung – zwei Gruppen in Rom und je eine in Britannien und Kleinasien – das ganze Reich in nur einem Zug sichern. Die neuen Verbindungen machen neue Truppenbewegungen möglich, und wir können uns fragen, ob es noch weitere Lösungen gibt. Ich werde diese Frage gegen Ende des Artikels beantworten.

Konstantins Problem ist zur Not noch durch Probieren zu lösen; aber für kompliziertere Aufgaben dieser Art greift man besser zu mathematischen Optimierungsverfahren. Dabei stellt man das Problem – zum Beispiel – in Form einer Tabelle dar (ein hochtrabender Name dafür wäre Matrix), deren Zeilen den Gebieten entsprechen und deren Spalten zu den Spielsteinen gehören. Die Matrix zu Konstantins Problem hat 8 Zeilen und 4 Spalten. Wir schreiben eine Eins in ein Feld, wenn der Spielstein, der zur Spalte des Feldes gehört, in dem Gebiet steht, das zur Zeile gehört, und eine Null sonst (Bild Seite 114, rechts oben). Die Truppenbewegungsregeln Konstantins lassen sich umformulieren als Regeln, nach denen die Einträge in solchen Matrizen geändert werden dürfen. Aus nahe liegenden Gründen nennt man derartige Probleme Null-Eins-Optimierungsaufgaben.

Das Verfahren von ReVelle und Rosing zerlegt das Problem in zwei Teilaufgaben. Die erste ist das Problem der überdeckenden Stationierung (set covering deployment problem). Man lässt die Bedingung, dass es nur 4 Spielsteine gibt, vorübergehend außer Acht und fragt stattdessen nach der kleinsten Anzahl von Spielsteinen, die sich so verteilen lassen, dass alle Gebiete absicherbar sind. (Wenn die Antwort mehr als 4 lautet, lässt sich Konstantins Problem nicht lösen.) Das zweite Problem ist dazu komplementär und heißt Problem der Stationierung mit maximaler Reichweite (maximal covering deployment problem). Man gibt die Anzahl der Spielsteine vor und fragt nach der größten Anzahl von Gebieten, die sich – bei geeigneter Aufstellung – mit höchstens einem Zug sichern lassen.

ReVelle und Rosing haben allgemeine Methoden zur Lösung beider Teilprobleme entwickelt und programmiert. Damit kann man nicht nur Konstantins ursprüngliches Problem lösen, sondern auch weiter gehende Fragen beantworten, zum Beispiel, ob man auch mit weniger Steinen auskommt (die Antwort ist nein). Interessant werden diese Verfahren für weit kompliziertere Probleme derselben Klasse.

Die Provinz Britannien ging den Nachfolgern Konstantins verloren. Die Gründe dafür sind natürlich viel komplexer als alles, was durch dieses einfache Modell erklärt werden könnte. Dennoch: Wäre Konstantin ein besserer Mathematiker gewesen, hätte das römische Weltreich vielleicht ein bisschen länger überdauert.

Aus: Spektrum der Wissenschaft 8 / 2000, Seite 114
© Spektrum der Wissenschaft Verlagsgesellschaft mbH