Lineare Optimierung

Lineare OptimierungMathematische Methoden werden in nahezu allen Wissenschaften angewandt. Ein sehr häufig genutzter Algorithmus ist der Simplex-Algorithmus zur Lösung einer Optimierungsaufgabe. Die Aufgabenstellung der linearen Optimierung besteht darin, für eine von mehreren Größen abhängige lineare Funktion unter Beachtung einer Vielzahl von Nebenbedingungen ein Optimum, d.h. ein Maximum oder Minimum, zu suchen.

Begründet wurde dieses Teilgebiet 1939 durch den sowjetischen Mathematiker und Nobelpreisträger Kantorowitsch. Auf ihn geht das Verfahren der Lösungsfaktoren zurück. Das heute hauptsächlich eingesetzte Lösungsverfahren, das Simplex-Verfahren, wurde 1947 von Dantzig gefunden. Die Bedeutung dieses Gebiets liegt vor allem in wirtschaftsmathematischen Anwendungen.

Im Programm wird der Simplex-Algorithmus mit maximal drei Variablen und acht Nebenbedingungen realisiert. Besteht z.B. folgende Aufgabenstellung:

Beispiel: Die Größe a sei von x und y mit a = x + 4y (Zielfunktion) abhängig, wobei für die Variablen x und y vier Nebenbedingungen gelten sollen:

x ≥ 0 y ≥ 0 2x + 3y ≤ 4 3x + y ≤ 3

Gesucht ist die Belegung von x und y für welche die Größe a ein Maximum erreicht!

so geben Sie die Koeffizienten der Zielfunktion in die Felder sowie die vier Nebenbedingungen ein. Dabei ist zu beachten, dass keine Divisionszeichen auftreten dürfen. Außerdem ist für „≥“ nur „>“ bzw. für „≤“ nur „>“ einzugeben. Als Vergleichsoperatoren können „<“, „>“ und das Gleichheitszeichen verwendet werden. Wählen Sie an den Auswahlfeldern zusätzlich Maximum und quittieren mit Berechnung, ermittelt das Programm das Maximum für a, im Beispiel a = 5,33 mit x = 0 und y = 1,33.

Beachten Sie bitte: Durch interne Rundung und rechnerspezifische Darstellung der Zahlen kann es zu folgendem Problem kommen: Eine Nebenbedingung lautet z.B. 2x + y = 24.
Bei Angabe dieser Gleichung findet das Programm keine oder nur die triviale (offensichtlich falsche) Lösung x = 0 und y = 0. Wandeln Sie in diesem Fall die Gleichung in die zwei Bedingungen 2x + y < 24 und 2x + y > 24 um. Nach erneutem RETURN erhalten Sie nun die korrekte Lösung.

OptimierungEnthält die Zielfunktion nur die zwei Variablen x und y (zweidimensionaler Fall) so stellt man sich zur Veranschaulichung der Lösung die vier Nebenbedingungen als lineare Ungleichungen der x-y-Ebene vor. Diese begrenzen ein Gebiet dessen Punkte alle für die Nebenbedingungen gültige Werte darstellen.

Gesucht ist damit der Punkt des zulässigen Bereichs, für den a das Maximum erreicht. Ohne Beweis sei darauf hingewiesen, dass im eindeutigen Lösungsfall das Optimum an einem der Eckpunkte des gebildeten Polygons auftritt.

Haben Sie ein zweidimensionales Problem eingegeben und berechnet, so zeichnet das Programm im Erfolgsfall im rechten Fensterteil die entsprechenden Geraden, färbt den zulässigen Bereich und stellt die Zielfunktion sowie das Optimum dar.
Beachten Sie bitte, dass im dreidimensionalen Fall keine grafische Auswertung erfolgt.

Widersprechen sich die Nebenbedingungen, erhalten Sie die Meldung: Keine Lösung !
Ist das Problem aufgrund von mangelnden Bedingungen nicht auflösbar, erhalten Sie: nicht lösbar.

Zur Theorie des Simplex-Verfahrens lesen Sie bitte in entsprechender Fachliteratur nach.

In diesem Unterprogramm können Sie maximal drei Variablen einsetzen sowie acht Nebenbedingungen. Eine eingegebene Optimierungsaufgabe können Sie in einer Datei ablegen sowie später wieder in das Programm aufnehmen.

Sieben Beispiele können Sie über den Rollbalken Beispiele laden, zum Beispiel die dreidimensionale Optimierungsaufgabe x + 4y + 2z –> Maximum mit den Bedingungen

2x+3y+z<14 x+2y<3
y>1 x>0.5

Als Lösung wird das Tripel (0.5;1.25;9.25) mit der Zielgröße y = 24 gefunden.