WikiDer > Lineares Programmieren

Beispiel mit zwei Variablen, in der Praxis sind es mehr. Die Bedingungen bestimmen die konvexe erlaubte Fläche. Erst danach wird die Zielfunktion eingegeben.

In dem Mathematik, spezieller in der operatives recherchieren, oder Englisch: OR für Operations Research, is Lineares Programmieren oder Lineares Programmieren eine Methode zur Lösung sogenannter linearer Programmierprobleme, kurz LP-Probleme. Jene sind Optimierungsprobleme wobei die Zielfunktion und die Randbedingungen alle sind linear sein.

Programmieren ist nicht im Sinne eines Computerprogramms zu verstehen, sondern im Sinne von Planung. Der Name wurde Mitte der 1940er Jahre von einem der Begründer der linearen Programmierung eingeführt, George Dantzig, lange bevor die Computer wurde für die Berechnungen in der linearen Programmierung verwendet.

Lineare Programmierung ist aus mehreren Gründen eine wichtige Disziplin bei der Optimierung. Viele praktische Probleme in der wissenschaftlichen Forschung können als lineare Programmierprobleme ausgedrückt werden. Bestimmte Sonderfälle der linearen Programmierung, wie zum Beispiel die Probleme vernetzter Flüsse, werden als ausreichend wichtig erachtet, um die Erforschung spezialisierter Algorithmen für ihre Lösung. Der Betrieb einer Reihe von Algorithmen für andere Arten von Optimierungsproblemen basiert auf der Lösung von Teilproblemen wie LP-Problemen. Die Ideen der linearen Programmierung haben im Laufe der Zeit viel zur Optimierungstheorie beigetragen, wie zum Beispiel die Konzepte Dualität, Zerlegung und konvex.

Geschichte

Der sowjetisch-russische Mathematiker Leonid Kantorowitsch diskutiert in 1939 in seinem Buch „Mathematische Methoden in der Organisation und Planung der Produktion“ wurde erstmals die Methode der linearen Programmierung vorgestellt. Angesichts der enormen Bedeutung der Planwirtschaft in dem Sovietunion Es überrascht nicht, dass der Ursprung dieses Zweiges der Mathematik aus Russland stammt. Kantorowitsch erhielt teilweise für diese Arbeit in 1975 das Nobelpreis für Wirtschaftswissenschaften. Der Amerikaner Frank L. Hitchcock verfasste kurz darauf einen Artikel über ein Transportproblem, doch die Arbeit der beiden Männer fand vor allem im Westen wenig Beachtung.

George Dantzig Mitte der 1940er Jahre verstanden, dass viele praktische Einschränkungen durch lineare . ausgedrückt werden Ungleichheiten und ersetzte die bisher verwendeten Faustregeln zur Lösung von Planungsproblemen durch eine lineare Zielfunktion. Dabei führte er eine klare Trennung zwischen dem Ziel der Optimierung und den Mitteln zur Lösung des Planungsproblems ein. Der Durchbruch gelang 1947, als Dantzig seine Arbeit über die Simplex-Methode veröffentlicht. Diese Algorithmus ist heute noch eines der am häufigsten verwendeten Mittel, um eine Lösung für ein „lineares Programm“ zu finden. Das US-Militär, insbesondere die Air Force, griff schnell Dantzigs Arbeit auf, um den militärischen Einsatz zu fördern und die Logistik um es weiter zu verbessern. In den Folgejahren entwickelte er unter anderem gemeinsam mit John von Neumann, Oskar Morgenstern und Tjalling Koopmans die Theorie weiter und stellte mehrere Verbindungen zu den Spieltheorie.

Theorie

Die linearen Nebenbedingungen, die Randbedingungen, bestimmen a Polyeder, dass es erlaubter Bereich wird genannt. Die erlaubte Fläche ist konvex. In der optimalen Lösung gibt es immer a Scheitel dieser erlaubten Fläche, da die Zielfunktion ebenfalls linear ist. Die optimale Lösung kann auch Liniensegment zwischen zwei Eckpunkten des zulässigen Bereichs.

Es gibt zwei Situationen, in denen keine optimale Lösung gefunden werden kann. Erstens, wenn sich die Randbedingungen widersprechen, zum Beispiel ${displaystyle xgeq 2}$ und ${displaystyle xleq 1}$, ist der zulässige Bereich leer, daher gibt es keine optimale Lösung.

Zweitens kann es Polyeder in Richtung der Zielfunktion sind unbeschränkt, zum Beispiel: maximieren ${displaystyle x_{1} 3 x_{2}}$ mit Bedingungen ${displaystyle x_{1}geq 0}$, ${displaystyle x_{2}geq 0}$ und ${displaystyle x_{1} x_{2}geq 10}$, wo es keine optimale Lösung gibt, da Lösungen mit beliebig hohen Werten der Zielfunktion konstruiert werden können.

Außer in diesen beiden Fällen gibt es immer einen Scheitelpunkt, an dem ein Optimum erreicht wird. Das Optimum ist jedoch nicht unbedingt eindeutig: Es ist möglich, eine Menge optimaler Lösungen zu haben, die eine Kante oder ein a enthalten eben des Polyeders.^[1]

Beispiel

