Ergänzung zu 7.3 Startalgorithmen Bemerkungen: • Am Ende sind jeweils genau m+n-1 Felder mit Zahlen (evtl. auch 0) belegt. Die restlichen Felder bleiben frei • Die belegten Felder heißen Basisfelder und entsprechen den Basisvariablen im Simplex-Algorithmus • die nichtbelegten (freien) Felder heißen Nichtbasisfelder • Je aufwändiger das Startverfahren, umso besser ist im Allgemeinen die Startlösung und umso geringer der Aufwand in der späteren Optimierunsgphase 7.4 Optimierungsphase Ziel: Bestimmung der optimalen Lösung des Transportproblems ausgehend von einer zulässigen Startlösung (1) Zyklen • Ein Zyklus ist eine geschlossene Folge von Tableaufeldern • Start- und Zielfeld ist ein Nichtbasisfeld • alle anderen Felder des Zyklus sind Basisfelder • Zyklus: Startfeld → Sprung zu Basisfeld in derselben Zeile → Sprung von dort zu Basisfeld in derselben Spalte → Sprung von dort zu Basisfeld in derselben Zeile → . . . bis entsprechender Sprung zum Starfeld zurück möglich ist oder Startfeld → Sprung zu Basisfeld in derselben Spalte → Sprung von dort zu Basisfeld in derselben Zeile → Sprung von dort zu Basisfeld in derselben Spalte → . . . bis entsprechender Sprung zum Starfeld zurück möglich ist • Zu jedem Nichtbasisfeld existiert genau ein Zyklus 1 Beispiel: B1 A1 30 A2 20 70 15 20 50 40 A3 bj B2 12 40 50 B3 B4 17 0 40 60 20 15 25 20 15 10 10 ai 50 30 40 20 120 (2) Die Stepping-Stone-Methode (2a) Kostenänderungswerte • Betrachten einen festen Zyklus mit Startfeld (Nichtbasisfeld) (i, j) • Wir stellen uns vor, daß wir eine Einheit in dieses Nichtbasisfeld eintragen und die verletzten Bedingungen für die Transportmengen entlang des Zyklus jeweils korrigieren Beispiel: B1 A1 A2 A3 bj B2 B3 B4 ai 70 15 17 20 50 15 25 40 12 20 15 50 40 20 10 60 50 30 40 20 120 • Für diese Transportmengenänderung berechnen wir die Kostenänderung ∆cij durch abwechselnde Addition und Subtraktion der Einheitstransportkosten entlang des Zyklus: c12 = +15 − 70 + 20 − 15 + 20 − 12 = −42 • Bei negativer Transporkostenänderung ergibt sich eine Verringerung der Gesamtkosten, bei positivem ∆cij dagegen eine Erhöhung Beispiel: B1 A1 A2 A3 bj 30 20 B2 B3 B4 70 15 17 20 50 15 25 20 15 40 50 40 12 40 10 0 10 20 60 20 2 ai 50 30 40 120 (2b) Iteration • Berechne für jedes Nichtbasisfeld die Transprotkostenänderung ∆cij • wähle dasjenige Nichtbasisfeld (i, j) aus, das den kleinsten negativen (negativen, betragsmäßig größten) Wert ∆cij aufweist. Gibt es mehrere davon, wähle eines davon beliebig. • Auf dem zum Feld (i, j) gehörigen Zyklus soll möglichst viel Transportgut umverteilt werden. Bilde dazu das Minimum der Transportmengen der Felder von denen im Zyklus etwas weggenmommen wird, d.h. - betrachte jedes zweite Feld im Zyklus beginnend mit dem zweiten bzw. - betrachte alle Felder im Zyklus für die bei der Kostenänderungsberechnung der Betrag subtrahiert wird. Nehme die entsprechnede Umverteilung vor. Beispiel: B1 A1 A2 A3 bj B2 B3 B4 ai 70 15 17 20 50 15 25 40 12 20 15 50 40 10 20 60 20 50 30 40 120 • Das Startfeld des Zyklus wird Basisfeld und genau ein bisheriges Basisfeld mit aktuellem Wert xij = 0 wird Nichtbasisfeld. Gibt es davon mehrere Kandidaten, wähle ein beliebiges, die anderen Kandidaten bekommen eine Entartungsnull. • Falls im Zyklus keine Umverteilung stattfinden kann - das Minimum über die fraglichen Werte ist 0 - so wird trotzdem der Tausch Basis - Nichtbasis vorgenommen. Das neue Basisfeld bekommt eine Entartungsnull. • Das Verfahren wird solange wiederholt, bis alle Kostenänderungswerte nichtnegativ, also ≥ 0 sind. 3 (3) Die MODI-Methode • wird auch u − v-Methode oder Potentialmethode genannt • unterscheidet sich nur in der Art der Berechnung der Kostenänderungswerte ∆cij von der Stepping-Stone-Methode (3a) Zeilenpotentiale ui und Spaltenpotentiale vj • Initialisierung: Lege ein beliebiges Potential fest: üblicherweise: v1 = 0 • Für alle Basisfelder gilt: ui + vj = cij Daraus können wir die restlichen n+m−1 Potentiale eindeutig berechnen. Beispiel: B1 A1 A2 A3 bj 30 20 B2 B3 B4 70 15 17 20 50 15 25 20 15 40 50 40 12 40 10 0 10 20 60 20 ai uj 50 30 40 120 vj (3b) Kostenänderungswerte ∆cij ∆cij = cij − ui − vj für alle Nichtbasisfelder Diese Kostenänderungswerte stimmen mit denen im Punkt (2) (Stepping-StoneMethode) ermittelten Werten überein. (3c) Iteration s. (2b) 4
© Copyright 2025 ExpyDoc
