Book:Claude Berge/Programming, Games and Transportation Networks

From ProofWiki
Jump to navigation Jump to search

Claude Berge and A. Ghouila-Houri: Programming, Games and Transportation Networks

Published $\text {1965}$, Methuen and Co. Ltd. (translated by Maxine Merrington and C. Ramanujacharyulu).
Translated from:

Programmes, Jeux et Réseaux de Transport


Subject Matter


Contents

Preface
Translator's Note (Maxine Merrington)
Part I: General Theory of Convex Programming (by A. Ghouila-Houri)
1. Preliminary ideas: sets, vector spaces
1.1 Sets
1.2 Vector spaces
1.3 Dimension of a vector space
1.4 Linear manifolds. Cones
1.5 Convex sets
1.6 Convex functions
2. Preliminary ideas: topological properties of the space $\R^n$
2.1 Scalar product. Norm
2.2 Open and closed sets
2.3 Limits. Continuous functions
2.4 Compact sets
2.5 Numerical semicontinuous functions
3. Properties of complex sets and functions in the space $\R^n$
3.1 Separation theorems
3.2 Theorem on supporting planes. Polytopes
3.3 Intersections of convex sets
3.4 Minimax theorem. Farkas-Minkowski theorem
3.5 Sion's theorem
4. Programming and associated problems
4.1 Differentiable functions
4.2 Kuhn and Tucker multipliers
5. Convex programmes with linear constraints
5.1 Associated problem
5.2 Duality in linear programming
5.3 The simplex method
5.4 Non-linear programming
5.5 Quadratic programming
5.6 Conjugate functions
5.7 Duality in certain non-linear programmes
6. Games of strategy
6.1 Introduction
6.2 Strictly determined games
6.3 Eluding games
6.4 Solution of a game by linear programming
6.5 Solution of a game by successive approximations
Bibliography to Part I


Part II: Problems of Transportation and of Potential (by C. Berge)
7. Cycles and coboundaries of a graph
7.1 General remarks on graphs
7.2 Cycles and coboundaries, lemma on coloured arcs
7.3 Strongly connected graphs and graphs without circuits
7.4 Trees and cotrees
7.5 Planar graphs
8. General study of flows and potential differences
8.1 Flow and potential difference
8.2 Matrix analysis of flows and potential differences
8.3 The transportation problem
8.4 New formulation of the transportation problem
8.5 The fundamental duality theorem
9. Flow algorithms
9.1 The path problem
9.2 The problem of the shortest path
9.3 The problem of the shortest spanning tree
9.4 The generalized problem of the shortest path
9.5 The problem of the maximum potential difference
9.6 The problem of the maximum flow
9.7 The generalized problem of maximum flow
9.8 The trans-shipment problem
9.9 The restricted problem of potential
9.10 The general transportation problem
10. Problems related to the transportation problem
10.1 General study of a symmetric transportation network
10.2 The transportation network with multipliers
10.3 Special problems of maximum flow
10.4 Special problems of flow and potential difference
Exercises
Bibliography to Part II
Index


Next


Source work progress