Ellipsoid-method
Relevante Bilder
Relevante Artikel
EllipsoidmethodeDie Ellipsoidmethode ist ein polynomialer Algorithmus zur Linearen Optimierung. Sie wurde ursprünglich in den Jahren 1976 und 1977 von David Yudin und Arkadi Nemirovski und unabhängig davon von Naum Schor zur Lösung konvexer Optimierungsprobleme entwickelt. Im Jahre 1979 wurde sie vom russischen Mathematiker Leonid Khachiyan zum ersten polynomialen Algorithmus zur Lösung linearer Programme erweitert. Damit bewies er erstmals die polynomiale Lösbarkeit linearer Optimierungsprobleme. Für praktische Zwecke ist die Ellipsoidmethode allerdings nicht geeignet, da sie dem Simplex-Verfahren numerisch in der Praxis weit unterlegen ist. .. weiterlesen
Lineare OptimierungDie 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. .. weiterlesen