Robert Sedgewick: Algorithmen

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


43. Lineare Programmierung



Lineare Optimierungsaufgaben

Bei mathematischen Optimierungsaufgaben liegt eine Menge von Variablen vor, die durch eine Menge mathematischer Gleichungen (Nebenbedingungen) miteinander verknüpft sind, und eine die Variablen enthaltende Zielfunktion, die unter Beachtung der Nebenbedingungen zu maximieren ist. Falls alle auftretenden Gleichungen einfach Linearkombinationen der Variablen sind, liegt der von uns betrachtete Spezialfall vor, den wir als lineare Programmierung bezeichnen.

Die folgende lineare Optimierungsaufgabe entspricht dem Problem des Flusses in einem Netzwerk aus Kapitel 33.

Maximiere xAB + xAD
unter Berücksichtigung der Nebenbedingungen

xAB<=6       xCD<=3
xAC<=8       xCE<=3
xBD<=6       xDF<=8
xBE<=3       xEF<=6

xBD + xBE = xAB'
xCD + xCE = xAC'
xBD + xCD = xDF'
xBE + xCE = xEF'

xAB', xAC', xBD', xBE', xCD', xCE', xDF', xEF' >= 0.

Dem Fluß in jedem der Rohre entspricht eine Variable in dieser linearen Optimierungsaufgabe. Diese Variablen genügen zweierlei Beziehungen: Ungleichungen, die den Nebenbedingungen bezüglich der Durchlaßfähigkeit der Rohre entsprechen, und Gleichungen, die den Nebenbedingungen für den Fluß an jeder der Verzweigungsstellen entsprechen. So besagt zum Beispiel die Ungleichung xAB <= 8, daß das Rohr AB die Durchlaßfähigkeit 8 hat, und die Gleichung xBD + xBE = xAB besagt, daß die an der Verzweigungsstelle B hinausfließende Menge gleich der hineinfließenden Menge sein muß. Wir bemerken, daß alle Gleichungen zusammen die implizite Nebenbedingung xAB + xAC = xDF + xEF ergeben, welche besagt, daß für das gesamte Netzwerk die hineinfließende Menge gleich der hinausfließenden Menge sein muß. Natürlich müssen darüberhinaus alle Durchflußmengen positiv sein.

Dies ist offensichtlich eine mathematische Formulierung des Problems des Flusses in einem Netzwerk: Eine Lösung dieses speziellen mathematischen Problems ist eine Lösung für das spezielle Beispiel des Problems des Flusses in einem Netzwerk. Das Wesentliche bei diesem Beispiel ist nicht etwa, daß die lineare Programmierung einen besseren Algorithmus für dieses spezielle Problem gäbe, sondern daß die lineare Programmierung eine sehr allgemeine Methode ist, die auf eine Vielzahl von Problemen angewandt werden kann. Wenn wir etwa das Problem des Flusses in einem Netzwerk dahingehend zu verallgemeinern hätten, daß neben den Durchlaßfähigkeiten zum Beispiel auch Kosten zu berücksichtigen sind, würde die Formulierung als lineare Optimierungsaufgabe nicht viel anders aussehen, obwohl eine Lösung des Problems auf direktem Wege bedeutend komplizierter sein könnte.

Lineare Optimierungsaufgaben sind nicht nur sehr aussagekräftig, sondern es existiert auch ein Algorithmus für ihre Lösung (der Simplex-Algorithmus), der sich für viele in der Praxis auftretende Probleme als sehr effizient erwiesen hat. Für manche Probleme (wie das des Flusses in einem Netzwerk) existiert möglicherweise ein speziell auf dieses Problem zugeschnittener Algorithmus, der leistungsfähiger ist als die lineare Programmierung/Simplexmethode; für andere Probleme (einschließlich verschiedener Verallgemeinerungen des Flusses in einem Netzwerk) sind keine besseren Algorithmen bekannt. Sogar dann, wenn ein besserer Algorithmus existiert, kann es sein, daß seine Implementation aufwendig oder kompliziert ist, während der Prozeß der Formulierung einer linearen Optimierungsaufgabe und ihrer Lösung mit Hilfe einer Bibliotheksroutine für die Simplexmethode oft sehr einfach ist. Dieser universelle Aspekt der Methode macht sie sehr attraktiv und war die Ursache dafür, daß sie weite Verbreitung fand. Wenn man sich jedoch zu sehr auf sie verläßt, besteht die Gefahr, daß sie für einige einfache Probleme (zum Beispiel für viele der in diesem Buch untersuchten) zu ineffizienten Lösungen führt.


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