Lineare Optimierung

Geschichte und Hintergrund
Vorwort
Geschichte

Leichte Beispielaufgabe
Aufgabe
Lösungsansatz
Graphische Lösung

Schwere Beispielaufgabe
Aufgabe
Lösungsansatz
Graphische Lösung

     schwere Beispielaufgabe

Das "Sortimentproblem"

Ein Hersteller produziert zwei Sortimente eines Artikels, der aus Teilen besteht, die geschnitten, zusammengebaut und fertiggestellt werden müssen. Der Unternehmer weiß, dass er so viele Artikel verkaufen kann, wie er produziert. Sortiment 1 benötigt 25 Minuten zum Zerschneiden, 60 Minuten zum Zusammenbau und 68 Minuten, um es verkaufsfertig zu machen. Es erzielt 30 DM Gewinn. Für Sortiment 2 braucht man 75 Minuten zum Schneiden, 60 Minuten für den Zusammenbau und 34 Minuten, zur Fertigstellung. Dieses Sortiment erzielt einen Gewinn von 40 DM. Es stehen nicht mehr als 450 Minuten zum, Zerschneiden, 480 Minuten zum Zusammenbau und 476 Minuten zum Fertigstellen pro Tag zur Verfügung. Nun stellt sich dem Unternehmer die Frage, wie viele Artikel von jedem Sortiment jeden Tag produziert werden müssen, um den Gewinn zu maximieren.

Lösungsansatz

 
Als erstes müssen wir wieder die Angaben in Ungleichungen umändern und Variablen verteilen. Es seien x die Anzahl der Artikel aus Sortiment 1 und y die Anzahl der Artikel aus Sortiment zwei. Die Werte für x und y können nicht negativ sein, sondern nur Beträge größer oder gleich null annehmen:                                   x >= 0
                                                      y >= 0
Die Zuschneide-, Zusammenbau- und Fertigstellungszeiten führen zu folgenden Ungleichungen:     25x+75y <= 450
                                                    60x+60y <= 480
                                                    68x+34y <= 476

Graphische Lösung

In einer Grafik repräsentieren diese drei Ungleichungen die Flächen unterhalb den vorgegebenen Linien, während die ersten beiden Ungleichungen genau auf den Achsen liegen, und damit die Fläche abgrenzen:              

Das Problem besteht nun darin, Werte für x und y zu finden, die alle Randbedingungen erfüllen und den Gewinn maximieren. Um dies zu erreichen müssen wir zunächst wieder die Zielfunktion aufstellen:
                                             30*x+40*y = Z
Nun wird diese Funktion in eine Form umgeschrieben, die in ein Koordinatensystem eingetragen werden kann.
                                            y = -3/4x + Z/40
Jetzt gibt man wieder beliebige Werte für Z ein, bis eine der entstehenden Funktionen den möglichen Bereich nur noch in einem Punkt schneidet. Dieser Punkt kennzeichnet das Wertepaar, mit dem eine optimale Anzahl an Sortimenten hergestellt wird (siehe roter Kreis).


                    

Dieses Ergebnis (3 / 5) lässt sich wieder mit der Probe überprüfen:
3*30DM+5*40DM=290DM. Der Unternehmer sollte also drei Artikel aus Sortiment 1 und fünf Artikel aus Sortiment 2 herstellen, um die Arbeitszeit optimal auszunutzen und den Gewinn dabei zu maximieren.