1 経営システム工学入門実験 ロジスティクス 第3回 2011/7/18 担当教員 森戸 晋・本間 裕大 担当助手 崔 漢龍 協力: 森戸研究室修士学生 +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 生産計画問題(2製品、3リソース) 大久保工場では、鉄鋼、電力、労働力という3種類のリソー スを使って、2種類の製品を生産しています。この工場では、 いま来週の生産計画を立てようとしています。手持ちのリ ソースの範囲で、利益最大とする生産計画を求めてください。 製品1 製品2 鉄鋼 電力 労働力 利益 1 1 3 2 2 1 1 3 来週使えるリソース 許容上限 14 8 18 6 数理計画問題(最適化問題)の定式化 変数(variables)の定義 なにが制御可能か。なにを動かして最適 化を達成しようとするのか。 目的関数(objective function)の定義 計画をどう評価するのか。評価値を大きく したいのか、小さくしたいのか。 制約条件(constraints)の定義 どのような制約条件があるのか。 7 線形計画問題 変数(決めること) 製品1の生産量 製品2の生産量 x1 x2 最大化 z=2 x1 + 3 x 2 (目的関数:利益) 制約条件 x1 + 2 x 2 ≦ 14 (鉄鋼) x1 + x 2 ≦ 8 (電力) 3 x1 + x 2 ≦ 18 (労働力) x1,x2≧0 (非負条件) 線形計画問題(LP) 8 (Linear Programming) 目的関数、制約条件がすべて線形関数から なる 変数は、原則として非負の実数(連続変数) 最大化 z =Σ j=1,...,ncj xj 制約条件 Σ j=1,...,naij xj = bi , i=1,...,m xj ≧0 , j=1,...,n ソルバー使用上の留意点 9 • 「変化させるセル」(変数セル)はなるべく一箇 所にまとめる – 複数の部分に分かれている場合はコンマ区切り • 式をコピーする場合は、セルの相対参照と絶対 参照を使いわける(セルの絶対参照切替はF4) • 「オプション」で、「線形モデルで計算」と「非負 数を仮定する」にチェックを忘れずに • 整数条件や0-1条件が必要なときは、制約条 件の指定の中で、変化させるセルを「区間」(= 整数)または「デー」(0-1)に 10 輸送問題(Transportation Problem) 問題のシナリオ: 早稲田工業では、4ヵ所の原料処理場 A,B,C,D で処理された原料を使って、3 つ の工場 X,Y,Z で生産を行っている。7 月の処理場、および工場の生産計画はすでに決まっている。この 原料の輸送は危険を伴うため、非常にコストがかさむ。輸送費は、輸送量*輸送単価で計算できる。 各処理場から工場に送ることのできる原料の供給量、各工場が生産に必要とする原料の必要量が下表 のように与えられ、さらに、各処理場から各工場までの輸送単価が既知であるとき、延輸送距離(輸 送距離*輸送量)が最小となる輸送計画を求めたい。 工場X 輸送量 (xij) 必要量 工場Y 工場Z 処理場A 処理場B 処理場C 処理場D 10 25 15 供給量 18 9 12 11 輸送問題 供給量 18 処理場A 必要量 6 5 1 9 12 11 処理場B 処理場C 処理場D 11 4 工場X 10 工場Y 25 工場Z 15 5 6 3 6 8 7 2 10 枝上に輸送距離 12 輸送問題 (Transportation Problem) 変数(決めたいこと) 処理場iから工場jへの輸送量xij (≧0) 制約条件 1)処理場iからの輸送量は処理場iの供給量以 下 2)工場jへの輸送量は、工場jの必要量以上 目的関数(評価尺度;狙い) 延輸送距離を最小化 13 輸送問題の数式による表現 変数 xij =処理場iから工場jへの輸送量≧0 目的関数 最小化 6xAX+xAY+ 5xAZ+ 4xBX+5xBY+…+2xDY+10xDZ (延輸送距離) 制約条件 xAX+xAY+ xAZ≦18(処理場Aの送出量≦処理場Aの供給量) ... xAX+xBX+xCX +xDX≧15( 工場Xへの輸送量≧工場Xの必 要量) ... 14 輸送問題の数式による表現 データ 処理場iの供給量ai, 工場jの必要量bj 処理場iから工場jへの距離cij 変数 xij =処理場iから工場jへの輸送量≧0 目的関数 最小化 ΣiΣjcijxij (延輸送距離) 制約条件 Σjxij ≦ai (処理場iから送り出される量≦処理場iの供給量) Σixij ≧bj ( 工場jへ輸送される量 ≧工場jの必要量) 15 パレット回送問題の言葉による表 現 流れの特徴: 都会から地方へのもの の流れが、地方から都会へのものの 流れより多い 特徴によって生じる問題: ほっておく と、都市のパレットあるいはケース(以 下、パレット)がなくなる 対策: 余っているところから、足りな いところに効率よく送る 16 コンピュータに問題を解かせる コンピュータに輸送問題を解かせるために は、解法が必要 解法については、「基礎OR」などで学習 数理計画を解くためのパッケージ ①EXCELのソルバー(小規模な問題) ②商用数理計画パッケージ CPLEX、OPL、XpressーMP、... 今日の演習・宿題 17 「鉄鋼電力労働力の生産計画問題」、「輸送 問題」をソルバーで解く(すでに終了) (実験後半) さまざまな問題を(数理計画で定式化して)ソ ルバーで解く 宿題は、レポートとして提出 締切7月25日(月)13時 提出箇所:実験室レポートボックス 演習: 数理計画問題集 (問題1~15) 18 全員以下の問題は解いてください (1)問題2(パレット)、問題5(速達配達) (2)問題6(レポート)、問題7(コンサート)、 問題8(ハブ)の少なくとも一つ (3)問題9(施設配置)、問題12(農場経 営)の少なくとも一つ 班内で手分けしてできるだけ多くの問題 を解くようにしてください 19 宿題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) 20 (問題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 た。どの選手をどの区間に出場させ るのが最適か。 宿題2 21 身近な問題、高尚な問題等、何でもよいで すから、最適化問題として捉えられる(現実 的な)問題のシナリオを提示し、数理計画問 題として定式化して下さい。定式化では、変 数が何、目的関数が何で、制約条件が何か を簡潔、かつ、正確に示して下さい。また、小 規模な問題でもよいので具体的なデータを与 えて、EXCELソルバーで解き、その結果をも とに簡単なレポートをまとめてください。 EXCEL ソルバーの設定 22 今日の実験では、EXCELソルバーを使いま す。EXCELのメニューバーの「データ」を選択 し、ツール内に「ソルバー」のアイコンが作ら れていることを確認してください。 アイコンが作られていない場合のソルバー の設定については 実験演習HP の表の下 |PC関連マニュアル| の左メニューの 4.(1)ソルバー・分析ツール のPDF資料内の 5.3 で確認ができます。
© Copyright 2024 ExpyDoc