FSI Informatik/pruefungen/nebenfach/mathematik/nalip-2023-07-24-01

Du befindest dich hier: FSI Informatik » Prüfungsfragen und Altklausuren » Nebenfächer » mathematik » Numerical Aspects of Linear Integer Programming (NALIP) (Übersicht)

Diese Seite ist nicht editierbar. Du kannst den Quelltext sehen, jedoch nicht verändern. Kontaktiere den Administrator, wenn du glaubst, dass hier ein Fehler vorliegt.

======  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**

Relativ einfache Prüfung, die auch allein mit dem Skript (ohne Übungen) machbar ist. Im Nachhinein hätte ich weniger in die Tiefe gelernt (evtl. z.B. weggelassen, wie man für Phase I im bounded Simplex mit unzulässigen Slack variablen den Algorithmus optimieren kann (im Skript Kapitel 3.2.3)) und mehr in die Breite.

**Fragen:**
  - F: Hast du die Übungen gemacht? Dann könntest du jetzt darüber ein wenig reden.
    * A: Eher weniger.
  - F: Okay, wir haben zwei Formen von LPs kennengelernt, schreib die mal hin.
    * A: [In natürlicher Form + Standardform aufgestellt]
  - F: Beschreibe mal den Simplex für LPs in Standardform beschreiben 
    * A: INPUT: Basis B mit zulässigem x_B; BTRAN:... 
  - F: Bei w <= 0 ist das Problem unbounded, warum?
    * A: Er wollte den algebraischen Beweis dafür, ich habe es graphisch begründet, was wohl auch okay war: w ist der Richtungsvektor der Kante, entlang der man sich bewegt, wenn man j in die Basis aufnimmt. Wenn w_i jetzt negativ ist, heißt das, dass man sich von dem constraint wegbewegen muss, um seine Zielfunktion zu verbessern (anstatt darauf zu), ohne je irgendwo anzustoßen. -> Unbounded.
  - F: Laufzeiten der einzelnen Schritte:
    * A: BTRAN O(m^3), Pricing O(m^2) (glaube O(n*m) wäre genauer gewesen), FTRAN O(m^3), Ratio-Test O(m), Update O(m)
  - F: Wenn man jetzt ein Problem mit riesigem n hat (z.b. m=1000, n=10 Mio.). Wie kann man dann beim Pricing die Laufzeit verbessern?
    * A: Habe erst angefangen mit sparse Matrizen angefangen, falls in dem Problem viele 0er sind. Bin dann später auf die modernen Pricing-Methoden gekommen.
  - F: Was für Arten haben wir denn kennen gelernt?
    * A: Bland, lexicographic Rule, Dantzig, Partial Pricing, Multiple Partial Pricing, Devex,
  - F: Wie funktioniert Dantzig denn?
    * A: ...
  - F: Wie schlägt sich denn Dantzig am Anfang?
    * A: Am Anfang gut, weil man schnell negative z findet, und nicht lange suchen muss. Viele normale Nachteile gelten aber trotzdem noch: konvergiert langsam, numerisch instabil.
  - F: Wir haben jetzt noch bisschen Zeit, was möchtest du so sonst noch machen? Phase I? Bounded LP? Sensitivitätsanalyse? 
    * A: Keine Ahnung... Sensitivitätsanalyse.
  - F: Was passiert denn wenn man ein bereits gelöstes LP hat, und sich nun das B geringfügig verändert? Wenn jetzt z.B. eine höhere Genauigkeit gewünscht ist?
    * A: (Es gab erst etwas hin und her, weil ich die Frage falsch verstanden habe). Bei einem Problem in Standardform ohne Slackvariablen? Dann ist das constraint verletzt => B nicht mehr primal zulässig => man braucht eine neue optimale Lösung. Aber da das z_N davon nicht beeinflusst wird, und für die optimale Lösung. z_N >= 0 gilt, ist die Basis immer noch dual zulässig => Man kann den dualen Simplex nehmen um die neue optimale Lösung. zu berechnen.
  - F: Tatsächlich ist es bei geringfügigen Änderungen von b so, dass das constraint nicht verletzt ist und damit die berechnete Lösung. optimal bleibt.
    * A: Achso, bei sooo geringfügigen Änderungen. Wenn Änderungen. innerhalb des Toleranzbereichs bleiben, im Skript lag der bei < 10^(-6), bleibt das LP natürlich zulässig.