経営システム工学入門実験 ロジスティクス 第３回

Presentation on theme: "経営システム工学入門実験 ロジスティクス 第３回"— Presentation transcript:

1 経営システム工学入門実験 ロジスティクス 第３回
経営システム工学入門実験 ロジスティクス　第３回 ２００９／７／６ 担当教員　森戸　晋 担当助手　黄　来国 協力：　森戸研究室修士学生

2 パレット回送問題 郵便局X 〒 郵便局Y 郵便局Z 郵便局A 郵便局B 郵便局C 郵便局D 140 120 270 250 70 50
出超局（都会） 入超局（田舎） +100 +250 +150 10 20 90 30 40 130 160 100 60 -180 -90 -120 -110

3

4 パレット回送問題のデータ

5 生産計画問題（２製品、３リソース） 大久保工場では、鉄鋼、電力、労働力という３種類のリソースを使って、２種類の製品を生産しています。この工場では、いま来週の生産計画を立てようとしています。手持ちのリソースの範囲で、利益最大とする生産計画を求めてください。 　 　　　製品１ 製品２ 　　　　来週使えるリソース 許容上限 鉄鋼 １ ２ １４ 電力 １ １ ８ 労働力 　 ３ １ １８ 利益 　 ２ 　３

6 数理計画問題（最適化問題）の定式化 変数(variables)の定義 なにが制御可能か。なにを動かして最適化を達成しようとするのか。
目的関数(objective function)の定義 計画をどう評価するのか。評価値を大きくしたいのか、小さくしたいのか。 制約条件(constraints)の定義 どのような制約条件があるのか。

7 線形計画問題 変数（決めること） 最大化 ｚ＝２ ｘ１ ＋ ３ ｘ ２ （目的関数：利益）
製品１の生産量 ｘ１ 製品２の生産量 ｘ２ 最大化 ｚ＝２ ｘ１ ＋ ３ ｘ ２ （目的関数：利益） 制約条件 ｘ１ ＋ ２ ｘ ２ ≦ １４ （鉄鋼） ｘ１ ＋ ｘ ２ ≦ ８ （電力） ３ ｘ１ ＋ ｘ ２ ≦ １８ （労働力） ｘ１，ｘ２≧０ 　（非負条件）

8 線形計画問題（ＬＰ） (Linear Programming)
目的関数、制約条件がすべて線形関数からなる 変数は、原則として非負の実数（連続変数） 最大化 　ｚ　＝Σ j=1,...,nｃｊ ｘｊ 制約条件 Σ j=1,...,nａｉｊ ｘｊ ＝ ｂｉ　, i=1,...,m 　　　　 ｘｊ ≧０ , j=1,...,n

9 ソルバー使用上の留意点 「変化させるセル」（変数セル）はなるべく一箇所にまとめる
複数の部分に分かれている場合はコンマ区切り 式をコピーする場合は、セルの相対参照と絶対参照を使いわける（セルの絶対参照切替はF4） 「オプション」で、「線形モデルで計算」と「非負数を仮定する」にチェックを忘れずに 整数条件や０－１条件が必要なときは、制約条件の指定の中で、変化させるセルを「区間」（＝整数）または「デー」（０－１）に

10 輸送問題(Transportation Problem)

11 輸送問題 供給量 必要量 １８ １０ ９ ２５ １２ １５ １１ 処理場A ６ 工場X １ ５ ４ 処理場B ５ ６ 工場Y ３ 処理場C
　９ ５ ６ 工場Y ２５ ３ 処理場C ６ １２ ８ 工場Z ７ ２ １５ 処理場D １０ １１ 枝上に輸送距離

12 輸送問題 (Transportation Problem)
変数（決めたいこと） 処理場ｉから工場ｊへの輸送量ｘij （≧０） 制約条件 １）処理場ｉからの輸送量は処理場ｉの供給量以下 ２）工場ｊへの輸送量は、工場ｊの必要量以上 目的関数（評価尺度；狙い） 延輸送距離を最小化

