contents
. . . . | Lineare Optimierung |
|
|
ADM II: Lineare
Optimierung, Wintersemester 2002
3. Programmieraufgabe: Der Netzwerksimplex
Abgabetermin: bis 19. Februar 2003
Aufgabenstellung
Implementiert den Netzwerksimplex-Algorithmus für das
verallgemeinerte Transportproblemtransshipmentproblem mit oberen
und unteren Kantenkapazitäten.
Dazu lest zunächst die Beschreibung eines gerichteten Graphen aus
einer Datei. Nach dem Einlesen werden die unteren
Kapazitäten durch eine Transformation entfernt,
so dass der Algorithmus nur noch obere Kapazitäten behandeln
muß.
Führt nun die Initialisierung von Phase I des
Netzwerksimplex-Algorithmus durch und baut somit einen aufspannenden
Baum auf.
Falls der Benutzer es verlangt, sollen stets streng
zulässige Baumlösungen verwaltet werden (siehe
8. Übungsblatt).
Achtung! Die Eingabegraphen sind nicht notwendigerweise
zusammenhängend. Zerlegt das Problem dann in zwei oder mehr
Teilprobleme und behandelt jedes Problem separat.
Überlegt euch, wie ihr den aufspannenden Baum am besten repräsentiert.
Achtet dabei besonders auf gute Implementierung folgender Aspekte:
- Neuberechnung der Knotenpotentiale bei geg. aufspannenden Baum (am Anfang
von Phase I und Phase II).
- Suche des sog. joins.
- Suche der Pivotkanten.
- Wie durchlaufe ich alle Knoten in dem Teilbaum unter einem bestimmten Knoten?
- Korrektur des aufspannenden Baumes (d.h. Korrektur der Fädelung).
- Nutzt es, die Höhe eines Knotens im Baum zu kennen?
- Update der Knotenpotentiale.
Pivotregeln
Folgende Pivotregeln soll Eure Implementation beherrschen:
- Erste mögliche Kante: Wähle die erste Kante mit negativen
reduzierten Kosten.
- Zyklisch erste mögliche Kante: Wähle die erste Kante mit
negativen reduzierten Kosten. Starte dabei nicht jedesmal wieder bei der
ersten Kante, sondern mit der letzten davor untersuchten Kante.
- Regel von Dantzig: Wähle die Kante mit möglichst kleinen
negativen reduzierten Kosten.
- Kandidatenliste: Halte eine Liste von Kanten mit negativen reduzierten
Kosten und wähle in jedem Schritt die Kante aus der Liste mit möglichst
kleinen negativen reduzierten Kosten. Wenn die Länge der Liste kleiner
wird als ein gegebener Wert p, so wird sie neu berechnet. Entweder
werden beim Neuberechnen alle Kanten mit negativen reduzierten Kostennegativen
reduzierten Kosten eingefügt, oder nur die ersten q Kanten
für ein gegebenen Wert q. (==> Übung)
Zusätzlich soll es (auf Bedarf) möglich sein streng-zulässige
Basislösungen zu produzieren, d.h. wenn eine der obigen
Pivotregeln eine degenerierte Pivotkante e auswählt, wird geprüft,
ob eine neue streng-zulässige Basislösung produziert werden kann.
Falls dies nicht möglich ist mit der Kante e, so wird diese
verworfen, d.h. nicht verwendet. Achtet bei dieser Regel darauf, daß
ihr keine Endlosschleife produziert.
Die Auswahl der entsprechenden Pivotregeln soll über folgende Parameter
möglich sein:
-s |
streng-zulässige Basislösungen produzieren |
-e |
Erste mögliche Kante |
-z |
Zyklisch erste mögliche Kante |
-d |
Regel von Dantzig |
-k |
Kandidatenliste |
Von den Optionen -e, -z, -d und -k
darf immer nur eine angegeben werden. Die Option -s kann zusätzlich
angegeben werden. Wenn keine Option angegeben wird, soll als Standard -e
gewählt werden.
Achtet bitte auf folgende 'Dinge':
Testdaten
... gibt es unter /homes/lop/lop-001/NetBsp.
|