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

Wir sind jetzt im Endspurt, was Begriffen, was das Simplex-Verfahren betrifft.

Wir haben im Prinzip das Simplex-Verfahren schon geometrisch eingeführt und jetzt geht es darum, diese wesentlichen Schritte,

zum einen überhaupt auffinden einer zulässigen Ecke, um das Verfahren starten zu können

und dann der Schritt, den wir gleich Austauschschritt nennen werden, warum wir dann klar werden,

nämlich den eben Austausch der Ecke durch eine bessere Ecke, durch Abstieg entlang einer Kante,

dass wir das Algebrage abbilden und damit algorithmisch zugänglich machen.

Dazu brauchen wir eine gewisse Grundformulierung des Polyeders und wir haben ja gesehen,

dass unsere wesentlichen Sätze, die uns sagen, das Minimum existiert und es wird auf einer Ecke angenommen

und die einzige Situation, wo das eben nicht der Fall ist, ist die, dass ich entlang von Kanten beliebig stark absteigen kann,

dass das voraussetzt, dass das Polyeder eine Ecke hat. Es muss nicht beschränkt sein, aber es muss eine Ecke haben.

Haben wir den weiteren Schritt gesehen, kann ich durch eine affine Transformation auf eine solche Grundform bringen,

die sehr dem ähnlich ist, mit dem wir mal gestartet sind. Ich habe eine Reihe von Ungleichungsbedingungen,

die ich jetzt mit kleiner gleich schreibe, nicht mit größer gleich, gegeben durch eine Matrix A, eine M-Kreuz-N-Matrix

und zusätzlich habe ich die Bedingung, dass die x alle größer gleich 0 sind. Auf diese Form kann ich es immer bringen

und die Tatsache, dass ich eine Ecke vorzuliegen habe, drückt sich dann in der Grundform aus, dass dann x gleich 0 zur Ecke wird

und x gleich 0 wiederum ist eine Ecke genau dann, das sieht man, wenn man hier x gleich 0 einsetzt, wenn der Vektor b größer gleich 0 ist.

Dadurch, dass ich hier die Vorzeichen vorgegeben habe, dass ich hier die Ungleichungen vorgegeben habe, ist das echt eine Bedingung zu sagen,

b ist größer gleich 0. Das kann ich nicht einfach so erzwingen. Jetzt haben wir aber schon ganz am Anfang gesehen,

ich kann Ungleichungen immer in Gleichungen umschreiben, indem ich sogenannte Schlupfvariablen einführe.

Hier diese Variablen y, dann ändert sich nichts an der obigen Aussage mit der Charakterisierung, dass x kleine Ecke ist.

Ich habe eben hier nur ein, ich habe die aus den Ungleichungen in Gleichungen gemacht, den Preis, den ich aber zahlen muss,

dass ich die Variablen deutlich erhöhe, dass ich jetzt hier statt n, n plus m Variablen habe.

Das wäre also die Variante mit Schlupf und schließlich die komprimierte Variante wäre zu sagen, nun gut,

ich weiß am Anfang noch nicht, dass diese spezielle Form hier vorliegt, sondern ich habe hier einfach eine rechteckige Matrix A,

das heißt, ich habe ein gewisses Gleichungssystem und ich habe eben die Vorzeichenbedingung.

In dieser Form, wo es mir nicht um die Struktur von A geht, kann ich immer obdA sagen, dass b größer gleich 0,

ansonsten multipliziere ich eben die betreffenden Gleichungen mit minus eins durch.

Das sind also die drei wesentlichen äquivalente Grundformen, also dass wir von eins nach, das eins und zwei äquivalent ist, ist klar,

also von zwei nach drei kommen, ist auch klar. Wir werden jetzt gleich sehen, wie man von drei dann auch wieder zu zwei kommt.

Die werden wir jetzt als erst mal zugrunde legen.

Hier ist das Ganze nochmal formuliert, also wir haben unser Zielfunktional, wir ändern ein kleines bisschen die Notation.

Um die Notation zu vereinfachen, wird jetzt aus der Spalte C eine Zeile C, das heißt also,

ich kann das Transponiertzeichen hier weglassen in der Formulierung des Zielfunktionales, das hat dann einen Vorteil bei der Aufstellung des sogenannten Tablos.

Ich kann mir dann einige Transponiertzeichen dann sparen beim Schreiben.

Das ist wie gesagt nochmal die Polyeder-Darstellung, die wir zugrunde legen wollen in dieser komprimierten Form

und obdA, wie gesagt, können wir jetzt hier erstmal davon ausgehen, dass b größer gleich 0 ist.

Das heißt also, die typische Situation, wir haben ein inhomogenes Gleichungssystem, das sollte immer lösbar sein, aber eben typischerweise nicht eindeutig lösbar.

Jetzt führen wir einen Begriff ein, der sich als algebraisches Äquivalent zum Begriff der zulässigen Ecke, also eine Ecke, die zum Polyeder gehört,

das soll dann eine zulässige Ecke sein, herausstellen wird und zwar in folgender Weise, das ist jetzt, wir würden jetzt den Begriff der Basis ein,

das natürlich nicht zu verwechseln mit einer Basis in einem Vektoraum, also wir sprechen jetzt hier von Basisvariablen und Nichtbasisvariablen ganz spezifisch auf dieses Eckenproblem bezogen.

Was soll das jetzt sein? Also wir haben diese Grunddarstellung, wir haben die Spalten aj der Einschränkungsmatrix,

das heißt also, wir haben damit, und aus diesen Spalten wählen wir eine Basis aus, das heißt also, wir wählen eine Basis des Spaltenraums aus,

das heißt, was wir jetzt hier als Basis betrachten, ist natürlich ganz spezifisch auch eine Basis, eben eine Basis des Spaltenraums.

Das hat jetzt Folgendes zur Folge, wir haben also insgesamt n Spalten, n ist typischerweise größer als m als die Anzahl der Zeilen

und aus diesen n Spalten wählen wir jetzt m Zeilen aus, wir können weiter davon ausgehen, dass m der Rang der Matrix A ist,

also wir können nach OBDA davon ausgehen, dass die Matrix vollen Zeilenrang hat, sonst hätten wir einfach Gleichungsbedingungen unnötig hingeschrieben.

Okay, was hat das jetzt zur Folge? Das diese Auswahl von Spalten erzeugt erstmal eine Zerlegung der Indexmenge 1 bis n,

und zwar eben in die Indizes, die zu der ausgewählten Menge gehören, das sind also m Stück, diese Indexmenge nennen wir b

und diese Menge nennen wir die Basismenge. Und dann gibt es noch das Komplement zu b, das sind also dann n minus m Stück,