Klassifizierung von Optimierungsverfahren in Supply Chain Management-Systemen

Abbildung 32: Lösungsbaum beim B&B, in Anlehung an [DoDr98, S.125]. Ein zu lösendes Problem P0 (Ausgangsproblem) wird in Teilprobleme P1 und P2 so verzweigt, dass die Vereinigung der Lösungsmenge wiederum diejenige von P0 ergibt und dass deren paarweise Durchschnitte, d.h. die Menge der möglichen Lösungen, nach Möglichkeit leer sind. Diese Teilprobleme werden dann weiter unterteilt. P0 bezeichnet man als Wurzel des (auf dem Kopf stehenden) Baumes, P1 ist die Wurzel des aus P1, P3 und P4 bestehenden Teilbaumes. [DoDr98, S.125] Bounding (Beschränkung): Wenn man sicher sein kann, dass die optimale Lösung einer Teilaufgabe nicht besser als eine schon bekannte Lösung ist, braucht diese Teilaufgabe nicht weiter betrachtet zu werden. Man spricht davon, daß sie ausgelotet ist. Um dies festzustellen, schätzt man beispielsweise den höchstens erreichbaren Gewinn für die betrachtete Teilaufgabe ab. Ein solcher Schätzwert heißt dann obere Schranke. [SKKD02-ol] Ein Gewinn von 0 kann demgegenüber die untere Schranke kennzeichnen. Der Verzweigungsprozess wird beschränkt, in dem man mit Hilfe der Schranken entscheidet, ob Teilprobleme verzweigt werden müssen oder nicht. [...]

nichtlinearer beschränkter Optimierungsprobleme angewandt werden. [Kall95, S177] „Der zentrale Gedanke der Innere-Punkt-Methoden ist die Konstruktion einer stetig von einem Parameter abhängigen Folge von Näherungslösungen, die asymptotisch gegen die exakte Lösung konvertiert.“ [Hock95-ol, S.58] Wie bereist dargestellt beruht das Simplex-Verfahren auf der fundamentalen Eigenschaft linearer Optimierungsprobleme, nämlich dass eine optimale Lösung immer in einer Ecke des durch die linearen Nebenbedingungen definierten konvexen Bereichs liegt. [Hock95-ol, S.6] Im Gegensatz zur Simplex-Methode suchen InnerePunkt-Methoden, ausgehend von einer im Inneren des zulässigen Bereichs liegenden Lösung, nach einer optimalen Lösung. Zu den bekanntesten Vorgehensweisen dieser Art gehören die Ellipsoid-Methode von Khachijan und die projektive Methode von Karmarkar. [DoDr98, S.19f.] Die Methode von Khachijan konstruiert eine Folge von Ellipsoiden, wobei jedes Folgeelement die optimale Lösung enthält und gleichzeitig im Inneren des vorhergehenden Folgeelements liegen. Sie generiert dadurch verbesserte Iterierte im Sinne einer sukzessiven monotonen Verkleinerung der Umgebung der Lösung. [Hock95-ol, S.9] Im Gegensatz zur Simplexmethode erzeugt Karmarkars Verfahren, ausgehend von einem Startpunkt im relativen Inneren der zulässigen Punktmenge, eine Folge, die gegen eine Optimallösung des linearen Programms konvergiert. Befindet man sich nahe genug an der Optimallösung, so kann man diese durch einen einfachen Rundungsprozess aus dem laufenden Iterationspunkt exakt gewinnen. [Krum94-ol, S.1] Weitergehende Informationen zu den Interior Point-Methoden finden sich in den angegebenen Literaturquellen. [...]

5.1.2.4 Die Big-M-Methode Die (Big-)M-Methode entspricht formal der Anwendung des primalen SimplexAlgorithmus auf ein erweitertes Problem. [DoDr98, S.27] Auf der Grundlage eines linearen Optimierungsproblems wird zu jeder Nebenbedingung, die keine Schlupfvariable mit positivem Vorzeichen besitzt, auf der linken Seite eine künstliche, fiktive Variable y mit positivem Vorzeichen hinzugefügt. In einer zu maximierenden Zielfunktion wird dann die Variable mit „–M“ bewertet. Auf das so erweiterte Problem wir dann der Simplex-Algorithmus angewendet, bis alle y, die sich zu Beginn in der Basis befinden, die Basis verlassen haben. Da sich diese Vorgehensweise nur sehr selten in der Praxis finden lässt, soll diese kurze Vorstellung im Rahmen dieser Arbeit genügen. Zur weiteren Vertiefung kann beispielsweise auf Domschke/Drexl [DoDr98, S.27ff.] verwiesen werden. [...]