Lineare Optimierung
auf dieser Seite:
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

Werte erfassen:
Beschreibung:
Wert:
LA - Maximalzahl x1 (Server).
LB - Maximalzahl x2 (Racks).
LC - Maximalzahl x1+x2 (Endkontrolle).
P1 - 'Preis'/Gewinn je Server
P2 - 'Preis'/Gewinn je Rack
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:
Arnim Jablonowski
mailto:aja@orcus.de
Durchwahl: 0911 80153-95

webcam

refresh-rate: 10 sec.

translate

quality matters

valid HTML 4.01 Transitional
valid CSS level 2.1
//HOME / Dienstleistungen / Numerische Software
© 1998-2009 by ORCUS GmbH - created with ORCUS® XmlSite-generator OxsSite 004.24 at:2012-10-5T0:37:0+01:00