簡易檢索 / 詳目顯示

回結果列表
研究生： 林修杰
Lin, Shiou-Jie
論文名稱： 應用網路單形法求解最小分配成本問題之研究
A network simplex algorithm for the minimum distribution cost problem
指導教授： 王逸琳
Wang, I-Lin
學位類別： 碩士
Master
系所名稱： 管理學院 - 工業與資訊管理學系
Department of Industrial and Information Management
論文出版年： 2006
畢業學年度： 94
語文別： 中文
論文頁數： 93
中文關鍵詞： 網路單形法 、最小分配成本問題 、最小成本流量問題 、網路最佳化
外文關鍵詞： network simplex algorithm, minimum distribution cost problem, network optimization, minimum cost flow problem
相關次數： 點閱：129  下載：1 
分享至:
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報

    • 網路最佳化為作業研究之一重要子領域，而最小成本流量問題(Minimum
    Cost Flows；MCF) 即為一常見的網路最佳化問題。MCF 事實上為線性規劃中
    的特例問題， 基於其特殊的網路架構， 得以簡化原本在使用單形法(simplex
    algorithm) 時繁瑣的矩陣運算，並由此發展出一套更有效率的網路單形法(network simplex algorithm)。MCF雖然能夠涵蓋許多網路問題，但仍有其應用的限制，Fang and Qi(2003) 基於產業中製造與分配之特性，將原本的MCF加入一種新型態的分配節點(D 節點)，並提出一套新的最小成本流量模型，稱之為最小分配成本問題(Minimum Distribution Cost Problem；MDCP)。MDCP中，流入D節點的總流量必須依照給定的比例分配給其所有流出的弧。在此架構下，以往的網路單形法將無法適用。雖然Fang and Qi(2003) 提出一套求解MDCP的網路單形法，但該方法僅適用於無弧容量限制下的MDCP，而且其求解方式仍偏向直接求解方程式，缺乏圖形化的求解方法；另外，他們對於網路單形法中諸如初始解之找尋、流量疊代與計算對偶變數等等的圖形化求解方式亦未深入探討。在本論文中，將進一步討論這些議題，並利用拆解基解圖使之成為數個基群集的方式，以基群集為基礎發展出一套可求解具弧容量限制MDCP的圖形化網路單形法。最後，本論文亦將進一步探討加入D節點的最大流量問題，以解釋Lin(2005) 論文中關於最大流量問題達最佳解的對偶變數之分群情形。

    The minimum cost flow problem seeks an optimal flow assignment over a network satisfying the node flow balance constraints and arc flow bounds constraints. These constraints are too simplified to model some real cases.To model the distillation or decomposition of products in some manufacturing processes, a minimum distribution cost problem (MDCP) on a specialized manufacturing network flow model has been investigated. In an MDCP, a specialized node called D-node is used to model a distillation process which only connects with a single incoming arc and several outgoing arcs. The flows entering a D-node have to be distributedaccording to a pre-specified ratio associated with each of its outgoing arcs. Such a proportional relationship between the arc flows associated with each D-node complicatesthe problem and makes the MDCP harder than conventional min-cost network flow problem. A network simplex algorithm for uncapacitated MDCP has been outlined in literature, but its detailed graphical procedures such as initial basic feasible solution computation, dual variables updates, and flow pivoting operations have not yet been given. In this thesis, we resolve these issues by upper bound techniques as well as graphical operations which decompose each pivoting graph into several components for calculating both the arc flows and the dual variables. Other issues regarding efficient ways to obtain an initial primal basic feasible solution to start with our algorithm and mathematical insights for solving the MDCP on distribution networks will also be investigated and discussed.

    摘要 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .i Abstract. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .ii 誌謝. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iii 表目錄. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .vii 圖目錄. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .x 符號說明. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .xi 第一章緒論. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1 1.1 研究動機. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .2 1.2 研究目的. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .3 1.3 研究範圍與限制. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .4 1.4 論文架構. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .5 第二章文獻探討. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .6 2.1 MCF相關文獻探討. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .6 2.1.1 MCF模式建構 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 2.1.2 MCF求解方法. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 2.1.3 處理容量上界之方法. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 2.1.4 最短路徑問題求解方法. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 2.1.5 最大流量問題求解方法. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 2.2 MDCP相關文獻探討. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 2.2.1 MDCP模式建構. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .12 2.2.2 MDCP求解方法. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .17 2.2.3 包含D節點之最短路徑問題求解方法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 2.2.4 包含D節點之最大流量問題求解方法. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 2.2.5 MDCP其他相關問題求解方法. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .20 2.3 小結. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .21 第三章模式轉換、主問題與對偶問題. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .22 3.1 模式轉換. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .22 3.2 主問題基解架構 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .26 3.3 對偶問題與最佳解條件. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .29 3.4 小結. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .36 第四章網路單形法. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .37 4.1 對偶變數計算程序. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .38 4.1.1 基群集. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 4.1.2 對偶變數求算方法. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 4.2 流量疊代－基變數的進入與退出. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .46 4.2.1 進入弧之兩端點位於同一群集. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 4.2.2 進入弧之兩端點位於不同群集. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 4.3 對偶變數更新－更新對偶變數與基群集. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .54 4.4 初始解. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .59 4.5 單形法、修正單形法與網路單形法的比較. . . . . . . . . . . . . . . . . . . . . . . . . . . 62 4.6 小結. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .64 第五章MDCP相關議題. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66 5.1 樞紐圖的錯誤判讀－不存在的Dead-cycle . . . . . . . . . . . . . . . . . . . . . . . . . . . .66 5.2 以T節點之需求為基礎的模式轉換. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .69 5.3 應用compatible component 求解樞紐圖流量比例. . . . . . . . . . . . . . . . . . . . . . 73 5.3.1 compatible component 求解概念. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73 5.3.2 應用compatible component 於流量疊代. . . . . . . . . . . . . . . . . . . . . . . . . . . . .75 5.3.3 compatible component 與基群集之比較. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78 5.4 應用網路單形法探討法最大流量問題. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .81 5.4.1 傳統最大流量問題之對偶性質. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81 5.4.2 包含D節點之最大流量問題其對偶性質. . . . . . . . . . . . . . . . . . . . . . . . . . . .83 5.5 小結. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .85 第六章結論與未來研究方向. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86 6.1 結論. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . .86 6.2 未來研究方向. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .87 參考文獻. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .89 自述. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .93

    Ahuja, R. K. and Orlin, J. B. Distance-directed augmenting path algorithms for maximum flow and parametric maximum flow problems. Naval Research Logistics
    Quarterly, 38, 413-430, 1991.

    Ahuja, R. K., Goldberg, A. V., Orlin, J. B. and Tarjan, R. E. Finding minimum-cost
    flows by double scaling. Mathematical Programming, 53, 243-266, 1992.

    Ahuja, R. K., Magnanti, T. and Orlin, J. B. Network flows: Theory, algorithms and
    applications. Englewood Cli®s, New Jersey, U.S.A.: Prentice Hall, 1993.

    Ali, A. I., Padman, R. and Thiagarajan, H. Dual algorithms for pure network problems.Operations Research, 37(1), 159-171, 1989.

    Armstrong, R. D., Chen, W., Goldfarb, D. and Jin, Z. Strongly polynomial dual
    simplex methods for the maximum flow problem. Mathematical Programming,
    80, 17-33, 1998.
    Armstrong, R. D. and Jin, Z. A new strongly polynomial dual network simplex algo-
    rithm. Mathematical Programming, 78, 131-148, 1997.

    Bellman, R. E. On a routing problem. Quarterly of Applied Mathematics, 16, 87-90,
    1958.

    Cohen, E. and Megiddo, N. Algorithms and complexity analysis for some flow problems.Algorithmica, 11(3), 320-340, 1994.

    Dantzig, G. Application of the simplex method to a transportation problem. In Activity
    analysis of production and allocation. New York, N. Y.: John Wiley & Sons Inc.,
    359-373, 1951.

    Dantzig, G. B. Linear programming and extensions. Princeton, N.J.: Princeton Uni-
    versity Press, 1962.

    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 generalized network flow
    model for manufacturing process modeling. Optimization Methods and Software,
    18, 143-165, 2003.

    Ford, L. R. Network flow theory. Santa Monica, California: The RAND Corp., 1956.

    Ford, L. R. and Fulkerson, D. R. Maximal flow through a network. Canadian Journal
    of Mathematics, 8, 399-404, 1956.

    Ford, L. R. and Fulkerson, D. R. Flows in networks. Princeton, N.J.: Princeton
    University Press, 1962.

    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.

    Goldberg, A. V. and Tarjan, R. E. A new approach to the maximum flow problem.
    Journal of the ACM, 35, 921-940, 1988.

    Goldfarb, D. and Chen, W. On strongly polynomial dual simplex algorithms for the
    maximum flow problem. Mathematical Programming, 159-168, 1997.

    Goldfarb, D. and Hao, J. A primal simplex algorithm that solves the maximum flow
    problem in at most nm pivots and O(n2m) time. Mathematical Programming,
    47, 353-365, 1990.

    Goldfarb, D. and Jin, Z. An O(nm)-time network simplex algorithm for the shortest
    path problem. Operations Research, 47(3), 445-448, 1999.

    Hoffman, A. J. and Kruskal, J. B. 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, 1956.

    Johnson, E. L. On shortest paths and sorting. In Proceedings of the ACM 25th annual
    conference, 510-517, 1972.

    Karzanov, A. V. Determining the maximal flow in a network by the method of preflows. Soviet Math. Dokl, 15, 434-437, 1974.

    Lin, J. C. Maximum flows in distribution networks: problem generator and algorithms.Master's thesis, National Cheng Kung University, 2005.

    Mo, J., Qi, L. and Wei, Z. A network simplex algorithm for simple manufacturing
    network model. Journal of Industrial and Management Optimization, 1(2), 251-
    273, 2005.

    Orlin, J. B. A polynomial time primal network simplex algorithm for minimum cost
    flows. Mathematical Programming, 78, 109-129, 1997.

    Orlin, J. B., Plotkin, S. A. and Tardos, E. Polynomial dual network simplex algorithms.Mathematical Programming, 60, 255-276, 1993.

    Ting, M. J. Maximum flow problem in the distribution network flow model. Master's
    thesis, National Cheng Kung University, 2005.

    Yang, Y. H. Uncapacitated minimum cost flow problem in a distribution network.
    Master's thesis, National Cheng Kung University, 2005.

    下載圖示 校內：2008-07-13公開
    校外：2008-07-13公開
    QR CODE