Dieser Audiobeitrag wird von der Universität Erlangen-Nürnberg präsentiert.

Herzlich willkommen zur heutigen Vorlesung.

Wir waren ja, oder letzte Woche hatten wir uns mit einem zentralen, grundlegenden Satz in der linearen Optimierung beschäftigt.

Dieser Satz wird offiziell als Lema bezeichnet, Farkas Lema, was letztendlich ein Trennungssatz ist, wo man feststellen kann, ob ein einfaches Zertifikat zur Hand hat,

um festzustellen, ob ein lineares Ungleichungssystem überhaupt eine zulässige Lösung hat, ja oder nein.

Und das war die Kernaussage von diesem Satz, den haben wir uns letzte Stunde sozusagen angeguckt und bewiesen, auch noch die geometrische Interpretation dazu uns angeguckt,

die da heißt, dass entweder ein Vektor B, also im Kegel eine Menge von aufspannenden Vektoren ist, oder eben es eine trennende Hübebene zwischen dem Kegel und einem Punkt oder Vektor dann entsprechend gibt.

Und heute wollen wir jetzt sozusagen dieses Ergebnis in Anführungszeichen ausschöpfen und ausschlachten, ein Stück weit.

Wir wollen uns erstmal noch in einer alternativen Formulierung angucken, die wir später dann wieder brauchen.

Und mit dem Satz dann sind wir auch in der Lage, den starken Dualitätssatz der linearen Optimierung zu beweisen.

Wir haben ja immer noch die offene Baustelle zwischen dem linearen und dem dualen.

Wir wissen bislang ja nur, dass das eine immer eine untere Schranke von dem anderen ist, aber ob da tatsächlich eine Lücke ist oder Gleichheit gilt, das ist noch offen.

Und mit Hilfe des Farkaslemmer können wir das jetzt beweisen und das wollen wir heute auch tun.

Die geometrische Interpretation war eben zu sagen, entweder das B ist eine konische Kombination der Spalten von A oder die Spalten stehen alle in einem Spitzenwinkel mit diesem Y,

in einem stumpfen Winkel mit dem B. Das heißt, das Y definiert mit dem normalen Vektor eine Hyper-Ebene, sodass die alle auf der einen Seite des Halbraums liegen und das B auf der anderen Seite.

Das war das Ergebnis der letzten Stunde. Und wir wollen jetzt das noch ein bisschen verallgemeinern.

Was heißt verallgemeinern? Das ist vielleicht das falsche Wort. Wir haben ja gesehen, dass es lineare Programme immer in unterschiedlichen Darstellungen gibt.

Hier, das ist die Standardform, so wie es das Simplex-Verfahren verwendet. Das werden wir auch nachher dann, wenn wir beim Simplex-Verfahren noch mal gucken, werden wir sozusagen genau diese Konstellation brauchen.

Der natürliche Zugang über Polyeda ist ja der Durchschnitt von endlich vielen Halbräumen. Also so machen wir es ja auch immer, wenn wir sozusagen geometrisch über Polyeda diskutieren.

Deswegen wollen wir hier jetzt noch als Corolla eine andere Variante angucken, wo wir genau diese Beschreibung von Polyedern uns angucken.

Und das ist das Corolla 1316. Da heißt dann eben, entweder hat A x kleiner gleich B eine Lösung, oder aber A transponiert, Y ist gleich Null,

Y ist größer gleich Null und B transponiert, Y ist kleiner Null.

Also das Alternativsystem sozusagen von dem hier, wenn ich A x kleiner gleich B fordere, ist auf der Seite das entsprechende.

Wie kann man sich es merken, die Faustregeln sind sozusagen wieder dieselben, wie wir schon beim Dualisieren von linearen Programmen hatten.

Wenn ich hier Ungleichungen habe, also für jede Ungleichung hier gibt es eine Variabel dort und umgekehrt.

Und wenn ich hier eine Ungleichung habe, dann ist die Variable dort vorzeigenbeschränkt, also deswegen ist Y größer gleich Null.

Wenn hier die Variabel nicht vorzeigenbeschränkt, dann habe ich hier eine Gleichung.

Das ist also H genau das Gleiche. Und warum brauchen wir es jetzt wieder, das intuitive Argument angenommen, das hätte keine Lösung.

Wie erzeuge ich damit einen Widerspruch?

Ich skaliere die Zeilen so, dass auf der linken Seite die Null steht und auf der rechten Seite eben etwas kleiner Null oder ungleich Null.

Ich kann ja hier dann entsprechend durch Skalierung das auch wieder anders rum sehen.

Gut, also wie beweisen wir das?

Wir beweisen das jetzt, indem wir einfach das auf den Fall zurückführen.

Das heißt wir machen diese Transformationen, die wir uns angeguckt haben, wie kommen wir von der Situation in diese.

Dann gehen wir von da nach da, dann machen wir die Transformation wieder rückgängig und hoffen, dann kommen wir hier raus.

Also schauen wir uns das an, den Beweis.

Also wir können das A x kleiner gleich B ist äquivalent dazu, indem ich einfach das x schreibe, also x plus minus x minus.

Das ist das eine, was ich mache.

Und ich führ zusätzlich schlupfvariablen ein, plus S größer gleich Null.

Dann kann ich das hier drüben schreiben als A x plus minus A x minus plus S ist gleich B.

Und ich habe x plus, x minus und S größer gleich Null.

So, wenn ich jetzt als, jetzt sind wir genau in dieser, jetzt nehme ich als wähle A Strich, packen wir jetzt das da rein.

Also A Strich wäre dann A plus A.

Hier seht ihr das Minus A und die Einheitsmatrix.

Ja, dann schreibt sich das ist damit äquivalent zu A Strich von x plus x minus und S ist gleich B.

Und wir haben x plus x minus und S größer gleich Null.

So, das heißt wir haben dieses System in das hier überführt, also wir sind von da nach da gegangen.

So, jetzt wenden wir an der Stelle, wissen wir dieses System hat eine Lösung oder aber, also aus dem Lemma 1314,

also aus dem Farkas Lemma folgt dieses System hat eine Lösung oder aber das folgende System hat eine Lösung.

Also A Strich transponiert y ist größer gleich Null und B transponiert y ist kleiner Null.