簡易檢索 / 詳目顯示

回結果列表
研究生： 林筑軍
Lin, Ju-Chun
論文名稱： Maximum flows in distribution networks: problem generator and algorithm
Maximum flows in distribution networks: problem generator and algorithm
指導教授： 王逸琳
Wang, I-Lin
學位類別： 碩士
Master
系所名稱： 管理學院 - 資訊管理研究所
Institute of Information Management
論文出版年： 2005
畢業學年度： 93
語文別： 英文
論文頁數： 94
外文關鍵詞： distribution network, maximum flow
相關次數： 點閱：58  下載：3 
分享至:
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報

    • none

    　The maximum flow (max-flow) problem is a fundamental network optimization problem which computes for the largest possible amount of flow sent through the network from a source node to a sink node. This problem appears in many applications and has been investigated extensively over the recent four decades. Traditional max-flow problem may require some modification in its constraints to deal with real-world applications. Fang and Qi propose a new max-flow model, named as manufacturing network flow model, to describe a network with special distillation nodes or combination nodes. Based on this new model, Ting proposes a multi-labeling method to solve the max-flow problem in a distribution network which contains both ordinary and distillation nodes. The approach identifies an augmenting subgraph connecting both source and sink nodes which can be further decomposed into several components where flows in each component can be expressed by a single variable and solved by a system of homogeneous linear equations. The method requires manual detection for components and thus is not trivial to implement. In this paper, we present a preprocessing procedure that reduces the size of a distribution network in polynomial time and then give detailed procedures for implementing the multi-labeling method. We also implement a random network generator that generates random distribution networks guaranteed to be acyclic, connected and in a compact form for our computational testing. Modification on the preflow-push algorithm and the max-flow min-cut theorem is investigated and discussed to provide more theoretical insights as well.

    ACKNOWLEDGEMENTS : : : : : : : : : : : : : : : : : : : : : : : : : : : i LIST OF TABLES : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : iv LIST OF FIGURES : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : v CHAPTER I. INTRODUCTION . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.1 Background and motivation . . . . . . . . . . . . . . . . . . . . 1 1.2 Objective and proposed approach . . . . . . . . . . . . . . . . . 5 1.3 Scope and limitation . . . . . . . . . . . . . . . . . . . . . . . . 6 1.4 Overview of thesis . . . . . . . . . . . . . . . . . . . . . . . . . 7 II. LITERATURE REVIEW . . . . . . . . . . . . . . . . . . . . . . . 8 2.1 Notation and formulations . . . . . . . . . . . . . . . . . . . . . 8 2.1.1 Traditional maximum flow problem . . . . . . . . . . 8 2.1.2 Distributed maximum flow problem . . . . . . . . . . 10 2.2 Solution methods for maximum flow problems . . . . . . . . . . 13 2.2.1 Algorithms for traditional network model . . . . . . . 13 2.2.2 Algorithms for distribution network model . . . . . . 15 2.3 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 III. NETWORK COMPACTION AND AUGMENTING PATH ALGORITHM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 3.1 Preprocessing . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 3.1.1 Compacting rules . . . . . . . . . . . . . . . . . . . . 18 3.1.2 Inducing relations . . . . . . . . . . . . . . . . . . . . 24 3.2 Implementing the multi-labeling method . . . . . . . . . . . . . 30 3.2.1 Constructing an augmenting subgraph . . . . . . . . . 31 3.2.2 Identifying components in an augmenting subgraph . 34 3.2.3 Solving a system of linear equations . . . . . . . . . . 36 ii 3.2.4 Calculating the flow to be sent on an augmenting sub- graph . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 3.2.5 Updating the residual network . . . . . . . . . . . . . 38 3.3 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 IV. RANDOM NETWORK GENERATOR . . . . . . . . . . . . . . 39 4.1 Notations for our random network generator . . . . . . . . . . . 39 4.2 Constructing a random distribution network . . . . . . . . . . . 41 4.3 Dicussion on random network generator . . . . . . . . . . . . . 44 4.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 V. PREFLOW-PUSH ALGORITHM AND MAX-FLOW MIN- CUT THEOREM . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 5.1 Preflow-push algorithm . . . . . . . . . . . . . . . . . . . . . . 51 5.1.1 Modifications for preflow-push algorithm . . . . . . . 53 5.1.2 Procedures of modified preflow-push algorithm . . . . 60 5.1.3 Summary of modified preflow-push algorithm . . . . . 73 5.2 Max-flow min-cut theorem in distribution networks . . . . . . . 73 5.2.1 Summary . . . . . . . . . . . . . . . . . . . . . . . . . 77 VI. CONCLUSION . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78 REFERENCES : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 80 APPENDICES : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 82

    Ahuja, R. K., Magnanti, T. and Orlin, J. Network flows: theory, algorithms and
    applications. Englewood CliRs, New Jersey, U.S.A.: Prentice Hall, 1993.
    Anderson, R. J. and Setubal, J. C. 1993. Goldberg's algorithm for maximum flow in
    perspective: a computatioinal study. In D. S. Johnson and C. McGeoch (Eds.),
    Network flows and matching: first dimacs implementation challenge (pp. 1-17).
    American Mathematical Society.
    Chen, S. Y. and Chern, C. C. 2000. Network flow problems for supply chain man-
    agement with product tree structure. Unpublished doctoral dissertation, National
    Taiwan University.
    Cherkassky, B. V. and Goldberg, A. V. On implementing push-relabel method for the
    maximum flow problem. Algorithmica, 19, 390-410, 1997.
    Dinic, E. A. Algorithm for solution of a problem of maximum flow in networks with
    power estimation. Soviet Math. Dokl., 11, 1277-1280, 1970.
    Edmonds, J. and Karp, R. M. Theoretical improvements in algorithmic e±ciency for
    network flow problems. Journal of the Association for Computation Machine,
    19, 248-264, 1972.
    Fang, S. C. and Qi, L. Manufacturing network flows: A generalized network flow
    80
    model for manufacturing process modeling. Optimization Methods and Software,
    18, 143-165, 2003.
    Ford, L. R. and Fulkerson, D. R. Maximal flow through a network. Canadian Journal
    of Mathematics, 8, 399-404, 1956.
    Fujishige, S. A maximum flow algorithm using ma orderings. Operations Research
    Letters, 31, 176 -178, 2003.
    Fulkerson, D. R. and Dantzig, G. B. Computation of maximum flow in networks. Naval
    Research Logistics Quarterly, 2, 277 - 283, 1955.
    Goldberg, A. V. and Tarjan, R. E. A new approach to the maximum flow problem.
    Journal of the Association for Computation Machine, 35, 921-940, 1988.
    Goldfarb, D. and Grigoriadis, M. D. A computational comparison of the dinic and
    network simplex methods for maximum flow. Annals of Operations Research, 13,
    83-123, 1988.
    Hoffman, A. and Kruskal, J. 1956. Integral boundary points of convex polyhedra.
    In H. Kuhn and A. Tucker (Eds.), Linear inequalities and related systems (pp.
    233-246). Princeton, NJ: Princeton University Press.
    Karzanov, A. V. Determining the maximal flow in a network by the method of preflows.
    Soviet Math. Dokl, 15, 434-437, 1974.
    Sleator, D. D. and Tarjan, R. E. A data structure for dynamic trees. Journal of
    Computer and System Sciences, 24, 362-391, 1983.
    Ting, M. J. 2005. Maximum flow problem in the distribution network flow model.
    Unpublished master's thesis, National Cheng Kung University.

    下載圖示 校內：立即公開
    校外：2005-07-22公開
    QR CODE