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

Okay, hallo. Also bevor wir anfangen, habe ich noch eine ganz kurze Anmerkung zu der Hausübung.

Und zwar ist einigen von euch aufgefallen, dass bei der H29C ein kleiner Fehler ist. Und zwar ist

es diese Aufgabe mit dem Greedy-Algorithmus und dem Binpacking. Und man soll bei der C so zwei

Ungleichungen zeigen. Und da ist einigen von euch aufgefallen, dass diese Ungleichung nicht stimmt,

wenn alle AIs gleich Null sind. Von daher nimmt bei der H29C bitte mal an, dass mindestens ein AI

ungleich Null ist. Und dann kann man die beiden Ungleichungen auch zeigen. Und das ist, glaube

ich, der interessante Fall. Wenn alle AIs Null sind, dann ist die ganze Binpacking irgendwie

sinnlos. Also von daher nimmt ruhig mal an, dass die positiv sind. Gut, dann machen wir jetzt heute

mit den linearen Programmen weiter. Und zwar hatten wir ja gestern schon mal kurz angefangen

zu definieren, was so ein lineares Programm ist und uns ein paar Beispiele für lineare Programme

angeguckt. Und heute geht es jetzt darum, mal zu überlegen, wie man so lineare Programme

dann löst. Das führt im Endeffekt dann auf den Simplex-Algorithmus. Den werden wir heute dann

wahrscheinlich nicht mehr schaffen. Der kommt dann nach Weihnachten im Januar. Aber heute so

mal ein paar Vorüberlegungen und Motivationen zum Simplex. Also wir waren im Kapitel 11.

Und bevor ich jetzt mit dem mit 11.1 anfange, mit der Motivation zum Simplex, mag ich mal kurz

noch ein Kapitel 11.0 einfügen, wo es darum geht, wie kann ich denn so lineare Programme

eigentlich grafisch, also per Hand, lösen, wenn ich nicht allzu viele Variablen habe.

So, und wirklich schön zeichnen kann ich es eigentlich nur, wenn ich zwei Variablen habe.

Bei drei geht es vielleicht gerade auch noch so, aber danach wird es schwierig, das wirklich

schön zu zeichnen. Gut, also schauen wir uns vielleicht einfach mal ein Beispiel an und machen

das anhand dieses Beispiels. Also ich habe ein Maximierungsproblem. Ich maximiere x1 plus 2x2

unter der Nebenbedingung, dass x2 kleiner als 2 ist und x1 plus x2 kleiner als 3 und meine

Variablen sollen positiv sein. Und was man als erstes immer mal machen sollte, ist, sich

den zulässigen Bereich zu zeichnen.

Dann machen wir das doch mal. So, auf jeden Fall sind x1 und x2 größer als 0, das heißt,

es reicht sich den Ortanden anzugucken. Dann soll laut der ersten Ungleichung x2 kleiner

als 2 sein, also alle Punkte hier drunter. Und die zweite Ungleichung sagt, dass das

x1 plus x2 kleiner als 3 sein soll. Das wäre dann die Ungleichung. Und kleiner ist alles,

was hier drunter ist, also der zulässige Bereich wäre jetzt das hier. So, an diesem

zulässigen Bereich wollen wir jetzt das Optimum finden. Und das kann man so machen, indem

man einfach die Zielfunktion mal gleich irgendeinen Wert eins, 0, 5 und so weiter und zeichnet

die entsprechenden Graden hier ein. Also zum Beispiel x1 plus 2x2 gleich 0 sieht folgendermaßen

aus, ungefähr so.

Also das ist die Niveau hier zu x1 plus 2x2 gleich 0. Also alle Punkte auf dieser Graden

erfüllen diese Gleichung x1 plus 2x2 gleich 0, sprich alle Punkte auf dieser Graden haben

denselben Zielfunktionswert, nämlich 0. Na gut, also hier liegt jetzt im zulässigen

Bereich nur der Nullpunkt, alle anderen sind eh nicht zulässig, aber dieser eine Zielfunktionswert

hat halt, also der Nullpunkt hat halt den Zielfunktionswert 0. Wichtig ist jetzt, alles,

was hier drunter ist, erfüllt x1 plus 2x2 kleiner gleich 0 und alles, was hier drüber

liegt erfüllt x1 plus 2x2 größer gleich 0. So und da wir jetzt möglichst großen Zielfunktionswert

suchen, der Zielfunktionswert hier oben ja größer gleich 0 ist, also in der Richtung

größer Wert, macht es halt auch Sinn in der Richtung nach einem neuen Zielfunktionswert

zu suchen, also nach einem besseren. Also könnten wir uns zum Beispiel nochmal eine

andere Niveaunlinie angucken, zum Beispiel die hier. Auf dieser Linie erfüllen alle

Punkte den Wert x1 plus 2x2 gleich 2, also auch auf dieser Linie haben alle Punkte denselben

Zielfunktionswert, nämlich 2 und der ist ja jetzt schon mal besser als der Zielfunktionswert

0. Interessant sind natürlich auch nur hier wieder die Punkte im zulässigen Bereich,

alles außerhalb ist halt nicht zulässig. So jetzt sehen wir auch hier wieder, alles

hier unteren hat einen Wert kleiner als 2, hier oben ist größer als 2 und wir wollen