| Ihre Fragen und Anregungen: |
|---|
|
|
|
|
|
|
 |
|
|
|
|
Was wird gezeigt?
|
|
Die lineare Optimierung ist eines der elementarsten
mathematischen Instrumente zum Lösen von Minimierungs-
bzw. Maximierungsaufgaben.
|
|
|
Die Einsatzgebiete sind oft die Optimierung von Produktionsprozessen
oder als Unterstützung für kaufmännische und logistische Aufgaben.
|
|
|
|
|
|
Zur Veranschaulichung wird hier ein möglichst einfach gehaltenenes
Problem gelöst, daß auch noch von einem Menschen leicht
nachvollzogen werden kann.
|
|
|
Zu Demonstrationszwecken können Sie von unserem Server das Beispiel
mit frei wählbaren Werten
online berechnen
lassen.
|
|
|
|
Eine konkrete Anwendung
|
|
Eine Elektronik-Unternehmen kann am Tag maximal 100 Server und
200 19-Zoll-Racks herstellen. Die Endkontrolle kann am Tag maximal
130 Server und Racks testen und zum Versand freigeben.
|
|
|
Für einen Server erzielt das Unternehmen einen Gewinn von
150 EUR, für ein Rack lediglich 100 EUR.
|
|
|
Ziel ist es die optimale Anzahl an Geräten herzustellen und dabei
den Gewinn zu maximieren.
|
|
|
|
Graphische Darstellung
|
|
Das genannte Beispiel kann man anschaulich als 2-dimensionales
Polygon darstellen.
|
|
|
 |
