簡易檢索 / 詳目顯示

回結果列表
研究生： 楊羽惠
Yang, Yu-Hui
論文名稱： Uncapacitated minimum cost flow problems in a distribution network
Uncapacitated minimum cost flow problems in a distribution network
指導教授： 王逸琳
Wang, I-Lin
學位類別： 碩士
Master
系所名稱： 管理學院 - 工業與資訊管理學系
Department of Industrial and Information Management
論文出版年： 2005
畢業學年度： 93
語文別： 英文
論文頁數： 86
外文關鍵詞： Manufacturing network, distribution network, minimum cost flow problem
相關次數： 點閱：63  下載：1 
分享至:
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報

    • none

    In this thesis, we consider three special minimum cost flow problems in a distri-
    bution network, a kind of manufacturing network recently introduced by Fang and Qi.
    The network diRers from a traditional network model because a new kind of nodes,
    called D-nodes, are incorporated to describe a distilling operation that decomposes one
    raw-material to several products with fixed ratios. Besides, all the arcs in our models
    have no upper bounds. We treat these uncapacitated minimum cost flow problems as
    specialized shortest path problems with side constraints in a distribution network. We
    give a preprocessing that compacts a distribution network to an equivalent network
    of smaller size, derive their mathematical formulations and develop e±cient solution
    methods.

    LIST OF FIGURES : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : iii LIST OF APPENDICES : : : : : : : : : : : : : : : : : : : : : : : : : : : : : v CHAPTER I. INTRODUCTION . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 Objectives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.3 Thesis outline . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 II. LITERATURE REVIEW . . . . . . . . . . . . . . . . . . . . . . . 6 2.1 Notations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 2.2 General MNF Optimization Problems . . . . . . . . . . . . . . 10 2.3 Traditional Shortest Path Problems and Algorithms . . . . . . 14 2.4 Dijkstra's Algorithm . . . . . . . . . . . . . . . . . . . . . . . . 16 2.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 III. UNCAPACITATED MINIMUM DISTRIBUTION COST PROB- LEM (ONE-TO-ONE CASES) . . . . . . . . . . . . . . . . . . . . 18 3.1 Preprocessing . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 3.2 One-to-one UMDCP1 . . . . . . . . . . . . . . . . . . . . . . . 23 3.2.1 Formulation and Solution Method for a One-to-one UMDCP1 . . . . . . . . . . . . . . . . . . . . . . . . . 23 3.2.2 Algorithm for Solving a One-to-one UMDCP1 . . . . 26 3.2.3 Correctness of a One-to-one UMDCP1 Algorithm . . . 28 3.2.4 A One-to-one UMDCP1 Example . . . . . . . . . . . 31 3.2.5 A Reduced Method for a One-to-one UMDCP1 . . . . 33 3.2.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . 36 3.3 One-to-one UMDCP2 . . . . . . . . . . . . . . . . . . . . . . . 37 3.3.1 Formulation and Solution Method for a One-to-one UMDCP2 . . . . . . . . . . . . . . . . . . . . . . . . . 37 3.3.2 Algorithm for Solving a One-to-one UMDCP2 . . . . 39 3.3.3 Correctness of our One-to-one UMDCP2 Algorithm . 41 3.3.4 A One-to-one UMDCP2 Example . . . . . . . . . . . 43 3.3.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . 45 3.4 One-to-one UMDCP3 . . . . . . . . . . . . . . . . . . . . . . . 46 3.4.1 Formulation and Solution Method for a One-to-one UMDCP3 . . . . . . . . . . . . . . . . . . . . . . . . . 47 3.4.2 Algorithm for Solving a One-to-one UMDCP3 . . . . 47 3.5 Correctness of our One-to-one UMDCP3 Algorithm . . . . . . . 50 3.5.1 A One-to-one UMDCP3 Example . . . . . . . . . . . 52 3.5.2 Summary . . . . . . . . . . . . . . . . . . . . . . . . . 53 IV. UNCAPACITATED MINIMUM DISTRIBUTION COST PROB- LEM (ONE-TO-SOME CASES) . . . . . . . . . . . . . . . . . . . 55 4.1 One-to-some UMDCP1 . . . . . . . . . . . . . . . . . . . . . . 55 4.1.1 Formulation for a One-to-some UMDCP1 . . . . . . . 55 4.1.2 A One-to-some UMDCP1 Example . . . . . . . . . . 57 4.1.3 Comparison on One-to-one and One-to-some UMDCP1 Solutions . . . . . . . . . . . . . . . . . . . . . . . . . 58 4.1.4 A Reduced Method for a One-to-some UMDCP1 . . . 59 4.2 One-to-some UMDCP2 . . . . . . . . . . . . . . . . . . . . . . 61 4.2.1 Formulation for a One-to-some UMDCP2 . . . . . . . 62 4.2.2 A One-to-some UMDCP2 Example . . . . . . . . . . 63 4.2.3 Comparison on One-to-one and One-to-some UMDCP2 Solutions . . . . . . . . . . . . . . . . . . . . . . . . . 65 4.3 One-to-some UMDCP3 . . . . . . . . . . . . . . . . . . . . . . 66 4.3.1 Formulation for a One-to-some UMDCP3 . . . . . . . 67 4.3.2 A One-to-some UMDCP3 Example . . . . . . . . . . 67 4.3.3 Comparison on One-to-one and One-to-some UMDCP3 Solutions . . . . . . . . . . . . . . . . . . . . . . . . . 68 4.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69 V. CONCLUSIONS AND FUTURE DIRECTIONS . . . . . . . . 70 5.1 Summary and Contributions . . . . . . . . . . . . . . . . . . . 70 5.2 Future Research Directions . . . . . . . . . . . . . . . . . . . . 72 REFERENCES : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 74 APPENDICES : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 76

    Ahuja, R. K., Magnanti, T. L. and Orlin, J. B. Network flows: Theory, algorithms,
    and applications. Prentice-Hall, New Jersey, 1993.
    Ahuja, R. K., Mehlhorn, K., Orlin, J. B. and Tarjan, R. E. Faster algorithms for the
    shortest path problem. Journal of ACM, 37, 213-223, 1990.
    Bellman, R. E. On a routing problem. Quarterly of Applied Mathematics, 16, 87-90,
    1958.
    Cormen, T. H., Leiserson, C. E., Rivest, R. L. and Stein, C. Introduction to algorithms,
    second edition. The MIT Press, 2001.
    Dial, R. Algorithm 360: Shortest path forest with topological ordering. Communica-
    tions of the ACM, 12(11), 632-633, 1969.
    Dijkstra, E. W. A note on two problems in connexion with graphs. Numerische
    Mathematik, 1, 269-271, 1959.
    Fang, S. C. and Qi, L. Manufacturing network flows: A general network flow model
    for manufacturing process modelling. Optimization Methods and Software, 18(2),
    143-165, 2003.
    Floyd, R. W. Algorithm 97: Shortest path. Communications of the ACM, 5(6), 345,
    1962.
    Ford, L. R. Network flow theory. Santa Monica, California: The RAND Corp., 1956.
    Fredman, M. L. and Tarjan, R. E. Fibonacci heaps and their uses in improved network
    optimization algorithms. Journal of the ACM, 34(3), 596-615, 1987.
    Johnson, E. L. 1972. On shortest paths and sorting. In Proceedings of the acm 25th
    annual conference (p. 510-517).

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