Herzlich willkommen zur heutigen Vorlesung. Heute sind wir wieder mal ein paar weniger.

Wir hatten uns gestern erstmal noch mal das geometrische Verständnis geholt zum Simplex-Verfahren,

haben festgestellt, dass zu diesen Basen tatsächlich Ecken gehören und dass Optimallösungen auch immer an Ecken angenommen werden.

Und damit es auch immer, wenn es eine optimale Lösung gibt, auch eine optimale Ecklösung gibt.

Gleichzeitig ist aus dem Beweis, ist noch eine ganz nette Idee abgefallen, wie man denn zu einer zulässigen Basislösung kommen kann,

wenn man denn überhaupt eine zulässige Lösung hat. Das war einfach die Idee zu sagen,

man schaut sich den Support dieses zulässigen Vektors an. Wenn der linear unabhängig ist,

machen wir Basisergänzungssatz der Linie in Algebra. Wenn die Spalten des Supports nicht linear unabhängig sind,

dann schmeißen wir solange linear Unabhängige raus, bis wir dann sozusagen den ersten Fall haben und den dann anwenden können.

Das Rausschmeißen können wir machen, ohne dass sozusagen die Zielfunktion sich verschlechtert.

Durch einen so kleinen Austausch sozusagen, indem wir sozusagen entlang des Kerns laufen,

bis wir sozusagen auf eine nächste Randbedingung treffen, die wir dann mit reinnehmen können.

Dann wollten wir jetzt sozusagen noch ein weiteres Konzept, was sozusagen eigentlich stark verbunden ist mit der linearen Programmierung,

nämlich das der Dualität. Dualität spielt eigentlich in allen Optimierungsfragen, die eine oder andere war vielleicht auch schon mal in der nicht-linearen Optimierung,

als Vorlesung spielt Dualität eine sehr wichtige Rolle. Es gibt aber ganz, weil sozusagen das ein Konzept ist,

Abschätzungen zu machen über die Qualität von Lösungen. Und in dem linearen Fall, das werden wir sehen,

da werden wir jetzt heute darauf hinarbeiten, vielleicht gehen wir dem Beweis auch heute sogar noch hin,

zu sagen, dass zwischen dem linearen und dem noch zu, im allgemeinen Fall zu definierenden Dualen tatsächlich nicht nur eine Schrankenbeziehung gilt,

das eine immer kleiner, gleich, dem mehr das andere ist, sondern dass es sogar Lösungen gibt, wo Gleichheit angenommen wird.

Und damit haben wir sogar ein Zertifikat für die Optimalität. Und wir werden dann auch später sehen, dass eigentlich, wenn man so ein Zertifikat hat

und das auch entsprechend kann, das mit sozusagen einer der wichtigen Getäne ist, um überhaupt das Potenzial zu haben,

schnelle oder auch grundsätzlich möglich polynomialer Verfahren zu kriegen. Das Simplex-Verfahren leistet das nicht,

aber die anderen Verfahren nutzen das aus, sozusagen nachher, dass es solche Zertifikate gibt.

Gut, wir haben uns jetzt gestern noch am Schluss sozusagen auf den Weg gemacht, dieses Duale zu motivieren.

Und das haben wir an einem kleinen Beispiel gemacht, dem kontinuierlichen Rucksackproblem, wo wir gesehen haben,

wie wir sozusagen zu diesem Dualen kommen, um möglichst gute Schranken für den Zielfunktionswert zu kriegen.

Wir wollen das jetzt heute in einem allgemeinen Kontext sozusagen für allgemeine LPs, oder genau gesagt auch für die LPs in Standardform tun

und dann Beziehungen zwischen diesen beiden Programmen herstellen.

Gibt es bis dahin noch Fragen zu gestern?

Gut, also wenn das nicht der Fall ist, dann schauen wir uns das duale lineare Programm an.

Das ist Kapitel 13.2, das duale Programm.

Also wir gehen davon aus, dass wir das Problem in Standardform haben.

Und die Idee, die wir ja verfolgen wollten, ist zu sagen, wir möchten sozusagen,

jetzt haben wir zwei Dinge, die ein bisschen anders sind zu dem Beispiel von gestern.

Also das eine ist, gestern haben wir maximiert, also wenn wir ein Maximierungsproblem haben, wollen wir gerne eine Schranke nach oben haben.

Wenn wir ein Minimierungsproblem haben, wollen wir gerne eine Schranke nach unten haben.

Also das heißt, wenn wir jetzt hier minimieren, hätten wir gerne hier was, wo wir schreiben können, größer gleich, irgendwas Fragezeichen.

Das zweite, was wir gesehen haben, um solche Beziehungen hinzubekommen, dass wir hier eine Abschätzung kriegen,

war ja die Idee, die Ungleichungen zu skalieren.

Das heißt, hier sozusagen mit einem Y dran zu multiplizieren, sodass, ja was brauchen wir jetzt?

Wir brauchen einerseits, um das hinzubekommen, müssen wir dafür sorgen, dass dieses Y transponiert A immer kleiner als das C ist,

damit ich hier sozusagen diese Beziehung kriegen kann.

Also ich brauche Y transponiert A kleiner gleich dem C.

Und ich möchte natürlich, hier oben kriege ich dann auf der rechten Seite das B transponiert Y.

Und das möchte ich jetzt so groß wie möglich machen, also schreibe ich hier einen Max davor.

Also wenn man das jetzt nochmal, also die Intuition, jetzt rechnen wir es nochmal genau nach, dass das auch stimmt.

Also wir nehmen jetzt sozusagen Skalare, also ein Vektor Y aus dem R hoch M.

Und wenn ich das jetzt sozusagen hier mal durchmultipliziere, dann kriege ich ja Summe YiAiX für i gleich 1 bis M.

Das ist dann das Gleiche wie auf der rechten Seite Summe Yi gleich 1 bis M YiBi.

Also ich skaliere jede und addiere die sozusagen auf.