Sprechzeiten

Fragen zu den Programmieraufgaben und zu den Rechner-Accounts bitte nur während der betreuten Rechnerzeit stellen.

Termine

Zeit	Montag	Dienstag	Mittwoch	Donnerstag		Freitag
08:00
10:00		VL MA 042		Tut MA 650
12:00		UE MA 043
14:00		Unix-Pool MA 241	Unix-Pool MA 241	VL MA 043
16:00				Tut MA 751	Unix-Pool MA 241

Während der Rechnervorrangzeiten sind für euch 15 Rechnerarbeitsplätze im UNIX-Pool (MA241) reserviert.
Selbstverständlich können die Rechner auch zu anderen Zeiten benutzt werden, nur habt Ihr dann halt keinen Anspruch auf einen Rechnerplatz.

Außerdem ist zu den betreuten Rechnerzeiten meistens ein Betreuer (Andreas) anwesend, um Fragen zu beantworten und Programmieraufgaben abzunehmen.

Aktuelles

Scheinkriterien

• Mindestens 50% aller Punkte aus den Übungsblättern 1-7 sowie mindestens 50% aller Punkte aus den übrigen Übungsblättern.
• Erfolgreiche Bearbeitung aller Programmieraufgaben. Dabei setzen wir die aus der CoMa bekannten Programmierrichtlinien voraus.
• Bestehen einer Rücksprache am Semesterende oder alternativ Vorrechnen von zwei Aufgaben (je eine pro Semesterhälfte) im Tutorium oder in der grossen Übung.

Ressourcen

• Informationen

  • Info-Blatt korrigiert am 15.10. [.tex] [.ps] [.pdf]
  • Hilfreiche Tools zum Angucken/Ausdrucken der Übungsblätter (TeX/PostScript/PDF-Format) und zur Java-Programmierung findet ihr auf der CoMa-CD, die ihr bei Andreas ausleihen könnt.
  • Im Sekretariat gibt es eine Kopier-Vorlage des Vorlesungs-Skripts von Herrn Möhring.

• Literaturhinweise

  • Grundlage für die VL:
    V. Chvátal:
    "Linear Programming",
    W.H. Freeman and Company, New York, 1980
  • Christos H. Papadimitriou, Kenneth Steiglitz:
    "Combinatorial Optimization: Algorithms and Complexity",
    Prentice Hall, Englewood Cliffs, NJ, 1982
  • Robert J. Vanderbei:
    "Linear Programming: Foundations and Extensions"',
    International Series in Operations Research and Management Science,
    Kluwer Academic Publ., 1998
  • Komplette Literaturliste: [tex] + [bbl], [ps], [pdf],

• Programme und Materialien aus den Übungen

  • 22.10.2002
    

    • CPLEX

      • Dokumentation für CPLEX 7.0   im Unix-Pool.
        
      • Eine Übersicht zur CPLEX-Installation im Unix-Pool gibt es auch.

    • ZIMPL

      Ein frei erhältlicher Modellgenerator für Lineare Programme ist ZIMPL von Thorsten Koch.
      Es gibt eine kurze ZIMPL Dokumentation.
      
      

    • ZIMPL-Beispiel: Kleine Ölraffinerie

      Dieses Beispiel liegt auch im Unixpool unter /homes/lop/lop-001/Modelle/oilklein/.
      
      1. Version: Das Zimpl-Modell, daraus baut zimpl ein LP und eine Übersetzungstabelle der Namen.
      
      2. Version: Das Zimpl-Modell liest die Parameter-Datei ein, daraus baut zimpl ein LP und eine Übersetzungstabelle der Namen.
      
      
  • 21., 26. + 28.11.2002: Netzwerk-Simplex
    
    Das "Skript" zu den ersten drei Netzwerk-Simplex-Übungen.
    Überarbeitet und ergänzt am 28.11.

Übungsblätter und Programmieraufgaben

