成功大學博碩士論文系統

簡易檢索 / 詳目顯示

回結果列表

研究生：	丁睦容 Ting, Mu-Jung
論文名稱：	分配式網路之最大流量問題 Maximum flow problem in the distribution network flow model
指導教授：	許瑞麟 Sheu, Ruey-Lin
學位類別：	碩士 Master
系所名稱：	理學院 - 數學系應用數學碩博士班 Department of Mathematics
論文出版年：	2005
畢業學年度：	93
語文別：	中文
論文頁數：	60
中文關鍵詞：	分配式網路、最大流量問題、標號法、迴圈
外文關鍵詞：	distribution network, maximum flow problem, labeling method, cycles
相關次數：	點閱：95 下載：1
分享至:	分享至facebook 分享至twitter

查詢本校圖書館目錄查詢臺灣博碩士論文知識加值系統勘誤回報

　　這篇論文我們要探討分配式網路上之最大流量問題，這是最近由Fang和Qi所提出來的一種網路。不同於傳統網路的地方是引進D節點，它描述了由一個物質按一定的比例分解成數個產物的現象。有了D節點的加入，網路結構變得很複雜。尤其，在分配式網路上常常需要經由多重的迴圈來增加流量。因此，我們發展了一套深度優先搜尋演算法來計算並找出所有的未飽和子圖。然而，有些未飽和子圖在結構上或者是數值上可能是無效圖形，我們必須能夠偵錯剔除並進行非重複搜尋。在有效的未飽和子圖上，我們用多重標號法來計算出所需要增加的流量值。最後，我們也提供了第一階段步驟來求得初始流量。

　In this paper, we are concerned with the maximum flow problem in the distribution network, a new kind of network recently introduced by Fang and Qi. It differs from the traditional networks by the presence of the D-node through which the commodities are to be distributed proportionally. Adding D-nodes into the network complicates the structure. Particularly, flows in the distribution network are frequently increased through multiple cycles. To this end, we develop a type of depth-first-search algorithm, which counts and finds all unsaturated subgraphs. Those configurations, however, could be invalid either topologically or numerically. The validity are then judged by computing the flow increment with a method we call the multi-labeling method. Finally, we also provide the phase-one procedure for finding an initial flow.

Contents

Introduction                                    5
1  The distribution network model.............5
2  Some examples for D-nodes..................5
3  LP Formulation.............................8
4  Failure of the classical labeling method..10
5  Thesis Outline............................12

Basic strategies to advance and retreat without cycles                                           13
1  Residual network..........................13
2  Advance...................................15
3  Retreat...................................19

Cycles                                         22
1  Necessity for cycles .....................22
2  Topologically invalid and numerically 
       invalid...................................23
3  Form the cycle............................25

Determining the flow value on G_M              27
1  Compatible components.....................27
2  The relation of the compatible components and  the dividing nodes...............................29

Retreat from an invalid G_M                    33
1  The importance of the searching order among all..............................................33
2  The necessity for un-marking the arcs in the retreat phase....................................38

Initial flow                                   41
1  The reverse-run algorithm for finding an initial flow.....................................41
2  An example for the entire phase-one procedure........................................43

Future study                                   47
1  Component Algorithm.......................47
2  Dual problem..............................51

Conclusion                                     58

                                    

[1] R. K. Ahuja, T. L. Magnanti, and J. R. Orlin.
Network Flows: Theory, Algorithms and Applications.
Prentice Hall, Englewood Cliffs, New Jersey, USA, 1993.
[2] R. G. Askin and C. R. Standridge.
Modelling and Analysis of Manufacturing Systems.
John Wiley & Sons, New York, USA, 1993.
[3] M. S. Bazaraa, J. J. Jarvis, and H. Sherall.
Linear Programming and Network Flow.
John Wiley & Sons, New York, USA, 1990.
[4] S. C. Fang and L. Qi.
Manufacturing network flows: A generalized network flow model
for manufacturing process modelling.
Optim. Methods Softw. 18, 143-165,2003.
[5] L. R. Ford and D. Fulkerson.
Flows in Networks.
Princeton University Press, Princeton, USA, 1962.
[6] E. L. Lawler.
Combinatorial Optimization: Networks and Matroids.
Holt, Rinehart and Winston, New York, USA, 1976.
[7] C. Leondes. Computer Integrated Manufacturing.
CRC Press, New York, USA, 2001.
[8] D. G. Luenberger.
Linear and Nonlinear Programming.
Addison-Wesley, Canada, 1984.
[9] J. Mao, L. Qi, and Z. Wei.
A network simplex algorithm for simple manufacturing network mode.
To appear in Journal of Industrial and Management Optimization (2004).
[10] K. G. Murty.
Network Programming.
Prentice Hall Englewood Cliffs, New Jersey, 1992.
[11] C. H. Papadimitriou and K. Steiglitz.
Combinatorial Optimization: Algorithms and Complexity.
Prentice-Hall, Englewood Cliffs, New Jersey, USA, 1982.

校內：立即公開
校外：2005-02-01公開

簡易檢索 / 詳目顯示

相關論文