Multicriteria.Optimization.(2nd).Matthias.Ehrgott.ed05.pdf-资料库

oneinmore-2169350-4744300845379296807.pdf-第1页.png

第1页 / 共328页

oneinmore-2169350-4744300845379296807.pdf-第2页.png

第2页 / 共328页

oneinmore-2169350-4744300845379296807.pdf-第3页.png

第3页 / 共328页

oneinmore-2169350-4744300845379296807.pdf-第4页.png

第4页 / 共328页

oneinmore-2169350-4744300845379296807.pdf-第5页.png

第5页 / 共328页

oneinmore-2169350-4744300845379296807.pdf-第6页.png

第6页 / 共328页

oneinmore-2169350-4744300845379296807.pdf-第7页.png

第7页 / 共328页

oneinmore-2169350-4744300845379296807.pdf-第8页.png

第8页 / 共328页

Multicriteria Optimization

Matthias Ehrgott Multicriteria Optimization Second edition With 88 Figures and 12 Tables 1 2

Dr. habil. Matthias Ehrgott, Associate Professor The University of Auckland Department of Engineering Science School of Engineering Private Bag 92019 70 Symonds Street Level 3 Auckland 1001 New Zealand m.ehrgott@auckland.ac.nz Originally published as volume 491 in the series: Lecture Notes in Economics and Mathematical Systems Cataloging-in-Publication Data Library of Congress Control Number: 2005924730 ISBN 3-540-21398-8 Springer Berlin Heidelberg New York Bibliographic information published by Die Deutsche Bibliothek. Die Deutsche Bibliothek lists this publication in the Deutsche Nationalbibliografie; detailed bibliographic dat is available in the Internet at http://dnb.ddb.de This work is subject to copyright. All rights are reserved, whether the whole or part of the material is concerned, specifically the rights of translation, reprinting, reuse of illus- trations, recitation, broadcasting, reproduction on microfilm or in any other way, and storage in data banks. Duplication of this publication or parts thereof is permitted only under the provisions of the German Copyright Law of September 9, 1965, in its current version, and permission for use must always be obtained from Springer-Verlag. Violations are liable for prosecution under the German Copyright Law. Springer is a part of Springer Science+Business Media springeronline.com ° Springer Berlin ´ Heidelberg 2005 Printed in Germany The use of general descriptive names, registered names, trademarks, etc. in this publica- tion does not imply, even in the absence of a specific statement, that such names are exempt from the relevant protective laws and regulations and therefore free for general use. Hardcover-Design: Erich Kirchner, Heidelberg SPIN 10996973 42/3153-5 4 3 2 1 0 ± Printed on acid-free paper

Preface Life is about decisions. Decisions, no matter if made by a group or an individ- ual, usually involve several conﬂicting objectives. The observation that real world problems have to be solved optimally according to criteria, which pro- hibit an “ideal” solution – optimal for each decision-maker under each of the criteria considered – has led to the development of multicriteria optimization. From its ﬁrst roots, which where laid by Pareto at the end of the 19th cen- tury the discipline has prospered and grown, especially during the last three decades. Today, many decision support systems incorporate methods to deal with conﬂicting objectives. The foundation for such systems is a mathematical theory of optimization under multiple objectives. Fully aware of the fact that there have been excellent textbooks on the topic before, I do not claim that this is a better text, but it has a consider- ably diﬀerent focus. Some of the available books develop the mathematical background in great depth, such as Sawaragi et al. (1985); G¨opfert and Nehse (1990); Jahn (1986). Others focus on a speciﬁc structure of the problems cov- ered as Zeleny (1974); Steuer (1985); Miettinen (1999) or on methodology Yu (1985); Chankong and Haimes (1983); Hwang and Masud (1979). Finally there is the area of multicriteria decision aiding Roy (1996); Vincke (1992); Keeney and Raiﬀa (1993), the main goal of which is to help decision makers ﬁnd the ﬁnal solution (among many “optimal” ones) eventually to be implemented. With this book, which is based on lectures I taught from winter semester 1998/99 to winter semester 1999/2000 at the University of Kaiserslautern, I intend to give an introduction to and overview of this fascinating ﬁeld of math- ematics. I tried to present theoretical questions such as existence of solutions as well as methodological issues and hope the reader ﬁnds the balance not too heavily on one side. The text is accompanied by exercises, which hopefully help to deepen students’ understanding of the topic.

