コラム・特集

4.2 離散形モデルの定式化の技法

IEハンドブック

第14部 インダストリアル・エンジニアリングの最適化


第4章 離散形最適化

4.2 離散形モデルの定式化の技法

整数計画法の定式化に対しては,より有効なモデルを得るために,各種の指針が作り出されてきた。ここで有効ということは, コンピュータにより比較的短時間でモデルの解が得られるということを意味する。それらの指針のいくつかは次のようなものである。

1.あらかじめ整数変数が大きな値(通常は20か,あるいはそれ以上)をとると分かっていれば,変数を連続として取り扱い,得られた連続解を丸める。

2.制約式の係数が問題を解くことを難しくしているのならば,制約式をできるだけ複雑でなく書くように注意する。たとえば,X1と X2が (非負)整数であることが要求されていれば,

121×1+164×2≦189

という制約条件式はこれと同値の式 ,


x1+x2≦ 1


と置き換えたほうがよい。他の同様な技法をShapiroが述べている。

3.許容領域の大きさを縮めれば,計算の手間を縮めることができる。そこで良い変数の下限と上限が望まれる。

また離散形モデルは,ある種の定式化の難しさを処理するために出現したものである。次のような状況の場合である。

 

1.2つの制約式のうちの,少なくとも1つをとる必要がある場合を考えてみる。たとえばある製品の製造 に関係して, 2つの資源のうち1つが選べるとする。このような場合は “どちらか一方” 制約となる。すなわち次のような制約に出合うことがある。

4×1+5×2く16
あるいは ,
2×1+x2く12

Mが十分に大きな数であり,yが (0-1)変数であるとすると,この “どちらか一方” 制約と同値の式は ,

4×1+5×2く 16+My
2×1+x2く12+M(1-y)

となる。最終解においてy=0ならば,第1式がとられ,第2式は冗長となる(なぜならMが大きい値のため)。逆にy=1となれば,もう一方の式が成り立つ。

2.先の技法の一般化をするには,L個の制約式のうち少なくともK個が成立する場合を考える(K<L)。
L個の制約式を ,

nΣj=1・aℓxj ≦bℓ  ℓ=1,2,…,L

と書けば,上の制約は次のように書ける。

となり ,ここでi=1,2,… …Rに対してyi=0 あるいは1である。

変数が(陽的にか陰的にか)有界であるPIPは「二進分割」とよばれる技法によっ て0-1計画に変換され, また非線形多項式0-1計画は,線形0-1形画に変換できることは知っておく価値がある(詳細については Phillips他あるいはGloverと Woolseyを参照されたい)。

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

関連記事一覧

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

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

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

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