Kombinatorische Optimierung")?> Die Optimierung beschäftigt sich mit der Aufgabe, unter einer gegebenen Menge von Elementen ein nach bestimmte Kriterien bestes zu finden. Es gibt viele verschiedene Ausprägungen dieser Fragestellung, die teilweise sehr unterschiedliche Fragen aufwerfen.

In der Linearen Optimierung beispielsweise ist die Menge der betrachteten Elemente implizit durch ein System von linearen Ungleichungen gegeben. Diese zulässigen Lösungen sind durch eine lineare Funktion, die Zielfunktion, bewertet. Es soll also das Minimum oder Maximum bezüglich der Zielfunktion gefunden werden, sofern es existiert.

Ganzzahlige Optimierung zeichnet sich dadurch aus, daß von den zulässigen Lösungen Ganzzahligkeit verlangt wird. Häufig tritt diese Bedingung zusätzlich zu den oben genannten Linearitätsbedingungen auf. Man spricht dann von ganzzahliger linearer Optimierung. Eine Klasse von Optimierungsproblemen, die in diesem Zusammenhang besondere Bedeutung hat, sind Netzwerkflußprobleme.

Wie schwierig es ist, Optimierungsprobleme zu lösen, ist eine Frage, mit der sich die Komplexitätstheorie beschäftigt. Ein weiterer Themenkreis auf diesem Gebiet ist die Approximationstheorie. Sie beschäftigt sich mit der näherungsweisen Lösung von Optimierungsproblemen, deren exakte Lösung sich als zu schwierig erwiesen hat.

Kontakt:")?> Tel.: 0221/470-6030
Fax: 0221/470-5160
contact@zpr.uni-koeln.de