Lineare Programmierung

Die lineare Programmierung optimiert eine lineare Zielfunktion unter linearen Gleichheits- und Ungleichheitsrestriktionen, der am weitesten verbreiteten Klasse von Optimierungsproblemen.

Definition

Ein lineares Programm minimiert oder maximiert eine lineare Funktion von Entscheidungsvariablen unter linearen Nebenbedingungen; sein zulässiger Bereich ist ein konvexes Polyeder, und ein Optimum, falls es existiert, wird an einem Eckpunkt erreicht.

Scope

Dieses Thema behandelt die Standardform eines linearen Programms, die Geometrie zulässiger Polyeder und ihrer Eckpunkte, die Simplex-Methode, die Dualität der linearen Programmierung und die komplementäre Lockerheit, die Sensitivitätsanalyse sowie Innere-Punkte-Verfahren für großskalige Probleme.

Core questions

• Wie wird ein praktisches Ressourcenproblem als lineares Programm formuliert?
• Warum tritt ein Optimum an einem Eckpunkt des zulässigen Polyeders auf?
• Was sagt uns das duale lineare Programm über das primale?
• Welche Algorithmen lösen große lineare Programme effizient?

Key theories

Fundamentalsatz der linearen Programmierung

Wenn ein lineares Programm eine optimale Lösung besitzt, dann wird ein Optimum an einem Eckpunkt des zulässigen Polyeders erreicht, wodurch die Suche auf endlich viele Kandidatenpunkte reduziert wird.

Dualität und komplementäre Lockerheit

Jedes lineare Programm hat ein Duales, dessen Optimalwert dem des Primalen entspricht, und die komplementäre Lockerheit verknüpft aktive Nebenbedingungen mit nicht-null dualen Variablen, was Optimalitätszertifikate und ökonomische Interpretationen liefert.

Simplex- und Innere-Punkte-Verfahren

Die Simplex-Methode bewegt sich zwischen Eckpunkten, um die Zielfunktion zu verbessern, während Innere-Punkte-Verfahren das Innere durchqueren und lineare Programme in nachweislich polynomialer Zeit lösen.

Clinical relevance

Die lineare Programmierung ist ein Eckpfeiler der Operations Research und wird für Produktionsplanung, Transport und Logistik, Terminplanung, Diät- und Mischungsprobleme sowie Netzwerkflüsse eingesetzt. Sie dient auch als Unterroutine in der ganzzahligen und nichtlinearen Optimierung.

History

Kantorovich führte 1939 die lineare Optimierung für die Produktionsplanung ein, und Dantzig formulierte 1947 das allgemeine Problem und die Simplex-Methode. Von Neumann erkannte die Dualität zur Spieltheorie, und Khachiyans Ellipsoid-Methode sowie Karmarkars Innere-Punkte-Methode etablierten später die Lösbarkeit in polynomialer Zeit.

Key figures

• George Dantzig
• Leonid Kantorovich
• John von Neumann
• Narendra Karmarkar

Seminal works

• dantzig1963
• luenberger2008

Frequently asked questions

Warum liegt das Optimum an einem Eckpunkt?

Eine lineare Zielfunktion steigt in einer festen Richtung am schnellsten an, sodass ihr bester Wert über einem konvexen Polyeder an die Grenze und letztendlich an eine Ecke gedrängt wird. Sofern die Zielfunktion nicht entlang einer Kante oder Fläche konstant ist, wird das Optimum an einem Eckpunkt erreicht.

Ist die Simplex-Methode immer schnell?

In der Praxis ist die Simplex-Methode sehr effizient, aber Worst-Case-Beispiele können eine exponentielle Anzahl von Schritten erfordern. Innere-Punkte-Verfahren bieten eine polynomiale Zeitgarantie, und moderne Solver verwenden je nach Problem beide Ansätze.