Hinweise zur Programmieraufgabe
Simplexalgorithmus
Aufgabenstellung:
Implementieren Sie den revidierten Simplexalgorithmus für lineare Programme
der Form
max c^T x
s.t. A_1 x <= b_1
A_2 x = b_2
A_3 x >= b_3
x >= 0
Implementieren Sie sowohl manuelles Pivoting (d.h. man kann in jeder Iteration
die in die Basis eintretende und die die Basis verlassende Spalte angeben) als
auch eine Pivotregel Ihrer Wahl.
Eingabeformat:
Ihr Programm soll Lineare Programme der oben beschriebenen Form aus
Files im LP-Format und im MPS-Format einlesen
können. Ein Parser wird Ihnen zusammen mit vielen anderen nützlichen
Routinen in der SPX-Library zur Verfügung
gestellt. Sie benötigen daher keine genauere Kenntnis der genannten
Formate (das LP-Format kennen Sie bereits aus Ihrem Umgang
mit CPLEX).
Ausgabeformat:
Ihr Programm soll (mindestens) den Namen des bearbeiteten Problems und
den Zielfunktionswert der Optimallösung ausgeben.
Problembeispiele:
Testen Sie Ihr Programm anhand der Beispielfiles mit dem Suffix .lp und .mps
in dem Directory /net/lop/data. Um Platz zu sparen, sind die
großen Beispieldaten im MPS-Format mit gzip komprimiert.
Ihre Ergebnisse können Sie mit Hilfe von CPLEX überprüfen.
Programmabgabe:
Die Programmvorführungen zu dieser Aufgabe finden am Semesterende oder
in der ersten Woche der Semesterferien statt. Näheres wird noch in den
Tutorien bzw. in der Übung vereinbart werden.
Die SPX-Library
Die SPX-Library und der LP-Löser Soplex wurden von Roland Wunderling,
einem Mitarbeiter von Prof. Grötschel, am ZIB entwickelt. Soplex ist
ein professioneller LP-Löser, der vom Leistungsumfang und der
Rechengeschwindigkeit den Vergleich mit CPLEX nicht zu scheuen
braucht. Ralf Borndörfer, ein weiterer Mitarbeiter von Prof. Grötschel,
hat eine Beschreibung der für Sie wichtigen Teile der SPX-Library erstellt,
die Sie hier finden.
Zurück zur Vorlesungsseite
University | Department
| Group
| FTP
Last modified: Thu Jun 12 17:26:24 MET DST
<skutella@math.tu-berlin.de>