Aktion	Zweigstelle	Standorte	Status	Frist	Vorbestellungen
Vorbestellen	Zweigstelle: 07., Urban-Loritz-Pl. 2a	Standorte: NN.MN Gritz / College 6a - Naturwissenschaften	Status: Entliehen	Frist: 05.12.2024	Vorbestellungen: 0

Das Buch entwickelt mathematische Grundlagen der linearen, nichtlinearen und diskreten Optimierung. Hierzu gehören Diskrete Strukturen und Algorithmen, eine ausführliche Einführung in die Komplexitätstheorie, die Grundlagen der Konvexitätstheorie, der Simplex-Algorithmus sowie die LP-Dualität und ihre Anwendungen. Methodisch zentral für viele Teile der Optimierung ist der geometrische Zugang; die zugrunde liegenden geometrischen Vorstellungen werden detailliert entwickelt und durch eine große Anzahl von Skizzen veranschaulicht. Die behandelten Probleme sind sämtlich durch reale Anwendungen motiviert; verschiedene konkrete Anwendungsbeispiele werden ausführlich besprochen. Der Methodenreichtum des Gebiets der mathematischen Optimierung wird durch vielfältige Querverbindungen zu anderen mathematischen Disziplinen sichtbar. Zahlreiche Übungsaufgaben unterstützen die Anwendbarkeit des Buches als Grundlage für Lehrveranstaltungen.

 

Der Inhalt:

Einleitung - Einstiege: Ungleichungssysteme und diskrete Strukturen - Einstiege: Algorithmen und Komplexität - Konvexitätstheorie - Der Simplex-Algorithmus - LP-Dualität

Die Zielgruppen- Studierende der Mathematik und Informatik- Studierende der Wirtschaftsmathematik und des Operations Research jeweils nach den Grundvorlesungen

 

Der Autor Prof. Dr. Peter Gritzmann lehrt am Zentrum Mathematik der Technischen Universität München.

 

 

Aus dem Inhalt:

Vorwort v / Inhaltsverzeichnis xiii // 1 Einleitung 1 / 1.1 Optimierungsprobleme 1 / 1.2 Einige Beispiele 7 / Produktionsplanung, Ernährungsplanung, Standortprobleme, / Das Zuordnungsproblem, Das Problem des Handlungsreisenden, / Rekonstruktion kristalliner Strukturen, Wire Spacing, Eine 'klassische ganzzahlige Optimierungsaufgabe' / 1.3 Standardnotation und Notationsstandards 20 / 1.4 Ergänzung: Verschiedene Formen von Lp-Aufgaben 25 / 1.5 Übungsaufgaben 28 // 2 Einstiege: Ungleichungssysteme und diskrete Strukturen 35 / 2.1 Von Gleichungs- zu Ungleichungssystemen: / Fourier-Motzkin-Elimination 35 / 2.2 Graphen 46 / Allgemeine Graphen, Hamiltonkreise und Eulertouren, Graphen / und Digraphen, Bäume und Wälder, Matchings und der Satz von Hall / 2.3 Von Basen zu diskreten Strukturen: Matroide 86 / Unabhängigkeitssysteme und Matroide, Maximierung über / Unabhängigkeitssystemen und der Greedy-Algorithmus, Minimierung / über Basissystemen, Durchschnitte von Matroiden / 2.4 Übungsaufgaben 107 // 3 Einstiege: Algorithmen und Komplexität 113 / 3.1 Algorithmische Berechnungen: Erste effiziente Methoden 113 / Algorithmen und das Halteproblem, Kodierungslänge, Polynomielle / Algorithmen, Polynomielle Berechnungen der / linearen Algebra, Erste polynomielle Algorithmen der Kombinatorik, / Orakel, polynomielle Reduktion und NP-Vollständigkeit / 3.2 Mehrstufige Entscheidungsprozesse 144 / Dynamische Optimierung, Das Rucksackproblem, Kürzeste Wege und Kantenzüge / 3.3 Einführung in die Komplexitätstheorie 173 / Alphabete, Sprachen und Probleme, Turing-Maschinen, / Entscheid- und Berechenbarkeit, Die Klassen P und NP, NP-Vollständigkeit und der Satz von Cook / 3.4 Einige NP-schwierige Optimierungsprobleme 205 / Varianten der Erfüllbarkeit Boolescher Ausdrücke und ganzzahliger / Optimierung, Hamiltonkreise und ihre Verwandten, / Partitionierungen, Normmaximierung und zulässige Teilsysteme / 3.5 Ergänzung: Nichtdeterminismus und Zufall 224 / 3.6 Übungsaufgaben 227 // 4 Konvexitätstheorie 233 / 4.1 KonvexeMengen 233 / Konvexe Mengen, Hüllen und Konvexkombinationen, Die Sätze / von Carathéodory, Radon und Helly, Polytope, Konvexität und elementare Topologie / 4.2 Trennungssätze, Kegel und linear-konvexe Optimierung 253 / Trennungssätze, Stützeigenschaften, Kegel und positive Hüllen, / Charakterisierung der Optimalität / 4.3 Darstellungssätze 272 / Extremalpunkte und Seiten, Linealitätsraum und Rezessionskegel, / Darstellungssätze für abgeschlossene konvexe Mengen, / Darstellungssätze für V- und H-Polyeder, Einige algorithmische Konsequenzen / 4.4 Ergänzung: Polarität 292 / 4.5 Ergänzung: Noch einmal verschiedene Formen von Lp-Problemen 306 / 4.6 Übungsaufgaben 308 // 5 Der Simplex-Algorithmus 315 / 5.1 Die geometrische Grundstruktur 315 / 5.2 Startvorbereitungen: Linealitätsraum und Startecke 319 / Geradenfreiheit, Finden einer Startecke: Konus, Homogenisierung und andere Methoden / 5.3 Finden einer Verbesserungskante 331 / berbestimmtheit und Basislösungen, Die Grundform des Algorithmus / 5.4 Über Zykel und ihre Vermeidung 343 / Zykel und ihre Geometrie, Perturbation, Die lexikographische Regel / 5.5 Über die Laufzeit des Simplex-Algorithmus 364 / Das Beispiel von Klee und Minty, Kombinatorischer Durchmesser von Polyedern und Hirsch-Vermutung / 5.6 Ergänzung: Kurze Pfade zum Gipfel 377 / 5.7 Übungsaufgaben 383 // 6 Lp-Dualität 387 / 6.1 Dualität linearer Programme 387 / Der Dualitätssatz, Eine Folgerung für die Komplexität linearer / Programmierung, Ein Anwendungsbeispiel: Additivität in der / diskreten Tomographie, Lagrange-Funktion und Sattelpunkte / 6.2 Clustering unter Nebenbedingungen 409 / Kontingentiertes Clustering, Power-Diagramme / 6.3 Dualität in ökonomischen Modellen 420 / Schattenpreise, Produktionsfunktionen, Koopmans' Effizienzpreistheorem, Matrixspiele / 6.4 Dualität und der Simplex-Algorithmus 445 / Der Simplex-Algorithmus für das Duale, Tableauform, Dualer Simplex-Algorithmus / 6.5 Primal-Duale Algorithmen 474 / Ein komplementaritätsbasierter Grundtyp, Ein Beispiel: Noch einmal Kürzeste Wege / 6.6 Übungsaufgaben 494 // Literaturverzeichnis 501 / Namensverzeichnis 506 / Symbolverzeichnis 509 / Stichwortverzeichnis 512