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≤c⋯
|
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≥und y>: Markiere den Bereich oberhalb der Linie
- y≤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≤2
- y−2x≤1
- x+y≤2
Nebenbedingungen umformen und einzeichnen:
- y≥0.5x−1
- y≤2x+1
- y≤−x+2
Beliebige Zielfunktion: z=2
Achsenschnittpunkte: 2=y+2⋅0→2=y und 2=0+2x→1=x
Einzeichnen und parallel verschieben zum Maximum:
Maximum im Punkt: x=2 und y=0
Maximum berechnen: z(2,0)=0+2⋅2=4