Robert Sedgewick: Algorithmen

[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]


43. Lineare Programmierung



Bei vielen praktischen Problemen treten komplizierte Wechselwirkungen zwischen einer Reihe veränderlicher Größen auf. Ein Beispiel dafür ist das in
Kapitel 33 betrachtete Problem des Flusses in einem Netzwerk: Die Strömungen in den verschiedenen Rohren müssen im gesamten Netzwerk physikalischen Gesetzen gehorchen. Ein anderes Beispiel ist die Planung des zeitlichen Ablaufs verschiedener Aufgaben in einem Produktionsprozeß unter Berücksichtigung von Lieferterminen, Prioritäten usw. Sehr oft ist es möglich, eine exakte mathematische Formulierung zu entwickeln, die die auftretenden Wechselwirkungen erfaßt und das vorliegende Problem auf ein einfacheres mathematisches Problem zurückführt. Dieser Prozeß der Gewinnung einer Menge mathematischer Gleichungen, deren Lösung die Lösung eines gegebenen praktischen Problems nach sich zieht, wird mathematische Programmierung (Optimierung) genannt. Wie in Kapitel 42 bezeichnet der Begriff »Programmierung« hierbei wieder den Prozeß der Auswahl der Variablen und der Aufstellung der Gleichungen in der Weise, daß eine Lösung der Gleichungen einer Lösung des Problems entspricht. Im vorliegenden Kapitel betrachten wir einen grundlegenden Typ der mathematischen Programmierung, die lineare Programmierung (lineare Optimierung), sowie einen effizienten Algorithmus zur Lösung linearer Optimierungsaufgaben, die Simplexmethode.

Die lineare Programmierung und die Simplexmethode sind von fundamentaler Bedeutung, da eine große Anzahl wichtiger Probleme eine Formulierung als lineare Optimierungsaufgabe gestattet und eine effiziente Lösung mit Hilfe der Simplexmethode ermöglicht. Für einige spezielle Probleme sind noch bessere Algorithmen bekannt, doch wenige Verfahren für die Lösung von Problemen sind so vielfältig anwendbar wie die Formulierung des Problems als lineare Optimierungsaufgabe und der anschließenden Berechnung der Lösung unter Anwendung der Simplexmethode. Eine Bibliotheksroutine für die Simplexmethode kann ein unverzichtbares Werkzeug für die Behandlung komplexer Probleme sein.

Die lineare Programmierung ist ein sehr gründlich erforschtes Gebiet, und ein volles Verständnis aller damit zusammenhängenden Fragen erfordert eine mathematische Vorbildung, die weit umfangreicher ist, als für dieses Buch vorausgesetzt wird. Andererseits sind einige Grundideen leicht verständlich, und wie wir sehen werden, ist der eigentliche Simplex-Algorithmus nicht schwer zu implementieren. Wie im Falle der schnellen Fourier-Transformation in Kapitel 41 besteht unsere Absicht nicht darin, eine vollständige, praktisch anwendbare Implementation bereitzustellen, sondern vielmehr darin, einige der grundlegenden Eigenschaften des Algorithmus und seine Beziehung zu anderen von uns betrachteten Algorithmen kennenzulernen.


[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]