Lineare Optimierung

Komplexität und Lösungsverfahren

Innere-Punkte-Verfahren

Innere-Punkte-Verfahren nähern sich einer Optimallösung durch das Innere des Polyeders.

siehe Hauptartikel: Innere-Punkte-Verfahren

Innere-Punkte-Verfahren, auch Barrier-Verfahren genannt, nähern sich einer optimalen Ecke durch das Innere des Polyeders (siehe Bild). Der erste solche Algorithmus wurde 1984 von Narendra Karmarkar beschrieben. Seine Bedeutung lag vor allem darin, dass er der erste polynomiale Algorithmus zum Lösen linearer Programme war, der das Potential hatte, auch praktisch einsetzbar zu sein. Die entscheidenden Durchbrüche, die Innere-Punkte-Verfahren konkurrenzfähig zum Simplex-Algorithmus machten, wurden aber erst in den 1990er Jahren erzielt. Ein Vorteil dieser Verfahren ist, dass sie, im Gegensatz zum Simplex-Verfahren, in leichter Abwandlung auch zum Lösen quadratischer oder bestimmter nichtlinearer Programme eingesetzt werden können. Des Weiteren sind sie für große, dünnbesetzte Probleme häufig dem Simplex-Verfahren überlegen. Ein Nachteil ist, dass sie sich nach dem Hinzufügen einer Nebenbedingung oder Variablen im LP bei weitem nicht so effizient „warmstarten“ lassen wie das Simplex-Verfahren.

Copyright- und Lizenzinformationen: Diese Seite basiert auf dem Artikel Lineare Optimierung aus der freien Enzyklοpädιe Wιkιpedιa und steht unter der Lizenz Creative Commons CC-BY-SA 3.0 Unported (Kurzfassung). Liste der Autoren

Anbieterkennzeichnung