OR事典

多品種フロー

読み方：たひんしゅふろー
【英】：multicommodity flow

1つのネットワーク上の複数の品種の流れ. 枝容量をもつ有向グラフと, 各品種ごとに出発点と到着点となる点が与えられているとき, 各枝ではすべての品種のフロー量の和はその枝の容量を超えず, 各品種ごとに出発点と到着点以外では, 流出量が流入量と等しくなる枝上の品種ごとの流れを多品種フローという. 連続値をとる多品種フローを求める問題は線形計画問題に定式化できるが, 整数値をとる多品種フローを求める問題はNP完全である.

「OR事典」の他の用語

グラフ･ネットワーク：

基多面体  基族  基本分割  多品種フロー  多項式時間アルゴリズム  安定結婚問題  完全グラフ