Network and discrete location: models, algorithms, and applications.pdf

发布时间：2022-06-16 发布人：admin 分类：说明书资料大小：22.42M 资料格式：pdf 举报版权申诉

c8772a46-503d-482d-830a-9118c5c79d87.pdf-第1页.png

第1页 / 共499页

c8772a46-503d-482d-830a-9118c5c79d87.pdf-第2页.png

第2页 / 共499页

c8772a46-503d-482d-830a-9118c5c79d87.pdf-第3页.png

第3页 / 共499页

c8772a46-503d-482d-830a-9118c5c79d87.pdf-第4页.png

第4页 / 共499页

c8772a46-503d-482d-830a-9118c5c79d87.pdf-第5页.png

第5页 / 共499页

c8772a46-503d-482d-830a-9118c5c79d87.pdf-第6页.png

第6页 / 共499页

c8772a46-503d-482d-830a-9118c5c79d87.pdf-第7页.png

第7页 / 共499页

c8772a46-503d-482d-830a-9118c5c79d87.pdf-第8页.png

第8页 / 共499页

文本预览

Network and Discrete Location

WILEY-INTERSCIENCE SERIES IN DISCRETE MATHEMATICS AND OPTIMIZATION ADVISORY EDITORS R O N A LD L. G R A H AM AT Bell Laboratories, Murray Hill, New Jersey, U.S.A. J AN K A R EL L E N S T RA Centre for Mathematics and Computer Amsterdam, Erasmus University, Rotterdam, The Netherlands The Netherlands Science, R O B E RT E. T A R J AN Princeton University, New Jersey, and NEC Research Institute, Princeton, New Jersey, USA. A complete list of titles in this series appears at the end of this volume

Network and Discrete Location Models, Algorithms, and Applications MARK S. DASKIN Northwestern University ﬁ A Wiley-Interscienee Publication JOHN WILEY & SONS, INC. New York • Chichester • Brisbane • Toronto • Singapore

This text is printed on acid-free paper. Copyright ' 1995 by John Wiley & Sons, Inc. All rights reserved. Published simultaneously in Canada. No part of this publication may be reproduced, stored in a retrieval sys in any form or by any means, electronic, mechanical, photocopying, Œ or otherwise, except as permitted under Sections 107 or 108 of the 19’ Copyright Act, without either the prior written permission of the Publi authorization through payment of the appropriate per-copy fee to the C Clearance Center, 222 Rosewood Drive, Danvers, MA 01923, (978) 7: (978) 750-4470. Requests to the Publisher for permission should be a Permissions Department, John Wiley & Sons, Inc., 111 River Street, t (201) 748-6011, fax (201) 748-6008. To order books or for customer service please, call 1(800)-CALL-WIL Library of Congress Cataloging Daskin, Mark S. 1952- in Publication Data: Network and discrete location: models, algorithms, and applications / Mark S. Daskin. p. cm. Includes bibliographical references. ISBN 0-471-01897-X 1. Industrial locationMathematical models. T57.6.D373 1995 658.2”…1156dc2 0 I. Title. 94-24488 CIP 11 1 0 9 8 7 6 5 43 2 1

To the absolute centers of my life.

Contents Preface 1 Introduction to Location Theory and Models Introduction 1.1. 1.2 Key Questions Addressed by Location Models 1.3 1.4 A Taxonomy of Location Problems and Models 1.5 Example Problem Descriptions Summary Exercises 2 Review of Linear Programming Problem Introduction The Canonical Form of a Linear Programming Problem 2.1 2.2 2.3 Constructing the Dual of an LP Problem 2.4 Complementary Slackness and the Relationships Between the Primal and the Dual Linear Programming Problems The Transportation Problem The Shortest Path Problem The Out-of-Kilter Flow Algorithm Summary Exercises 2.5 2.6 2.7 2.8 3 An Overview of Complexity Analysis Introduction 3.1 3.2 Basic Concepts and Notation 3.3 3.4 3.5 Example Computation of an Algorithm’ s Complexity The Classes and NP (and NP-Hard and NP-Complete) Summary Exercises xi 1 1 3 4 10 18 19 20 20 20 23 25 31 41 53 64 64 80 80 81 84 85 89 90 vii

viii 4 Covering Problems Introduction and the Notion of Coverage 4.1 4.2 The Set Covering Model 4.3 Applications of the Set Covering Model 4.4 Variants of the Set Covering Location Model 4.5 4.6 4.7 The Maximum Covering Location Model The Maximum Expected Covering Location Model Summary Exercises 5 Center Problems Introduction 5.1 5.2 Vertex P-Center Formulation 5.3 5.4 T he Absolute 1- and 2-Center Problems on a Tree The Unweighted Vertex P-Center Problem on a General Graph T he Unweighted Absolute P-Center Problem on a General Graph Summary Exercises 5.5 5.6 6 Median Problems Introduction Formulation and Properties 1-Median Problem on a Tree 6.1 6.2 6.3 6.4 Heuristic Algorithms for the P-Median Problem 6.5 An Optimization-Based Lagrangian Algorithm for the P- Median Problem 6.6 Computational Results Using the Heuristic Algorithms and 6.7 the Lagrangian Relaxation Algorithm Summary Exercises 7 Fixed Charge Facility Location Problems Introduction 7.1 7.2 Uncapacitated Fixed Charge Facility Location Problems 7.3 Capacitated Fixed Charge Facility Location Problems 7.4 Summary Exercises Contents 92 92 92 105 107 110 130 134 135 154 154 160 162 173 176 191 191 198 198 200 203 208 221 232 236 238 247 247 250 275 302 303

Contents 8 Extensions of Location Models Introduction 8.1 8.2 Multiobjective Problems 8.3 Hierarchical Facility Location Problems 8.4 Models of Interacting Facilities 8.5 Multiproduct Flows and Production/Distribution Systems 8.6 8.7 Hub Location Problems 8.8 Dispersion Models and Models for the Location of Location/Routing Problems 8.9 Undesirable Facilities Summary Exercises 9 Location Modeling in Perspective 9.1 9.2 9.3 Introduction The Planning Process for Facility Location Summary Exercises Appendices A ´ C D ¯ F G ˙ SITATION Operations Guide NET-SPEC Operations Guide M O D - D I ST Operations Guide C O L O R S ET Operations Guide M E N U - O KF Operations Guide P R I N T E R . C NS File Description Longitudes, Latitudes, Demands, and Fixed Costs for CITY1990.GRT: An 88-Node Problem Defined on the Continental United States Longitudes, Latitudes, Demands, and Fixed Costs for S O R T C A P . G R T: A 49-Node Problem Defined on the Continental United States References Author Index Subject Index 309 309 309 317 328 333 339 349 363 373 374 383 383 383 398 399 401 446 450 459 463 474 476 480 483 491 494

分享到：

赞收藏

资料库

Network and discrete location: models, algorithms, and applications.pdf

相关推荐

行业

热门标签

最新资料