ネットワークフロー問題の一般化
循環 問題とその変種は、 ネットワーク フロー の問題を一般化したものです が、エッジ フローの下限の制約が追加され、ソースとシンクにも フローの保存 が要求されます (つまり、特別なノードはありません)。問題の変種では、ネットワークを流れる複数の商品があり、フローにコストがかかります。
意味 次のようなフロー ネットワークが与えられます 。
グ （ 五 、 え ）
{\displaystyle G(V,E)}
l （ ヴ 、 わ ）
{\displaystyle l(v,w)}
、ノードからノードへの フローの下限 、
ヴ
{\displaystyle v}
わ
{\displaystyle w}
あなた （ ヴ 、 わ ）
{\displaystyle u(v,w)}
、ノードからノードへの フローの上限 、
ヴ
{\displaystyle v}
わ
{\displaystyle w}
c （ ヴ 、 わ ）
{\displaystyle c(v,w)}
、フロー単位のコスト
（ ヴ 、 わ ）
{\displaystyle (v,w)}
制約は次のとおりです。
l （ ヴ 、 わ ） ≤ ふ （ ヴ 、 わ ） ≤ あなた （ ヴ 、 わ ）
{\displaystyle l(v,w)\leq f(v,w)\leq u(v,w)}
、
∑
わ ∈ 五
ふ （ あなた 、 わ ） = 0
{\displaystyle \sum _{w\in V}f(u,w)=0}
(フローはノード内で現れたり消えたりすることはできません)。 制約を満たすフロー割り当てを見つけることで、与えられた循環問題の解決策が得られます。
問題の最小コスト変種では、最小化する
∑
（ ヴ 、 わ ） ∈ え
c （ ヴ 、 わ ） ⋅ ふ （ ヴ 、 わ ） 。
{\displaystyle \sum _{(v,w)\in E}c(v,w)\cdot f(v,w).}
多品目の流通 複数の商品の循環問題では、個々の商品の流れも追跡する必要があります。
各商品の流れにも下限があります。
保全制約は商品ごとに個別に遵守されなければなりません。
∑
わ ∈ 五
ふ
私
（ あなた 、 わ ） = 0.
{\displaystyle \\sum_{w\inV}f_{i}(u,w)=0.}
解決 循環問題に対しては、多くの多項式アルゴリズムが開発されてきた（例えば、 Edmonds-Karpアルゴリズム 、1972年、Tarjan 1987-1988年）。Tardosは最初の強多項式アルゴリズムを発見した。 [1]
複数の商品がある場合、整数フローでは問題は NP完全で ある。 [2] 分数フローの場合は、問題を 線形計画法として定式化できるため、 多項式時間 で解くことができる 。
以下にいくつかの問題と、上記の一般的な循環設定でそれらを解決する方法を示します。
最小コストの複数商品循環問題 - 上記のすべての制約を使用します。 最小費用循環問題 - 単一の商品を使用する 複数商品の循環 - コストを最適化せずに解決します。 シンプルな循環 - 商品を 1 つ使用するだけで、コストはかかりません。 複数商品フロー - が から までの商品 の需要を表す場合 、 すべて の 商品 について の エッジを作成します 。 他のすべてのエッジ について とします。
け
私
（
s
私
、
t
私
、
d
私
）
{\displaystyle K_{i}(s_{i},t_{i},d_{i})}
d
私
{\displaystyle d_{i}}
私
{\displaystyle i}
s
私
{\displaystyle s_{i}}
t
私
{\displaystyle t_{i}}
（
t
私
、
s
私
）
{\displaystyle (t_{i},s_{i})}
l
私
（
t
私
、
s
私
） = あなた （
t
私
、
s
私
） =
d
私
{\displaystyle l_{i}(t_{i},s_{i})=u(t_{i},s_{i})=d_{i}}
私
{\displaystyle i}
l
私
（ あなた 、 ヴ ） = 0
{\displaystyle l_{i}(u,v)=0}
最小コストの複数商品フロー問題 - 上記と同じですが、コストを最小化します。 最小費用フロー問題 - 上記と同様、商品が 1 つあります。 最大フロー問題 - すべてのコストを 0 に設定し、シンクから ソースに 、、 ∞、および のエッジを追加します 。
t
{\displaystyle t}
s
{\displaystyle s}
l （ t 、 s ） = 0
{\displaystyle l(t,s)=0}
あなた （ t 、 s ） =
{\displaystyle u(t,s)=}
c （ t 、 s ） = − 1
{\displaystyle c(t,s)=-1}
最小コスト最大フロー問題 - まず最大フロー量を見つけます 。次に、 とを使って解きます 。
メートル
{\displaystyle m}
l （ t 、 s ） = あなた （ t 、 s ） = メートル
{\displaystyle l(t,s)=u(t,s)=m}
c （ t 、 s ） = 0
{\displaystyle c(t,s)=0}
単一ソースの最短経路 - グラフ内のすべてのエッジをおよび とし、 および を持つエッジを追加します 。
l （ あなた 、 ヴ ） = 0
{\displaystyle l(u,v)=0}
c （ あなた 、 ヴ ） = 1
{\displaystyle c(u,v)=1}
（ t 、 s ）
{\displaystyle (t,s)}
l （ t 、 s ） = あなた （ t 、 s ） = 1
{\displaystyle l(t,s)=u(t,s)=1}
c （ t 、 s ） = 0
{\displaystyle c(t,s)=0}
全ペア最短経路 - すべての容量を無制限とし、ノードのペアごとに 1 つの商品 に対してフロー 1 を見つけます。
ヴ （ ヴ − 1 ）
/
2
{\displaystyle v(v-1)/2}
参考文献
^ Éva Tardos (1985). 「強力多項式最小コスト循環アルゴリズム」. Combinatorica . 5 (3): 247–255. doi :10.1007/BF02579369. ^ S. Even、A. Itai 、 A. Shamir (1976)。「時刻表と複数商品フロー問題の複雑さについて」 。SIAM Journal on Computing。5 ( 4)。SIAM: 691–703。doi :10.1137/0205048。2013年1 月 12日時点のオリジナルよりアーカイブ。 
