Lineare Programmierung

ist ein Rechenverfahren im Rahmen der Operations Research. Damit wird die optimale Kombination verschiedener Größen (z.B. Erstellung verschiedener Produkte) errechnet, die unter Berücksichtigung bestimmter Nebenbedingungen (z.B. gegebene -Kapazitäten) zur Erfüllung bestimmter Ziele (meist vorgegeben als Minimal- oder Maximalziele, z.B. Gewinn), führen. (= Lineare Optimierung) Gebiet der mathematischen Optimierungstheorie, das sich mit der Lösung folgender Problemstellungen befaßt: Zu optimieren ist eine Zielgröße (z.B. Nutzen, Gewinn, Umsatz), die sich als lineare Funktion mehrerer unabhängiger Variablen darstellen läßt, wobei bestimmte lineare als Gleichungen bzw. Ungleichungen formulierte Nebenbedingungen (Restriktionen) in diesen Variablen zu beachten sind. Lineare Programmierungsverfahren sind u.a. dazu geeignet, eine optimale Aufteilung knapper Ressourcen auf die Aktivitäten einer Unternehmung zu erreichen. Spezialfälle von Linearen Programmierungsproblemen sind z.B. das Transport- und das Zuordnungsproblem. Das allgemeine Maximierungsproblem der Linearen Programmierung (Standardproblem) lautet: Maximiere die Zielgröße unter Beachtung der Nebenbedingungen und der Nichtnegativitätsbedingungen x1....,x     0, wobei ai,ci und b; (1 <_ i <_ m); (1 <_ j <_ n) gegebene reellwertige Konstanten darstellen. Typisches Beispiel ist die Programmplanung: Zu bestimmen sind die herzustellenden Mengeneinheiten x1,...,x„ der Produkte P1....,P,,, so dass der Gewinn unter Beachtung von Kapazitätsbeschränkungen (Maschinenlaufzeiten, Arbeitsstunden etc.) maximiert wird. Da jedes lineare Minimierungsproblem in ein Maximierungsproblem überführt werden kann (Primal-Dual-Theorie in der Linearen Programmierung) und viele Optimierungsaufgaben in obige Form gebracht werden können, ist die Anwendbarkeit der Linearen Programmierungsverfahren vielseitig. Die Qualität der Lösungen von Linearen Programmierungsproblemen hängt in der Praxis jedoch davon ab, ob das gewählte lineare Modell unterstellt werden kann. Insbes. in den Wirtschaftswissenschaften erscheinen oft Modelle mit nichtlinearen Funktionen dem Untersuchungsgegenstand angemessener zu sein. Allg. Lösungsalgorithmen existieren jedoch nicht für alle diese Aufgabenstellungen, sondern nur für bestimmte Problemklassen (z.B. quadratische, konvexe oder nichtkonvexe Programmierung). Der Rechenaufwand ist erheblich. Das bekannteste allg. Lösungsverfahren von linearen Programmierungsaufgaben ist die Simplex-Methode, von der auch »revidierte« Versionen existieren. Ein weiteres Verfahren stellt die zweiphasige Duoplex-Methode dar. Literatur: Hillier, F.S.,Lieberman, G.J. (1988). Hadley, G. (1974). Dantzig, G.B. (1963) (lineare Planungs­rechnung): Im allgemeinsten Sinne ist Lineare Programmierung ein Verfahren der Festlegung optimaler Verhaltensweisen zur Erreichung an­gestrebter Ziele unter Einsatz von begrenzten Hilfsmitteln. In der Betriebswirtschaft wird die li­neare Planungsrechnung zur Ermittlung derjeni­gen von mehreren Kostenkonstellationen ver­wendet, bei der sich der größte Ertrag ergibt. Die­se Ermittlung ist möglich, wenn zwischen den verschiedenen Kostenfaktoren eines Wirtschafts­unternehmens eine lineare Beziehung besteht.