Einführung in die Optimierung | Vordiplom | Informatik | Universität Braunschweig

Einführung in die Optimierung | Informatik

12.03.2009

Art der Hochschule:

Universität

Prüfungsort:

Braunschweig

Studienfach:

Informatik

Art der Prüfung:

Vordiplom

Prüfungsfach:

Einführung in die Optimierung

Dauer:

15-20 Minuten

Note:

Konntest du mit einem selbst gewählten Thema beginnen?

keine Angabe

Versucht der Prüfer bei Schwierigkeiten zu helfen?

keine Angabe

Prüfungsablauf / Tipps

Vorbemerkung: Diese verdammte Nervosität! Das ganze wäre viel besser gelaufen, wenn ich nicht so verdammt nervös gewesen wäre. Hab so meine Probleme mit mündlichen Prüfungen.

Warnung: Das Protokoll ist aus dem Gedächtnis geschrieben. Ich übernehme keine Garantien für die Richtigkeit!

Prüfungsfragen

Prof.:
Simplex Algorithmus: Was ist das? / Was tut er?

Ich:

* Verfahren, dass lineare Optimierungsprobleme in endlich vielen Schritten löst, oder aber dessen Unbegrenztheit oder Unlösbarkeit feststellt.
* Laufzeit in der Praxis polynomiell. Es gibt aber zu jeder Variante des Verfahrens Instanzen, für die er exponentielle Laufzeit braucht. Z.B.: Klee-Minty-Würfel, bei dem alle 2^n Ecken abgesucht werden.
* Idee: Zulässige Basislösung als Start-Ecke. Dann zur Nachbarkante weiterhangeln, bei der sich der Zielfunktionswert erhöht. Da Polyeder konvex ==> Es gibt einen Weg zur optimalen Ecke.

Prof.:
Wie entscheidet der Algorithmus, welche Kante er wählen soll, um den Zielfunktionswert zu verbessern?

Ich:
Reduzierte Kostenkoeffizienten. Größten wählen. (Pivotspalte)

Prof.:
Formel der reduzierten Kostenkoeffizienten?

Ich:
Cn = ?
[Da fingen die Probleme an.]

Prof.:
Wie sieht die Zielfunktion aus?

Ich:
[Hab ich nicht so gut hinbekommen. Nervosität.]

Prof: Standartform LP?

Ich:
[Mit etwas Hilfe hinbekommen]
max CT x | Ax = 0

Prof.:
Wie sieht das im Tableau aus?

Ich:
Allgemeines Tableau aufgestellt. Leichte Probleme mit Initial-Werten.

Prof:
Wir machen nun einen Iterationsschritt.

Ich:
Mit VIEL Hilfe hab ich die Iterations-Operationen hinbekommen. Ich wusste die Formeln nicht auswendig und hab dann die Rechnung so gut es ging mit eigenen Worten erklärt.

* Optimalitätstest
* Pivotspalte
* Endlichkeitstest
* Pivotzeile
* Pivotoperationen

Prof:
Themenwechsel (Uhr tickt! - Sonst hätte er sicherlich noch gerne etwas über den revidierten Simplex, die Zweiphasen- und die M-Methode gehört.)

Dualitätssätze: Was besagen sie?

ich:
Zu jedem LP (P) kann man ein duales LP (D) definieren.

* Primal: max CT x | Ax < b, x >= 0
* Dual: min yT b | yT A > CT x
* Duales ist 90° gedreht.

Prof. hat bei der Aufstellung geholfen.

Prof:
Was ist CT x, was ist yT b ?

Ich:
Wusste nicht recht was er wollte. Eigentlich wollte er nur hören, dass CT x Lösung des primalen, und yT b Lösung des dualen ist.

Prof: Und die Dualitätssätze?

Ich:
Hab mit dem starken Satz angefangen und mit gleich ein Fauxpas erlaubt, indem ich behauptet habe, dass die LP's die gleiche Lösung hätten
Richtig: Die Zielfunktionen haben die selben Werte.

Dann noch etwas mit dem schwachen Dualitätssatz, ist aber auch nicht so toll gelaufen.

Prof.:
Letzte Frage:
Wenn P unbeschränkte zulässige Lösung besitzt, was ist dann mit D ?

Ich:
Auch unbeschränkt?
FALSCH! Man weiß es nicht!

ENDE DER PRÜFUNG

Fazit: Mit allem drum und dran kann ich mich mit der 4.0 sehr glücklich schätzen. Hab ich nicht dran geglaubt, als ich den Raum für die Beratung verlassen musste. Diese hat auch SEHR lange gedauert, da es genauso gut eine 5.0 hätte werden können.
Das schlimmste ist, dass ich diese ganzen Lücken und Fehler nicht gehabt hätte, wenn er mich nicht in einer Prüfung danach gefragt hätte. Das waren alles Sachen, die man aus dem FF können muss!

Gefallen hat ihm meine Struktur der Antworten. Alles war irgendwo logisch sortiert, besonders am Anfang bei der Beschreibung des Simplex (danke Wikipedia).

Gar nicht gefallen haben ihm meine sichtbare Nervosität und meine mangelnde Formalität. Bei den Simplex-Schritten muss man die Formeln mit allen Indizes auswendig können (ist aber eigentlich auch nicht zu viel verlangt).

Prof. ***** war ein sehr hilfsbereiter Prüfer, der die Themen, und die Prüfung an sich, sehr Fair gestaltet hat. Kann ich nur weiterempfehlen.

Mit meiner eigenen Leistung bin (und kann) ich nicht zufrieden (sein).

Studienfächer