So, herzlich willkommen zur heutigen Vorlesung.

Wir haben uns ja gestern mit dem Farkaslemmer sozusagen intensiv beschäftigt und die Konsequenzen

daraus, den Dualitätssatz bewiesen.

Man mungelt ja häufig, was ist zuerst da, der Dualitätssatz oder das Farkaslemmer,

weil wenn man genau guckt, ist es ja eigentlich, kann man mit dem einen das eine beweisen,

mit dem anderen das andere und hin und her, also je nachdem, was man will, man zuerst

beweist, was nicht, was ist zuerst da, die Hände oder das Ei, so ein bisschen da auch.

Also manchmal kann man das genauso gut andersherum aufziehen.

Und den Dualitätssatz, wenn man möchte, auf die Art beweisen und damit dann mit dem

Dualitätssatz, das Farkaslemmer, was manche auch tun.

Aber wie auch immer, ich finde immer diesen geometrischen Zugang eigentlich erstmal über

die Existenz von Lösungen von Ungleichungssystemen eigentlich den sympathischen und dann geht

man zu der Optimierungsfragestellung über.

Also wir wissen jetzt sozusagen, lineare Programme sind solche, da gibt es das Duale,

das Duale vom Dualen ist wieder das Primale und wir wissen, dass die Optimallösungen

des Primalen und des Dualen übereinstimmen.

Und wenn wir nochmal das rückwirkend schauen, was wir bislang in der Vorlesung so gemacht

haben, dann ist das häufiger schon aufgetreten.

Auch bei Beispielen Min-Cost-Flow-Problem, Max-Flow-Problem, Max-Flow-Problem, da war es

explizit, da konnte man sogar das Duale, diese Variablen des Dualen, eine Interpretation

geben.

Im Moment sind ja die Dualvariablen, sage ich mal, immer skalare von den Ungleichungen

des Primalen.

Bei einem Max-Flow-Min-Cut entsprechen sozusagen die Dualvariablen schnitten, da ist ein direkt

zusätzliches grafisches Objekt damit verbunden.

Das ist natürlich nicht immer der Fall.

Wir werden heute noch eine kleine Interpretation sehen, dass man gerade in wirtschaftlichen

Anwendungen diese Dualvariablen gerne auch als sogenannte Schattenpreise interpretieren

kann.

Das kommt uns heute auch noch an, bevor wir das tun, noch eine wichtige Konsequenz oder

Eigenschaft, die solche Optimallösungen haben.

Bislang haben wir ja nur die Eigenschaft, dass wenn ich eine Optimallösung vom Primalen

und eine Optimallösung vom Dualen habe, dann stimmen die Zielfunktionswerte überein.

Man kann aber deutlich mehr sagen und das ist das, was dann zu dem Satz des Komplementären

Schlups führt, dass nämlich sozusagen Komplementarität herrscht.

Das heißt, wenn eine Variabe im Einfall positiv ist, muss die zugehörige Ungleichung mit

Gleichheit erfüllt sein und umgekehrt.

Da ist eine 1 zu 1 Beziehung, das heißt, man kann noch tiefer sozusagen Dinge ausschöpfen

aus den zugehörigen Lösungen, nicht nur was den Zielfunktionswert betrifft.

Das steht heute auf dem Programm und je nachdem, wie weit wir da kommen, kann es sein, dass

wir noch mit dem letzten Kapitel der Vorlesung beginnen.

Wir haben ja noch ein paar offene Baustellen, was das Verfahren betrifft.

Das Terminieren haben wir immer noch offen und wie fängt das Simplex-Verfahren an?

Das wollen wir uns dann anschließend noch angucken und je nachdem, was Zeit bleibt,

auch noch ein bisschen in die Details gehen, wie man so ein Verfahren eigentlich gut implementiert.

Bislang ist es ja rein von außen betrachtet, zweimal lösen von Gleichungssystem, Vektor

mal Matrix und Minimumsbildung.

Mehr steckt da eigentlich ja nicht dahinter.

Dass man das gut und weniger gut implementieren kann, liegt vielleicht nahe, aber da gibt es

einige sehr, sehr interessante Tricks, in Anführungszeichen, die auch sozusagen mathematisch