Eckpunktberechnungsmethode: Unterschied zwischen den Versionen

Zum nächsten Versionsunterschied →

VisuellWikitext

@@ Zeile 1: / Zeile 1: @@
 == Definition ==
-Die '''Eckpunktberechnungsmethode''' basiert auf der mathematischen Erkenntnis, dass die optimale Lösung eines [[Lineares Optimierungsproblem|linearen Optimierungsproblems]] immer in einem Eckpunkt des zulässigen Bereichs (Planungspolyeder) liegt.
+Die '''Eckpunktberechnungsmethode''' ist ein grafisches Lösungsverfahren für lineare Optimierungsprobleme mit zwei Variablen.
-Dieses Verfahren ist besonders effizient bei zwei oder drei Entscheidungsvariablen, wenn die grafische Genauigkeit nicht ausreicht.
+== Grundidee ==
+* Der zulässige Bereich ist ein Vieleck
+* Das Optimum liegt stets in einem '''Eckpunkt'''
-== Vorgehensweise ==
+== Vorgehen ==
-Die Ermittlung der optimalen Lösung erfolgt in vier Schritten:
+. Zeichnen aller Nebenbedingungen
+. Bestimmung der Eckpunkte (Schnittpunkte der Geraden)
+. Berechnung der Zielfunktion an jedem Eckpunkt
+. Auswahl des optimalen Wertes
-# '''Bestimmung des zulässigen Bereichs''': Aufstellen der Nebenbedingungen und der Nichtnegativitätsbedingungen.
+== Mathematischer Hintergrund ==
-# '''Identifikation der Eckpunkte''': Die Eckpunkte entstehen durch die Schnittpunkte der begrenzenden Geraden.
+Die Eckpunkte entstehen durch das Lösen von linearen Gleichungssystemen (vgl. [[Lineares Gleichungssystem]]).
-# '''Berechnung der Koordinaten''': Die Koordinaten der Eckpunkte werden durch das Lösen von [[Lineares Gleichungssystem|linearen Gleichungssystemen]] ermittelt (z. B. mit dem [[Gaußsches Eliminationsverfahren]]).
-# '''Prüfung der Zielfunktion''': Alle berechneten Eckpunkte werden in die Zielfunktion eingesetzt. Der Punkt mit dem höchsten Wert (Maximierung) bzw. niedrigsten Wert (Minimierung) ist die optimale Lösung.
 == Beispiel ==
-Betrachtet man das Beispiel der Modellwerk Ruhr GmbH, ergeben sich folgende Begrenzungslinien:
+Zielfunktion:
-* \(L_1: 2x_1 + x_2 = 100\)
+:<math>Z = 4x + 3y \rightarrow \max</math>
-* \(L_2: x_1 + 2x_2 = 80\)
-Der relevante Eckpunkt \(C\) im Inneren entsteht durch den Schnittpunkt von \(L_1\) und \(L_2\):
+Nebenbedingungen:
-\[
+:<math>
-\begin{vmatrix}
+\begin{aligned}
-(I) & 2x_1 + x_2 = 100 \\
+x + y &\le 6\\
-(II) & x_1 + 2x_2 = 80
+x + y &\le 8\\
-\end{vmatrix}
+x,y &\ge 0
-\]
+\end{aligned}
-Lösung mittels [[Gaußsches Eliminationsverfahren]]: \(x_1 = 40, x_2 = 20\).
+</math>
-'''Vergleich der Eckpunkte:'''
+Die Eckpunkte werden berechnet und in die Zielfunktion eingesetzt.
-* \(A(0|0) \Rightarrow z = 0\)
-* \(B(50|0) \Rightarrow z = 2000\)
-* \(C(40|20) \Rightarrow z = 2600\) (Optimum)
-* \(D(0|40) \Rightarrow z = 2000\)
-== Zusammenhang mit anderen Themen ==
+== Wirtschaftlicher Bezug ==
-Die Eckpunktberechnung ist eng verknüpft mit dem Thema [[Matrix|Matrizenrechnung]], da Bedingungssysteme auch in Matrixform geschrieben werden können. Im Vergleich zum [[Simplexalgorithmus]] ist sie anschaulicher, bei vielen Variablen jedoch deutlich aufwendiger.
+Typische Anwendungen:
+* Produktionsplanung
+* Transportproblem
+* Einsatzproblem
+* Zuschnittproblem
+== Vorteil ==
+* Anschaulich
+* Gut geeignet für den Grundkurs
+== Nachteil ==
+* Nur für zwei Variablen praktikabel
 [[Kategorie:Lineare_Optimierung]]
 [[Kategorie:AHR_WuV_Mathe_GK]]