--- title: "Lineare Programmierung" source: "https://systems-analysis.info/int/Lineare_Programmierung" wiki: "systems-analysis.info/int" article: "Lineare_Programmierung" language: "de" categories: - "Category:German" - "Category:Mathematical modeling" - "Category:Modeling" - "Category:Operations research" - "Category:Optimization" revision_id: 3871 wiki_created_at: 2026-09-06T23:27:19Z wiki_modified_at: 2026-09-06T23:27:19Z downloaded_at: 2026-09-07T22:59:31Z --- # Lineare Programmierung **Lineare Programmierung** (LP), auch **lineare Optimierung** genannt, ist ein Teilgebiet der mathematischen Programmierung und eine weit verbreitete Methode des Operations Research. Sie befasst sich mit der Theorie und den Methoden zur Lösung von Problemen, bei denen ein Extremwert (Maximum oder Minimum) einer linearen Funktion unter linearen Nebenbedingungen gesucht wird. Die LP ist eines der leistungsfähigsten und am häufigsten verwendeten Werkzeuge zur Lösung von Optimierungsproblemen in Wirtschaft, Management, Planung, Logistik und anderen Bereichen. ## Gegenstand und Zweck Die **Hauptaufgabe der linearen Programmierung** besteht darin, den besten (optimalen) Weg zur Verteilung begrenzter Ressourcen zu finden, um ein bestimmtes Ziel zu erreichen, wenn sowohl das Ziel als auch die Einschränkungen bei der Ressourcennutzung durch lineare Beziehungen ausgedrückt werden können. Die lineare Programmierung ermöglicht die Lösung praktischer Aufgaben wie: - Optimale Produktionsplanung. - Optimierung von Verkehrsflüssen (Transportproblem). - Optimale Verteilung von Investitionen. - Optimaler Materialzuschnitt. - Zuordnungsproblem. ## Mathematische Formulierung des LP-Problems Ein Standardproblem der linearen Programmierung wird wie folgt formuliert: Es sollen die Werte der Entscheidungsvariablen gefunden werden, die eine lineare Zielfunktion maximieren oder minimieren. Dabei unterliegen die Entscheidungsvariablen Nebenbedingungen in Form eines Systems linearer Gleichungen und/oder linearer Ungleichungen. In der Regel wird eine Nichtnegativitätsbedingung für die Entscheidungsvariablen hinzugefügt (ihre Werte müssen größer oder gleich null sein), was oft durch den physikalischen oder wirtschaftlichen Kontext des Problems bedingt ist. Mathematisch bedeutet dies die Arbeit mit linearen Funktionen und Systemen linearer Gleichungen/Ungleichungen. ## Grundbegriffe der LP - **Entscheidungsvariablen** (Steuervariablen): Größen, deren Werte im Zuge der Problemlösung bestimmt werden müssen (z. B. Produktionsmengen verschiedener Produkte, die Menge der für verschiedene Zwecke eingesetzten Ressourcen). - **Zielfunktion:** Eine lineare Funktion der Entscheidungsvariablen, deren Wert maximiert oder minimiert werden soll. Sie drückt das Ziel des Problems quantitativ aus (z. B. Gesamtgewinn, Gesamtkosten). - **Nebenbedingungen:** Ein System linearer Gleichungen und/oder Ungleichungen, denen die Entscheidungsvariablen genügen müssen. Die Nebenbedingungen spiegeln Ressourcenbeschränkungen, technologische Anforderungen, Planvorgaben und andere Bedingungen des Problems wider. - **Zulässiger Bereich** (zulässige Lösungsmenge): Die Menge aller Wertekombinationen der Entscheidungsvariablen, die alle Nebenbedingungen des Problems erfüllen. Geometrisch stellt der zulässige Bereich in einem mehrdimensionalen Raum ein konvexes Polyeder dar, das unbeschränkt oder leer sein kann. - **Zulässige Lösung:** Jede Wertekombination von Variablen, die zum zulässigen Bereich gehört. - **Optimale Lösung:** Eine zulässige Lösung, bei der die Zielfunktion ihren Extremwert (Maximum oder Minimum) erreicht. Wenn eine optimale Lösung existiert, befindet sie sich immer auf dem Rand des zulässigen Bereichs, mindestens in einer der Ecken des konvexen Polyeders (Hauptsatz der linearen Programmierung). ## Lösungsmethoden für LP-Probleme Es gibt mehrere grundlegende Methoden zur Lösung von Problemen der linearen Programmierung: - **Grafische Methode:** Wird für Probleme mit zwei Entscheidungsvariablen angewendet. Sie ermöglicht die anschauliche Darstellung des zulässigen Bereichs und der Zielfunktion in einer Ebene und die Findung der optimalen Lösung durch Analyse der Ecken des zulässigen Bereichs oder durch Verschieben der Niveaulinie der Zielfunktion. - **Simplex-Verfahren:** Ein universeller iterativer Algorithmus, der von George Dantzig entwickelt wurde. Das Verfahren bewegt sich schrittweise von einer Ecke des zulässigen Bereichs zu einer benachbarten und verbessert bei jedem Schritt den Wert der Zielfunktion, bis die optimale Lösung gefunden ist. Es ist das klassische und bekannteste Verfahren zur Lösung von LP-Problemen. - **Innere-Punkte-Verfahren:** Eine alternative Klasse von Algorithmen, die später als das Simplex-Verfahren entwickelt wurden. Sie bewegen sich auf dem Weg zur optimalen Lösung im Inneren des zulässigen Bereichs und nicht entlang seiner Grenzen. Diese Verfahren sind besonders effizient bei der Lösung sehr großer LP-Probleme. ## Dualität in der linearen Programmierung Jedem Problem der linearen Programmierung (dem primalen Problem) kann ein anderes LP-Problem zugeordnet werden, das als duales Problem bezeichnet wird. Das primale und das duale Problem sind eng miteinander verbunden: Die Lösung des einen Problems liefert Informationen über die Lösung des anderen. Die optimalen Werte der Zielfunktionen beider Probleme stimmen überein (sofern sie existieren). Die Variablen des dualen Problems haben eine wichtige wirtschaftliche Interpretation — sie entsprechen den Schattenpreisen (oder dualen Variablen) der Ressourcen und zeigen an, wie sich der optimale Wert der Zielfunktion des primalen Problems ändert, wenn sich die Beschränkung für die entsprechende Ressource geringfügig ändert. ## Anwendungen der LP Die lineare Programmierung findet breite Anwendung in: - Wirtschaft und Business (Produktionsplanung, Logistik, Finanzen, Marketing). - Industrie (Optimierung von technologischen Prozessen, Bestandsmanagement, Materialzuschnitt). - Transportwesen (Optimierung von Routen, Fahrplänen). - Landwirtschaft (Optimierung von Anbauflächen, Futterrationen). - Energiewirtschaft (Optimierung der Auslastung von Erzeugungskapazitäten). ## Siehe auch - [Optimierung](https://systems-analysis.info/int/Optimierung "Optimierung") - [Zielfunktion](https://systems-analysis.info/int/Zielfunktion "Zielfunktion") - [Ganzzahlige Programmierung](https://systems-analysis.info/int/Ganzzahlige_Programmierung "Ganzzahlige Programmierung") - [Nichtlineare Programmierung](https://systems-analysis.info/int/Nichtlineare_Programmierung "Nichtlineare Programmierung") - [Mathematisches Modell](https://systems-analysis.info/int/Mathematisches_Modell "Mathematisches Modell") ## Literatur - *Dantzig, G. B.* Lineare Programmierung und Erweiterungen. Moskau: Progress, 1966. - *Judin, D. B., Golstein, E. G.* Lineare Programmierung (Theorie, Methoden und Anwendungen). Moskau: Nauka, 1969. - *Taha, H. A.* Operations Research: An Introduction. 10. Aufl. Pearson, 2017. - *Hillier, F. S., Lieberman, G. J.* Introduction to Operations Research. 11. Aufl. McGraw-Hill Education, 2021.