Lineare und Netzwerk-Optimierung / Linear and Network-Optimization

1 Introduction and Applications.- 1.1 Linear Programs.- 1.2 Shortest Path and Network Flow Problems.- 2 The Simplex Method.- 2.1 Linear Programs in Standard Form.- 2.2 Basic Solutions: Optimality Test and Basis Exchange.- 2.3 The Fundamental Theorem of Linear Programming.- 2.4 Degeneracy and Finiteness of the Simplex Method.- 2.5 Finding a Feasible Starting Solution.- 2.6 The Revised Simplex Method.- 2.7 Linear Programs with Bounded Variables.- 3 Duality and Further Variations of the Simplex Method.- 3.1 Dual Programs and the Duality Theorem.- 3.2 Complementary Slackness Conditions.- 3.3 The Dual Simplex Method.- 3.4 The Primal-Dual Simplex Method.- 4 Interior Point Methods: Karmarkar's Projective Algorithm.- 4.1 Basic Ideas.- 4.2 One Iteration of Karmarkar's Projective Algorithm.- 4.3 The Algorithm and its Polynomiality.- 4.4 A Purification Scheme.- 4.5 Converting a Given LP into the Required Format.- 5 Introduction to Graph Theory and Shortest Spanning Trees.- 5.1 Introduction to Graph Theory.- 5.2 Shortest Spanning Trees.- 6 Shortest Path Problems.- 6.1 Shortest Dipaths with Nonnegative Costs.- 6.2 Shortest Dipaths with Negative Costs.- 6.3 Pairwise Shortest Dipaths.- 6.4 Shortest Path Problems.- 6.5 Shortest Dipath Problems and Linear Programs.- 7 Network Flow Problems.- 7.1 Definition and Basic Properties of Network Flows.- 7.2 Maximal Flows.- 7.3 Feasible Flows for NFP and the Negative Dicycle Algorithm.- 7.4 The Network Simplex Algorithm.- 8 Matchings.- 8.1 Definition and Basic Properties.- 8.2 Bipartite Matching Problems.- 8.3 Matching Problems in Arbitrary Graphs.- References.- Stichwortverzeichnis.