コラム・特集

5.4 特別なネットワーク・アルゴリズム

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

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

5.4 特別なネットワーク・アルゴリズム

ネットワーク・システムとしてモデル化できる問題はたくさんあることが分かったと思うネットワークはシンプレックス法を使っても最適化することはできるが , ネットワーク・モデルの構造を利用して, シンプレックス法のルールを特殊化するための努力が積み重ねられてきた。その結果得られたアルゴリズムはきわめ有効で通常の線形計画法の手順ではとても解くことができないような,大きなネットワーク ・モデルを解くことができ るようになった。この有効性は次のような事実に基づいている。それはシンプレックス法のピボット演算において,各繰り返しごとにシンプレックス表を保持し,更新するという必要が無くなり,単純に足し算と引き算だけで実行できるということである。さらにこれらのアリゴリズムの利点は,関連したデータが整数ならば,最適解は整数値で得られるということである。

5.3節で述べた,すべてのネットワーク・モデルについての有効なアルゴリズムを ,ここで説明する余裕は無いが,割り当て問題を解くアルゴリズムについては,特 別なアルゴリズムを使って,ネットワーク・モデルを解くことの容易さを示す実例として述べておこう。この他のモデルの解法に興味をもつIEエンジニヤは,一般の数理計画法やオペレーションズ・リサーチのテキストを参照されたい。

図表14.5.4に示す割り当て問題を考えてみよう。最適な割り当てを見つける基本的な手段は費用行列で,どの行どの列に定数を加えてもあるいは引いても,最終の解には影響を与えないという 事実にもとづいている。

たとえば機械2にかけるどの仕事の費用も3ドルずつ増せば,第2行日は18,14,16となり,明らかにこの変更は最適割り当てに何ら影響を与えない。

この解法の手順では,ほうぼうの行や列から適当な大きさの費用を差し引いて,そ れにより目の子で最適解が見つかるようにする。まず費用行列の各行(列)の最小 な要素を見つけて,この値を行(列)のすべての要素から 差し引きそれぞれの行と列に少なくとも1つ0を含むような行列を作る。次に費用0の要素を使って許容解 を見つけることを試みる。もし見つかれば,それが最適割り当てである。

この例題では, 1行目から7, 2行目から11, 3行目から13を引いて,縮約した費用行列を作るすると図表14.5.5に示すような費用となり,これから次の許容割り当てが得られる。

これは最適割り当てである。一般には,行と列の操作だけで許容解を見つけるのは 不可能な場合がある。そこで図表14.5.6のように問題を修正して考えてみよう。

この問題の縮約行列は図表14.5.7のようになり,これから許容解を見つけることはできない。しかし , これ以後の検討から行列の0の位置を取り除くことによって, この行列への操作を続ける方法がある。この方法で例題を解いてみよう。行列から0を持つ位置を取り除くに当たって,最小限の数の行と列を消すことが必要である。縮約行列を見れば明らかなように,第1行と第2列を省くことによりこれが可能である。このようにして選ばれた行と列を線で抹消する。そこで縮約行列は図表14.5.8 のようになる。

次に,残った行列の中で最も小さい要素を探し出す。

この要素の値を残っている要素の値から差し引き,同時に先の行と列の削除のとき,交叉した位置の要素にはその値を加えておく。この例では残った行列の最小の位置はx23=1である。この値をx21,x23,x31,x33から差し引き,最後にx12にこの値を加える。この操作で図表14.5.9の行列が得られる。これでx32,x23,x11, というゼロ径路を選ぶことができ,総費用は

C32+C23+C11=13+13+7=33

となる 。

一般には,こ の行と列を抹消する過程を繰り返し実行する。1回の操作で許容なゼロ径路が見つからなくても,これが見つかるまで何度でも ,行列への操作を続ければよい。以上の例により特殊なアルゴリズムを使えば,ネットワーク・モデルを解くのが比較的容易になることが分かったであろう。

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

関連記事一覧

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

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

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

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