[zurück]

Lineare Optimierung (Christian Schmaltz)

[vor]

Eigentlich hat das Thema mit Quasikristallen nichts zu tun. Aber wir müssen innerhalb dieses Kurses in hochdimensionale Räume vordringen. Der Ausflug dorthin ist sehr mühsam, da (wie sich jeder vorstellen kann) das räumliche Vorstellungsvermögen nicht mehr mitspielt. Um uns diesen Ausflug etwas schmackhafter zu machen, bringe ich eine Anwendung mit praktischer Relevanz: lineare Optimierung und insbesondere das Simplex-Verfahren.

Es geht um das Problem, begrenzte Ressourcen optimal (das heißt mit maximalem Gewinn) auszunutzen. Wie sollen Tabak oder Kaffeemischungen aus begrenzten verfügbaren Rohstoffen unterschiedlicher Qualität zusammengesetzt werden? Soll ein Bauer seine begrenzten Kapazitäten eher in Weizen oder Roggen investieren? Zur Erläuterung werden wir nun ein einfaches, fiktives Beispiel betrachten:

Ein Bauer kann Weizen und Roggen anbauen. Für ein Kilogramm Weizen werden drei Quadratmeter Ackerland benötigt, während Roggen mit zwei Quadratmeter Platz pro Kilogramm auskommt. Allerdings muss man für ein Kilogramm Weizen nur eine Stunde arbeiten, während zur Herstellung eines Kilogramms Roggen zwei Stunden Arbeit nötig sind. Ein Kilogramm Weizen bringt einen Gewinn von drei Cent, ein Kilogramm Roggen einen Gewinn von vier Cent. Wenn man nun 50m² Ackerland besitzt und die Arbeitskräfte maximal 25 Stunden arbeiten, wieviel Weizen und Roggen soll man dann anbauen, um den maximalen Gewinn zu erzielen?

Um ein solches Problem zu lösen, muss man zunächst die gegebenen Daten in (Un-)Gleichungen fassen. Sei x die Menge an Weizen, y die Menge an Roggen (jeweils in Kilogramm). Für die Frage des Ackerlandes ergibt sich nun folgende Ungleichung (die Einheiten wurden weggelassen):

Die Gleichung y = 25 - 1,5x wird nun in ein Koordinatensystem eingetragen (Abb. 1):

Alle Punkte, die exakt auf der Gerade liegen, beanspruchen nun sämtliches zur Verfügung stehende Ackerland. Punkte unterhalb der Gerade (schraffierter Bereich) verwenden weniger Land, als zur Verfügung steht. Punkte aus diesen beiden Bereichen heißen zulässige Punkte. Die restlichen Punkte entsprechen mehr Ackerland, als zur Verfügung steht, und sind deshalb nicht zulässig. Natürlich wird nur der erste Quadrant des Koordinatensystems verwendet, da kein negativer Weizen oder Roggen angebaut werden kann. (Man kann auch sagen: Die Bedingungen x ³ 0 und y ³ 0 gehören zum System.)

Nun werden nacheinander alle Geraden für die restlichen Bedingungen eingetragen. In unserem Fall also die Gerade x + 2y = 25     Û     y = 12,5 - 0,5x:

Die Gesamtheit aller Punkte, die jede dieser Bedingungen erfüllen, heißt zulässige Menge (schraffierter Bereich in Abb. 2).

Nun stellt sich die Frage, wie eine zulässige Menge im Prinzip aussehen kann. Es gibt weder Löcher (Abb. 3) noch einspringende Ecken (Abb. 4), weil die Geraden, die für das Loch bzw. die einspringende Ecke verantwortlich sind, weitere Bereiche herausgeschnitten hätten. Es ergibt sich also ein konvexes Polygon.

Die exakte Form der zulässigen Menge einschließlich der Koordinaten der Schnittpunkte der Geraden kann aus den in der Aufgabenstellung gegebenen Informationen berechnet werden. Ein typisches Beispiel zeigt Abbildung 5.

Als nächstes stellt man den Gewinn als Funktion dar (Gewinn = 3x + 4y) und zeichnet einen Repräsentanten der Funktion in sein Koordinatensystem ein, zum Beispiel: 120 = 3x + 4y     Û     y = 30 - 0,75x (vgl. Gerade a in Abb. 6) Die entstandene Gerade nennt man eine Isoprofitable, d. h. eine Gerade konstanten Gewinns.

Sieht man sich den Graph der Gewinn-Funktion a an, bemerkt man, dass kein Punkt der Geraden in der zulässigen Menge liegt. Für eine tiefere Gerade (z. B.: 30 = 3x + 4y     Û     y = 7,5 - 0,75x; vgl. Gerade b in Abb. 6) liegen zwar Punkte in der zulässigen Menge, jedoch ist es möglich (oder sogar offensichtlich), dass 30 nicht der maximale Gewinn dieser Aufgabe ist. Die Frage ist also, welches der höchste Gewinn ist, der in der zulässigen Menge liegt, d. h. dessen Isoprofitable das Polygon trifft.

