コラム・特集

5.2 一般ネットワーク・フロー問題

28日IEハンドブック
第14部 インダストリアル・エンジニアリングの最適化

第5章 ネットワーク最適化

5.2 一般ネットワーク・フロー問題

典型的なネットワーク・フロー 問題は兵培問題から起こり,工場(供給地)から市場(目的地)への製品の物流問題に及んでいる。工場での生産量と市場での需要量が既知である。製品は供給地から目的地へ直接運ばれる必要はなく,中間点で積み替えることもできる。輸送路が容量制限を持っ場合もある。この問題の目標は消費者の需要を満たした上で,製品の製造と輸送の変動費を最小にすることである。供給地,需要地,積み替え地は 「ノード 」と呼ばれ,ノード間をつなぐ輸送路は「アーク」と呼ばれている。

ネットワ ーク・ノード の例が図表4.5.1に示してあるノードは番号のついた丸で,またアークは矢印で表わされている。アークは方向を持つと仮定する。図表14.5.1 のネットワークには,さらにネットワーク問題でのその他の性質も付け加えられている。

各アークには流れ容量と,各アークを運ぶときの1単位当たりの輸送費用力導己入されている(たとえば,アーク3-5を 流れる流量は0から10単位の間にあり ,その費用は単位流当たり4ドルである)。括弧内の数字は,各ノードでの供給量か需要量を表わしている。ノード1は25単位供給する供給ノードであり,ノード 4と5はそれぞれ5単位と20単位とを必要とする需要(吸い込み)ノードであり,その需要量は負で示されている ノード2と3は積み替えノードである。

この形の問題は「最小費用流問題」あるいは「容量制限つき積み替え問題」と呼ばれている。この問題の目標は,最小費用流のパターンを見つけ, 供給ノードから需要を満たすことである。このネットワークに対して,次のような線形計画モデルを作ることができる。Xijをアーク i-j を使って,ノード iからj へ輸送する単位数とする 目的関数は,

これらのバランス式の特殊な構造に注目しておく必要がある。ネットワーク中の各ノードに対して, 1本のバランス式が対応しており,各式の流量変数Xijの係数は 0,+1,-1だけに限られている。各変数は必ず2本のバランス式の中に現われ, 1回は+1の係数を持ち ,

そのアークが出ていくノードに対応する式の中に,もう1回は-1の係数を持ち,そのアークが入っていくノードに対応する式の中に現われる。この特殊な構造が,これ専用の効率の良いアルゴリズムを作る上で利用されている。

上式での加算は,ネットワーク中に存在するアークの上でのみ実施される。すなわち, i番目の流れバランス式における第1項の和は, i-jがこのネットワーク のアークであるような,すべてのノードjに対し計算され , 第2項の和はk-iがこのネットワークのアークであるような,すべてのノードk に対して計算される。目的関数の和は ,ネットワークに含まれるすべてのアークi-jに対して計算され,ネットワーク上での流れに必要な総費用を表わしている。i番目のバランス式は,既に説明したようにノードiの流出量からiヘの流入量を差し引いたものが,そのノードでの正味の供給量(bjが負の場合には需要量)に等しくなければならないことを意味する。アークの流量の上限はUijであり, アークi-jの容量に制限がない場合には+∞ となる。アーク 流量の下限はlijであり,先の例題のようにゼロをとることが多い。次の節ではこの一般問題のいくつかの変種について,少し詳しくみてみよう。

本コラムは絶版となっている「IEハンドブック(サルベンティ編・日本能率協会訳・1986)」をアーカイブとして掲載するものです。このハンドブックの各章は多くの事例と理論を通して生産性向上に対するアイデアを提供するべく専門家によって執筆されています。基盤をなしているIEの考え方・原則はインダストリアル・エンジニアリングにかかわるすべてのひとに有用でしょう。

関連記事一覧

2019ものづくり公開セミナーガイド

B2Bデジタルマーケティングセミナー

ものづくり人材育成ソリューション

マーケティング分野オンラインセミナー