查看“︁多物網絡流問題”︁的源代码

{{NoteTA
| G1 = Math
| G2 = IT
}}

'''多物網絡流問題（Multi-commodity Flow Problem）'''是多種物品（或貨物）在網絡中從不同的源點流向不同的匯點的[[網絡流]]問題。

==定義==

已知一流網絡<math>\,G(V,E)</math>，其中邊<math>(u,v) \in E</math>的容量為<math>\,c(u,v)</math>。有<math>\,k</math>件物品<math>K_1,K_2,\dots,K_k</math>，定義為<math>\,K_i=(s_i,t_i,d_i)</math>，其中<math>\,s_i</math>和<math>\,t_i</math>是物品<math>\,i</math>的'''源點'''及'''匯點'''，及<math>\,d_i</math>是需求。物品<math>\,i</math>沿邊<math>\,(u,v)</math>的流量是<math>\,f_i(u,v)</math>。求一個符合以下限制的流量分配：

:{|
| '''容量限制'''：|| <math>\,\sum_{i=1}^{k} f_i(u,v) \leq c(u,v)</math>
|-
| '''流守恆'''：|| <math>\,\sum_{q \in V} f_i(u,q) - \sum_{w \in V} f_i(w,u) = 0 \quad \mathrm{when} \quad u \neq s_i, t_i </math> 
|-
| '''需求的滿足'''：|| <math>\,\sum_{w \in V} f_i(s_i,w) = d_i \Leftrightarrow \sum_{w \in V} f_i(w,t_i) = d_i</math>
|}

在'''最小成本多物網絡流問題'''中，在<math>\,(u,v)</math>上傳送需要成本<math>a(u,v) \cdot f(u,v)</math>。目的是要最小化 

:<math>\sum_{(u,v)\in E} \left(a(u,v) \sum_{i=1}^{k} f_i(u,v) \right)</math>

在'''最大多物網絡流問題'''中，每件物品都沒有硬性的需求，但最大化總生產量：

:<math>\sum_{i=1}^{k} \sum_{w \in V} f_i(s_i,w)</math>

在'''最大同時網絡流問題'''中，任務是要將物品的流量對它的需求的最小比例最大化：

:<math>\min_{1 \leq i \leq k} \frac{\sum_{w \in V} f_i(s_i,w)}{d_i}</math>

==與其它問題的關係==

最小成本變體是普遍化的[[最小成本網絡流問題]]。[[環流問題]]的變體是所有網絡流問題的概括。

==用途==

利用多物網絡流的公式可以接近在[[光學網絡]]的[[光學群聚交換]]中的[[路由波長分配|路由波長分配（RWA, Routing Wavelength Assignment）]]。

==解==

這問題已知的解是建基於[[線性規劃]]<ref>{{cite book | author = [[Thomas H. Cormen]]、[[Charles E. Leiserson]]、[[Ronald L. Rivest]]和[[Clifford Stein]] | title = [[Introduction to Algorithms]] | origyear = 1990 | edition = 2nd edition | year = 2001 | publisher = MIT Press and McGraw-Hill | pages = 788-789 | chapter = 29 | id = ISBN 978-0-262-03293-3}}</ref>.

就算只有兩件物品，對於整體流來說，這問題是[[NP完全]]<ref name="EIS76">{{cite journal | author = S. Even and A. Itai and A. Shamir | title = On the Complexity of Timetable and Multicommodity Flow Problems | publisher = SIAM | year = 1976 | journal = SIAM Journal on Computing | volume = 5 | number = 4 | pages = 691-703 | url = http://link.aip.org/link/?SMJ/5/691/1 | doi = 10.1137/0205048 | deadurl = yes | archiveurl = https://archive.today/20130112133748/http://link.aip.org/link/?SMJ/5/691/1 | archivedate = 2013-01-12 | access-date = 2021-08-31 }}</ref>。在有錯誤限下，已有完全多項式時間近似值的方法去解決這難題<ref name="">{{cite conference | author = George Karakostas | title = Faster approximation schemes for fractional multicommodity flow problems | booktitle = Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms | year = 2002 | isbn = 0-89871-513-X | pages = 166--173}}</ref>。對於這難題的分數變體，在多項式時間中已有解。

==參考==
<references/>

[[Category:網絡流]]