Kombinatorische Optimierung

 

In der kombinatorischen Optimierung geht es darum, optimale Entscheidungen unter sehr vielen Alternativen zu treffen. Betrachten wir zunächst eines der populärsten Probleme der kombinatorischen Optimierung:

Das Problem des Handelsreisenden:

Ein Händler muss 50 Kunden besuchen und möchte wissen, in welcher Reihenfolge er die Kunden besuchen sollte, um die Gesamtlänge der Wege, die er dafür zurücklegen muss, zu minimieren. Die Distanzen zwischen je zwei seiner Kunden sind ihm bekannt, bzw. können anhand einer Karte abgelesen werden.

Die Alternativen, unter denen der Händler bei diesem Problem wählen muss, sind die verschiedenen Reihenfolgen, in denen er die Kunden besuchen könnte. Dies sind insgesamt 50!=50*49*48*...*2*1 unterschiedliche Reihenfolgen, was einer 65-stelligen Dezimalzahl entspricht. Eine optimale Entscheidung entspricht bei diesem Problem einer Reihenfolge, die die zurückzulegende Gesamtwegstrecke minimiert.

Alle verschiedenen Reihenfolgen miteinander zu vergleichen und unter den entsprechenden Touren die kürzeste zu wählen ist unmöglich, denn alleine das Zählen von 1 bis 50! würde einen Hochleistungsrechner von jetzt an bis zum Zeitpunkt des Erlöschens der Sonne beschäftigen.

In der kombinatorischen Optimierung werden mathematische Methoden verwendet, um die Menge der möglichen Alternativen von vornherein radikal einzuschränken, um so schnell an optimale, oder zumindest fast optimale Touren zu kommen. Weitere klassische Problemstellungen der kombinatorischen Optimierung umfassen beispielsweise

  • Routenplanung: Was ist die schnellste Route von einem Ausgangspunkt zu einem Zielort? Entlang welcher Routen sollten Güter transportiert werden?
  • Zuordnungsprobleme: In welcher Reihenfolge und auf welchen Prozessoren sollten Aufträge bearbeitet werden?
  • Flugplanerstellung: Wie sollte Flugpersonal auf Flüge verteilt werden, ohne die zahlreichen Restriktionen (Ruhezeiten, etc) zu verletzen?
  • Standortplanung: Wo sollten Krankenhäuser errichtet werden? Wo sollten Lagerhallen angemietet werden?