Degeneracy graphs and simplex cycling
著者
書誌事項
Degeneracy graphs and simplex cycling
（Lecture notes in economics and mathematical systems, 357）
Springer-Verlag, c1991
- : gw
- : us
大学図書館所蔵 件 / 全42件
-
該当する所蔵館はありません
- すべての絞り込み条件を解除する
注記
Bibliography: p. [180]-194
内容説明・目次
内容説明
Many problems in economics can be formulated as linearly constrained mathematical optimization problems, where the feasible solution set X represents a convex polyhedral set. In practice, the set X frequently contains degenerate verti- ces, yielding diverse problems in the determination of an optimal solution as well as in postoptimal analysis.The so- called degeneracy graphs represent a useful tool for des- cribing and solving degeneracy problems. The study of dege- neracy graphs opens a new field of research with many theo- retical aspects and practical applications. The present pu- blication pursues two aims. On the one hand the theory of degeneracy graphs is developed generally, which will serve as a basis for further applications. On the other hand dege- neracy graphs will be used to explain simplex cycling, i.e. necessary and sufficient conditions for cycling will be de- rived.
目次
1. Introduction.- 2. Degeneracy problems in mathematical optimization.- 2.1. Convergence problems in the case of degeneracy.- 2.1.1 Cycling in linear complementarity problems.- 2.1.2 Cycling in network problems.- 2.1.3 Cycling in bottleneck linear programming.- 2.1.4 Cycling in integer programming.- 2.2 Efficiency problems in the case of degeneracy.- 2.2.1 Efficiency loss by weak redundancy.- 2.2.2 Efficiency problems from the perspective of the theory of computational complexity.- 2.3 Degeneracy problems within the framework of postoptimal analysis.- 2.4. On the practical meaning of degeneracy.- Summary of Chapter 2.- 3. Theory of degeneracy graphs.- 3.1. Fundamentals.- 3.1.1 The concept of degeneracy.- 3.1.2 The graphs of a polytope.- 3.1.3 Degeneracy graphs.- 3.2 Theory of ? x n-degeneracy graphs.- 3.2.1 Foundations of the theory of finite sets.- 3.2.2 Characterization of ? x n-degeneracy graphs.- 3.2.3 Properties of ? x n-degeneracy graphs.- 3.3. Theory of 2 x n-degeneracy graphs.- 3.3.1 Characterization of 2 x n-degeneracy graphs.- 3.3.2 Properties of 2 x n-degeneracy graphs.- Summary of Chapter 3.- 4. Concepts to explain simplex cycling.- 4.1. Specification of the question.- 4.2 A pure graph theoretical approach.- 4.2.1 The concept of the LP-degeneracy graph.- 4.2.2 Characterization of simplex cycles by means of the LP-degeneracy graph.- 4.3 Geometrically motivated approaches.- 4.3.1 Fundamentals.- 4.3.2 Characterization of simplex cycles by means of the induced point set.- 4.3.3 Properties of the induced point set.- 4.3.4 Characterization of simplex cycles by means of the induced cone.- 4.4 A determinant approach.- 4.4.1 Terms and foundations.- 4.4.2 Characterization of simplex cycles by means of determinant inequality systems.- Summary of Chapter 4.- 5. Procedures for constructing cycling examples.- 5.1 On the practical use of constructed cycling examples.- 5.2 Successive procedures for constructing cycling examples.- 5.2.1 Modification of a row in the initial tableau.- 5.2.2 Modification of a column in the initial tableau.- 5.2.3 Addition of a column to the initial tableau.- 5.2.4 Addition of a row to the initial tableau.- 5.2.5 Combination of construction steps.- 5.2.5.1 Successive modification of rows.- 5.2.5.2 Successive addition of columns.- 5.2.6 Open questions in connection with the practical performance of the procedures.- 5.3 On the construction of general cycling examples.- Summary of Chapter 5.- A. Foundations of linear algebra and the theory of convex polytopes.- B. Foundations of graph theory.- C. Problems in the solution of determinant inequality systems.- References.
「Nielsen BookData」 より