Hier ist ein Beispiel für ein lineares Programmierproblem. Ein Bauer hat ein Stück Ackerland, sagen wir ${Anzeigestil A}$ Quadratkilometer groß. Er kann darauf Weizen, Gerste oder eine Kombination aus beidem anbauen. Weizen bringt eine Menge pro Flächeneinheit ${displaystyle S_{1}}$ auf und Gerste eine Menge ${displaystyle S_{2}}$. Es scheint lukrativ, nur die ertragreichsten Pflanzen anzubauen, aber der Anbau unterliegt aufgrund des erforderlichen Düngers und Insektizids Einschränkungen. Die benötigten Mengen pro Flächeneinheit sind für die beiden Kulturen unterschiedlich, nämlich für Weizen (${Displaystil F_{1},P_{1}}$) und für Gerste (${Displaystil F_{2},P_{2}}$). Der Bauer hat eine begrenzte zulässige Menge ${Anzeigestil F}$ Dünger und ${Anzeigestil P}$ Insektizid, das verwendet werden kann. Wenn wir die mit Weizen bzw. Gerste bepflanzten Flächen messen ${displaystyle x_{1}}$ und ${displaystyle x_{2}}$ die optimale Verteilung der verfügbaren landwirtschaftlichen Fläche zwischen den beiden Kulturen kann als lineares Programmierungsproblem ausgedrückt werden:

maximieren	${displaystyle ,S_{1}x_{1} S_{2}x_{2}}$	der Profit
mit Bedingung	${displaystyle ,x_{1} x_{2}leq A}$	Begrenzung der Gesamtfläche
	${displaystyle ,F_{1}x_{1} F_{2}x_{2}leq F}$	Beschränkung auf Dünger
	${displaystyle ,P_{1}x_{1} P_{2}x_{2}leq P}$	Beschränkung auf Insektizide
	${displaystyle ,x_{1}geq 0,,x_{2}geq 0}$	kann keine negative fläche pflanzen

Algorithmen

Es Simplex-Algorithmus löst LP-Probleme, indem er eine plausible Lösung an einem Scheitelpunkt des Polyeders konstruiert und dann entlang von Kanten des Polyeders zu Scheitelpunkten mit sequentiell höheren Werten der Zielfunktion läuft, bis das Optimum erreicht ist. Obwohl dieser Algorithmus in der Praxis recht effizient ist und sichergestellt werden kann, dass das globale Optimum gefunden wird, wenn bestimmte Vorkehrungen gegen Endlosschleifen getroffen werden, nimmt er im schlimmsten Fall viel Zeit in Anspruch: Es ist möglich, ein lineares Programmierproblem zu konstruieren, für das die Simplex-Methode dauert ein paar Schritte exponentiell in Bezug auf die Problemgröße.

Narenda Karmarkar entwickelt in 1984 die „Projektionsmethode“. Dies ist der erste Algorithmus, der sowohl in der Theorie als auch in der Praxis gut funktioniert. Es gehört zur internen Punktmethode.

Im Allgemeinen werden LP-Randbedingungserfüller verwendet, um verschiedene Probleme in der Industrie zu optimieren, beispielsweise von Strömungen in Verkehrsnetzen.

Es kann vorkommen, dass die meisten Variablenwerte, die meisten Variablen in einer Lösung gleich 0 sein. In einem solchen Fall kann es effizient sein, zunächst nicht alle Variablen in das Problem einzubeziehen, sondern erst hinzuzufügen, wenn sie sich als interessant erweisen. Algorithmen, die dieses Prinzip anwenden, verwenden eine verzögerte Spaltengenerierung. Neue Variablen werden häufig anhand eines Teilproblems gesucht, das üblicherweise als „Preisproblem“ bezeichnet wird. Das Preisproblem wird durch die Schattenpreise, auch Duals genannt, der aktuellen Lösung gesteuert. Diese Schattenpreise existieren so lange, wie es im Hauptproblem keine Bedingungen für Variablen gibt, die gerade Zahl muss sein.

Integer lineare Programmierung

Wenn alle unbekannten Variablen a . haben müssen gerade Zahl sein sollte, wird das Problem ein ganzzahliges lineares Programmierproblem genannt.^[2] Diese Probleme sind im Allgemeinen schwieriger zu lösen als LP-Probleme. Das 0-1-Problem ist ein Sonderfall des ganzzahligen linearen Programmierproblems, bei dem die Variablen nur die Werte 0 oder 1 annehmen dürfen. Wenn nur wenige unbekannte Variablen ganze Zahlen sein müssen, wird das Problem als gemischt ganzzahliges Programmierproblem bezeichnet.^[3]

Manchmal die LP-Entspannung gelöst und geprüft, ob es eine akzeptable Lösung für das ursprüngliche Problem darstellt. Bei der LP-Relaxation die Forderung, dass die Variablen vollständig weggelassen werden müssen. Falls die Bedingungsmatrix voorwaarden total unimodular h., die Lösung der LP-Relaxation ist ganzzahlig. Wenn nicht, liefert die LP-Relaxation eine reine Ganzzahllösung, die die optimale Lösung für das ganzzahlige lineare Programmierproblem findet. Wenn in der LP Entspannung Brüche auftreten, gibt es zwei Haupttechniken, mit denen die Lösung ganzzahlig gemacht werden kann. Zum Beispiel ist es möglich, dem Problem zusätzliche Bedingungen hinzuzufügen, die Lösungen, in denen Brüche vorkommen, aus dem zulässigen Lösungsraum eliminieren. Diese Technik wird Schnittebenen erwähnt. Ein anderer Ansatz besteht darin, Branch and Bound zu verwenden, wobei der Wert der LP-Relaxation als natürliche untere oder obere Schranke verwendet werden kann.