- Was lineare Optimierung ist
- Visuelle Karte zur linearen Optimierung
- Elemente des Modells
- Beispiel: Produktmix aus zwei Produkten
- Grafisches Verfahren: die Eckpunkte prüfen
- Wie das Simplex-Verfahren zum selben Ergebnis kommt
- Schattenpreise: was eine zusätzliche Stunde wert ist
- Anwendungen
- Häufige Fehler
- Häufige Fragen
Was lineare Optimierung ist
Lineare Optimierung (lineare Programmierung) ist ein Optimierungsverfahren, das den besten Wert, Maximum oder Minimum, einer Zielfunktion unter einer Reihe linearer Nebenbedingungen findet. In der Fertigung beantwortet sie Fragen wie: Wie viel von jedem Produkt sollten wir herstellen, um mit den vorhandenen Maschinen- und Personalstunden den höchsten Deckungsbeitrag zu erzielen?
Das Simplex-Verfahren, 1947 von George Dantzig entwickelt, ist der Algorithmus, der solche Probleme löst, indem er sich entlang der Eckpunkte des zulässigen Bereichs bewegt, bis er das Optimum erreicht.
Visuelle Karte zur linearen Optimierung
Die Karte zeigt die Modellelemente, den zulässigen Bereich mit seinen vier Eckpunkten, die optimale Lösung und die Schritte des Simplex-Verfahrens.
Elemente des Modells
| Element | Bedeutung | Im Beispiel |
|---|---|---|
| Entscheidungsvariablen | Was bestimmt werden soll | x = Stück von Produkt A; y = Stück von Produkt B |
| Zielfunktion | Was maximiert oder minimiert werden soll | Z = 40x + 30y (gesamter Deckungsbeitrag) |
| Nebenbedingungen | Grenzen der Ressourcen | 2x + y ≤ 100 und x + 2y ≤ 80 |
| Nichtnegativität | Keine negative Produktion | x ≥ 0 und y ≥ 0 |
| Zulässiger Bereich | Punkte, die alle Nebenbedingungen erfüllen | Polygon mit den Ecken (0,0), (50,0), (40,20) und (0,40) |
Beispiel: Produktmix aus zwei Produkten
Jedes Stück A bringt einen Deckungsbeitrag von 40, jedes Stück B einen von 30. Die erste Nebenbedingung kann für Maschinenstunden stehen (A benötigt 2 Stunden, B benötigt 1, verfügbar sind 100); die zweite für Montagestunden (A benötigt 1, B benötigt 2, verfügbar sind 80).
Maximiere Z = 40x + 30y | 2x + y ≤ 100 | x + 2y ≤ 80 | x, y ≥ 0
Grafisches Verfahren: die Eckpunkte prüfen
Bei zwei Variablen lassen sich die Nebenbedingungen zeichnen und der zulässige Bereich sichtbar machen. Das Optimum liegt immer in einem Eckpunkt:
| Ecke (x, y) | Z = 40x + 30y | Hinweis |
|---|---|---|
| (0, 0) | 0 | Ursprung |
| (50, 0) | 2.000 | Nur Produkt A |
| (0, 40) | 1.200 | Nur Produkt B |
| (40, 20) | 2.200 | Schnittpunkt beider Nebenbedingungen: Optimum |
Die optimale Lösung ist, 40 Stück A und 20 Stück B herzustellen, mit Z = 2.200. In diesem Punkt sind beide Nebenbedingungen bindend: 2 × 40 + 20 = 100 und 40 + 2 × 20 = 80.
Wie das Simplex-Verfahren zum selben Ergebnis kommt
- Das Problem formulieren: Zielfunktion und Nebenbedingungen.
- In die Standardform überführen: Schlupfvariablen hinzufügen (2x + y + s1 = 100; x + 2y + s2 = 80).
- Das Anfangstableau aufstellen, beginnend im Ursprung.
- Iterieren: Die Variable, die Z am stärksten verbessert, tritt in die Basis ein, und die, die zuerst ihre Grenze erreicht, verlässt sie.
- Optimalität prüfen: Kann keine Variable Z mehr verbessern, ist die Lösung optimal.
- Interpretieren: x = 40, y = 20, kein Schlupf und Z = 2.200.
Für reale Probleme erstellt niemand Tableaus von Hand: Der Excel-Solver mit dem Simplex-LP-Lösungsverfahren bewältigt Hunderte von Variablen in Sekunden.
Schattenpreise: was eine zusätzliche Stunde wert ist
Die Sensitivitätsanalyse zeigt, wie stark sich Z verbessert, wenn eine Nebenbedingung gelockert wird. Im Beispiel erhöht eine zusätzliche Maschinenstunde Z um etwa 16,67, eine zusätzliche Montagestunde um etwa 6,67. Diese Schattenpreise zeigen, wo sich eine Investition lohnt: Zusätzliche Maschinenkapazität zahlt sich stärker aus als zusätzliche Montagekapazität, solange die Zusatzstunde weniger kostet als der Gewinn.
Dieselbe Logik findet sich in der Theory of Constraints: Die Ressource mit dem höchsten Schattenpreis ist der wirtschaftliche Engpass.
Anwendungen
- Produktionsplanung: optimaler Produktmix wie im Beispiel, zur Unterstützung von Produktionsplanung und -steuerung (PPS).
- Verschnittoptimierung: geringster Abfall beim Zuschnitt von Blechen, Coils und Stangen.
- Logistik: kostengünstigster Transport und Ladungszuteilung.
- Mischungsprobleme: Futtermittel, Legierungen und Kraftstoffe zu minimalen Kosten unter Einhaltung der Spezifikationen.
- Personaleinsatzplanung und Ressourcenzuteilung.
Häufige Fehler
- Eine schlecht modellierte Zielfunktion, die Umsatz und Deckungsbeitrag vermischt.
- Fehlende Nebenbedingungen, die Lösungen erzeugen, die die Fertigung nicht umsetzen kann.
- Vertauschte Ungleichheitszeichen (≤ statt ≥).
- Zu übersehen, dass Variablen bei Teilen ganzzahlig sein müssen; dann ist die ganzzahlige Optimierung zu verwenden.
- Das Ergebnis anzuwenden, ohne zu prüfen, ob es für die Menschen vor Ort Sinn ergibt.
Häufige Fragen
Was ist lineare Optimierung?
Ein Optimierungsverfahren, das eine lineare Funktion unter linearen Nebenbedingungen, etwa begrenzten Ressourcen, maximiert oder minimiert.
Was ist das Simplex-Verfahren?
Der von George Dantzig entwickelte Algorithmus, der sich entlang der Eckpunkte des zulässigen Bereichs bewegt, bis er die optimale Lösung findet.
Wie lautet die Lösung des Beispiels?
40 Stück A und 20 Stück B herstellen, mit Z = 2.200, in der Ecke, in der sich beide Nebenbedingungen schneiden.
Wie löst man lineare Optimierung in Excel?
Mit dem Add-in Solver: Zielzelle, veränderbare Zellen und Nebenbedingungen festlegen und dann das Lösungsverfahren Simplex-LP wählen.
Was ist ein Schattenpreis?
Der Betrag, um den sich die Zielfunktion mit einer zusätzlichen Einheit einer knappen Ressource verbessert.
Quellen
- DANTZIG, G. B. Linear Programming and Extensions. Princeton: Princeton University Press, 1963.
- HILLIER, F. S.; LIEBERMAN, G. J. Introduction to Operations Research. New York: McGraw-Hill.
- TAHA, H. A. Operations Research: An Introduction. Hoboken: Pearson.
Zum Weiterlernen: verlässliche Quellen und Links
- INFORMS: What is Operations Research? (auf Englisch)
- INFORMS: Institute for Operations Research and the Management Sciences (auf Englisch)
- Wikipedia: Lineare Optimierung
- Wikipedia: Operations Research
Merken Sie sich diese Adresse: Manufatura Enxuta ist Ihre Schule für Lean Manufacturing. Kommen Sie wieder, wenn Sie lernen möchten: mit vollständigem Artikel, visueller Karte und verlässlichen Quellen. Folgen Sie einem der Lernpfade oder schlagen Sie im Glossar A–Z nach.
Sie möchten mit Zahlen entscheiden?
Laden Sie das kostenlose E-Book zu Kennzahlen für die Produktionssteuerung herunter.
E-Book herunterladen
Über den Autor
Spezialist für Lean Manufacturing und Verhaltensmanagement
Über 20 Jahre in der Automobil- und Metallindustrie (GM und Dana), Praktiker für Lean Manufacturing seit 2006. SENAI-Dozent und Mentor im brasilianischen Programm Brasil Mais Produtivo, mit Beratung, Schulung und Audits für über 50 Unternehmen. Er verbindet Qualität, Produktivität und Personalentwicklung.
