Lineare Optimierung

Geschichte und Hintergrund
Vorwort
Geschichte

Leichte Beispielaufgabe
Aufgabe
Lösungsansatz
Graphische Lösung

Schwere Beispielaufgabe
Aufgabe
Lösungsansatz
Graphische Lösung

Leichte Beispielaufgaben

"Zeltekauf"

Eine Jugendgruppe beschließt, Zelte einzukaufen. In einem Sonderangebot werden zwei verschiedene Sorten von Zelten für jeweils 10 und 15 Personen preiswert angeboten. Von den 10-Personenzelten sind noch 5 und von den 15-Personenzelten nur noch 4 vorrätig. Die Zelte für 10 Personen kosten 200 DM je Stück und diejenigen für 15 Personen insgesamt 400 DM je Stück. Die Jugendgruppe kann insgesamt höchstens 1800 DM für die Zelte ausgeben. Wie viele 10- und 15-Personenzelte kann die Jugendgruppe kaufen, damit eine möglichst große Anzahl von Jugendlichen in den Zelten untergebracht werden kann?

Lösungsansatz

Diese Aufgabenstellung ist in zwei Teile unterteilt: Zunächst erfahren wir Bedingungen, die die Lösung beeinflussen, danach wird das Ziel bestimmt. Um die Lösung übersichtlicher zu gestalten ordnen wir zunächst den beiden Zelten variabeln zu, nämlich
                                                          x = 10-Personenzelte
                                                          y = 15-Personenzelte
Der nächste Schritt besteht in dem Umformen der Bedingungen in mathematische Formeln. Dadurch erhalten wir folgende Ungleichungen:
                                                          x >= 0
                                                         y >= 0
                               (da von beiden Zelten ja eine Anzahlgrößer null oder                                                   auch gar keines gekauft wird)
                                                         x <= 5
                                                         y <= 4
                              (da höchstens 5 bzw. 4 Zelte gekauft werden können)
Außerdem wissen wir, dass der Jugendgruppe nur 1800 DM zur Verfügung stehen und dass die Zelte 200 DM bzw. 400DM kosten. Daraus ergibt sich folgende Ungleichung:
                                      200*x+400*y<=1800
Diese Bedingung formen wir zur besseren Handhabung in
                                                    x+2y<=9 um.
Um diese Vorraussetzungen in ein Koordinatensystem einzufügen, werden sie zunächst in Gleichungen umgewandelt:
                                                             x=0
                                                             y=0
                                                             x=5   
                                                             y=4
                                                       x+2y=9

Graphische Lösung

In einem Koordinatensystem sieht das dann folgendermaßen aus:

Dadurch erhalten wir die hier gelb gefärbte, denn nur die Punkte dieses Bereiches erfüllen die Bedingungen.
Von diesen zulässigen Lösungen muss nun das Wertepaar (x/y) bestimmt werden, mit dem die Jugendgruppe die meisten Personen unterbringen kann.
Dafür stellen wir zunächst die sog. Zielfunktion auf:
                                                           10*x+15*y=Z
                                   (wobei Z die Menge der Personen ist)
Durch Umstellen dieser Zielfunktion mit drei Variablen erhalten wir die Formel        y= -2/3x + Z/15, die wir in das Koordinatensystem einfügen.
Jetzt geben wir beliebige Werte für Z ein, bis eine Funktion nur noch einen Punkt mit der Menge der zulässigen Lösungen gemeinsam hat. Dieser Punkt kennzeichnet das Wertepaar, mit dem die meisten Personen untergebracht werden können (siehe roter Kreis).

                        

Das hier abzulesende Ergebnis (5 Zehnpersonenzelte und                           2 Fünfzehnpersonenzelte) lässt sich auch rechnerisch überprüfen, indem man die Probe macht:                 5*200 DM+2*400 DM=1800 DM