13 輸送問題の数式による表現 変数 ｘij =処理場ｉから工場ｊへの輸送量≧0
目的関数　　最小化　 6ｘAX+ｘAY+ 5ｘAZ+ 4ｘBX+5ｘBY+…+2ｘDY+10ｘDZ 制約条件 ｘAX+ｘAY+ ｘAZ≦18（処理場Aの送出量≦処理場Aの供給量） ．．． ｘAX+ｘBX+ｘCX +ｘDX≧15（ 工場Xへの輸送量≧工場Xの必要量） ．．．

14 輸送問題の数式による表現 データ 処理場ｉの供給量ai， 工場ｊの必要量ｂｊ 処理場ｉから工場ｊへの距離ｃij
目的関数　　最小化　ΣiΣｊｃijｘij 制約条件 Σｊｘij ≦ai　（処理場ｉから送り出される量≦処理場ｉの供給量） Σiｘij ≧ｂｊ （ 工場jへ輸送される量　　　 ≧工場ｊの必要量）

15 パレット回送問題の言葉による表現 流れの特徴： 都会から地方へのものの流れが、地方から都会へのものの流れより多い
流れの特徴：　都会から地方へのものの流れが、地方から都会へのものの流れより多い 特徴によって生じる問題：　ほっておくと、都市のパレットあるいはケース（以下、パレット）がなくなる 対策：　余っているところから、足りないところに効率よく送る

16 コンピュータに問題を解かせる コンピュータに輸送問題を解かせるためには、解法が必要 解法については、「基礎OR」などで学習
数理計画を解くためのパッケージ ①EXCELのソルバー（小規模な問題） ②商用数理計画パッケージ 　　CPLEX、OPL、XpressーMP、．．．

17 今日の演習・宿題 「鉄鋼電力労働力の生産計画問題」、「輸送問題」をソルバーで解く（すでに終了）
（実験後半） さまざまな問題を（数理計画で定式化して）ソルバーで解く 宿題は、レポートとして提出 締切7月1３日（月）13時 提出箇所：実験室レポートボックス

18 宿題1-1 （問題16） （問題16）乗捨てレンタカーの回送
宿題1-1　（問題16） （問題16）乗捨てレンタカーの回送 R社は、北海道の函館、室蘭、千歳、小樽、札幌、旭川、帯広に営業所を構え、50台の車で観光客相手にレンタカー事業を営んでいる。週末に車を借り出した客の多くが、最終旅行地近くの営業所に車を乗り捨てていくため、週明けの車の配置が週末の需要と著しく異なる。このため、毎週、週の半ばに週末の需要に合わせて、社員が手分けして車を1台ずつ回送している。R社の社長は、常々、回送にかかる手間や時間、それに費用をもっと節約できないものかと考えている。 右の表で、ある週の各営業所における週明けの配置と週末の需要(台数)と、各地点間の（最短）距離(km)が与えられている。どうしたら適切な回送計画が立てられるだろうか? レンタカーの週明けの配置 と週末の需要 各営業所間の（最短）距離（km）

19 宿題1-2 （問題17） （問題17）駅伝レースの出場順序
宿題1-2　（問題17） （問題17）駅伝レースの出場順序 　W大学の競走部では、今年も大学対抗の駅伝レースに参加することになった。この駅伝は、1チーム5人編成の5区間レースである。起伏の激しさが区間ごとに異なり、選手によって区間ごとの走行タイムがかなり違うため、選手登用の優劣がチームの成績に大きく影響する。A・B・C・D・Eの5人の選手を選抜し、各区間ごとに選手の走行タイム(分)を計ったところ、以下の表の結果を得た。どの選手をどの区間に出場させるのが最適か。 選手の区間別走行タイム(分)

20 宿題２ 　　身近な問題、高尚な問題等、何でもよいですから、最適化問題として捉えられる（現実的な）問題のシナリオを提示し、数理計画問題として定式化して下さい。定式化では、変数が何、目的関数が何で、制約条件が何かを簡潔、かつ、正確に示して下さい。また、小規模な問題でもよいので具体的なデータを与えて、EXCELソルバーで解き、その結果をもとに簡単なレポートをまとめてください。