Lineare Optimierung

Problemdefinition

Mathematische Formulierung

Bei einem linearen Programm (LP) sind eine Matrix und zwei Vektoren und gegeben. Eine zulässige Lösung ist ein Vektor mit nichtnegativen Einträgen, der die linearen Bedingungen

erfüllt. Ziel ist es, unter allen zulässigen Vektoren x einen zu finden, der das Skalarprodukt

c^T x = c₁ x₁ + ... + c_n x_n

maximiert. Dieses Optimierungsproblem in der sogenannten Standardform wird oft abkürzend als

geschrieben, wobei die Bedingungen und komponentenweise zu verstehen sind.

Darüber hinaus gibt es noch weitere äquivalente Formulierungen, die sich durch einfache Operationen in diese Standardform bringen lassen:

• Minimierungsproblem statt Maximierungsproblem: Multiplikation des Zielfunktionsvektors c mit (-1)
• Größer-gleich- statt Kleiner-gleich-Bedingungen: Multiplikation der entsprechenden Ungleichungen mit (-1)
• Gleichheitsbedingungen statt Ungleichheitsbedingungen: Ersetzung von a_i x = b_i durch und
• Variablen ohne Nichtnegativitätsbedingung: Ersetzung von x durch x' - x'' mit

Die lineare Optimierung behandelt nur Probleme, bei denen die Variablen beliebige reelle Zahlen annehmen dürfen. Ein (gemischt-)ganzzahliges lineares Programm, bei dem einige Variablen nur ganzzahlige Werte annehmen dürfen, ist kein Spezialfall, sondern – im Gegenteil – eine Verallgemeinerung. Solche Optimierungsprobleme sind im allgemeinen NP-äquivalent, d. h. vermutlich nicht effizient lösbar. Dieser Fall wird von der ganzzahligen linearen Optimierung behandelt.

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