A few years ago nobody would have anticipated that in connection with degeneracy in Linear Programming quite a new field. could originate. In 1976 a very simple question has been posed: in the case an extreme- pOint (EP) of a polytope is degenerate and the task is to find all neighbouring EP's of the degenerate EP, is it necessary to determine all basic solutions of the corresponding equalities system associated with the degenerate EP -in order to be certain to determine all neighbours of this EP? This question implied another one: Does there exists a subset of the mentioned set of basic solutions such that it suffices to find such a subset in order to determine all neighbours? The first step to solve these questions (which are motivated in the first Chapter of this book) was to define a graph (called degeneracy graph) the nodes of which correspond to the basic solutions. It turned out that such a graph has some special properties and in order to solve the above questions firstly these properties had to be investigated. Also the structure of degeneracy graphs playes hereby an important role.
Because the theory of degeneracy graphs was quite new, it was necessary to elaborate first a completely new terminology and to define new notions. Dr.
1. Introduction.- 2. The Concept of Degeneracy.- 3. Degeneracy Graphs.- 3.1 The concept of degeneracy graphs.- 3.2 Properties of degeneracy graphs.- 3.2.1 Properties of degeneracy graphs in case of simple degeneracy.- 3.2.2 Properties of degeneracy graphs in case of multiple degeneracy.- 3.3 Degeneracy tableaux.- 4. On the Number of Nodes of Degeneracy Graphs.- 4.1 The maximum number of nodes of degeneracy graphs.- 4.2 The density of degeneracy tableaux.- 4.3 The minimum number of nodes of degeneracy graphs.- 4.4 On the existence and uniqueness of ?xn-degeneracy graphs.- 4.5 An algorithm for determining the number of nodes of degeneracy graphs.- 5. A Method to Solve the Neighbourhood Problem.- 5.1 Examples of the occurrence of the neighbourhood problem.- 5.1.1 The neighbourhood problem in connection with sensitivity analysis.- 5.1.2 The neighbourhood problem in bottleneck linear programming.- 5.2 Solution of the neighbourhood problem by means of degeneracy graphs.- 5.2.1 On the existence of N-minimal trees of a positive degeneracy graph.- 18.104.22.168 The existence of N-minimal trees in case of simple degeneracy.- 22.214.171.124 The existence of quasi-N-minimal trees in case of multiple degeneracy.- 5.2.2 The N-tree method for solving the neighbourhood problem.- 126.96.36.199 The principle of the N-tree method.- 188.8.131.52 Algorithmic description of the procedure.- 184.108.40.206 The N-tree algorithm in programmable form.- 220.127.116.11 Some explanations with respect to TREE and ALL.- 5.2.3 On the efficiency of the N-tree method.- 18.104.22.168 Comparison of TREE and ALL.- 22.214.171.124 Estimations with respect to the number of nodes of TREE-solutions and N-trees.- 5.2.4 On the application of the N-tree method.- Appendices.- A. Basic concepts of linear programming and of theory of convex polytopes.- B. Basic concepts of graph theory.- C. On 2xn-degeneracy graphs.- D. Flow-charts.- References.- Index of symbols.- Index of terms.
Series: Lecture Notes in Economic and Mathematical Systems
Number Of Pages: 132
Published: March 1986
Publisher: Springer-Verlag Berlin and Heidelberg Gmbh & Co. Kg
Country of Publication: DE
Dimensions (cm): 23.39 x 15.6
Weight (kg): 0.21