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

Herzlich willkommen zur heutigen Vorlesung. Wir haben uns letzte Woche damit beschäftigt,

das Simplex-Verfahren. Das haben wir in seinen Grundzügen kennengelernt, also die Grundversion,

und haben auch nachgewiesen, dass wenn das Verfahren denn stoppt, dann tatsächlich die

korrekte Antwort gibt. Was noch offen ist, ist, dass es tatsächlich stoppt. Und auch das zweite,

was offen ist, wie man denn tatsächlich das Verfahren in Gang bringt, weil wir haben bislang

ja immer angenommen, dass wir schon zumindest mal eine primal zulässige Basislösung haben. Und

diese zwei Fragen, die wollen wir auch noch beantworten, aber bevor wir das tun, wollen

wir erstmal ein bisschen ein geometrisches Verständnis über das Verfahren und eigentlich

auch das grundlegende Problem, nämlich lineare Programme bekommen. Und die zulässigen Mengen von

linearen Programmen sind nämlich genau Polyeder. Und da haben wir das letzte Mal die Grundbegriffe

dafür kennengelernt, was ist überhaupt ein Polyeder, und haben schon mal die ersten

Eigenschaften wie Konzumixität und solche Dinge nachgewiesen, sind da stehen geblieben bei der

Definition, was Extremalmengen sind. Und die wollen wir heute etwas genauer analysieren,

weil wie wir sehen werden, werden Optimallösungen von linearen Programmen immer auf solche

Extremalmengen angenommen und sprich man kann sogar reduzieren, wenn es den Ecken gibt, auch

immer an den Ecken, also sprich den eindimensionalen oder nulldimensionalen Extremalmengen. Das steht

heute auf dem Programm und wenn wir das geschafft haben, mal schauen, ob wir das heute noch schaffen

oder dann morgen ist, gibt es nämlich ein zusätzliches oder interessantes Konzept,

nämlich das der Dualität bei dem Lösen von Optimierungsproblemen. Das heißt, wie können

wir den tatsächlichen Nachweis einer Optimalität führen und dazu werden wir ein zweites Problem

einführen, wo wir sehen werden, dass das ganz interessante Eigenschaften hat, nämlich zum

einen, dass es immer eine Schranke liefert für das eigentliche Problem und wie wir sehen werden,

in der Optimalität letztendlich sogar Gleichheit zwischen dem Dualen und dem ursprünglich primalen

Problem existieren. Das ist dann einer der zentralen Sätze oder der zentrale Setz, wenn

überhaupt, der linearen Programmierung, nämlich der starke Dualitätssatz, dass sozusagen

diese Werte immer übereinstimmen. Aber das schauen wir uns dann im Detail genauer an,

wenn wir entweder heute gegen Ende oder morgen mit dem Themenbereich dann beginnen. Gibt

es erstmal noch Fragen zu dem, was wir letzte Woche besprochen hatten, Simplex-Verfahren,

die Grundversion, die ersten Begriffe zu Polyedertheorie. Gut, wenn das nicht der Fall ist, dann schauen

wir uns nochmal an. Wir sind stehen geblieben bei das letzte Mal, was eine Extremalmenge ist.

Ich mache nochmal die Kurzversion an die Tafel, also eine Menge E, Teilmenge E einer konvexen

Menge K, heißt Extremalmenge von K, falls mit, falls aus Z aus E und Z gleich Lambda x plus

1 minus Lambda y mit dem Lambda echt zwischen 0 und 1 folgt, dass auch x und y aus E sein

müssen. Also wenn ich einen Punkt aus einer Extremalmenge nehme, ja und ich kann den hier

konvex kombinieren, echt konvex kombinieren, dann halt, dann impliziert es, dass die beiden

Punkte auch in dieser Menge liegen müssen. Also das klassische Bild dazu ist sozusagen,

was hier steht, ist, wenn ich einen Punkt habe, wie sagen wir mal hier, habe ich das Z, das

liegt jetzt hier, kann das ein Extremalpunkt sein? Nein, warum? Weil letztendlich geometrisch

heißt das, ich habe ein kleines geraden Stück sozusagen, was ich um diesen Punkt herumlegen

kann, sodass diese beiden Punkte auch sozusagen aus dieser Extremalmenge sind und diesen konvex

kombinieren. Wie ist es hier? So, denn die einzige Möglichkeit, einen Punkt hier sozusagen

konvex zu kombinieren, sodass beide Punkte, das x und das y, ja, die müssen beide aus

dem k sein, ja, um das zu machen, ist, so kann ich es nicht machen, ja, weil dann wäre dieser

Punkt außerhalb von meiner zulässigen Menge k, ja, das heißt die einzige Chance, den hier

konvex zu kombinieren, ist das x dahin zu legen und das y dahin, ja, sodass ich sozusagen

das direkt auf dieses geraden Stück lege, das heißt, das Teil hier selber wäre also

eine Extremalmenge, also hier, ja, weil die einzige Chance, egal welchen Punkt ich hier

drauf nehme, den zu kombinieren, muss ich Punkte aus der blauen Menge nehmen, ja, jeder

andere müsste ich einen aus dem unterflässigen Bereich nehmen. Und die kleinsten Mengen,