OR-Labor
Das Färbungsproblem in der Betriebswirtschaftslehre


Problemformulierung
Gegeben sei ein ungerichteter Graph G=(V,E) mit Knotenmenge
V und Kantenmenge E. Die Knoten von G heißen
zulässig gefärbt, wenn jedem Knoten eine Farbe so zugeordnet ist, dass die
Knoten, die durch eine Kante verbunden sind, nicht dieselbe Farbe tragen. Man spricht
auch vereinfachend von der Färbung des Graphen. Eine triviale Färbung
erhält man, wenn jedem Knoten eine andere Farbe zugewiesen wird; bei n
Knoten benötigt man genau n Farben. Interessant sind nun genau die
zulässigen Färbungen, bei denen möglichst wenig Farben verwendet werden.
Das Minimum der für eine zulässige Färbung von G
erforderlichen Farben heißt die chromatische Zahl .
Anwendungen
Ampelschaltung
Die Ampeln stellen die Knoten im Graphen dar. Zwei Ampeln, die nicht gleichzeitig
GRÜN zeigen dürfen, sind durch Kanten im Graphen verbunden. Eine Phase ist
durch eine bestimmte Ampelschaltung charakterisiert. Eine solche Schaltung heißt
dann zulässig, wenn die freigegebenen Wege nicht zu Verkehrskonflikten auf der
Kreuzung führen. Versuchen Sie nun mit dem von uns programmierten
Applet einmal selbst, eine
möglichst gute Färbung eines Graphen zu finden.
Frequenzblockzuweisung im Bereich der Telekommunikation
Die Deutsche Telekom hat ein Softwarepaket zur Verteilung von Sendefrequenzen
entwickelt, bei dem auch Tabu Search implementiert ist. Beim digitalen
terrestrischen Hörrundfunk werden sechs Stereoprogramme zu einem Programmblock
zusammengefasst und in einem Frequenzblock abgestrahlt. Für jedes
Verbreitungsgebiet, in der Bundesrepublik können das mehrere Hundert sein, ist
ein Frequenzblock erforderlich.
Herr Hackelbörger, Mitarbeiter im Technologiezentrum der Telekom in Darmstadt,
gab interessante Erläuterungen (6MB), von
denen Sie einen Ausschnitt hier sehen können. Das vollständige Interview
finden Sie auf unserer CD Intelligente Strategien in Theorie und Praxis.
Konfliktfreie Lagerung von Sonderabfällen
Der sachgerechten Lagerung von Chemikalien wird bei Sicherheitsbetrachtungen oft wenig
Bedeutung beigemessen, doch Unfälle wie der spektakuläre Lagerbrand bei der
Firma Sandoz in Basel 1986 zeigen, dass auch mit der Lagerung schwer kalkulierbare
Gefahren verbunden sein können. Kernpunkt der Abbildung des Lagerproblems auf das
Graphenfärbungsproblem ist die Unterscheidung von unterschiedlichen
Gefahrenklassen, die im Chemikaliengesetz unter Berücksichtigung des individuellen
Gefahrengrades festgelegt ist. Ordnet man jeder Klasse einen Knoten im Graphen zu und
drückt das Verbot der gemeinsamen Lagerung von Stoffen unterschiedlicher Klassen
durch eine entsprechende Kante aus, so ergibt sich - wie Untersuchungen gezeigt haben -
für das beschriebene allgemein formulierte Problem ein Graph mit 26 Knoten und
254 Kanten. Mit der vorgenommenen Transformation des Problems sind auch entsprechende
Algorithmen anwendbar, die insbesondere für die Konzeption von Lagern und die
damit verbundenen Entscheidungen von großer Bedeutung sind.
Applet-Seite
Zum Ampelproblem wurde von uns ein Applet programmiert, mit
dem Sie einmal selbst die Einfärbung eines Graphen vornehmen können, um eine Ampelschaltung
mit konfliktfreien Grünphasen zu generieren.
Die Lösung des Färbungsproblems mittels neuerer Verfahren wie Simulated Annealing und Tabu Search
wird im multimedialen Lehrprogramm »Intelligente Strategien in Theorie und Praxis«
behandelt.