vi Preface The decision to design these courses as an introduction to multicriteria optimization lead to certain decisions concerning the contents and material contained. The text covers optimization of real valued functions only. And even with this restriction interesting topics such as duality or stability have been excluded. However, other material, which has not been covered in earlier textbooks has found its way into the text. Most of this material is based on research of the last 15 years, that is after the publication of most of the books mentioned above. This applies to the whole of Chapters 6 and 7, and some of the material in earlier chapters. As the book is based on my own lectures, it is well suitable for a mathe- matically oriented course on multicriteria optimization. The material can be covered in the order in which it is presented, which follows the structure of my own courses. But it is equally possible to start with Chapter 1, the basic results of Chapters 2 and 3, and emphasize the multicriteria linear program- ming part. Another possibility might be to pick out Chapters 1, 6, and 7 for a course on multicriteria combinatorial optimization. The exercises at the end of each Chapter provide possibilities to practice as well as some outlooks to more general settings, when appropriate. Even as an introductory text I assume that the reader is somehow famil- iar with results from some other ﬁelds of optimization. The required back- ground on these can be found in Bazaraa et al. (1990); Dantzig (1998) for linear programming, Mangasarian (1969); Bazaraa et al. (1993) for nonlinear programming, Hiriart-Uruty and Lemar´echal (1993); Rockafellar (1970) for convex analysis, Nemhauser and Wolsey (1999); Papadimitriou and Steiglitz (1982) for combinatorial optimization. Some results from these ﬁelds will be used throughout the text, most from the sources just mentioned. These are generally stated without proof. Accepting these theorems as they are, the text is self-contained. I am indebted to the many researchers in the ﬁeld, on whose work the lectures and and this text are based. Also, I would like to thank the students who followed my class, they contributed with their questions and comments, and my colleagues at the University of Kaiserslautern and elsewhere for their cooperation and support. Special thanks go to Horst W. Hamacher, Kathrin Klamroth, Stefan Nickel, Anita Sch¨obel, and Margaret M. Wiecek. Last but not least my gratitude goes to Stefan Zimmermann, whose diligence and apti- tude in preparing the manuscript was enormous. Without him the book would not have come into existence by now.

Preface vii Preface to the Second Edition Much has happened in multicriteria optimization since the publication of the ﬁrst edition of this book. Too much in fact for all the contributions in the ﬁeld to be reﬂected in this new edition, which – after all – is intended to be a textbook for a course on multicriteria optimization. Areas which have seen particularly strong growth are multiobjective combinatorial optimization and heuristics for multicriteria optimization problems. I have tried to give an indication of these new developments by adding “Notes” sections to all chapters but one. These sections contain many references to the literature for the interested reader. As a consequence the bibliography has more than doubled compared to the ﬁrst edition. Still, heuristics feature only in the very last section and metaheuristics are not even mentioned. There are a number of other changes to the organization of the book. Linear and combinatorial multicriteria optimization is now spread over ﬁve chapters, which seems appropriate for material that covers roughly half the pages. It also reﬂects the way in which I have usually taught multicriteria optimization, namely a course on general topics, containing material of the ﬁrst ﬁve chapters, and a course on linear and combinatorial problems, i.e. the second half of the book. I have therefore tried to make the second part self contained by giving a brief revision of major deﬁnitions. Some reorganization and rewriting has taken place within the chapters. There is now a section on optimality conditions, previously distributed over several chapters. Topics closely related to the weighted sum method have been collected in Chapter 3. Chapter 4 has been extended to include several scalar- ization techniques not mentioned in the ﬁrst edition. Much of the material on linear programming has been rewritten, and scalarization of multiobjective integer programs has been added in Chapter 8. Of course, I have done my best to eliminate errors contained in the ﬁrst edition. I am grateful to all students and colleagues who made me aware of them, especially Dagmar Tenfelde-Podehl and Kathrin Klamroth, who used the book for their own courses. There will still be mistakes in this text, and I welcome any suggestions for improvement. Otherwise, I hope that you approve of the changes and ﬁnd the book useful. Auckland, March 2005 Matthias Ehrgott

Notation These are some guidlines concerning the notation I have used in the book. In general, calligraphic capitals denote sets, latin capitals denote matrices (or some combinatorial objects) and small latin or greek letters denote elements of sets, variables, functions, parameters, or indices. Superscripts indicate entities (such as particular vectors), subscripts indicate components of a vector or matrix. Due to a limited supply of alphabetical symbols, I have reused some for several purposes. Their usage should be clear form the context, nevertheless I apologize for any confusion that may arise. The following table summarizes the most commonly used symbols.

x Notation Notation X Y := f (X ) C x = (x1, . . . , xn) y = (y1, . . . , yp) f = (f1, . . . , fp) g = (g1, . . . , gm) A ∈ R(m×n) C ∈ R(p×n) b ∈ Rm yI yN yU λ ∈ Rp y1 < y2 y1 y2 y1 ≤ y2 Rp > Rp ≥ Rp Explanation feasible set of an optimization problem feasible set in objective space cone variable vector, variables vector of objective function values vector of objective functions vector of constraint functions constraint matrix of an LP objective matrix of an MOLP right hand side vector of an (MO)LP ideal point nadir point utopian point k for k = 1, . . . , p k for k = 1, . . . , p vector of weights y1 k < y2 k ≤ y2 y1 y1 y2 but y1 = y2 {y ∈ Rp : y > 0} {y ∈ Rp : y ≥ 0} {y ∈ Rp : y 0}

资料库

Multicriteria.Optimization.(2nd).Matthias.Ehrgott.ed05.pdf

相关推荐

课程资源

热门标签

最新资料