• Übungsblätter

  • LaTeX-Inputs für alle Übungsblätter: [uebung.tex], [Head.tex],
  • 1. Übungsblatt [tex], [ps], [pdf], (Abgabe bis 22.10.2002)
  • 2. Übungsblatt [tex], [ps], [pdf], (Abgabe bis 31.10.2002)
  • 3. Übungsblatt [tex], [ps], [pdf], (Abgabe bis 07.11.2002)
  • 4. Übungsblatt [tex], [ps], [pdf], (Abgabe bis 14.11.2002)

    Es kam vorhin die Frage auf, warum in 16.b) steht |I|>=n, wo doch stets die Annahme gelten soll m<n. Hier die Lösung des Problems:

    Wenn ihr genau hinseht, haben wir in der Aufgabe ein Polytop definiert durch Ax<=b. Die Annahme m<n gilt aber nur fuer die Standard-Form (also Ax=b, d.h. nach Einführung von Schlupf-Variablen).

    Es gilt doch, dass eine Ecke eine 0-dimensionale Seitenfläche von P ist, somit muss es Schnitt von mindestens n Hyperebenen sein. Diese liefern dann das System I.

    Noch ein kleiner Tipp: es könnte Hilfreich sein, in eines der Bücher zu schauen, die auf der Homepage erwaehnt sind und als "Grundlage für die VL" markiert sind. ( Wenn ich noch was sage, dann kann ich auch gleich die ganze Lösung hier hin schreiben. ;-) )

  • 5. Übungsblatt [tex], [ps], [pdf], (Abgabe bis 21.11.2002)
    Korrigierte Punkteverteilung: Aufgabe 20 = 4+4 Punkte, Aufgabe 21 = 5 Punkte, Aufgabe 22 = 4+1 Punkte
    Wer für Aufgabe 22 dennoch die 4+4 Punkte haben möchte, muss das LP per Hand mit der Tableau-Methode lösen !!!
  • 6. Übungsblatt [tex], [ps], [pdf], (Abgabe bis 28.11.2002)
    
  • 7. Übungsblatt [tex], [ps], [pdf], (Abgabe bis 05.12.2002)
    
  • 8. Übungsblatt [tex], [ps], [pdf], (Abgabe bis 12.12.2002)
    
  • 9. Übungsblatt [tex], [ps], [pdf], (Abgabe bis 19.12.2002)
    
  • 10. Übungsblatt [tex], [ps], [pdf], (Abgabe bis 09.01.2003)
    
  • 11. Übungsblatt [tex], [ps], [pdf], (Abgabe bis 16.01.2003)
    
  • 12. Übungsblatt [tex], [ps], [pdf], (Abgabe bis 23.01.2003)
    Achtung: Aufgabe 47.b) gilt als Zusatzaufgabe
    
  • 13. Übungsblatt [tex], [ps], [pdf], (Abgabe bis 30.01.2003)
    
  • 14. Übungsblatt [tex], [ps], [pdf], Grafik für die TeX-Source: [eps], (Abgabe bis 06.02.2003)
    

• Programmieraufgaben

  • 1. Programmieraufgabe: Modellierung und Optimierung einer Farm, siehe 2. Übungsblatt (Abgabe bis 13.11.2002)
    
    Die benötigten Dateien als Tabelle (.dat) und als Parameter-File (.par, wie in der Übung):
    belegung.dat,  belegung.par - Anteil der Fläche die in jedem Monat von der ausgewählten Fläche belegt wird.
    aufwand.dat,  aufwand.par - Aufwand an Arbeitskraft pro Fläche.
    
    Kleiner Tipp: Die Optimallösung ist 2 Hektar jeweils für Baumwolle, Zwiebeln und Tomaten.
    Optimalwert: 1898.52
    
    
  • 2. Programmieraufgabe: Simplex-Algorithmus in Tableau-Form, siehe 4. Übungsblatt (Abgabe bis 18.12.2002)
    
    
  • 3. Programmieraufgabe: Netzwerksimplex-Algorithmus, siehe 10. Übungsblatt sowie folgende zusätzliche Hinweise (Abgabe bis 19.02.2003)