mini|240px|Bei linearen Optimierungsproblemen ist die Menge der zulässigen Punkte (braun) durch lineare Ungleichungen (Halbräume, definiert durch Hyperebenen) eingeschränkt.
Die lineare Optimierung oder lineare Programmierung ist eines der Hauptverfahren des Operations Research und beschäftigt sich mit der Optimierung linearer Zielfunktionen über einer Menge, die durch lineare Gleichungen und Ungleichungen eingeschränkt ist. Häufig lassen sich lineare Programme (LPs) zur Lösung von Problemen einsetzen, für die keine speziell entwickelten Lösungsverfahren bekannt sind, beispielsweise bei der Planung von Verkehrs- oder Telekommunikationsnetzen oder in der Produktionsplanung. Die lineare Optimierung ist ein Spezialfall der konvexen Optimierung und Grundlage mehrerer Lösungsverfahren in der ganzzahligen linearen und der nichtlinearen Optimierung. Viele Eigenschaften linearer Programme lassen sich als Eigenschaften von Polyedern interpretieren und auf diese Art geometrisch modellieren und beweisen.
Der Begriff „Programmierung“ ist eher im Sinne von „Planung“ zu verstehen als im Sinne der Erstellung eines Computerprogramms. Er wurde schon Mitte der 1940er-Jahre von George Dantzig, einem der Begründer der linearen Optimierung, geprägt, bevor Computer zur Lösung linearer Optimierungsprobleme eingesetzt wurden.
Aus komplexitätstheoretischer Sicht ist die lineare Optimierung ein einfaches Problem, da es sich beispielsweise mit einigen Innere-Punkte-Verfahren in polynomialer Zeit lösen lässt. In der Praxis hat sich allerdings das Simplex-Verfahren als einer der schnellsten Algorithmen herausgestellt, obwohl es im schlechtesten Fall exponentielle Laufzeit besitzt. Neben dem eigentlichen Problem löst es immer auch das sogenannte duale Problem mit, was unter anderem in mehreren Verfahren zur Lösung ganzzahliger linearer Programme ausgenutzt wird.
Geschichte Die Methode der linearen Optimierung wurde 1939 von dem sowjetischen Mathematiker Leonid Witaljewitsch Kantorowitsch in seinem Aufsatz „Mathematische Methoden für die Organisation und Planung der Produktion“ eingeführt.Mathematical Methods of Organizing and Planning Production. (PDF; 1,4 MB). In: Management Science. Band 6, Nr. 4 (Juli 1960), S. 366–422. Kurz danach veröffentlichte der Amerikaner Frank L. Hitchcock eine Arbeit zu einem Transportproblem. Damals erkannte man noch nicht die Bedeutung dieser Arbeiten. Unter anderem für seinen Beitrag zur linearen Optimierung bekam Kantorowitsch aber 1975 den Nobelpreis für Wirtschaftswissenschaften.
Mitte der 1940er-Jahre erkannte George Dantzig, dass sich viele praktische Beschränkungen durch lineare Ungleichungen beschreiben ließen, und ersetzte erstmals die bis dahin vorherrschenden Faustregeln zur Lösung von Planungsproblemen durch eine (lineare) Zielfunktion. Insbesondere etablierte er damit eine klare Trennung zwischen dem Ziel der Optimierung und den Mitteln zur Lösung des Planungsproblems.
Den Durchbruch für die lineare Optimierung schaffte Dantzig 1947, als er eine Arbeit über das Simplex-Verfahren veröffentlichte, das heute eines der meistgenutzten Verfahren zur Lösung linearer Programme ist.Heiner Müller-Merbach: Operations Research. 3. Auflage. Verlag Franz Vahlen, München 1973, ISBN 3-8006-0388-8, S. 89. Interesse an dieser Arbeit zeigten zunächst die amerikanischen Militärs, speziell die US Air Force, die militärische Einsätze optimieren wollten. In den Folgejahren entwickelten Dantzig, John von Neumann, Oskar Morgenstern, Tjalling Koopmans und andere das Verfahren und die zugehörige Theorie weiter und stellten Zusammenhänge zur Spieltheorie her. Mit dem Aufkommen von Computern Mitte der 1950er-Jahre konnte man auch größere Probleme lösen. Etwa ab 1950 entdeckte die Wirtschaft, insbesondere Ölraffinerien, die Anwendungsmöglichkeiten der linearen Optimierung. Ab den 1970er-Jahren profitierte der Simplex-Algorithmus von algorithmischen Fortschritten der numerischen linearen Algebra. Insbesondere die Entwicklung numerisch stabiler LR-Zerlegungen zur Lösung großer linearer Gleichungssysteme trugen maßgeblich zum Erfolg und der Verbreitung des Simplex-Verfahrens bei.
Im Jahre 1979 veröffentlichte Leonid Khachiyan die Ellipsoidmethode, mit der lineare Programme erstmals – zumindest theoretisch – in Polynomialzeit gelöst werden konnten. 1984 begannen Narendra Karmarkar und andere mit der Entwicklung von Innere-Punkte-Verfahren zur Lösung linearer Programme.N. Karmarkar: A new polynomial-time algorithm for linear programming. Combinatorica 4 (1984), Nr. 4, 373–395. Diese Algorithmen, die als erste polynomiale Lösungsmethoden auch das Potential zum praktischen Einsatz hatten, wurden innerhalb des nachfolgenden Jahrzehnts noch wesentlich verbessert. Parallel dazu wuchs die Bedeutung des Simplex-Verfahrens zur Lösung von Unterproblemen in der ganzzahligen linearen Optimierung. Anfang der 1990er-Jahre wurden hier noch einmal große Fortschritte durch die Entwicklung neuer Pivotstrategien für den dualen Simplex-Algorithmus erzielt, insbesondere durch das dual steepest edge pricing von John Forrest und Donald Goldfarb.
Sowohl das Simplex-Verfahren als auch verschiedene Innere-Punkte-Verfahren sind nach wie vor Gegenstand aktueller Forschung. Die lineare Optimierung wird heute in sehr vielen Bereichen zur Lösung praktischer Probleme eingesetzt. Unter der in praktischen Anwendungen fast immer erfüllten Voraussetzung, dass die auftretenden LP-Matrizen dünnbesetzt sind (also nur wenige Nicht-Null-Einträge besitzen), können heute lineare Programme mit mehreren hunderttausend Variablen oder Ungleichungen innerhalb weniger Minuten bis Stunden optimal gelöst werden. Die tatsächliche Lösungszeit hängt dabei neben dem verwendeten Lösungsverfahren auch stark von der Anzahl und Anordnung der Nicht-Null-Einträge in der beteiligten Matrix und von der Wahl der Startlösung ab.
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 einen zu finden, der das Standardskalarprodukt
maximiert. Dieses Optimierungsproblem in der sogenannten Standardform (auch als Ungleichungsform bezeichnet) 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 mit Größer-gleich- statt Kleiner-gleich-Bedingungen: Multiplikation der entsprechenden Ungleichungen mit Gleichheitsbedingungen statt Ungleichheitsbedingungen: Ersetzung von durch und Variablen ohne Nichtnegativitätsbedingung: Ersetzung von durch 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.
Geometrische Interpretation Ein lineares Programm lässt sich geometrisch interpretieren. Wenn die i. Zeile eines linearen Programms in Standardform ist, dann beschreibt die Menge aller Punkte , die die zugehörige lineare Gleichung erfüllen, eine Hyperebene im -dimensionalen Raum. Die Menge der Punkte, die die lineare Ungleichung erfüllen, besteht aus allen Punkten auf der einen Seite der Hyperebene (inklusive der Hyperebene selbst), bildet also einen Halbraum. Jede Zeile teilt daher den -dimensionalen Raum in zwei Hälften, wobei die Punkte in der einen Hälfte zulässig sind und in der anderen nicht. Die Menge
der Punkte, die alle Ungleichungen des LPs erfüllen, ist genau der Schnitt dieser Halbräume, also die Menge aller Punkte, die für jede Ungleichung in der jeweiligen zulässigen Hälfte des Raumes liegen. Diese Lösungsmenge des linearen Programms bildet ein konvexes Polyeder, also ein -dimensionales Vieleck, in dem die Verbindungslinie zwischen zwei beliebigen Punkten von vollständig in enthalten ist. Ziel der Optimierung ist es, unter allen Punkten des Polyeders einen zu finden, der die lineare Funktion maximiert. Geometrisch entspricht dies der Verschiebung der Hyperebene in Richtung des Vektors , bis die verschobene Hyperebene das Polyeder gerade noch berührt. Die Menge aller Berührungspunkte ist genau die Menge der Optimallösungen des linearen Programms.
mini|250px|Zulässige Menge (blau) eines LPs in Standardform mit einschränkenden Ungleichungen (grün), Zielfunktion (rote Linie) und einer optimalen Lösung (roter Punkt)
Im nebenstehenden Bild ist diese Anordnung für den Fall von nur zwei Variablen dargestellt. Eine Hyperebene im zweidimensionalen Raum ist eine Gerade, im Bild grün dargestellt. Jede dieser Geraden teilt den Raum in eine zulässige und eine unzulässige Hälfte. Die Menge der Punkte, die auf der zulässigen Seite jeder Geraden liegen, bilden das blau dargestellte Polyeder (Vieleck). Die rote Gerade stellt die Zielfunktion dar. Ziel ist es, sie so weit wie möglich in Richtung des roten Vektors zu verschieben, ohne das Polyeder zu verlassen. Im nebenstehenden Bild ist der rote Berührungspunkt der Zielfunktionsgeraden mit dem Polyeder die einzige Optimallösung.
Beispiel aus der Produktionsplanung (zweidimensional) Ein Unternehmen stellt zwei verschiedene Produkte her, für deren Fertigung drei Maschinen A, B, C zur Verfügung stehen. Diese Maschinen haben eine maximale monatliche Laufzeit (Kapazität) von 170 Stunden (A), 150 Stunden (B) bzw. 180 Stunden (C). Eine Mengeneinheit (ME) von Produkt 1 liefert einen Deckungsbeitrag von 300 Euro, eine ME von Produkt 2 dagegen 500 Euro. Fertigt man eine ME von Produkt 1, dann benötigt man dafür eine Stunde die Maschine A und eine Stunde die Maschine B. Eine Einheit von Produkt 2 belegt zwei Stunden lang Maschine A, eine Stunde Maschine B und drei Stunden Maschine C. Ziel ist es, Produktionsmengen zu bestimmen, die den Deckungsbeitrag des Unternehmens maximieren, ohne die Maschinenkapazitäten zu überschreiten. Fixkosten können in dem Optimierungsproblem ignoriert und anschließend addiert werden, da sie per Definition unabhängig von den zu bestimmenden Produktionsmengen sind.
Mathematische Modellierung mini|330px|Veranschaulichung des Beispiels (Erklärung siehe Text)
Angenommen, der Betrieb fertigt pro Monat ME von Produkt 1 und ME von Produkt 2. Dann beträgt der Gesamtdeckungsbeitrag
Diesen Wert möchte das Unternehmen maximieren. Da die Maschinenkapazitäten eingehalten werden müssen, ergeben sich die Nebenbedingungen:
Da außerdem keine negativen Produktionsmengen möglich sind, muss gelten (Nichtnegativitätsbedingung).
Geometrische Interpretation als Polyeder Im nebenstehenden Bild sind die Ungleichungen aus dem obigen Beispiel als türkise, schwarze und violette Beschränkungen eingezeichnet. Zusammen definieren sie das (blau umrandete) Polyeder der zulässigen Punkte. Die rotgestrichelten Linien stellen Iso-Gewinnfunktionen dar, d. h., alle Punkte auf einer solchen Linie haben denselben Zielfunktionswert. Da das Unternehmen möglichst viel Gewinn erzielen will, ist das Ziel der Optimierung, solch eine rot gestrichelte Linie so weit nach rechts oben zu schieben, dass sie gerade noch das Polyeder berührt. Alle Berührungspunkte sind dann optimal. In diesem Fall ist der Punkt (130,20) die eindeutige optimale Ecke, und der optimale Zielfunktionswert beträgt 49.000 Euro.