1 経営システム工学入門実験ロジスティクス第３回２００９／７／６担当教員森戸晋担当助手黄来国協力：森戸研究室修士学生 +250 出超局（都会） +100 〒郵便局Y 140 270 -180 〒郵便局A 40 20 90 〒郵便局Z 100 60 70 250 120 〒郵便局X 50 パレット回送問題 2 130 160 90 〒郵便局B 入超局（田舎） -90 10 20 〒郵便局C -120 40 〒郵便局D 70 10 10 30 +150 120 -110 3 4 パレット回送問題のデータ 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 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) 問題のシナリオ：早稲田工業では、４ヵ所の原料処理場 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 11 ４工場X １０工場Y ２５工場Z １５５６３６８７２１０枝上に輸送距離 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    変数ｘij =処理場ｉから工場ｊへの輸送量≧0 目的関数最小化 Σ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）乗捨てレンタカーの回送 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） 19 （問題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 た。どの選手をどの区間に出場させるのが最適か。宿題２ 20 身近な問題、高尚な問題等、何でもよいですから、最適化問題として捉えられる（現実的な）問題のシナリオを提示し、数理計画問題として定式化して下さい。定式化では、変数が何、目的関数が何で、制約条件が何かを簡潔、かつ、正確に示して下さい。また、小規模な問題でもよいので具体的なデータを与えて、EXCELソルバーで解き、その結果をもとに簡単なレポートをまとめてください。