http://dev.kaibel.net/index.php?action=history&feed=atom&title=Lineare_Programmierung
Lineare Programmierung - Versionsgeschichte
2026-08-25T01:17:08Z
Versionsgeschichte dieser Seite in dev.kaibel.net
MediaWiki 1.43.0
http://dev.kaibel.net/index.php?title=Lineare_Programmierung&diff=167&oldid=prev
PhilKa: Die Seite wurde neu angelegt: „= Lineare Programmierung = == Definition == Die '''Lineare Programmierung''' (engl. ''Linear Programming, LP'') ist ein mathematisches Optimierungsverfahren zur Maximierung oder Minimierung einer linearen Zielfunktion unter linearen Nebenbedingungen. --- == Grundlagen == === Zielfunktion === Die Zielfunktion ist eine lineare Funktion der Entscheidungsvariablen: : max / min z = c₁x₁ + c₂x₂ + ... + cₙxₙ Beispiel: : Maximierung des Gewinns…“
2026-02-28T10:07:43Z
<p>Die Seite wurde neu angelegt: „= Lineare Programmierung = == Definition == Die '''Lineare Programmierung''' (engl. ''Linear Programming, LP'') ist ein mathematisches Optimierungsverfahren zur Maximierung oder Minimierung einer linearen Zielfunktion unter linearen Nebenbedingungen. --- == Grundlagen == === Zielfunktion === Die Zielfunktion ist eine lineare Funktion der Entscheidungsvariablen: : max / min z = c₁x₁ + c₂x₂ + ... + cₙxₙ Beispiel: : Maximierung des Gewinns…“</p>
<p><b>Neue Seite</b></p><div>= Lineare Programmierung =<br />
<br />
== Definition ==<br />
Die '''Lineare Programmierung''' (engl. ''Linear Programming, LP'') ist ein mathematisches Optimierungsverfahren zur Maximierung oder Minimierung einer linearen Zielfunktion unter linearen Nebenbedingungen.<br />
<br />
---<br />
<br />
== Grundlagen ==<br />
<br />
=== Zielfunktion ===<br />
Die Zielfunktion ist eine lineare Funktion der Entscheidungsvariablen:<br />
<br />
: max / min z = c₁x₁ + c₂x₂ + ... + cₙxₙ<br />
<br />
Beispiel:<br />
: Maximierung des Gewinns<br />
<br />
---<br />
<br />
=== Entscheidungsvariablen ===<br />
Variablen, deren Werte gesucht werden:<br />
<br />
: x₁, x₂, ..., xₙ ≥ 0<br />
<br />
---<br />
<br />
=== Nebenbedingungen ===<br />
Lineare Gleichungen oder Ungleichungen:<br />
<br />
: a₁₁x₁ + a₁₂x₂ + ... ≤ b₁ <br />
: a₂₁x₁ + a₂₂x₂ + ... ≥ b₂ <br />
<br />
---<br />
<br />
=== Lösungsraum ===<br />
Die Menge aller zulässigen Lösungen wird als '''zulässiger Bereich''' (feasible region) bezeichnet.<br />
<br />
Eigenschaften:<br />
* konvex<br />
* durch lineare Ungleichungen begrenzt<br />
<br />
---<br />
<br />
== Mathematische Formulierung ==<br />
<br />
Allgemeine Form:<br />
<br />
Maximiere oder minimiere:<br />
: z = cᵀx<br />
<br />
unter den Nebenbedingungen:<br />
: Ax ≤ b <br />
: x ≥ 0<br />
<br />
---<br />
<br />
== Geometrische Interpretation ==<br />
<br />
Bei zwei Variablen lässt sich das Problem grafisch darstellen:<br />
<br />
* Nebenbedingungen bilden einen Bereich<br />
* Zielfunktion wird als Gerade verschoben<br />
* Optimum liegt an einer Ecke (Extrempunkt)<br />
<br />
---<br />
<br />
== Beispiel ==<br />
<br />
Maximiere:<br />
: z = 3x + 2y<br />
<br />
Nebenbedingungen:<br />
: x + y ≤ 4 <br />
: x ≤ 2 <br />
: y ≤ 3 <br />
: x, y ≥ 0<br />
<br />
Lösung:<br />
* Optimum liegt an einem Eckpunkt des zulässigen Bereichs<br />
<br />
---<br />
<br />
== Lösungsverfahren ==<br />
<br />
=== Simplex-Verfahren ===<br />
* Klassisches Verfahren<br />
* Durchläuft systematisch die Eckpunkte<br />
* Sehr effizient in der Praxis<br />
<br />
---<br />
<br />
=== Innere-Punkte-Verfahren ===<br />
* Arbeiten im Inneren des Lösungsraums<br />
* Gut für große Probleme geeignet<br />
<br />
---<br />
<br />
=== Graphische Methode ===<br />
* Nur für 2 Variablen praktikabel<br />
* Veranschaulichung des Problems<br />
<br />
---<br />
<br />
== Eigenschaften ==<br />
<br />
* Konvexe Optimierungsprobleme<br />
* Lokales Optimum = globales Optimum<br />
* Lösungen liegen an Randpunkten<br />
<br />
---<br />
<br />
== Dualität ==<br />
<br />
Zu jedem linearen Problem existiert ein '''duales Problem'''.<br />
<br />
Eigenschaften:<br />
* Zusammenhang zwischen primalem und dualem Problem<br />
* Wirtschaftliche Interpretation (z. B. Schattenpreise)<br />
<br />
---<br />
<br />
== Sensitivitätsanalyse ==<br />
<br />
Untersuchung, wie sich Änderungen der Parameter auswirken:<br />
<br />
* Änderung der Koeffizienten<br />
* Änderung der Nebenbedingungen<br />
* Stabilität der Lösung<br />
<br />
---<br />
<br />
== Anwendungen ==<br />
<br />
* Produktionsplanung<br />
* Transportprobleme<br />
* Ressourcenallokation<br />
* Finanzoptimierung<br />
* Netzflussprobleme<br />
* Landwirtschaft (z. B. optimale Düngemittelverteilung)<br />
<br />
---<br />
<br />
== Vorteile ==<br />
<br />
* Mathematisch gut untersucht<br />
* Effiziente Algorithmen verfügbar<br />
* Eindeutige Lösungen<br />
<br />
---<br />
<br />
== Nachteile ==<br />
<br />
* Nur lineare Zusammenhänge modellierbar<br />
* Vereinfachung realer Probleme notwendig<br />
<br />
---<br />
<br />
== Erweiterungen ==<br />
<br />
* Ganzzahlige Programmierung (Integer Programming)<br />
* Gemischt-ganzzahlige Programmierung (MILP)<br />
* Nichtlineare Programmierung (NLP)<br />
<br />
---<br />
<br />
== Vergleich zu anderen Verfahren ==<br />
<br />
{| class="wikitable"<br />
! Verfahren !! Eigenschaften<br />
|-<br />
| Lineare Programmierung || Exakt, effizient, linear<br />
|-<br />
| Nichtlineare Optimierung || Komplex, nicht-konvex möglich<br />
|-<br />
| Heuristiken || Schnell, aber nicht exakt<br />
|}<br />
<br />
---<br />
<br />
== Begriffe ==<br />
<br />
* Zielfunktion<br />
* Nebenbedingungen<br />
* Lösungsraum<br />
* Simplex<br />
* Dualität<br />
<br />
---<br />
<br />
== Literatur ==<br />
<br />
* Dantzig, G.: ''Linear Programming and Extensions''<br />
* Nocedal, J.: ''Numerical Optimization''<br />
<br />
---<br />
<br />
== Siehe auch ==<br />
<br />
* [[Optimierungsverfahren]]<br />
* [[Ganzzahlige Programmierung]]<br />
* [[Simplex-Verfahren]]<br />
* [[Multi-Objective Optimization]]<br />
* [[Pareto-Optimierung]]</div>
PhilKa