基本介紹
- 中文名：最小費用最大流問題
- 外文名：Minimum-cost flow problem
- 限制條件：每段路徑都有“容量”和“費用”
- 相關定義：前向弧和後向弧
- 解決方法：兩條途徑
簡介,網路流,參見,
簡介
最小費用最大流問題是經濟學和管理學中的一類典型問題。在一個網路中每段路徑都有“容量”和“費用”兩個限制的條件下，此類問題的研究試圖尋找出：流量從A到B，如何選擇路徑、分配經過路徑的流量，可以達到所用的費用最小的要求。
在實際中：n輛卡車要運送物品，從A地到B地。由於每條路段都有不同的路費要繳納，每條路能容納的車的數量有限制，如何分配卡車的出發路徑可以達到費用最低，物品又能全部送到。
網路流
在圖論中，網路流（英語：Network flow）是指在一個每條邊都有容量（capacity）的有向圖分配流，使一條邊的流量不會超過它的容量。通常在運籌學中，有向圖稱為網路。頂點稱為節點（node）而邊稱為弧（arc）。一道流必須匹配一個結點的進出的流量相同的限制，除非這是一個源點（source）──有較多向外的流，或是一個匯點（sink）──有較多向內的流。一個網路可以用來模擬道路系統的交通量、管中的液體、電路中的電流或類似一些東西在一個結點的網路中遊動的任何事物。
