コラム・特集

4.3 離散形モデルの実例

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


第4章 離散形最適化

4.3 離散形モデルの実例

整数計画モデルについては多くの公表された実例があるが,そのうち最もよく研究されている2つのものは, ナップザック問題と工場配置問題である。

Xi≧0 , 整数j=1,……,J 
と定式化できる このモデルは各XJに対して,どんな非 負整数をも許す一般ナップザック問題であり,ナップザックには複数個の品物を入れることが許されている。ナップザック問題の特殊な場合として,Xjが0か 1に限定されていて,それぞれの品物はナップザック中に1個以上入れられないものもある。

ナップザック問題は1本の制約を持つPIPである。ナップザック問題は次の2つの理由で重要である。第1に,資本投資計画,機械負荷計画,プロジェクト選択間題などを含む多数の整数計画問題が,ナ ップザック問題に等価であることが示されている。第2の理由は,このクラスの問題を解くために,効率のよい解法が開発されている。ナップザック問題の解を求める効率のよい手順は,一般整数計画問題を解く新手順を開発する上での基盤となっている。ナップザック問題,その性質,解法に関するさらに多くの情報についてはGarfinkelとNem―hauser を参照されたい。

例題14.4.2「工場配置問題」 ある商品に対して,それぞれ既知の需要Djを持つ何人かの顧客がいるものとする。この商品を候補地の中から3個所を超えない用地を選んで製造しようとする。Fiは用地iに工場を建設するための固定費,Biは用地iにおける工場の最大能力。Cijは用地iから 顧客jヘの商品の単位当たりの輸送費である。 この問題の目的は,可能な最小の費用で顧客の需要を満たすには,工場を何個所に,またどの用地に建設したらよいかを決定することである。そこで ,

この工場配置問題は,MIP問題としてモデル化されている。このモデルを,次のようなさらに複雑な物流モデルに変換することもできる。すなわち,多品種生産, 1人の顧客からの注文は製造を分割しないという 条件,輸送路での時間制限を考えてのサービスヘの考慮,多段階在庫への考慮,のような特色を含めたモデルである。

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

関連記事一覧

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

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

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

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