施设配置问题.pptVIP

１０．施設配置問題 物流費用削減のための問題 この時、施設を２つ閉鎖したいのだが どの２つを閉鎖すれば一番費用が最小となるか？ （表中数値は施設から顧客ゾーンへの推定輸送費用を示し、 ＊印は顧客がどの施設から輸送するのが最適かを表す） 常識に基づいた解き方 各施設を閉鎖したと仮定した時、輸送費用の増加が最小のところを閉鎖する。（このような意思決定を貪欲ヒューリスティックと呼ぶ） ?Aを閉鎖した場合　４５０－１１０＝３４０ ?Bを閉鎖した場合　１１５－６５＝５０ ?Cを閉鎖した場合　１６５－１２５＝４０ ?Dを閉鎖した場合　１１５－１００＝１５　　　　よってDを閉鎖 常識に基づいた解き方（つづき） 同様の方法でもう１つ閉鎖する施設を求める。 ?Aを閉鎖した場合　６４０－１１０＝５３０ ?Bを閉鎖した場合　５８５－６５＝５２０ ?Cを閉鎖した場合　 （１６５－１２５）＋（５８０－１１５）＝５０５　　　　Cを閉鎖 この結果年間輸送費用は９２０となる 貪欲ヒューリスティックは完璧か？ 今回の問題では貪欲ヒューリスティックを使って、 正しい解は得ることはできず、解としては 「施設Aと施設D」を残すことが最適解であった。 以上のことから、常識に従った判断では最適解を 得られるとは限らず、時に大きな損失を引き起こす。 流通経路の輸送費用最小化 流通経路＜工場→倉庫→顧客＞において どのような経路を選択すれば費用が最小となるのか？ （ただし工場２は老朽化のため60000kgしか製造できない） 解き方その１ 顧客を１番輸送費用の安い倉庫に割り振り、 工場から倉庫への輸送はできるだけ安い工場から選ぶ。 解き方その２ 工場から顧客に至るルートの中で、最も輸送費用が安いところを 通るように顧客を倉庫に振り分ける。 解き方その２（運送費用が下がった場合） 倉庫２→顧客３の運送費用が４から２に下がった場合 解き方その２（運送費用が下がった場合2) 倉庫２→顧客１の運送費用が２から０．５に下がった場合 まとめ 以上のことから、常識や山勘だけでは最適解を出すことはできず、 最適化理論を用いたロジスティック最適化が必要となってくる。 * * １００＊ ８４０ １１５ ４５０ 施設D １１５ １２５＊ ５９０ ６７０ 施設C ５８０ ２００ ６５＊ ６４０ 施設B　 ５９５ １６５ ５８５ １１０＊　 施設A 顧客４ 顧客３ 顧客２ 顧客１ １１５＊ １２５＊ ５９０ ６７０ 施設C ５８０ ２００ ６５＊ ６４０ 施設B　 ５９５ １６５ ５８５ １１０＊ 施設A 顧客４ 顧客３ 顧客２ 顧客１ 施設Dを閉鎖した後の顧客の施設への割り振り ＜解き方＞ ５８０＊ ２００ ６５＊ ６４０ 施設B ５９５ １６５＊ ５８５ １１０＊ 施設A 顧客４ 顧客３ 顧客２ 顧客１ 施設Cを閉鎖した後の顧客の施設への割り振り これだと年間輸送費用は４９０となり、貪欲ヒューリスティックによる解より４３０も安い！！ １００ ８４０ １１５＊ ４５０ 施設D ５９５ １６５＊ ５８５ １１０＊ 施設A 顧客４ 顧客３ 顧客２ 顧客１ 最適解における顧客の施設への割り振り 工場１ 工場２ 倉庫１ 倉庫２ 顧客１ 顧客２ 顧客３ 0 5 4 2 3 4 5 2 1 4 ≦60000 需要量 50000 需要量 需要量 100000 50000 工場１ 工場２ 倉庫２ 顧客１ 顧客２ 顧客３ 5x140000 2x60000 2x50000 1x100000 4x50000 ≦60000 需要量 50000 需要量 需要量 100000 50000 工場?倉庫間 小計 820000 合計 1220000 小計 400000 倉庫?顧客間 倉庫１ ＜解き方その１＞ 工場１ 工場２ 倉庫１ 倉庫２ 顧客１ 顧客２ 顧客３ 0x100000 5x40000 2x60000 3x50000 5x50000 1x100000 ≦60000 需要量 50000 需要量 需要量 100000 50000 工場?倉庫間 小計 320000 合計 820000 小計 500000 倉庫?顧客間 ＜解き方その２＞ 工場１ 工場２ 倉庫１ 倉庫２ 顧客１ 顧客２ 顧客３ 0x50000 5x90000 2x60000 3x50000 1x100000 ２x50000 ≦60000 需要量 50000 需要量 需要量 100000 50000 工場?倉庫間 小計 570000 合計 920000 小計 350000 倉庫?顧客間 工場１ 工場２ 倉庫１ 倉庫２ 顧客１ 顧客２ 顧客３ 5x140000 2x60000 0.5x50000 1x100000 2x50000 ≦60000 需要量