|
|
Die Variablen werden dann entsprechend wie folgt bestimmt:
|
|
|
|
Gegeben:- LA ~ Maximalzahl Server Produktion= 100
- LB ~ Maximalzahl Racks Produktion= 200
- LC ~ Maximalzahl Server+Racks Endkontrolle = 130
- P1 ~ Preis/Gewinn je Server = 150
- P2 ~ Preis/Gewinn je Rack = 100
|
|
|
Gesucht:- Z(x1,x2) = x1*P1 + x2*P2 (maximal)
- x1 ~ Anzahl der herzustellenden Server
- x2 ~ Anzahl der herzustellenden Racks
|
|
|
Es wird letztlich das Zahlenpaar (x1,x2) gesucht für das die
sogenannte Zielfunktion Z(x1,x2)=x1*P1+x2*P2 maximal wird. also
welche Anzahl x1 von Servern zum Preis P1 und welche Anzahl
x2 von Racks zum Preis P2 muß hergestellt werden, damit der
Gewinn maximal wird.
|
|
|
Mit anderen Worten: Welche Anzahl x1 von Servern zum Preis P1
und welche Anzahl x2 von Racks zum Preis P2 muß hergestellt
werden, damit der Gewinn maximal wird?
|
|
|
|
Brute-Force
|
|
Der naive Ansatz einfach für sämtliche Paarungen von x1 und x2
die Zielfunktion zu berechnen wird hier ignoriert. Zudem würde
dieser 'Algorithmus' für große Werte von LA, LB und LC bereits
an seine Grenzen stoßen.
|
|
|
Für das Beispiel müßten bereits für
100*200 = 20000 Berechnungen der Zielfunktion durchgeführt
und diese gegen die Randbedingungen getestet werden.
|
|
|
Falls man jetzt einfach einmal 10000 bzw. 20000 mögliche Werte
für x1 bzw. x2 vorsieht, so wird man schnell erkennen, daß
200 Millionen Punkte mit entsprechend vielen Berechnungen
abzuhandeln wären...
|
|
|
|
Interaktive Berechnung - Eckpunktmethode
|
|
|
|
|
|
Für die Berechnung der Werte haben wir auf unserem
Server eine einfache Implementierung der Eckpunkt-Methode
bereitgestellt.
|
|
|
Dabei entsprechen die Defaultwerte den Werten aus dem Beispiel.
|
|
|
Spielen Sie doch einfach mal mit verschiedenen Werten!
|
|
|
Im folgenden wird jedenfalls von den Defaultwerten ausgegangen.
|
|
|
|
|
|
|
Erläuterung der Beispielergebnisse
|
|
Mit der Lösung Z(x1,x2)=Z(100,30)=1800 ergibt sich
ein maximaler Gewinn von 1.800 EUR / Tag, wenn 100 Server
und 30 Racks hergestellt werden.
|
|
|
Offensichtlich ist es eben sinnvoll möglichst viele Server
herzustellen und die restliche Kapazität der Endkontrolle durch
Produktion von Racks zu ergänzen.
|
|
|
|
Die Eckpunktmethode
|
|
Dieses stark vereinfachte Beispiel zeigt sehr anschaulich, wie abhängig von
einem Verkaufspreis und den jeweils verfügbaren Mengen von x1 und x2 deren
optimale Stückzahl ermittelt wird.
|
|
|
Für dieses Trivialproblem ist die Eckpunkt-Methode mehr als ausreichend.
Bei der Eckpunkt-Methode werden die Eckpunkte eines n-dimensionalen Polyeders
berechnet. Bei unserem zweidimensionalen Problem handelt es sich entsprechend
nur um ein Polygon und die begrenzenden Hyperebenen reduzieren sich auf Geraden.
|
|
|
Sofern überhaupt eine Lösung existiert, so liegt diese auf einem der
Schnittpunkte der Geradenpaare (oder ist im Entartungsfall eine der
begrenzenden Teilstrecken - wird im weiteren nicht diskutiert).
|
|
|
|
|
|
Bei unserem zweidimensionalen Problem bestimmen die Geraden
der begrenzenden Funktionen von LA, LB und LC, sowie die durch
die x1- und die x2-Achse definierten Geraden den Rand des Polygons.
|
|
|
Für jeden Schnittpunkt zweier Geradenpaare wird dabei zunächst
abgeprüft ob der Schnittpunkt gegen eine der definierten Grenzbedingungen
verstößt. Aus sämtlichen zulässigen Schnittpunkten wird derjenige
mit dem maximalen Zielwert ausgewählt.
|
|
|
Da die Schnittpunkte der x1- und x2-Geraden (0,0) für unser Beispiel irrelevant
ist ergeben sich hier nur noch maximal 4 relevante Schnittpunkte zur Berechnung.
Zusätzlich müssen noch 4! (4 Fakultät = 4*3*2*1 = 12) Geraden-Schnittpunkte
berechnet werden.
|
|
|
Anders als beim naiven Vorgehen ist bei der Eckpunkt-Methode die Größe
des von LA, LB und LC definierten Intervalle ohne jegliche Auswirkung auf die
Anzahl der benötigten Berechnungsschritte!
|
|
|
Es verbleibt die Behandlung des Falles, daß
die optimale Lösung identisch zu einer Kante des Polygons ist.
(genau dann der Fall wenn zwei benachbarte Schnittpunkte den
gleichen maximalen Zielwert ergeben). In diesem Fall ergeben
alle Punkte auf der Gerade ein identisches Optimum. In unserem
Beispiel ist es ausreichend in diesem Fall einen der beiden
Punkte zu wählen.
|
|
|
|
Der echte Gewinn
|
|
Aus dem aufgespannten Polyeder (bzw. hier Polygon) lassen
sich aber zusätzliche wichtige Aussagen ableiten.
|
|
|
Sofern die Produktion an Servern nicht weiter gesteigert werden
kann, ist die Endkontrolle das hemmende Element.
Ein optimales Zusammenspiel würde sich ergeben, wenn sich die
durch LA, LB und LC bestimmten Hyperebenen (bzw. hier Geraden)
in einem einzigen Punkt treffen würden.
|
|
|
Alternativ könnte es auch sinnvoll sein die Produktion
von Racks einzustellen, sofern die Produktion von
Servern um weitere 30 Geräte am Tag gesteigert werden
kann. Das Personal aus der Rackherstellung arbeitet bei
optimaler Zielfunktion weit unterhalb seiner Kapazität.
Zudem werden die Produktionsanlagen und Flächen nicht
annähernd ausgenutzt.
|
|
|
Die beiden vorherigen Aussagen lassen sich unmittelbar aus der
Überlegung ableiten, daß das Optimum nur weiter gesteigert
werden kann, wenn zunächst die beiden beteiligten Geraden
verschoben werden können.
|
|
|
Eine Änderung an den restlichen Geraden hat bestenfalls keine Auswirkung
oder führt zu einer verschlechterung des Ergebnisses.
|
|
|
In unserem konkreten Fall kann man leicht sehen, daß das Optimum
dann ausgeschöpft wird, wenn die Enkontrolle ausreichende
Kapazität hat um sowohl die maximale Fertigungszahl an
Servern und auch Racks bedienen zu können.
|
|
|
|
Real-Life
|
|
Die Eckpunkt-Methode ist für eine begrenzte Anzahl von Dimensionen
(als Variablen x1, x2, ..., xn) und Grenzbedingungen (L1,L2,..,Lm)
durchaus ausreichend.
|
|
|
Eine Berechnung größerer Systeme sorgt allerdings für eine
starke Zunahme von Schnittkanten und Punkten. Zusätzlich steigt mit
jeder Dimension des Problems der Aufwand für die Berechnung deren
'Schnittgeraden'.
|
|
|
So müssen bei einen 7-dimensionale Polyeder die Schnitte von
6-dimensionalen Hyperebenen ermittelt werden...
|
|
|
Große Systeme verlangen also offensichtlich nach einem besseren
Werkzeug wie z.B. dem Simplex-Algorithmus.
|
|
|
|
Fragen zum Artikel?
|
|
|
|
Falls Sie Fragen und auch Anregungen haben, kontaktieren Sie uns bitte!
|
|
|
Ihre Ansprechpartner:
|
|
|
|
|
|
|
|
|
|
|
|
|
Durchwahl: 0911 80153-95
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
webcam
|
|
refresh-rate: 10 sec.
|
|
|
|
|
|
|
quality matters
|
|
valid HTML 4.01 Transitional
|
|
|
|
|
|
valid CSS level 2.1
|
|
|
|
|
|
|
