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

Herzlich willkommen zur Vorlesung kombinatorischer Optimierung.

Mein Name ist Alexander Martin. Ich werde die Vorlesung halten und Susanne Pape wird

mich begleiten und insbesondere bei den Übungen. Das wird das eine oder andere Mal geben, wo ich

leider terminlich verhindert bin, wo dann Susanne auch die Vorlesungen ein Stück weit übernehmen wird.

Ich möchte vielleicht erst ein paar Sachen zu uns oder selber sagen. Ich selber habe Wirtschaftsmathematik

studiert, ich nehme an ein Großteil von Ihnen tut das auch gerade. Ich fand immer diese Kombination

aus Wirtschaftswissenschaft, ein Stück Informatik und Mathematik eigentlich ganz spannend und in

der Optimierung, wo jetzt glaube ich ihre erste Vorlesung in der Optimierung ist, da treffen genau

auch diese Dinge zusammen und wir versuchen sozusagen aus mathematischer Sicht an Probleme

heranzugehen, die von wirtschaftlichen, gesellschaftlichen, anderen weiteren technischen

Interessen sind, mit Hilfe mathematischer Methoden. Und die kombinatorische Optimierung ist in dem

Sinne Einstiegsvorlesung in diese Optimierung. Wir werden verschiedene Dinge sozusagen, sind

vielleicht neu und kommen auf sie zu. Optimierung an sich haben sie vermutlich schon gekannt, weil

letztendlich aus der Analysis oder selbst in der Schule, wenn sie extremer bestimmen, ist das

eigentlich nichts anderes als ein Optimierungsproblem lösen, nur damals klassisch ein- oder

mehrdimensional jetzt in der Analysis. Wir werden versuchen nicht mit analytischen Methoden an solche

Probleme heranzugehen, sondern mit Methoden, die neuen Zugang brauchen, weil wir nicht voraussetzen

können, dass sozusagen unsere zugrunde liegenden Funktionen stetig sind. Wir werden annehmen, dass

zum Beispiel Variable nur Werte 0 oder 1 annehmen können und alles dazwischen macht keinen Sinn.

Also Beispielentscheidung fahren sie mit dem Auto oder mit dem Zug, da können sie nicht sagen, ich

verhalte mit dem Auto, halte mit dem Zug. Das heißt, sie müssen, wenn sie das mathematisch

modellieren wollen, sich entscheiden zwischen Ja und Nein, sprich mathematisch zwischen 0 oder 1 und

als einzige Lösung sind nur 0 oder 1 erlaubt, alles dazwischen eben nicht. Damit haben sie keinen

Grenzwert mehr, damit haben sie keine Ableitung mehr und trotzdem wollen sie optimieren. Und das

ist der algorithmische diskrete Zugang, also deswegen unser Gebiet nennt sich auch diskrete

Optimierung in der Mathematik, diskret jetzt nicht als Gegenteil von indiskret, dass wir nicht

verraten wollen, was wir machen, sondern das darum geht, nur dass ganz zahlige Werte auftreten können,

alles mögliche Lösungen. Also deswegen ein Stück anders als der Zugang in der Analysis.

In der kombinatorischen Optimierung werden wir in erster Linie uns erstmal mit vielen anschaulichen

Dingen beschäftigen, sprich auf Graph und Netzwerken arbeiten, dort klassische

Verfahren kennenlernen, wie kürzeste Wege, wie in jedem Navi zum Beispiel drin ist, wie Mincos Flow

Algorithmen, Malte-Community-Flow Sachen, also Themen, die im Bereich der Logistik auftreten,

bis hin zu auch Fragen der Färbung von Graphen, wie sie bei Frequenzplanung, bei Mobilfunknetzen

auftreten und dergleichen mehr. Also wir sehen, da ist ganz schnell eine Verbindung zur Praxis da,

aber andererseits werden wir sehen, dass es da auch spannende mathematische Fragestellungen gibt,

die wir versuchen wollen im Rahmen der Vorlesung zu beantworten. Das wird der erste Teil sein,

der Vorlesung, und der zweite Teil geht dann um lineare Programmierung, also nichts mit

Programmieren zu tun, sondern es sind Optimierungsprobleme, wo alle Randbedingungen

linears sind und auch die Zielfunktion linear ist. In diesem speziellen Fall gibt es einen sehr guten,

in der Praxis sehr gut funktionierenden Algorithmus, das sogenannte Simplex-Verfahren,

was wir auch im Rahmen dieser Vorlesung kennenlernen werden. Der Vorteil von dem

Verfahren ist, wie gesagt, dass es in der Praxis supergut, theoretisch super schlecht ist,

das werden wir auch noch sehen und im Laufe des Studiums sollten sie ein Stück weit bei der

Optimierung bleiben, dann noch zwei andere Verfahren kennenlernen, wovon eines theoretisch supergut ist

und praktisch super schlecht und eins, was von jedem ein bisschen was hat, also theoretisch gut

und praktisch auch ganz gut. Also es gibt drei total unterschiedliche Ansätze zum Lösen von

solchen linearen Optimierungsproblemen, wir werden in der Vorlesung eins kennenlernen und wenn sie

dabei bleiben, werden sie die anderen im Laufe des Studiums auch noch kennenlernen. So vielleicht

erstmal so ganz grob, was wir inhaltlich vorhaben, Sie haben vielleicht schon mitgekriegt, die