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.
F: Hast du die Übungen gemacht? Dann könntest du jetzt darüber ein wenig reden.
F: Okay, wir haben zwei Formen von LPs kennengelernt, schreib die mal hin.
F: Beschreibe mal den Simplex für LPs in Standardform beschreiben
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?
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?
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?
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.