Weiterführende Informationen zum Thema Optimierung

An dieser Stelle geben wir eine kurze, eher wissenschaftlich orientierte Einführung in das Thema "Optimierung".

Der folgende Text ist teilweise aus dem Buch: Optimierung im Transport I: Grundlagen (Grünert und Irnich, 2005) entnommen.

Es gibt in der Praxis sehr unterschiedliche Methoden zur Planung und zur Planungsunterstützung. Diese Methoden sind mehr oder weniger formal orientiert und wissenschaftlich fundiert. Optimierung ist eine solche Methode.

Zu den Begriffen Optimierung oder optimieren findet man u. a. folgende Definitionen:

• die Verbesserung eines Vorgangs oder Zustands bzgl. eines Kriteriums wie z. B. Qualität, Kosten, Geschwindigkeit, Effizienz oder Effektivität,
• im Sinne der Mathematik die Bestimmung bestmöglicher zulässiger Punkte eines durch eine Zielfunktion und Restriktionen gegebenen Modells und
• in der Informatik die Verbesserung der Leistung eines Computerprogramms.

Wir verstehen Optimierung als eine auf quantitativen mathematischen Modellen beruhende Technik zur Berechnung von Entscheidungsvorschlägen. Es handelt sich dabei um eine Methode, die von einem geschlossenen mathematischen Modell ausgeht und darauf aufbauend eine Lösung bestimmt. Entsprechende Lösungsverfahren, auch Algorithmen genannt, werden in der Regel nicht "von Hand gerechnet", sondern auf Computern in Programme bzw. Softwaresysteme umgesetzt.

Da die meisten Optimierungsprobleme schwierig zu lösen sind (dies kann mathematisch präzisiert werden), spielen auch solche Verfahren eine wichtige Rolle, die nicht unbedingt garantieren, dass man eine im mathematischen Sinne optimale Lösung findet. Dabei hofft man, mit einem wesentlich geringeren Aufwand, als er zum Auffinden einer optimalen Lösung benötigt wird, eine möglichst gute Lösung zu finden. Derartige Methoden werden im Bereich der Optimierung als Heuristiken bezeichnet. In der Praxis setzt man, abgesehen von einigen wichtigen Spezialfällen, aus Zeit- und Kostengründen nahezu ausschließlich Heuristiken zur Optimierung ein.

Die (mathematische) Optimierung beschäftigt sich mit dem Auffinden einer oder mehrerer Handlungsalternativen bzw. Lösungen aus einer endlichen oder nicht endlichen Menge von potenziellen Lösungen. Grundlage dieser Auswahl ist eine Bewertung der Lösungen. Es gilt, eine oder mehrere Lösungen zu finden, welche bezüglich der gewählten Bewertung am attraktivsten erscheinen. Diese Lösungen werden als optimale Lösungen bezeichnet.

Die Menge der potenziellen Lösungen wird im Allgemeinen formal durch die Definition von Entscheidungsvariablen und deren zulässige Beziehungen oder explizit durch die Angabe aller möglichen Lösungen definiert. Entscheidungsvariablen geben unterschiedliche Aspekte einer Entscheidung wieder. Typische Entscheidungsvariablen sind die Ankunftszeit bei einem Kunden, die Besuchsreihenfolge eines Vertreters bei seinen Kunden, die Menge, die zwischen zwei Standorten transportiert wird, usw.

Meistens ist es in der Optimierung nur möglich, die Menge der Lösungen implizit durch Beziehungen zwischen den Entscheidungsvariablen zu beschreiben. Diese Beziehungen bilden die Restriktionen (engl.: constraints) eines Problems. Formal beschreibt man die Restriktionen mit Hilfe von Gleichungen und Ungleichungen in den Entscheidungsvariablen.

Der bekannteste Grundansatz der Optimierung ist die lineare Programmierung (LP). Dabei wird angenommen, dass ein Modell der Art:

gelöst werden soll. Darin sind x_j die Entscheidungsvariablen, c_j die Zielfunktionskoeffizienten und a_{ij} und b_i die Parameter der Restriktionen. Der Optimalwert "max z" existiert nur, wenn das Modell eine zulässige Lösung besitzt (d. h. das Gleichungs- und Ungleichungssystem besitzt mindestens eine Lösung) und nicht unbeschränkt ist (d. h. man kann nicht die Variablen unbeschränkt wachsen lassen und dabei trotzdem das Gleichungs- und Ungleichungssystem erfüllen).

Eine Verallgemeinerung der linearen Programmierung ist die sog. gemischt-ganzzahlige Programmierung. Bei dieser fordert man, dass bestimmte Entscheidungsvariablen nur ganzzahlige Werte annehmen können. Damit kann man auch diskrete Entscheidungen modellieren, wie z. B. das Öffnen von Lagern oder Depots und die Bestimmung optimaler Reihenfolgen.