Lineare Optimierung

Die lineare Optimierung beschäftigt sich mit dem Lösen von Extremwertproblemen einer linearen Zielfunktion unter bestimmten Nebenbedingungen . Die Nebenbedingungen sind dabei lineare Ungleichungen – zum Beispiel begrenzter Lagerplatz, begrenztes Kapital oder begrenzte Arbeitszeit. Häufig findet sie in der Wirtschaft Anwendung, z. B. bei der Gewinnmaximierung oder der Kostenminimierung : Wie viele Stück von Produkt A und B soll eine Firma herstellen, damit der Gewinn am größten ist? Die gefärbte Fläche enthält alle Mengenkombinationen, die alle Nebenbedingungen gleichzeitig erfüllen. Bausteine eines linearen Optimierungsproblems - Entscheidungsvariablen: z. B. x und y = produzierte Stückzahlen - Lineare Zielfunktion: die Größe, die maximal oder minimal werden soll, z. B. G = a cdot x + b cdot y - Nebenbedingungen als lineare Ungleichungen, z. B. 3x + 2y leq 280 - Nichtnegativitätsbedingungen: x geq 0 , y geq 0 (man kann nichts Negatives produzieren) Der zulässige Bereich ist die Menge aller Punkte, die alle Ungleichungen erfüllen. Er ist ein Vieleck (Polygon). Hauptsatz: Das Optimum einer linearen Zielfunktion liegt immer in einer Ecke des zulässigen Bereichs. Lösungswege - Grafisch (bei zwei Variablen): Bereich zeichnen, Zielfunktion parallel verschieben. - Eckenmethode: Alle Ecken berechnen und die Zielfunktion dort vergleichen. - Simplex-Verfahren: rechnerisches Verfahren für viele Variablen. Beispiel 1: Text in Ungleichungen übersetzen Ein Bäcker backt Brote ( x ) und Kuch

Worum geht's?

Die lineare Optimierung beschäftigt sich mit dem Lösen von Extremwertproblemen einer linearen Zielfunktion unter bestimmten Nebenbedingungen . Die Nebenbedingungen sind dabei lineare Ungleichungen – zum Beispiel begrenzter Lagerplatz, begrenztes Kapital oder begrenzte Arbeitszeit. Häufig findet sie in der Wirtschaft Anwendung, z. B. bei der Gewinnmaximierung oder der Kostenminimierung : Wie viele Stück von Produkt A und B soll eine Firma herstellen, damit der Gewinn am größten ist?
Zulässiger Bereich für die Produktion
f(x) = −1,5x + 140g(x) = −0,5x + 65
20406080100102030405060708090xyfgE(75|27,5)
Die gefärbte Fläche enthält alle Mengenkombinationen, die alle Nebenbedingungen gleichzeitig erfüllen.

Formel mit Erklärung

Bausteine eines linearen Optimierungsproblems Entscheidungsvariablen: z. B. x x x und y y y = produzierte Stückzahlen Lineare Zielfunktion: die Größe, die maximal oder minimal werden soll, z. B. G = a ⋅ x + b ⋅ y G = a \cdot x + b \cdot y G = a ⋅ x + b ⋅ y Nebenbedingungen als lineare Ungleichungen, z. B. 3 x + 2 y ≤ 280 3x + 2y \leq 280 3 x + 2 y ≤ 280 Nichtnegativitätsbedingungen: x ≥ 0 x \geq 0 x ≥ 0 , y ≥ 0 y \geq 0 y ≥ 0 (man kann nichts Negatives produzieren) Der zulässige Bereich ist die Menge aller Punkte, die alle Ungleichungen erfüllen. Er ist ein Vieleck (Polygon). Hauptsatz: Das Optimum einer linearen Zielfunktion liegt immer in einer Ecke des zulässigen Bereichs. Lösungswege Grafisch (bei zwei Variablen): Bereich zeichnen, Zielfunktion parallel verschieben. Eckenmethode: Alle Ecken berechnen und die Zielfunktion dort vergleichen. Simplex-Verfahren: rechnerisches Verfahren für viele Variablen.

Beispiele

Leicht#1
Beispiel 1: Text in Ungleichungen übersetzen Ein Bäcker backt Brote ( x x x ) und Kuchen ( y y y ). Im Ofen ist Platz für höchstens 40 40 40 Stück. Für ein Brot braucht er 1   kg 1\,\text{kg} 1 kg Mehl, für einen Kuchen 0,5   kg 0{,}5\,\text{kg} 0 , 5 kg ; er hat 30   kg 30\,\text{kg} 30 kg Mehl. Ofen: x + y ≤ 40 x + y \leq 40 x + y ≤ 40 Mehl: x + 0,5 y ≤ 30 x + 0{,}5y \leq 30 x + 0 , 5 y ≤ 30 Nichtnegativität: x ≥ 0 x \geq 0 x ≥ 0 , y ≥ 0 y \geq 0 y ≥ 0

Zusammenfassung

Lineare Optimierung : eine lineare Zielfunktion unter linearen Nebenbedingungen (Ungleichungen) maximieren oder minimieren. Typische Anwendung: Gewinnmaximierung und Kostenminimierung in der Wirtschaft. Alle Nebenbedingungen zusammen ergeben den zulässigen Bereich – ein Vieleck. Das Optimum liegt immer in einer Ecke dieses Bereichs. Lösungswege: grafisch, Eckenmethode oder Simplex-Verfahren; bei Stückzahlen auf ganzzahlige Lösungen achten.

Jetzt üben

Kostenlose Aufgaben mit Lösungsweg zu diesem Begriff: