Lineare Programmierung, mathematische Modellierungstechnik, bei der eine lineare Funktion maximiert oder minimiert wird, wenn sie verschiedenen Einschränkungen ausgesetzt ist. Diese Technik war nützlich, um quantitative Entscheidungen in der Unternehmensplanung, im Wirtschaftsingenieurwesen und in geringerem Maße in den Sozial- und Physikwissenschaften zu treffen.
Optimierung: Lineare Programmierung
Obwohl die lineare Programmierung heute weit verbreitet ist, um alltägliche Entscheidungsprobleme zu lösen, war sie vor 1947 vergleichsweise unbekannt. Keine Arbeit von Bedeutung
Die Lösung eines linearen Programmierproblems reduziert sich darauf, den optimalen Wert (je nach Problem am größten oder am kleinsten) des linearen Ausdrucks (als Zielfunktion bezeichnet) zu finden.
vorbehaltlich einer Reihe von Einschränkungen, die als Ungleichungen ausgedrückt werden:
Die a, b und c sind Konstanten, die durch die Kapazitäten, Bedürfnisse, Kosten, Gewinne und andere Anforderungen und Einschränkungen des Problems bestimmt werden. Die Grundannahme bei der Anwendung dieser Methode ist, dass die verschiedenen Beziehungen zwischen Nachfrage und Verfügbarkeit linear sind; das heißt, keines der x i wird auf eine andere Potenz als 1 angehoben. Um die Lösung für dieses Problem zu erhalten, ist es notwendig, die Lösung des Systems linearer Ungleichungen (dh der Menge von n Werten von) zu finden die Variablen x i, die gleichzeitig alle Ungleichungen erfüllen). Die Zielfunktion wird dann bewertet, indem die Werte von x i in die Gleichung eingesetzt werden, die f definiert.
Die Anwendung der Methode der linearen Programmierung wurde erstmals Ende der 1930er Jahre vom sowjetischen Mathematiker Leonid Kantorovich und vom amerikanischen Ökonomen Wassily Leontief in den Bereichen Fertigungspläne und Wirtschaft ernsthaft versucht, ihre Arbeit wurde jedoch jahrzehntelang ignoriert. Während des Zweiten Weltkriegs wurde die lineare Programmierung ausgiebig genutzt, um den Transport, die Planung und die Zuweisung von Ressourcen unter bestimmten Einschränkungen wie Kosten und Verfügbarkeit zu regeln. Diese Anwendungen haben viel dazu beigetragen, die Akzeptanz dieser Methode zu belegen, die 1947 mit der Einführung der Simplex-Methode des amerikanischen Mathematikers George Dantzig, die die Lösung linearer Programmierprobleme erheblich vereinfachte, weitere Impulse erhielt.
Als jedoch immer komplexere Probleme mit mehr Variablen versucht wurden, nahm die Anzahl der erforderlichen Operationen exponentiell zu und überstieg die Rechenkapazität selbst der leistungsstärksten Computer. 1979 entdeckte der russische Mathematiker Leonid Khachiyan einen Polynom-Zeit-Algorithmus, bei dem die Anzahl der Rechenschritte eher als Potenz der Anzahl der Variablen als exponentiell zunimmt, wodurch die Lösung bisher unzugänglicher Probleme ermöglicht wurde. Der Algorithmus von Khachiyan (Ellipsoid-Methode genannt) war jedoch bei praktischer Anwendung langsamer als die Simplex-Methode. 1984 entdeckte der indische Mathematiker Narendra Karmarkar einen anderen Polynom-Zeit-Algorithmus, die Interior-Point-Methode, die sich als wettbewerbsfähig mit der Simplex-Methode erwies.
