Hinweise zur Programmieraufgabe
LP-Solver mit Fourier-Motzkin-Elimination

Aufgabenstellung:

Überlegen Sie sich, wie man mit Hilfe der Fourier-Motzkin-Elimination zu einem durch Ungleichungen gegebenen Polyeder einen zulässigen Punkt bestimmen kann.
Entwerfen Sie mit Hilfe von 1. und Aufgabe 15 vom 4. Übungsblatt einen Algorithmus, der, basierend auf Fourier-Motzkin-Elimination, zu einem gegebenen Linearen Programm eine Optimallösung berechnet oder feststellt, daß es keine Optimallösung gibt.
Erweitern Sie Ihr Programm zur Fourier-Motzkin-Elimination wie in 2. beschrieben. Ihr Programm soll gut dokumentiert sein.

Eingabeformat:

Wie bei der letzten Programmieraufgabe soll Ihr Programm Files im sogenannten ieq-Format einlesen können. Um die Zielfunktion angeben zu können, fügen wir zu diesem Format eine weitere Section OBJECTIVE hinzu, in der zunächst MAX oder MIN und dann die Koeffizienten der Zielfunktion stehen, also beispielsweise

OBJECTIVE
MIN 3 7 -4 2

für die Zielfunktion min 3 x1 + 7 x2 - 4 x3 + 2 x4. In dieser Aufgabe benötigen wir also nur die folgenden sections:

DIM, INEQUALITIES_SECTION, OBJECTIVE, END

Außerdem betrachten wir wieder nur Nebenbedingungen der Form Ax <= b.

Ausgabeformat:

Ihr Programm soll ausgeben, ob eine optimale Lösung existiert, und ggfs. deren Wert und die Belegung der Variablen zurückgeben.

Problembeispiele:

Testen Sie Ihr Programm anhand der Beispieldaten, die für die letzte Programmieraufgabe zur Verfügung gestellt wurden, indem Sie jeweils die fehlende Section OBJECTIVE selbst hinzufügen und eine beliebige Zielfunktion einsetzen. Erstellen Sie außerdem neue Beispiele aus den in den Übungsaufgaben besprochenen LPs. Durch gerinfügige Modifikation des Fileformats können Sie Ihre Ergebnisse mit Hilfe von CPLEX überprüfen.

Programmabgabe:

Die Programmvorführungen zu dieser Aufgabe finden in der Woche vom 19. bis zum 23. Mai im Unix-Pool auf den IBM-Rechnern statt. Termine werden in den Tutorien am 15. Mai vereinbart werden.

Zurück zur Vorlesungsseite

University | Department | Group | FTP

Last modified: Fri May 9 08:04:53 MET DST