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

Wir sind thematisch kurz vor Weihnachten den Grafen- und Algorithmental ein Stück weit abgeschlossen

und ein neues Thema angefangen, die sogenannte lineare Programmierung oder lineare Optimierung,

wo es darum geht, ganz allgemein ein System von Ungleichungen mit einer also eine lineare Zielfunktion

und einem System von linearen Ungleichungen zu optimieren.

Und das allgemein spricht man von einem linearen Programm, also bitte auch immer nicht verwechseln mit Programmierung an der Stelle,

sondern das hat sich einfach historisch so ergeben, dass man dort früher von Programmen sprach,

weil natürlich dann mit auch verbunden war, eine Art der Vorgehensweise solche Probleme zu lösen,

hat aber nichts mit dem eigentlichen Programmieren zu tun.

Und Sie haben das letzte Mal dazu schon ein paar grundlegende Überlegungen angestellt,

in dem wir kleine Beispiele im R2 angeguckt haben und auch ein paar Modellierungssachen,

wo lineare Programme auftreten können.

Wir werden sehen, dass lineare Programme, wenn man so möchte, oder das Lösen von linearen Programmen

der Kernbaustein von sehr, sehr vielen linearen und ganzzeitigen Optimierungsproblemen ist.

Wir werden auch sehen, dass was wir alles bislang betrachtet haben, sowohl kürzeste Wege

oder maximale Flüsse oder Min-Cost-Flow-Probleme können als Spezialfälle von linearen Programmen aufgefasst werden.

Ob man es dann nachher so lösen wird, das ist eine andere Geschichte, aber grundsätzlich ist es ein Spezialfall dessen.

Wir werden dann auch sehen, dass was wir immer mit reduzierten Bogengewichten und so weiter bezeichnet haben,

das tritt hier jetzt dann in einem deutlich allgemeineren Kontext auf, wo wir dann wieder sehen werden,

wie die Verbindung an der Stelle ist. Wir werden sehen, lineare Programme erstmal sind ein sehr, sehr allgemeines Tool

und wir werden im Laufe dieser Vorlesung, der verbleibenden fünf Wochen haben wir ja glaube ich noch,

erstmal auch grundlegende Sachen über lineare Programme noch ein bisschen kennenlernen,

hier geometrischen Objekte stecken dort dahinter und wir werden einen ersten Algorithmus zum Lösen von linearen Programmen kennenlernen,

nämlich die Simplex Methode und die haben sie ja schon im A2 sozusagen sich ein bisschen angeguckt

und das wollen wir uns heute sozusagen das allgemeine Schema dafür uns erarbeiten.

Die Simplex Methode ist eine von drei grundsätzlichen Ansätzen zum Lösen von linearen Programmen.

Wir werden sehen, dass sie noch theoretische Defizite hat in gewisser Weise,

also das heißt, dass was das Laufzeitverhalten dieses Verfahrens betrifft bis heute noch nicht bekannt ist, wie gut es tatsächlich ist.

Also egal, egal welche, wir werden sehen an zwei Stellen gibt es sozusagen Auswahlregeln, wo man was wählen kann

und egal mit welcher Auswahlregel bislang Leute kamen, ist immer im anderen ein Beispiel eingefallen,

sodass mit dieser Auswahlregel dieses Verfahren exponentiell lange braucht.

Und das war lange Zeit, wir werden sehen dieses Simplex Verfahren ist das erste Verfahren zum Lösen von linearen Programmen,

das geht auf George Stancic zurück, das er Ende der 40er Jahre entwickelt hat, Anfang der 50er aufgeschrieben dann in Paperform,

ist das erste Verfahren zum Lösen von linearen Programmen.

Interessanterweise ist es bis heute eigentlich das Schnellste auch, also wenn es um Implementierung geht,

es gibt die zweite Methode, innere Punkte Methode, gibt es Fälle, wo die innere Punkte Methode manchmal schneller ist,

aber so im Schnitt ist nach wie vor eigentlich das Simplex Verfahren das Schnellste Verfahren und da ist, ja, das, wie soll man sagen,

das wurmt natürlich ein bisschen die Wissenschaftler, dass man einerseits, dass praktisch unheimlich gut ist das Verfahren,

aber man theoretisch noch nicht wirklich nachweisen kann, dass dem tatsächlich so ist.

Wobei theoretisch nachweisend tatsächlich so ist, muss man in Anführungszeichen setzen, man hat inzwischen nachgewiesen,

dass es im, also theoretisch nachgewiesen, dass es im Durchschnitt sehr schnell ist.

Ja, also wenn ich jetzt zufällig lineare Programme auswürfel und dann das Verfahren ansetze, dann kommt im Durchschnitt eine sehr sehr schnelle Laufzeit raus.

Ja, das geht auf Arbeiten zurück von Borgwardt Mitte der 80er Jahre oder Anfang der 80er Jahre,

wo man zumindest weiß, im Durchschnitt ist es gut, aber was natürlich mathematisch immer der Fall ist,

ist denn auch im Worst Case, also im schlechtersten Fall, wie verhält sich da so ein Algorithmus.

Und letztendlich, wenn wir unsere Laufzeitanalysen, die wir bislang gemacht haben, war immer der Worst Case Fall mit drin,

das heißt im Moment, wenn da ein, was weiß ich, ein Max-Floor-Algorithmus in n²m steht, dann hat er im schlimmsten Fall diese Laufzeit n²m gehabt.

Er konnte vielleicht auch schneller fertig sein, aber im schlimmsten Fall war es n²m.

Und eine solche polynomialen Laufzeit für den schlimmsten Fall, für den Worst Case, ist für Simplex-Verfahren bis heute noch nicht bekannt.

Wir werden nachher den Algorithmus ja noch sehen, wir werden sehen, der ist eigentlich von der Struktur her sogar am Ende relativ einfach, es sind nur 5 Schritte.