Lineare Optimierung berechnen

Definition

Bei der linearen Optimierung soll der Wert einer linearen Funktion (Zielfunktion) maximiert oder minimiert werden. Dabei ist der Definitions- und der Wertebereich durch gegebene

Nebenbedingungen einschränkt.

Begriffe

ZIELFUNKTION

Funktion mit zwei Variablen, deren Wert maximiert werden soll.

$z(x,y)=dx+ey$

NEBENBEDINGUNGEN

Ungleichungen, die den Definitions- und den Wertebereich einschränken.

$ax+by\le c\\\cdots$

Lösung eines linearen Optimierungsproblems

Zum Lösen benötigt man ein Koordinatensystem.

VORGEHEN

1.	Bei allen Ungleichungen $y$ alleine stellen. Beachte: Multipliziert oder dividiert man mit einer negativen Zahl, so muss man das Ungleichzeichen umdrehen.
2.	Ungleichungen jeweils als lineare Funktion im Koordinatensystem einzeichnen:
3.	Einzelne Lösungsbereiche markieren. Für Gleichungen mit: $y\geq und\ y>:$ Markiere den Bereich oberhalb der Linie $y\le und\ y<:$ Markiere den Bereich unterhalb der Linie
4.	Markiere den Bereich deutlich, wo sich alle einzelnen Lösungsbereiche überdecken.
5.	Wähle einen beliebigen Wert und ersetze in der Zielfunktion: Dies definiert eine lineare Funktion Bestimme die Achsenschnittpunkte dieser Funktion: Setze $x=0$ und berechne y  y-Achsenschnittpunkt Setze $y=0$ und berechne x  x-Achsenschnittpunkt Zeichne die beliebige Zielfunktion anhand der Achsenschnittpunkte ein.
6.	Bestimme den optimalen Punkt: Verschiebe die Zielfunktion solange parallel, bis sie den höchsten (beim Maximum) bzw. den tiefsten (beim Minimum) Eckpunkt des Lösungsbereichs erreicht.
7.	Setze die Koordinaten dieses Eckpunkts in die allgemein Zielfunktion ein und berechne den optimalen Wert der Zielfunktion.

Beispiel

Zielfunktion: $z(x,y)=y+2x$

Nebenbedingungen:

$x-2y\le2$
$y-2x\le1$
$x+y\le2$

Nebenbedingungen umformen und einzeichnen:

$y\geq0.5x-1$
$y\le2x+1$
$y\le-x+2$

Mathematik; Lineare Optimierung; BMS; Lineare Optimierung berechnen

Beliebige Zielfunktion: $z=2$

Achsenschnittpunkte: $2=y+2\cdot0\rightarrow\underline{2=y}$ und $2=0+2x\rightarrow\underline{1=x}$

Einzeichnen und parallel verschieben zum Maximum:

Mathematik; Lineare Optimierung; BMS; Lineare Optimierung berechnen

Maximum im Punkt: $\underline{x=2}$ und $\ \underline{y=0}$

Maximum berechnen: $z\left(2,0\right)=0+2\cdot2=\underline{4}$