コラム・特集

5.3 特殊なネットワーク・モデル

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

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

5.3 特殊なネットワーク・モデル

この節では,いくつかの特殊な最小費用流モデルのケ ースについて述べる。

輸送問題
輸送問題は,中間点をもたないネットワーク・フロー・モデルである。次の量が与えられているも のとする。

a1=供給地iで供給可能な単位数
b1=需要地jで必要とされる単位数
cij=供給地iから需要地jヘの単位輸送費

初めは総製品供給量は,総製品需要量に等しいと仮定する。すなわち

*訳者注原本ではこの点の説明はされていない。普通,上式が等しくない場合は,そのアンバランスの分だけのダミーの供給地,またはダミーの需要地を作って,この等式を成り立たせている。

(1)式は輸送に関する線形費用の構造を仮定して,総輸送費用の最小化を表わしたものである。(2)式は供給地iから,すべての可能な需要地への輸送量の和は,その供給地における総供給量αiに等しくなければならぬことを表わしている。(3)式は,すべての可能な供給地から需要地jヘの輸送量の和が,その需要地における 必要量bjに等しいことを示している。通常は(3)式は-1を乗じることにより,係数と右辺は正で書かれている。

輸送問題に対するネットワーク・モデルを図表14.5.2 に示す。輸送問題に対する情報は,通常図表14.5.3に示すような特別な表で示される。

割り当て問題

輸送問題は,供給地から需要地への資材の流れの形で述べられてきた。このモデルには,いろいろな応用が付け加えられる。n個の仕事がn機械に割り当てられる間題を考えてみよう。ここではCijが機械jによる仕事iの費用の尺度である。そこで

xij=1  仕事iが機械jに割り当てられた場合=0  それ以外の場合

と置くと,次の最適化問題を解くことによって,最良の割り当てを見つけることができる。

最初の制約条件式は,おのおの仕事が必ず1台の機械に割り当てられ, 2番目の式は,おのおの機械が必ず1つの仕事を受け持つことを示している。

割り当て問題は,決定変数xijが必ず0か1をとるのであるから整数計画問題である。しかし,これらの整数制約をxij ≧0で置き換えたとすれば,モデルは各供 給点(仕事)での供給量が1単位だけで,各需要点(機械)での必要量が1単位だけという輸送問題の特別な場合となる。ネットワーク・フロー問題は整数解を持つので,整数制約式の形式的な述は不必要である。したがって,ネットワーク・フロー・アルゴリズムを適用すれば,このような整数計画問題を直接解いたことになる。

最大流問題
最大流問題の目的は,供給ノードSから需要ノード t まで,できるだけ多くの資材を送ることである。この流れでの費用は考えない。∨をノードSからノード tへ送る資材の量とし,xijはアークi-jを経てノードiからjへの流量とすると,次のように定式化できる。

最短径路問題
最短径路問題は,理論面と実際面の両方の理由から,大きな興味が持たれている 特殊なネットワーク・モデルである。問題の要点をまとめていうと,各アークが距離 cijをもつネットワークが与えられたとき,このネットワークの中で,特定の始点(供給点)から特定の終点(需要点)までの最短距離をもつような径路を見つけることである。最短径路問題として,定式化できるいくつかの重要な応用があるが,そこでは初めからいま述べたような定式化にはなっていない。この種の応用には設備取替え資本投資,プロジェクト・スケジューリング,在庫計画などの問題が含まれる。この問題の理論的な興味はネットワークであることに加えて,特殊な構造をもつという点にあり,そのことが効率の良い解法を得ることにつながっている。


最短径路問題は,供給点から需要点に最小費用で1単位だけ輸送する,ネットワーク・フロー問題であると考えればよい。

最長径路問題
最短径路問題の定式化を目的関数最大化とし て形を変えれば ,ネットワーク上で最長径路を見つけることがで きる。この最長径路問題は,本質的には11部2章で示したアクティビティ・ネットワークの解析となる。その章でのアルゴリズムは, ネットワーク・モデルを解くのに役立つ効率の良い解法の実例である。

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

関連記事一覧

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

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

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

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