"Lineare und diskrete Optimierung 001.ps.gz" - читать интересную книгу автораLineare und Diskrete Optimierung Manuskript zur Vorlesung WS 1996/1997 Uwe Zimmermann Abteilung Mathematische Optimierung Technische Universit"at Braunschweig Braunschweig, den 1. Oktober 1996 Inhaltsverzeichnis I Lineare Optimierung 3 1 Faktorisierungstechniken . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 2 Explizite Behandlung nichtkanonischer Systeme . . . . . . . . . . . . . . . . 14 3 Duale Simplexverfahren . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 4 Matrixspiele . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 5 Sensitivit"atsanalyse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 6 Darstellung von Polyedern . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 7 Dekomposition linearer Optimierungsaufgaben . . . . . . . . . . . . . . . . 51 8 Parametrische Kosten . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 9 Parametrische Beschr"ankungen . . . . . . . . . . . . . . . . . . . . . . . . . 73 II Diskrete Optimierung 83 4.1 Projektplanung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122 4.2 Transportproblem als Flussproblem . . . . . . . . . . . . . . . . . . . 125 4.3 Kilterbedingungen beim Transportproblem . . . . . . . . . . . . . . 125 5 Vollst"andige Unimodularit"at . . . . . . . . . . . . . . . . . . . . . . . . . . . 125 6 Vollst"andig Dual Ganzzahlige Systeme . . . . . . . . . . . . . . . . . . . . . 133 7 Schnittebenenverfahren . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136 8 Rucksackprobleme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 146 9 Approximative Algorithmen . . . . . . . . . . . . . . . . . . . . . . . . . . . 153 9.1 0-1 Rucksackprobleme . . . . . . . . . . . . . . . . . . . . . . . . . . 157 10 Relaxation und Dualit"at . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 159 11 Maximale submodulare Fl"usse . . . . . . . . . . . . . . . . . . . . . . . . . . 171 11.1 Submodulare Polyeder P (h) . . . . . . . . . . . . . . . . . . . . . . . 171 11.2 Aktive Restriktionen (Mengen) S 2 F zu y 2 P (h) . . . . . . . . . . 172 11.3 Minimale aktive Mengen S(i) zu y 2 P (h) . . . . . . . . . . . . . . . 172 11.4 Submodulare Fl"usse (Edmonds, Giles 1976) . . . . . . . . . . . . . . 172 11.5 Aktive Menge S 2 F . . . . . . . . . . . . . . . . . . . . . . . . . . . 172 11.6 Erweiterungen von Gx . . . . . . . . . . . . . . . . . . . . . . . . . . 173 1 2 INHALTSVERZEICHNIS 11.7 @\Sigma ; @0 "uber E+ [ E\Gamma bzw. E0 . . . . . . . . . . . . . . . . . . . . . . 173 11.8 Geeignete Kreise C in Gx . . . . . . . . . . . . . . . . . . . . . . . . 175 11.9 Maximale submodulare Fl"usse . . . . . . . . . . . . . . . . . . . . . 178 11.10 KW-Methode . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 178 11.11 Lexikographische KW . . . . . . . . . . . . . . . . . . . . . . . . . . 179 11.12 Submodulare Flusspolyeder ("uber G) . . . . . . . . . . . . . . . . . . 179 12 Submodulare Fl"usse mit minimalen Kosten . . . . . . . . . . . . . . . . . . 181 12.1 Inkrementgewichte . . . . . . . . . . . . . . . . . . . . . . . . . . . . 181 12.2 Kurze negative Kreise . . . . . . . . . . . . . . . . . . . . . . . . . . 181 12.3 Stark ff-zusammenh"angende Graphen . . . . . . . . . . . . . . . . . 182 12.4 Orientierung ungerichteter Graphen . . . . . . . . . . . . . . . . . . 182 12.5 Umorientierungen . . . . . . . . . . . . . . . . . . . . . . . . . . . . 183 A Simplexverfahren und duale Programme 185 B Trennungss"atze 193 11. MAXIMALE SUBMODULARE FL "USSE 171 11 Maximale submodulare Fl"usse Submodularit"at V endlich, ;; V 2 F ` 2V Verband. h : F ! R heisst submodular, falls |
|
|