Inhalt

• Termine
• Sprechzeiten
• Voraussetzungen
• Übungsblätter
• Programmieraufgaben
• CPLEX
• letzte Übung 1998
• Tip zur Programmieraufgabe (neu)

1. Analyse des Netzwerksimplex-Algorithmus |Theorie]
2. Test der Datenstrukturen für den Netzwerksimplex
3. Implementation des Netzwerksimplex

• 1. Übungsblatt  [LaTeX, Postscript] Achtung: Bitte gleich die Postscript-Version zum Drucken verwenden!

kleine Korrektur: Bei der Beschreibung des Simplex gab es zwei Tippfehler:
• Initialisierung: Da die rechte Seite b^T=(2,3) positiv...
• 1. Schritt: ... Die neue Lösung ist x^T=(0,2,0,1) mit ...
• 2. Übungsblatt  [LaTeX, Dvi, Postscript]
• 3. Übungsblatt  [LaTeX, Dvi, Postscript] + Bild [pictex]
• 4. Übungsblatt  [LaTeX, Dvi, Postscript], Abgabe am Freitag!
• 5. Übungsblatt  [LaTeX, Dvi, Postscript], Abgabe am Freitag!

kleine Korrekturen: in Aufgabe 16
• Wir nehmen für alle Teilaufgaben ganzzahlige Bedarfs-/Überschu\3werte sowie ganzzahlige und nicht-negative Kantenkosten an.
• In Teilaufgabe (iv) lautet die Definition von h wie folgt: h(T_i)=\sum_{v \in V}(y_v-y_r)
• In Teilaufgabe (viii) ist b_7=+2.
Tips:
• In Teilaufgabe (v) wird die Kante e nach der Pivotregel aus (iv) gewa\"ahlt.
• In Teilaufgabe  (vii) mu\3 vor allem die Korrektheit bei Terminierung nachgewiesen werden (d.h. da\3 die Bauml\"osung optimal ist, auch wenn bei der Terminierung noch Kanten existieren, die bei negative reduzierte Kosten haben aber aufgrund der Pivotregel nicht als Pivotkante in Frage kommen)
• 6. Übungsblatt  [LaTeX, Dvi, Postscript]
• 7. Übungsblatt  [LaTeX, Dvi, Postscript]
• 8. Übungsblatt  [LaTeX, Dvi, Postscript]
• 9. Übungsblatt  [LaTeX, Dvi, Postscript]
• 10. Übungsblatt  [LaTeX, Dvi, Postscript]

CPLEX ist ein kommerzielles Programm zur Lösung linearer Programme. Aufgrund des hohen Preises ist es nicht auf jedem Rechner installiert.
Um mit CPLEX zu arbeiten muss mensch entweder an einem der CPLEX-Rechner  (c101 bis c106) sitzen, oder den Befehl "tadm" eingeben und im erscheinenden Menue den Punkt "CPLEX-Rechner" wählen (daraufhin wird eine Verbindung zu einem Rechner aufgebaut, der CPLEX installiert hat).

Dokumentation zu CPLEX findet sich unter folgender URL: http://www.utexas.edu/cc/math/CPLEX

Beispiel-Sitzung:
 

lop-001 <4>% cplex

Welcome to CPLEX Linear Optimizer 4.0.8
  with Mixed Integer & Barrier Solvers
Copyright (c) CPLEX Optimization, Inc., 1989-1995
CPLEX is a registered trademark of CPLEX Optimization, Inc.

Type 'help' for a list of available commands.
Type 'help' followed by a command name for more
information on commands.

CPLEX> read sample.lp
Warning: 'End' missing.
Problem 'sample.lp' read.
Read time =    0.32 sec.
CPLEX> display problem
Maximize
 obj: x1 + 2 x2 + 3 x3
Subject To
 c1: - x1 + x2 + x3 <= 20
 c2: x1 - 3 x2 + x3 <= 30
Bounds
 0 <= x1 <= 40
 All other variables are >= 0.
CPLEX> optimize
No LP presolve or aggregator reductions.
Presolve time =    0.01 sec.

Iteration Log . . .
Iteration:     1    Objective     =            60.000000

Primal - Optimal:  Objective =    2.0250000000e+02
Solution time =    0.07 sec.    Iterations = 3 (0)

CPLEX> display solution x1-x3
Variable Name           Solution Value
x1                           40.000000
x2                           17.500000
x3                           42.500000
CPLEX> quit

Maximize
 obj: x1 + 2 x2 + 3 x3
Subject To
 c1: - x1 + x2 + x3 <= 20
 c2: x1 - 3 x2 + x3 <= 30
Bounds
 0 <= x1 <= 40
 0 <= x2
 0 <= x3