Numerical Aspects of Linear Integer Programming (NALIP)

Prüfer: Florian Rösel (Beisitzerin Martina Kuchlbauer) Datum: 24.07.2023 Prüfungsdauer: 15 min Note: 1.0

Dieses Braindump ist aus zweiter Hand, daher evtl. nicht ganz vollstaendig. Super entspannte Prüfung.

Fragen:

F: Was hast du in den Übungen so gemacht?
- A: Habe bisschen erzählt.
F: Wir haben zwei Arten von LPs kennengelernt, welche gibt es?
- A: Habe beide aufgeschrieben.
F: Suche dir eine davon aus und schreibe den zugehörigen Simplex-Algorithmus dafür auf.
- A: Simplex in Standardform aufgeschrieben
F: Warum kann man mit dem Simplex in der nächsten Iteration mit dem neuen A_B_new einfach weitermachen? Also warum ist A_B_new regulär?
- A: Beweis mit den Eta-Matrizen.
F: Was ist denn die Komplexität des Algorithmus?
- A: In naiver Form eher schlecht, da die Inversenberechnung (für BTRAN/FTRAN) aufwändig ist.
- ⇒ LU Zerlegung. Diese ist auch aufwändig, macht man aber nicht andauernd, denn man verwendet die Update-Formeln mit den Eta-Matritzen. Damit ist der durchschnittlicher Aufwand O(m^2).
F: Eine Frage zur Sensitivity-Analysis.