Braindump, alle Angaben ohne Gewähr

10 ECTS Klausur

Lineare und kombinatorische Optimierung

Prof. Dieter Wenninger

90 Minuten

Hilfsmittel: 4 handbeschriebene DIN A4 Seiten (also z.B. 2 beidseitig oder 4 einseitig)


== Kommentare: ==

Zeitlich gut machbar.

Starke Empfehlung die Flussalgorithmen und Umformung in Standardform + Simplex zu üben bis es sehr leicht fällt (hab beides zu wenig geübt und gemeint, dass es schon klappen wird... das tut es nicht, glaubt es mir :D

Ok, vlt. lag's auch daran, dass ich zwei Stunden Schlaf hatte, who knows...

Macht die Übungen + Probeklausuren, die sind deutlich schwerer als die Klausuraufgaben. Wenn man das gut draufhat, hat man easy ne 1.0

Kreislöschung und Simplex hab ich verbockt, 30/34 Punkten --> 1.7 (vor Einsicht). Dafür, dass ich bei ca. Übungsblatt 5 die Vorlesung überhaupt nicht mehr verfolgt und erst 2 Tage vorher wieder den Stoff angeschaut hab, bin ich happy :D Ich vermute mal, dass relativ nett korrigiert wurde, dafür war der Notenschlüssel entsprechend streng.


=== Inhalt: ===

== Aufgabe 1) ==

Eigenschaften zu gegebenen Graphen in Tabelle ankreuzen (Hamilton, Knotenbedeckung, ...)

Gegeben: Zwei Matroide. Zeige, dass Schnitt kein Matroid.

Gegeben: Matroid. Zeichne Graph des zum Matroid isomorphen Kreismatroiden.

Gib Kreissystem des dualen Matroiden an.


== Aufgabe 2) ==

Kreislöschung in Graph mit 4 Knoten (ohne s, t), in jedem Schritt Residualgraph, Fluss und Wert des Flusses angeben, laut Prof nach 2-3 Iterationen fertig, ich war nach der ersten fertig, vermutlich negativen Kreis übersehen oder Zahlen verdreht...


== Aufgabe 3) ==

O-Kalkül, zwei Polynome f und g, dritten Grades, zeige, dass f in O_mit_Strich (g).
Danach sollte man glaub ich, aber da bin ich mir unsicher, noch zeigen, dass irgendein Polynom vom Grad 7 nicht in O(f) ist oder so.

Zeige, dass Komplementärgraph (keine Kante <-> Kante) des gegebenen Graphen (überall Grad 3, insgesamt 10 Knoten) eine Eulertour hat (max. 9 Kanten, von 3 zu 6, 6 ist gerade, Eulertour, easy).


== Aufgabe 4) ==

Modelliere: 4 Futtermittel, 3 Nährstoffe mit Ober/Untergrenze, minimiere Preise... vermutlich (exakt?) selbe Aufgabe wie im 2019 Braindump

Stelle Dual auf, zeige (2,0,0,0) ist Optimallösung, wie heißt der verwendete Satz?


== Aufgabe 5) ==

Gegeben: LP in nicht-Standardform, 2 Variablen (eine frei, eine beschränkt), 2 Ungleichungen

Zeichne zulässige Menge,

Verwandle in Standard-Form (freie Variable aufsplitten, zwei Schlupfvariablen einführen --> 5 Variablen)

Mit primalem Simplex lösen (vermutlich im Pricing 2. Iteration laut Zeichnung fertig)


== Aufgabe 6) ==

Primal und Dual mit 4 Variablen gegeben, zeigen, dass (c_1 + 1) x_1 + (c_2 + 2) x_2 + (c_3 + 3) x_3 + (c_4 + 4) x_4 >= b^T y (indem man dies von c^T x >= b^T y mittels schwacher Dualität folgert)

Zeigen Sie: Wenn x und y zulässige Lösungen eines LP sind, dann ist auch tx+(1-t)y für t /in (0,1) eine zulässige Lösung.