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

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 演習： 数理計画問題集 （問題１～１５） 全員以下の問題は解いてください （１）問題２（パレット）、問題５（速達配達）
演習：　数理計画問題集 　　　（問題１～１５） 全員以下の問題は解いてください （１）問題２（パレット）、問題５（速達配達） （２）問題６（レポート）、問題７（コンサート）、問題８（ハブ）の少なくとも一つ （３）問題９（施設配置）、問題１２（農場経営）の少なくとも一つ 班内で手分けしてできるだけ多くの問題を解くようにしてください

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

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

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

22 EXCEL ソルバーの設定 　　今日の実験では、EXCELソルバーを使います。EXCELのメニューバーの「データ」を選択し、ツール内に「ソルバー」のアイコンが作られていることを確認してください。 　　アイコンが作られていない場合のソルバーの設定については 実験演習ＨＰ の表の下 　　　　　｜ＰＣ関連マニュアル｜　 の左メニューの　 　　　４．（１）ソルバー・分析ツール のＰＤＦ資料内の　５．３　で確認ができます。