Bei der Lösung dieser Frage hilft uns das Eckenprinzip: Der Wert des höchsten Gewinns wird auf einer polygonalen zulässigen Menge stets (auch) in einer Ecke angenommen. Daraus folgt, dass der größte Gewinn der Geraden entspricht, die die zulässige Menge gerade noch in einem Punkt (Gerade c in Abb. 6) oder einem Geradenstück (siehe Abb. 7) trifft.

Rechnerisch kann man solche Probleme nach dem Eckenprinzip auf folgende Art lösen: Man berechnet die Eckpunkte der zulässigen Menge, die Gewinne, die zu diesen Ecken gehören, und wählt die Ecke mit dem größten Gewinn.

Statt des Gewinns kann man auch irgendeine andere Größe optimieren. Man spricht allgemeiner von Zielfunktion (objective function).

Bei komplexeren Aufgaben ergeben sich allerdings zwei Probleme: Erstens gibt es bei manchen Aufgaben eine gewaltige Zahl von Ecken, so dass sehr viele Berechnungen durchgeführt werden müssen, und zweitens ist es nicht möglich, die Aufgabe in einer Ebene zu lösen, wenn es sich um mehr als zwei Produkte handelt, da man für jedes Produkt eine Unbekannte und damit eine Raumdimension benötigt. In bestimmten Fällen kann die Anzahl der Ecken sogar die Anzahl der Sandkörner auf der Erde übersteigen. Die Rechenzeit steigt ins Astronomische...

Statt eines Polygons ergibt sich im n-dimensionalen Raum ein Polytop (d. h. ein Ding mit Punkten am Rande des Dings , die durch Kanten verbunden werden...), das wieder von (n-1)-dimensionalen Hyperebenen begrenzt wird. Durch ähnliche überlegungen wie oben erkennt man, dass das Polytop konvex ist, d. h. die Verbindungsstrecke zweier beliebiger Punkte liegt vollständig innerhalb des Polytops.

Um diese Schwierigkeiten zu überwinden, hat der amerikanische Mathematiker George Dantzig kurz nach dem 2. Weltkrieg den Simplexalgorithmus entwickelt. Er ermöglicht es, viele Probleme in Sekunden zu lösen, dessen Lösung sonst mehrere hundert Jahre gedauert hätte. Der Name kommt daher, dass das einfachste Polytop in n Dimensionen Simplex heißt. (Ein 2-dimensionaler Simplex ist ein Dreieck, ein 3-dimensionaler ein Tetraeder usw.)

Der Simplexalgorithmus funktioniert so: Man nimmt einen beliebigen Startpunkt und berechnet die Gewinnfunktion für alle angrenzenden Ecken. Dann nimmt man unter diesen Punkten den mit dem höchsten Gewinn als neuen Startpunkt und wiederholt diese Prozedur, bis man keinen Punkt mehr findet, der einen höheren Gewinn als der letzte Punkt hat. Da das Polytop konvex ist, handelt es sich um den Punkt mit dem maximalen Gewinn oder, falls es mehrere Punkte maximalen Gewinns gibt, um einen dieser Punkte.

Dieser Algorithmus ist in der Praxis schneller, als man theoretisch vermuten würde. Er erspart den Weg durch alle Ecken; falls aber zwischen der Start- und der Zielecke viele kurze Kanten liegen, kommt der Simplexalgorithmus nur sehr schleppend voran.

Wieso ist dieses Polytop eigentlich konvex?

Aus denselben Gründen wie das Polygon in der Weizen-Roggen-Ebene. Aber man muss das nachrechnen, um sich zu vergewissern. Nicht immer sind Ideen aus der Ebene ohne weiteres in hochdimensionale Räume übertragbar. Wir haben, sagen wir, n Variable und m Bedingungen. Die sind sämtlich von der Form

oder auch

(Skalarprodukt!). Dabei ist x = (x₁, x₂, ..., x_n) der Vektor der Unbekannten und a_i = (a_i1, a_i2, ..., a_in) der Vektor der Koeffizienten für die i-te Bedingung. Geometrisch ist a_i der Normalenvektor für die Hyperebene (d. h. den (n-1)-dimensionalen Unterraum), die in dem n-dimensionalen Raum der xe die (bezüglich der i-ten Bedingung) zulässigen von den unzulässigen Punkten trennt. Insgesamt zulässig sind die Punkte, für die alle m Ungleichungen erfüllt sind.

Ist die Menge dieser Punkte konvex? Eine Menge heißt konvex (Achtung, Kopfstand!), wenn sie mit zwei Punkten x und y stets auch deren Verbindungsstrecke (das heißt die Menge der Punkte tx + (1 - t)y für 0 £ t £ 1) enthält. Also: Wenn zwei Punkte x und y alle Ungleichungen erfüllen, gilt das auch für die Punkte der Verbindungsstrecke? Nachrechnen! Rechenregeln fürs Skalarprodukt anwenden.

denn x erfüllt ja die Bedingung a_i · x £ b_i, ebenso y. Man darf die Ungleichung so einsetzen, weil t und 1 - t beide ³ 0 sind.

[zurück]

[Inhaltsverzeichnis]

[vor]