{"id":491,"date":"2014-04-09T10:49:54","date_gmt":"2014-04-09T08:49:54","guid":{"rendered":"http:\/\/www.mi.uni-koeln.de\/opt\/?page_id=491"},"modified":"2014-07-18T10:12:35","modified_gmt":"2014-07-18T08:12:35","slug":"vorlesungen","status":"publish","type":"page","link":"http:\/\/www.mi.uni-koeln.de\/opt\/veranstaltungen\/operations-research\/vorlesungen\/","title":{"rendered":"Vorlesungen"},"content":{"rendered":"
1. Mittwoch, 9. April 2014 <\/span><\/b>(pdf)<\/a><\/div>\n
TEIL I: KOMBINATORISCHE GRAPHEN-ALGORITHMEN<\/strong><\/div>\n
Kapitel 1 Einf\u00fchrung: Stabile Matchings<\/strong><\/div>\n
1.1 Grundbegriffe<\/i><\/div>\n
Def: Matching<\/div>\n
Interpretation als Massenhochzeit<\/div>\n
Def: Stabiles Matching<\/div>\n
Naiver Algorithmus mit Laufzeit n!<\/div>\n
1.2 Gale<\/a>–Shapley<\/a> Algorithmus<\/i><\/div>\n
Algorithmus<\/div>\n
Beispiel<\/div>\n
Satz: Gale-Shapley Algorithmus berechnet stabiles Matching. Insbesondere gibt es immer eines.<\/div>\n
<\/div>\n
2. Freitag, 11. April 2014<\/b><\/span> (pdf)<\/a><\/div>\n
Bem: Nur $n^2$ Heiratsantr\u00e4ge im Gale-Shapley Algorithmus.<\/div>\n
Satz: Der Gale-Shapley Algorithmus berechnet das f\u00fcr die M\u00e4nner beste stabile Matching<\/div>\n
1.3 Geometrische Modellierung<\/i><\/div>\n
Vor- und Nachteile kombinatorischer Algorithmen<\/div>\n
Vor- und Nachteile geometrischer Modellierung mit linearen Ungleichungen<\/div>\n
Codierung von stabilen Matchings mit Hilfe von Permutationsmatrizen<\/div>\n
Satz: Charakterisierung von stabilen Matchings mit linearen Ungleichungen<\/div>\n
Ausblick: Lineare Optimierung \u00fcber das Stabile Matching Polytop<\/div>\n
Kapitel 2 K\u00fcrzeste Wege<\/strong><\/div>\n
2.1 Nichtnegative Kantenl\u00e4ngen<\/i><\/div>\n
Notation: gerichteter Graph, Knoten, gerichtete Kanten, Kantenl\u00e4ngen, Kantenfolge,<\/div>\n
s-t-Weg, Abstand, s-t-Schnitt<\/div>\n
Satz: min-max Charakterisierung k\u00fcrzester Weg<\/div>\n
<\/div>\n
3. Mittwoch, 16. April 2014<\/strong> (pdf)<\/a>
\n<\/a><\/span><\/div>\n
Satz: min-max Charakterisierung k\u00fcrzester Weg<\/div>\n
2.2 Beliebige Kantenl\u00e4ngen<\/em><\/div>\n
Bsp: Rucksackproblem<\/div>\n
Algorithmus von Bellman-Ford<\/div>\n
Satz: $d_k($v$) = \\min\\{l(P) : P$ ist s-v-Kantenfolge mit $\\leq k$ Kanten$\\}$<\/div>\n
Def: gerichteter Kreis<\/div>\n
Satz: Existenz k\u00fcrzester s-t-Kantenfolgen, die Wege sind, falls Graph keine Kreise negativer L\u00e4nge enth\u00e4lt<\/div>\n
<\/div>\n
4. Mittwoch, 23. April 2014<\/strong><\/span>\u00a0(pdf)<\/a><\/div>\n
Bemerkungen zu Algorithmus von Bellman-Ford<\/div>\n
Satz: $d_n = d_{n-1}$ genau dann, wenn alle von s aus erreichbaren gerichteten Kreise nicht-negative L\u00e4nge haben<\/div>\n
2.3 Geometrische Modellierung, Potentiale<\/em><\/div>\n
Def: Potential<\/div>\n
Satz: Es existiert ein Potential genau dann, wenn alle gerichteten Kreise nicht-negative \u00a0L\u00e4nge haben<\/div>\n
Satz: geometrische Modellierung k\u00fcrzester Wege mit linearen Ungleichungen<\/div>\n
Kapitel 3 Matchings in bipartiten Graphen<\/strong><\/div>\n
3.1 Definitionen<\/em><\/div>\n
gerichteter Graph, Knoten, Kanten, Kantenfolge, Weg, Kreis, Nachbar, wegzusammenh\u00e4ngend, Zusammenhangskomponente, zusammenh\u00e4ngend, bipartit<\/div>\n
5. Freitag, 25. April 2014<\/strong><\/span>\u00a0(pdf)
\n<\/a>3.2 Matchings mit maximaler Kardinalit\u00e4t\u00a0<\/em><\/div>\n
Def: M-augmentierender Weg<\/div>\n
Satz: Entweder ist M Matching mit maximaler Kardinalit\u00e4t oder es gibt einen M-augmentierenden Weg
\nAlgorithmus zur Bestimmung eines Matchings mit maximaler Kardinalit\u00e4t<\/div>\n
Residualgraph zur Bestimmung eines M-augmentierenden Wegs in bipartiteten Graphen<\/div>\n
3.3 Das Matching Theorem von K\u00f6nig<\/em><\/div>\n
Def: Knoten\u00fcberdeckung<\/div>\n
Satz: Sei G bipartiter Graph, dann ist die maximale Kardinalit\u00e4t eines Matchings in G gleich der minimalen Kardinalit\u00e4t einer Knoten\u00fcberdeckung in G<\/div>\n
6. Mittwoch, 30. April 2014<\/strong><\/span>\u00a0(pdf)
\n<\/a><\/div>\n
3.4 Matchings mit maximalem Gewicht<\/em><\/div>\n
Def: extremes Matching<\/div>\n
Def: L\u00e4ngenfunktion<\/div>\n
Satz: Augementierung eines extremen Matchings mit Hilfe eines M-augmentierenden Weg minimaler L\u00e4nge<\/div>\n
Algorithmus: Die ungarische Methode<\/div>\n
Satz: Residualgraph hat keine gerichteten Kreise negativer L\u00e4nge<\/div>\n
\n
7. Freitag, 2. Mai 2014<\/strong><\/span>\u00a0(pdf)<\/a><\/div>\n
Kapitel 4 Fl\u00fcsse in Netzwerken<\/strong><\/div>\n
4.1 Das Max-Flow-Min-Cut Theorem<\/em><\/div>\n
Def: s-t-Fluss<\/div>\n
Lemma: Wert eines s-t-Flusses ist durch Kapazit\u00e4t eines s-t-Schnitts beschr\u00e4nkt<\/div>\n
Def: Residualgraph<\/div>\n
Lemma: Erkennung eines maximalen Flusses durch Residualgraph<\/div>\n
Theorem: Max-Flow = Min-Cut<\/div>\n
Korollar: ganzzahlige Kapazit\u00e4t => ganzzahliger maximaler Fluss<\/div>\n
Algorithmus von Ford-Fulkerson<\/div>\n
8. Mittwoch, 7. Mai 2014<\/strong><\/span>\u00a0(pdf)<\/a><\/div>\n
Satz: Endlichkeit des Ford-Fulkerson-Algorithmus f\u00fcr rationale Kapazit\u00e4ten<\/div>\n
4.2 Verbesserung des Ford-Fulkerson-Algorithmus<\/em><\/div>\n
Satz: (Dinits 1970, Edmonds-Karp 1972) Falls immer k\u00fcrzeste s-t-Wege zur Flussverbesserung gew\u00e4hlt werden, ist die Anzahl der Iterationen h\u00f6chstens |V| |A| (insbesondere unabh\u00e4ngig von den Kapazit\u00e4ten)<\/div>\n
\n
9. Freitag, 9. Mai 2014<\/strong><\/span>\u00a0(pdf)<\/a><\/div>\n
Teil II: THEORIE DER LINEAREN OPTIMIERUNG
\nKapitel 5 Polyedertheorie
\n<\/strong><\/div>\n
Lineares Programm<\/div>\n
5.1 Konvexe Mengen<\/em><\/div>\n
Def: Konvexkombination, Verbindungsstrecke, konvexe Menge<\/div>\n
Satz: Charakterisierung von konvexen Mengen<\/div>\n
\n
10. Mittwoch, 14. Mai 2014<\/strong><\/span>\u00a0(pdf)<\/a><\/div>\n
Bsp: Einheitskugel bzgl. einer Norm<\/div>\n
Def: konvexe H\u00fclle<\/div>\n
Satz: Charakterisierung der konvexen H\u00fclle<\/div>\n
Def: Polytop<\/div>\n
Def: affine Unabh\u00e4ngigkeit, Dimensions<\/div>\n
Satz: Caratheodory<\/div>\n
11. Freitag, 16. Mai 2014<\/strong><\/span>\u00a0(pdf)
\n<\/a><\/div>\n
5.2 Trenn- und St\u00fctzhyperebenen<\/em><\/div>\n
Def: Hyperebene, Halbraum, Trennhyperebene, St\u00fctzhyperebene<\/div>\n
Lemma: metrische Projektion<\/div>\n
Theorem: Existenz von Trennhyperebenen<\/div>\n
12. Mittwoch, 21. Mai 2014<\/strong><\/span>\u00a0(pdf)<\/a><\/div>\n
Def: Polyeder<\/div>\n
5.3 Extrempunkte und Ecken<\/em><\/div>\n
Def: Extrempunkt, Ecke<\/div>\n
Satz: Charakterisierung von Ecken eines Polyeders<\/div>\n
Korollar: Polyeder besitzen nur endlich viele Ecken<\/div>\n
13. Freitag, 23. Mai 2014<\/strong><\/span>\u00a0(pdf)<\/a><\/div>\n
Theorem: (Minkowski) Beschr\u00e4nktes Polyeder ist Polytop<\/div>\n
Def: Polare<\/div>\n
Lemma: Eigenschaften der Polaren<\/div>\n
Theorem: (Weyl) Polytop ist beschr\u00e4nktes Polyeder<\/div>\n
14. Mittwoch, 28. Mai 2014<\/strong><\/span>\u00a0(pdf)
\n<\/a><\/div>\n
Def: konvexer Kegel<\/div>\n
Def. und Satz: konische H\u00fclle<\/div>\n
Theorem: Polyeder sind genau die Minkowskisummen von Polytopen und konvexer Kegel<\/div>\n
5.4 Lemma von Farkas<\/em><\/div>\n
Satz: L\u00f6sbarkeitskriterium f\u00fcr lineare Gleichungssysteme<\/div>\n
Satz: Farkas Lemma<\/div>\n
Korollar: Variante von Farkas Lemma<\/div>\n
15. Freitag, 30. Mai 2014\u00a0<\/strong>(pdf)<\/a><\/div>\n
5.5 Lineare Programmierung<\/em><\/div>\n
Def: Lineares Programm (LP)<\/div>\n
Satz: Optimale L\u00f6sungen werden in Ecken angenommen<\/div>\n
Def: Primales, duales LP<\/div>\n
Satz: schwache Dualit\u00e4t<\/div>\n
Satz: Optimalit\u00e4tsbedingung, Komplementarit\u00e4tsbedingung<\/div>\n
16. Mittwoch, 4. Juni 2014 <\/strong>(pdf)<\/a><\/div>\n
Theorem: Starke Dualit\u00e4t<\/div>\n
Korollar: Variante des Dualit\u00e4tstheorems<\/div>\n
Kapitel 6 Ganzzahlige Optimierung und vollst\u00e4ndig unimodulare Matrizen
\n<\/strong><\/div>\n
6.1 Ganzzahlige lineare Programme<\/em><\/div>\n
Def: Ganzzahliges LP in Standardform<\/div>\n
Bsp: Matchingzahl eines Graphen als ganzzahliges LP<\/div>\n
Dualit\u00e4tsbeziehungen und P vs. NP-Problem (Millenium Prize)<\/a><\/div>\n
Def: Ganzzahliges Polytop<\/div>\n
17. Freitag, 6. Juni 2014 <\/strong>(pdf)<\/a><\/div>\n
6.2 Vollst\u00e4ndig unimodulare Matrizen<\/em><\/div>\n
Def: Vollst\u00e4ndig unimodulare (VU) Matrix<\/div>\n
Satz: $A$ VU, $b$ ganzzahlig, dann ist jede Ecke von $P = \\{x : Ax \\leq b\\}$ ganzzahlig<\/div>\n
Def: Ganzzahliges Polyeder<\/div>\n
Satz: $A$ VU, $b$ ganzzahlig, dann ist Polyeder $P = \\{x : Ax \\leq b\\}$ ganzzahlig<\/div>\n
Korollar: Ganzzahlige LP Dualit\u00e4t<\/div>\n
Satz: (Hoffman-Kruskal) Charakterisierung von vollst\u00e4ndig unimodularen Matrizen<\/div>\n
18. Mittwoch, 18. Juni 2014\u00a0<\/strong>(pdf)<\/a><\/div>\n
6.3 Vollst\u00e4ndig unimodulare Matrizen und bipartite Graphen<\/em><\/div>\n
Satz: Graph ist bipartit genau dann wenn seine Inzidenzmatrix vollst\u00e4ndig unimodular ist<\/div>\n
Korollar: Matchingtheorem von K\u00f6nig<\/div>\n
Korollar: Ungleichungsbeschreibung des Matchingpolytops von bipartiten Graphen<\/div>\n
19. Freitag, 20. Juni 2014\u00a0<\/strong>(pdf)<\/a><\/div>\n
Korollar: Theorem von Egervary \u00fcber gewichtete Matchings in bipartiten Graphen<\/div>\n
6.4 Vollst\u00e4ndig unimodulare Matrizen und gerichtete Graphen<\/em><\/div>\n
Satz: Inzidenzmatrizen von gerichteten Graphen sind vollst\u00e4ndig unimodular<\/div>\n
Korollar: Max-flow-min-cut Theorem<\/div>\n
20. Mittwoch, 25. Juni 2014\u00a0<\/strong>(pdf)
\n<\/a>TEIL III: ALGORITHMEN DER LINEAREN OPTIMIERUNG<\/strong><\/div>\n
Kapitel 7 Das Eliminationsverfahren von Fourier und Motzkin<\/strong><\/div>\n
7.1 Fourier-Motzkin Elimination<\/em><\/div>\n
7.2 Das L\u00f6sen von linearen Programmen mit Fourier-Motzkin Elimination<\/em><\/div>\n
7.3 Farkas Lemma mit Fourier-Motzkin<\/em><\/div>\n
21. Freitag, 27. Juni 2014\u00a0<\/strong>(pdf)
\n<\/a>Kapitel 8 Das Simplexverfahren<\/strong><\/div>\n
Algorithmus<\/div>\n
22. Mittwoch, 2. Juli 2014\u00a0<\/strong>(pdf)<\/a><\/div>\n
Satz: Simplexalgorithmus terminiert in endlich vielen Schritten<\/div>\n
Finden einer Startecke<\/div>\n
Zur praktischen und theoretischen Effizienz<\/div>\n
23. Freitag, 4. Juli 2014\u00a0<\/strong>(pdf)<\/a><\/div>\n
Kapitel 9 Die Ellipsoidmethode
\n24.\u00a0Mittwoch 9. Juli 2014<\/span>\u00a0<\/span><\/strong><\/strong>(pdf)
\n25. Freitag 11. Juli 2014<\/span>\u00a0<\/span><\/strong><\/strong><\/a>(pdf)<\/a>
\n<\/strong><\/div>\n
Kapitel 10 Die Innere-Punkte-Methode<\/strong><\/div>\n
10.1 Der zentrale Pfad
\n26.\u00a0Mittwoch 16. Juli 2014<\/span>\u00a0<\/span><\/strong><\/strong>(pdf)<\/a>
\n<\/em><\/div>\n
10.2 Der Algorithmus uns seine Analyse
\n27. Freitag 18. Juli 2014<\/span>\u00a0<\/span><\/strong><\/strong><\/a>(pdf)<\/a>
\n<\/em><\/div>\n<\/div>\n<\/div>\n<\/div>\n","protected":false},"excerpt":{"rendered":"

1. Mittwoch, 9. April 2014 (pdf) TEIL I: KOMBINATORISCHE GRAPHEN-ALGORITHMEN Kapitel 1 Einf\u00fchrung: Stabile Matchings 1.1 Grundbegriffe Def: Matching Interpretation als Massenhochzeit Def: Stabiles Matching Naiver Algorithmus mit Laufzeit n! 1.2 Gale–Shapley Algorithmus Algorithmus Beispiel Satz: Gale-Shapley Algorithmus berechnet stabiles Matching. Insbesondere gibt es immer eines. 2. Freitag, 11. April 2014 (pdf) Bem: Nur $n^2$ … „Vorlesungen“ <\/span>weiterlesen<\/a><\/p>\n","protected":false},"author":5,"featured_media":0,"parent":218,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"sidebar-page.php","meta":{"footnotes":""},"class_list":["post-491","page","type-page","status-publish","hentry"],"_links":{"self":[{"href":"http:\/\/www.mi.uni-koeln.de\/opt\/wp-json\/wp\/v2\/pages\/491","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/www.mi.uni-koeln.de\/opt\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"http:\/\/www.mi.uni-koeln.de\/opt\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"http:\/\/www.mi.uni-koeln.de\/opt\/wp-json\/wp\/v2\/users\/5"}],"replies":[{"embeddable":true,"href":"http:\/\/www.mi.uni-koeln.de\/opt\/wp-json\/wp\/v2\/comments?post=491"}],"version-history":[{"count":52,"href":"http:\/\/www.mi.uni-koeln.de\/opt\/wp-json\/wp\/v2\/pages\/491\/revisions"}],"predecessor-version":[{"id":912,"href":"http:\/\/www.mi.uni-koeln.de\/opt\/wp-json\/wp\/v2\/pages\/491\/revisions\/912"}],"up":[{"embeddable":true,"href":"http:\/\/www.mi.uni-koeln.de\/opt\/wp-json\/wp\/v2\/pages\/218"}],"wp:attachment":[{"href":"http:\/\/www.mi.uni-koeln.de\/opt\/wp-json\/wp\/v2\/media?parent=491"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}