Lineare Optimierung: Unterschied zwischen den Versionen

Version vom 7. Januar 2014, 15:00 Uhr

Die lineare Optimierung eignet sich besonders für wirtschaftliche Anwendungen, um (unter anderem) die optimale Produktionsmenge und den maximalen Gewinn zu bestimmen.

Einleitung - Was ist lineare Optimierung?

Im Jahre 1948 wurden beim Wiederaufbau der Stadt Moskau Mathematiker damit beauftragt, den Transport von Kies aus 20 Kiesgruben zu 230 Baustellen kostensparend zu optimieren. Mit Hilfe der linearen Optimierung konnte eine Kostensenkung von 10% gegenüber dem ursprünglichen Preis erreicht werden. W. Knödl von der TU Wien errechnete 1960 mit Hilfe der linearen Optimierung einen optimalen Kostenplan für den Transport von Zucker aus fünf österreichischen Zuckerfabriken an alle 300 österreichischen Großhändler. Auch hier konnten die Transportkosten um 10 % gesenkt werden. Heute wird die lineare Optimierung im Transportwesen angewendet, um Transportkosten zu senken, in der Landwirtschaft, um Nutzflächen optimal auszunützen, in der Organisationsplanung, um die günstigsten Stunden- und Schichtpläne zu ermitteln usw. Wir beschränken uns hier auf die Grundidee der linearen Optimierung und beschränken uns auf 2 Variablen.

Methode (zusammengefasst)

1. Zuerst lese den Text ganz genau durch und überlege dir, was gefragt ist. Was soll x sein, was soll y sein?
2. Dann werden aus der Angabe alle Nebenbedingungen in Form von Ungleichungen herausgelesen. Dazu gehören in der Regel auch immer die Nichtnegativitätsbedingungen
3. Das Planungsfeld wird erstellt, indem die Lösungsmengen der Ungleichungen gezeichnet werden
4. Die Zielfunktion wird aufgestellt: Z gibt an, was maximiert/minimiert werden soll.
5. Der Graph der Zielfunktion wird in das Planungsfeld gezeichnet (mit Z=0) und anschließend bis zum optimalen Punkt parallel hinauf (für das Maximum) oder hinunter (für das Minimum) verschoben.
6. Die Koordinaten des optimalen Punktes werden bestimmt, indem man

   a) die Koordinaten abliest

   b) den Schnittpunkt der beiden Geraden, die sich in diesem Punkt schneiden, berechnet.

Video

Musterbeispiel

Angabe

Lösung

a) Übersetze die Nebenbedingungen aus dem Texte in Ungleichungen.
Sei x die Anzahl der Hosen, y die Anzahl der Röcke.

$$ I:x\leq 70$$ $$II: y\leq 100 $$

$$ III: x+y\leq 140 \rightarrow y\leq -x+140 $$ Nichtnegativitätsbedingungen: $$ IV: x\geq 0 \textrm{ und }V: y\geq 0$$

b) Stelle die Zielfunktion auf, wobei maximaler Gewinn angestrebt werden soll.

Gewinn für eine Hose: $45-20=25$ €.
Gewinn für einen Rock: $35-15=20$ €.
Somit lautet die Zielfunktion, die den Gewinn angibt:

$$\begin{align} Z=25x+20y &\rightarrow -25x+Z=20y \\ &\rightarrow y=-\frac{25}{20}x+\frac{Z}{20} \end{align}$$

c) Löse das System und interpretiere die Lösung.

1. Schritt: Zuerst zeichnen wir das Planungsfeld:

$\begin{align} I:&x\leq 70&\\ II:&y\leq 100&\\ III: &x+y\leq 140& \rightarrow y\leq -x+140 \\ IV:& x\geq 0&\\ V: &y\leq 0& \end{align}$

2. Schritt: Dann zeichnen wir die Zielfunktion ein und verschieben sie parallel ganz nach oben, bis sie das Planungsfeld nur noch in einem Punkt berührt.

$$y=-\frac{25}{20}x+\frac{Z}{20}\rightarrow k=\frac{25}{20} \textrm{und d kann frei gewählt werden.}$$

Der optimale Punkt ist der Schnittpunkt von $I: x=70$ und $II: y=-x+140$. (Hinweis: Natürlich können die Koordinaten des optimalen Punktes auch abgelesen werden, wir wollen sie hier aber berechnen).


3. Schritt Nun berechnen wir den optimal Punkt, indem wir die Geraden $I: x=70$ und $III: y=-x+140$ schneiden:

$$I: x=70$$ $$III: y=-x+140$$ Einsetzungsverfahren: I in III einsetzen. $$ y=-70+140 \rightarrow y=70$$ Somit lauten die Koordinaten des optimalen Punktes: $P(70|70)$


4. Schritt: Zuletzt berechnen wir noch den maximalen Gewinn, indem wir den optimalen Punkt $(70|70)$ in die Zielfunktion $Z=25x+20y$ einsetzen: $$Z=25\cdot 70+20\cdot 70=3150$$

5. Schritt: Antwortsatz Der maximale Gewinn von 3150 € wird bei einer Produktion von 70 Hosen und 70 Röcken erzielt.

Beispiele

1. Übungsaufgaben samt Lösungen
2. Weinhandel(mit Lösung, Quelle: bifie.at)