経営システム工学入門実験 ロジスティクス 第３回 ２００６／７／３ 担当教員 森戸 晋 担当助手 後藤 允 協力： 森戸研究室修士学生 ビールゲーム表彰 総合評価（発表＋総費用） 上位２チームを以下に表彰します 4班（ODAI） 6班（株式会社 白髭） パレット回送問題 +250 出超局（都会） +100 〒 郵便局Y 140 120 〒 郵便局X 270 -180 70 〒 郵便局A 40 20 90 〒 郵便局Z 100 60 50 250 130 160 90 〒 郵便局B 入超局（田舎） -90 10 20 〒 郵便局C -120 40 〒 郵便局D 70 10 10 30 +150 120 -110 パレット回送問題のデータ X X Y Z A B C D 受取量計 120 90 50 40 30 20 350 Y 140 270 120 90 70 50 740 実パレット 局間移動量 Z A B C 100 70 50 30 250 180 130 160 100 70 80 40 10 50 30 10 10 50 70 20 30 50 20 120 500 480 300 450 D 60 150 40 30 30 90 400 送出量 受取量 合計 合計 送出－受取 450 350 100 990 740 250 650 500 150 300 480 -180 210 300 -90 330 450 -120 290 400 -110 3220 3220 0 生産計画問題（２製品、３リソース） 大久保工場では、鉄鋼、電力、労働力という３種類のリソー スを使って、２種類の製品を生産しています。この工場では、 いま来週の生産計画を立てようとしています。手持ちのリ ソースの範囲で、利益最大とする生産計画を求めてください。 製品１ 製品２ 鉄鋼 電力 労働力 利益 １ １ ３ ２ ２ １ １ ３ 来週使えるリソース 許容上限 １４ ８ １８ 数理計画問題（最適化問題）の定式化 変数(variables)の定義 なにが制御可能か。なにを動かして最適 化を達成しようとするのか。 目的関数(objective function)の定義 計画をどう評価するのか。評価値を大きく したいのか、小さくしたいのか。 制約条件(constraints)の定義 どのような制約条件があるのか。 線形計画問題 変数（決めること） 製品１の生産量 製品２の生産量 ｘ１ ｘ２ 最大化 ｚ＝２ ｘ１ ＋ ３ ｘ ２ （目的関数：利益） 制約条件 ｘ１ ＋ ２ ｘ ２ ≦ １４ （鉄鋼） ｘ１ ＋ ｘ ２ ≦ ８ （電力） ３ ｘ１ ＋ ｘ ２ ≦ １８ （労働力） ｘ１，ｘ２≧０ （非負条件） 線形計画問題（ＬＰ） (Linear Programming) 目的関数、制約条件がすべて線形関数から なる 変数は、原則として非負の実数（連続変数） 最大化 ｚ ＝Σ j=1,...,nｃｊ ｘｊ 制約条件 Σ j=1,...,nａｉｊ ｘｊ ＝ ｂｉ , i=1,...,m ｘｊ ≧０ , j=1,...,n ソルバー使用上の留意点 • 「変化させるセル」（変数セル）はなるべく一箇 所にまとめる – 複数の部分に分かれている場合はコンマ区切り • 式をコピーする場合は、セルの相対参照と絶対 参照を使いわける（セルの絶対参照切替はF4） • 「オプション」で、「線形モデルで計算」と「非負 数を仮定する」にチェックを忘れずに • 整数条件や０－１条件が必要なときは、制約条 件の指定の中で、変化させるセルを「区間」（＝ 整数）または「デー」（０－１）に 輸送問題(Transportation Problem) 問題のシナリオ： 早稲田工業では、４ヵ所の原料処理場 A,B,C,D で処理された原料を使って、3 つ の工場 X,Y,Z で生産を行っている。7 月の処理場、および工場の生産計画はすでに決まっている。こ の原料の輸送は危険を伴うため、非常にコストがかさむ。輸送費は、輸送量＊輸送単価で計算できる。 各処理場から工場に送ることのできる原料の供給量、各工場が生産に必要とする原料の必要量が下表 のように与えられ、さらに、各処理場から各工場までの輸送単価が既知であるとき、総輸送費が最小 となる輸送計画を求めたい。 工場X 輸送量 (xij) 必要量 工場Y 工場Z 処理場A 処理場B 処理場C 処理場D 10 25 15 供給量 18 9 12 11 輸送問題 供給量 １８ 処理場A 必要量 ６ ５ １ ９ １２ １１ 処理場B 処理場C 処理場D ４ 工場X １０ 工場Y ２５ 工場Z １５ ５ ６ ３ ６ ８ ７ ２ １０ 枝上に輸送距離 輸送問題 (Transportation Problem) 変数（決めたいこと） 処理場ｉから工場ｊへの輸送量ｘij （≧０） 制約条件 １）処理場ｉからの輸送量は処理場ｉの供給量以 下 ２）工場ｊへの輸送量は、工場ｊの必要量以上 目的関数（評価尺度；狙い） 延輸送距離を最小化 輸送問題の数式による表現 変数 ｘ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の必 要量） ．．． 輸送問題の数式による表現 データ 処理場ｉの供給量ai， 工場ｊの必要量ｂｊ 処理場ｉから工場ｊへの距離ｃij 変数 ｘij =処理場ｉから工場ｊへの輸送量≧0 目的関数 最小化 ΣiΣｊｃijｘij 制約条件 Σｊｘij ≦ai （処理場ｉから送り出される量≦処理場ｉの供給量） Σiｘij ≧ｂｊ （ 工場jへ輸送される量 ≧工場ｊの必要量） パレット回送問題の言葉による表 現 流れの特徴： 都会から地方へのもの の流れが、地方から都会へのものの 流れより多い 特徴によって生じる問題： ほっておく と、都市のパレットあるいはケース（以 下、パレット）がなくなる 対策： 余っているところから、足りな いところに効率よく送る コンピュータに問題を解かせる コンピュータに輸送問題を解かせるために は、解法が必要 解法については、「基礎OR」などで学習 数理計画を解くためのパッケージ ①EXCELのソルバー（小規模な問題） ②商用数理計画パッケージ CPLEX、OPL、XpressーMP、．．． 今日の演習・宿題 「鉄鋼電力労働力の生産計画問題」、「輸送 問題」をソルバーで解く（すでに終了） （実験後半） さまざまな問題を（数理計画で定式化して）ソ ルバーで解く 宿題は、レポートとして提出 締切7月10日（月）13時 提出箇所：51号館2階レポートボックス 宿題1-1 （問題16） （問題16）乗捨てレンタカーの回送 R社は、北海道の函館、室蘭、千歳、小樽、札 幌、旭川、帯広に営業所を構え、50台の車 で観光客相手にレンタカー事業を営んでい る。週末に車を借り出した客の多くが、最終 旅行地近くの営業所に車を乗り捨てていくた め、週明けの車の配置が週末の需要と著し く異なる。このため、毎週、週の半ばに週末 の需要に合わせて、社員が手分けして車を1 台ずつ回送している。R社の社長は、常々、 回送にかかる手間や時間、それに費用を もっと節約できないものかと考えている。 右の表で、ある週の各営業所における週明け の配置と週末の需要(台数)と、各地点間の （最短）距離(km)が与えられている。どうした ら適切な回送計画が立てられるだろうか? レンタカーの週明けの配置 と週末の需要 函館 室蘭 千歳 小樽 札幌 旭川 帯広 週明け配置 10 1 25 2 6 2 4 週末の需要 4 4 13 3 15 8 2 各営業所間の（最短）距離 （km） 始点 終点 函館 室蘭 千歳 小樽 札幌 旭川 帯広 函館 室蘭 千歳 小樽 札幌 旭川 帯広 0 191 278 273 309 447 600 191 0 87 161 125 263 416 278 87 0 74 38 176 329 273 161 74 0 36 174 327 309 125 38 36 0 138 291 447 263 176 174 138 0 179 600 416 329 327 291 179 0 宿題1-2 （問題17） （問題17）駅伝レースの出場順序 W大学の競走部では、今年も大学対 選手の区間別走行タイム(分) 抗の駅伝レースに参加することに なった。この駅伝は、1チーム5人編 成の5区間レースである。起伏の激 区間 しさが区間ごとに異なり、選手に 1区 2区 3区 4区 5区 よって区間ごとの走行タイムがかな A 22.2 33.2 16.6 39.3 50.3 り違うため、選手登用の優劣がチー ムの成績に大きく影響する。A・B・ 選 B 21 32.8 16.7 40.2 51.2 C・D・Eの5人の選手を選抜し、各区 手 C 24.6 36.1 18.5 37.4 46.4 D 26.0 35.2 19.1 36.9 45.7 間ごとに選手の走行タイム (分)を 計ったところ、以下の表の結果を得 E 22.5 33.6 17.5 37.8 49.0 た。どの選手をどの区間に出場させ るのが最適か。 宿題２ 身近な問題、高尚な問題等、何でもよいで すから、最適化問題として捉えられる（現実 的な）問題のシナリオを提示し、数理計画問 題として定式化して下さい。定式化では、変 数が何、目的関数が何で、制約条件が何か を簡潔、かつ、正確に示して下さい。また、小 規模な問題でもよいので具体的なデータを与 えて、EXCELソルバーで解き、その結果をも とに簡単なレポートをまとめてください。
© Copyright 2024 ExpyDoc
