Please enable JavaScript.
Coggle requires JavaScript to display documents.
網路分析 - Coggle Diagram
網路分析
最短延展樹問題(minimum spanning tree problem)
存在於無向網路
不會產生迴路
連接所有節點(直接或間接)
最短的路徑
Prim’s 演算法
第6章的4個問題中，只有此問題的數學規劃模型不好寫，因為有不能產生迴路的限制，所以模型完全case by case，只有交大考過一次而已，題庫班有
一定能找出一組解，若想找出多重解，則必須回到有相同選擇的地方，走別條路，才會有第二組解。
最大流量問題(maximum flow problem)
所有正流量的路徑加起來，求最大
擴充路徑法(augmenting path method)
最大流量之最小切割定理
(Max-flow min-cut theorem)
考試說要驗證，才會使用，不然演算法找出來的都會是最佳解。
驗證優先以剩餘量為0的地方去切，然後再把流量上限加起來，注意！不是加剩餘流量。
若題目給的不是我們習慣的方式，那就花點時間改成習慣的方式，比較好
最短路徑問題(shortest path problem)
找出一條成本，距離、時間最短的路線
Dijkstra's 演算法
有系統化的窮舉，多重解也可以找出來
最短路徑問題，操作很簡單，比較難的是拿來考生產規劃問題，例如p239，可以去看，邏輯是什麼。
最小成本流量問題(minimum cost flow problem)
具有網路最佳化模式，並且有一般性的結構，可以當成通用的解法應用在其他問題上。
使用網路單體法來求解
找一條符合方向、上限流量、節點淨流量和成本最小的一條路徑
運輸問題
(但還是運輸表格比較好做)
指派問題
最短路徑問題
最大流量問題
(最麻煩)
淨流量總和必須為0
n個節點，必須只有n-1個BV，才能使用網路單體法
當題目的弧線上有限制流量時，有可能會需要使用上界法，先隱藏掉達上限的BV，這樣才能使用網路單體法
5,6章都是線性規劃的特例，所以都可以建出線性規劃模式
4種問題4個演算法