Degeneracy Graphs and Simplex Cycling
- PDF / 19,936,801 Bytes
- 211 Pages / 481.89 x 691.65 pts Page_size
- 83 Downloads / 190 Views
357 Peter Zornig
Degeneracy Graphs and Simplex Cycling
Springer-Verlag Berlin Heidelberg New York London Paris L--""'¥""'--I
Tokyo Hong Kong Barcelona Budapest
Editorial Board
H.Albach M.Beckmann (Managing Editor)
P. Dhrymes G. Fandel G. Feichtinger W. Hildenbrand W. Krelle (Managing Editor) H. P. Kunzi K. Ritter U. Schittko P. Schonfeld R. Selten W. Trockel Managing Editors
Prof. Dr. M. Beckmann Brown University Providence, RI 02912, USA Prof. Dr. W. Krelle Institut fUr Gesellschafts- und Wirtschaftswissenschaften der Universitiit Bonn Adenauerallee 24-42, D·5300 Bonn, FRG
Author
Peter Zornig Universitiit Bochum Sprachwissenschaftliches Institut Postfach 102148, W·4630 Bochum 1
ISBN-13: 978-3-540-54593-4 001: 10.1007/978-3-642-45702-9
e-SBN-13: 978-3-642-45702-9
This work is subjectto copyright. All rights are reserved, whether the whole or part ofthe material is concerned, specifically the rights of translation, reprinting, re-use of illustrations, recitation, broadcasting, reproduction on microfilms or in other ways, and storage in data banks. Duplication ofthis publication or parts thereof is only permitted under the provisions ofthe German Copyright Law of September 9, 1965, in its current version, and a copyright fee must always be paid. Violations fall under the prosecution act of the German Copyright Law.
© Springer-Verlag Berlin Heidelberg 1991 Typesetting: Camera-ready by author
42/3140-543210 - Printed on acid-free paper
Foreword
The first monograph on -Degeneracy Problems· appeared 1986 as -Degeneracy Graphs and the Neighbourhood Problem- by H.-J. Kruse as No 260 of Lecture Notes. The contents of that book was based upon a simple problem of degeneracy in linearly constraint optimization problems which has been posed in 1976. Since then the literature concerning degeneracy grew and a part of the corresponding research throughout the world has been devoted to the theory and application of degeneracy graphs. It turned out that the better should be the use of degeneracy graphs to solve practical problems of various kind the more theoreti~ knowledge about such graphs is needed. Just to mention one of such problems, let us remind of the cycling of the simplex method. This phenomenon is known since the beginning of the SO-ies and caused some trouble. Several "anticycling" methods have been elaborated as the time passed and even in the late SO-ies new proposals have been published. Strange enough, there has been no publication in which a trial was made to explain this phenomenon, i.e. to pose the question "When or under which conditions simplex-cycling occurs?-. The author of this book makes a valuable contribution to the theory of the degeneracy graphs and answers the above question. Based on his results the research into degeneracy and degeneracy graphs can now turn to new unsolved degeneracy problems, which would remain unsolvable without the knowledge presented in this book. Hagen, May 1991
Tomas Gal
Acknowledgements The present publication is based on my doctoral thesis which was submi
Data Loading...
