南山大学情報理工学部 情報システム数理学科 鈴木 敦夫

Presentation on theme: "南山大学情報理工学部 情報システム数理学科 鈴木 敦夫"— Presentation transcript:

1 南山大学情報理工学部 情報システム数理学科 鈴木 敦夫
2012年度　 オペレーションズ・リサーチ概論 南山大学情報理工学部 情報システム数理学科 鈴木　敦夫 The last speaker is myself. This is a joint work with Zvi Drezner and Tammy Drezner. Our topics is about a competitive location problem model in a plane. Let’s see the next slide.

2 厳禁 講義を始めるにあたって 注意してもたびたび繰り返す学生には他の学生のために退室を求めることも 成績評価 講義中の注意事項
講義に集中すること 他の受講生の邪魔にならぬこと 私語 教室からの途中退室 その他講義の妨げとなること 注意してもたびたび繰り返す学生には他の学生のために退室を求めることも 厳禁

3 OR（オペレーションズ・リサーチ）とは ORの起源
軍事研究としてスタート  1935年にイギリスで実用的なレーダーが開発され ると、ドーバー海峡に面した地域に、敵機や敵艦の接近を察知するために 配備する計画がたてられた。当時の技術水準では製造できるレーダーに限 りがあったため、どのように配備して運用すればもっとも高い効果が期待で きるかが、問題になった。物理学者のブラケットをはじめとして、さまざまな 学問分野の研究者が動員されて、検討が開始された。 その結果、1939年にはじまった第2次世界大戦の初めにはドイツ軍機1機を 撃墜するのに、平均して高射砲弾2万発を要していたのが、5分の1程度に 減少したといわれる。イギリスでの成果は、アメリカでも関心をあつめ、42年 には大規模なORチームがつくられて研究がすすめられた。 "オペレーションズリサーチ" Microsoft(R) Encarta(R) Encyclopedia (C) Microsoft Corporation. All rights reserved.

4 OR（オペレーションズ・リサーチ）とは 第2次世界大戦でもドイツのUボートは連合軍に対して通商破壊戦を しかけ、イギリスを敗北の一歩手前までおいこんだ。 "潜水艦" Microsoft(R) Encarta(R) Encyclopedia 2001 (C) Microsoft Corporation. All rights reserved.

5 OR（オペレーションズ・リサーチ）とは 爆弾をつんだ戦闘機で、アメリ カの戦艦に体当たりする特攻戦 法は、1944年から組織的に採 用されるようになった。特攻隊 の攻撃になやまされたアメリカ 軍は、この攻撃を「カミカゼ」とよ んでおそれた。 "特別攻撃隊の攻撃で炎 上する米空母" Microsoft(R) Encarta(R) Encyclopedia 2001 (C) Microsoft Corporation. All rights reserved.

6 戦後のOR 大戦末期から戦後にかけては、ORが軍事研究だけでなく、工業や経営計画にま で広がり、線形計画法、動的計画法、多変量解析、待ち行列理論、PERT/CPM、 ゲーム理論などの応用数学の形式が生みだされ、コンピューターを活用した解析 がおこなわれるようになっていった。 初期にはすでに、同一の原料や資源から複数の製品を製造できるときに、それぞ れの製品をどの程度生産すると利益を最大化できるかとか、複数の地点を巡回す るのに、最短時間で完了する経路を探索するといった問題がとりあげられた。 ORにとっては対象となる問題や解決手法には制限がなく、時間、距離、数量と いった明らかに数値化できるものから、一定の基準で数値化できるものであれば、 満足度や好感度といった感覚的なものまであつかうことができる。今日では、企業 経営の意思決定だけでなく、全地球規模の資源利用などについても応用されてい る。学問分野としても、工学をはじめとして、会計学、経営学、経済学など多方面 でとりいれられている。 "オペレーションズリサーチ" Microsoft(R) Encarta(R) Encyclopedia 2001 (C) Microsoft Corporation. All rights reserved.

7 コンピュータの発達 コンピュータの起源 ENIAC(Electronic Numerical Integrator and Computer)は初の完 全電子式の大型汎用(はんよう)のデジタ ル・コンピューターである。1946年、ペン シルベニア大学でつくられたこのコン ピューターは、55年まで使用された。 ENIACには約1万8000本の真空管が つかわれたほか、プログラミングごとに 手作業で配線しなおす必要があった。 UPI/THE BETTMANN ARCHIVE/Corbis "ENIAC(エニアック)" Microsoft(R) Encarta(R) Encyclopedia (C) Microsoft Corporation. All rights reserved.

8 コンピュータの発達 1964年、IBMは革命的なコ ンピューター、システム360 を開発した。これはソフトウェ アやシステム機器を交換で きる最初のメインフレーム・ コンピューターだった。60年 代から70年代にかけてIBM は世界のメインフレーム市 場を席巻した。 Charles E. Rot/Corbis "IBMのメインフレーム型コンピューター、シ ステム360" Microsoft(R) Encarta(R) Encyclopedia 2001 (C) Microsoft Corporation. All rights reserved.

9 コンピュータの発達 Elena Rooraid/Photo Edit/PNI; Robert Frerck/Woodfin Camp and Associates, Inc.; Rick Friedman/Black Star "パーソナルコンピューター" Microsoft(R) Encarta(R) Encyclopedia 2001 (C) Microsoft Corporation. All rights reserved. パソコンのおかげで、人間の仕事や遊びが大きく変化し た。現在では、日常生活のさまざまな場面でパソコンが 活躍している。写真はコンピューターの万能性と機能性 をしめす。

10 DEC（Digital Equipment Corporation)（1995年） Global Supply Chain再編成
ＤＥＣの事例 DEC（Digital Equipment Corporation)（1995年） Global Supply Chain再編成 どこで何を生産し，どこへ運ぶか どの部品をアウトソーシングするか どのベンダーから調達するか 手法：混合整数計画法 効果：年間1億$の費用削減 Franz Edelman Award (1995) Interfaces 25：１ (1995) pp

11 DECの事例（改善前） ＝ロジスティクス・センター ＝チップ＆メディア ＝本体 ＝モジュール NewEnglandSites Ayr
Queensterry Hull Kantana Galway Cororado Augusta Clonmel Nijimegen NewEnglandSites WCVC Cupertino Hudson Westminster Shenzhen Tokyo Phenix Greenville Shrewsbury springfiled Boston India Westfield Mexico Taiwan Mariboro Franklin HongKong Andover PuetroRico Saiem Singapore Brazil Sydney ＝ロジスティクス・センター ＝チップ＆メディア ＝本体 ＝モジュール

12 DECの事例（改善後） ＝ロジスティクス・センター ＝チップ＆メディア ＝本体 ＝モジュール Ayr Queensterry Kantana
Cororado Augusta England Nijimegen WCVC Tokyo Albuquerque Greenville Mexico Taiwan HongKong Singapore Sydney ＝ロジスティクス・センター ＝チップ＆メディア ＝本体 ＝モジュール

13 Thank you Dr. Milne. I am Hans Jürgen Marx, the president of Nanzan University. I greatly appreciate INFORMS giving us a chance to present our projects as a finalist of Franz Edelman Competition.   You may wonder why an educator is standing here before you. Obviously, I am not the CEO of a large international corporation, though I understand that most applicants for the Franz Edelman Award are from business. But, I believe that being relatively small and being a non-profit educational institution are exactly the reasons why my colleagues and I should be standing here before you today, introducing to you the projects we undertook. Before we begin to tell you how OR/MS has become a critical tool in helping Nanzan to become more competitive, I would first like to show you a video that will introduce Nanzan. (VIDEO)

14 The Science of Better Project
INFORMSが2004年から開始したプロジェクト ORを企業にもっと利用してもらおう Franz Edelman 賞をプロモート 華やかな授賞式 アメリカを代表する企業のCEOたち 過去の受賞者のクラブ さて、INFORMSが2004年から開始したThe Science of Betterプロジェクトですが、いまよりもっと企業にORを理解してもらおう、ORを使って利潤をあげてもらおうという学会あげての活動です。このようなバッジや帽子、Tシャツ、ポスターなどをつくり全国大会や支部の活動で配布しています。 また、企業が受賞対象になるFranz Edelman賞を今年から大々的にプロモートしています。華やかな授賞式を行い、GMなどのアメリカを代表する企業のCEOを呼んで講演し、また、過去の受賞者には、あらためて表彰を行っています。

15 この写真は過去のファイナリストにメダルを授与するときのものです。中央に私と、南山大学教授で元OR学会会長の長谷川教授が写っています。

16 ORの威力 ２００５年のFranz Edelman Finalist賞受賞者から ゼネラルモータース：年間21億ドルのコスト削減
アテネオリンピック実行委員会：7千万ドルの利益 P＆G：２年半で３億ドルのコスト削減 スィフト：年間1300万ドルの利潤増大 さて、このようにINFORMSはORを売り込んでいるのですが、実際のところ、ORは企業経営に役立つのかと皆さんはお思いになるかもしれません。そこで、2005年のFranz　Edelman　Finalistがどのくらい、ORを使ってコスト削減、利潤増大をはかったかをまとめてみました。 ＜スライドにしたがって説明＞ Elli　Lillyは直接金額に言及しなかったのでわかりませんが、製薬会社ですので、かなりの金額になっていると思います。 南山大学は、あとでご紹介しますように、１年間で約３億円、つまり３00万ドルですから規模ではこれらの企業に及ばないのですが、予算規模が年間１１０億円ですから、パーセントとしては大きいと思います。

17 ORの威力 Franz Edleman 賞受賞者 2006 Warner Robins Air Logistics Center
年間5千万ドルの経常経費の節約 24億ドルの取替えコストの削減 2004　Motorolla 6億ドルの調達コスト削減 2003　Canadian Pacific Railway 1億7千万ドルのコスト削減 こちらは、Franz　Edelman賞を受賞した企業です。 2006年はWarner　Robins　Air　Logistics　Centerが受賞しました。ここは、米軍がイラクで使用しているC-5輸送機の修繕とオーバーホールを請け負っている会社で、要員と作業のシフトスケジュールを改善して、年間5千万ドルの経費と、C-5のオーバーホールと修繕の時間を短縮したことで、新規に購入するとすれば24億ドルかかるC-5を買わなくてすむようにしたと言っていました。 2005年はさきほど紹介したGMです。 2004年はモトローラが購買のシステムをIT化して、ORの手法を用いて改善し、6億ドルの調達コストを削減しました。 2003年はカナディアンパシフィックレイルウェイが貨車のスケジューリングを改善して1億7千万ドルのコスト削減に成功しています。 このように、Franz　Edelman賞に応募してくる企業だけでもおそらく毎年20億ドルを越えるコスト削減を行っていると思います。実際にORを使っている企業はこの何十倍にもなりますので、ORによるコスト削減は全米で数百億ドルになるのではないでしょうか。

18 この写真は10月28日、Franz　Edelman　Finalist賞を祝って、名古屋駅のマリオットホテルで行われた授賞式で撮ったものです。中央のお二人はアメリカのOR／経営科学学会の元会長のピーター・ノルデン博士夫妻です。こちらは，南山大学のハンス・ユーゲンマルクス学長です。マルクス学長はカソリックの神父ですが，改革に熱心で，思い切った施策をいくつも実施しています。私もその一人ですが，学内でもファンが多く，彼らをマルキストと呼んでいます。カソリックなのにマルキストというのも変ですが，これからお話しする事例も，マルクス学長，マルキストたちの強い支援がなければ実現しませんでした。実際、マルクス学長は、昨年の4月にカリフォルニア州、パームスプリングスで開催されたFranz Edelman賞の最終審査会にわれわれと一緒に参加し、ORがいかに組織の改革に役立っているかを力説されました。 トップの理解とサポートはどのような改革にも非常に重要です。

19 スクールバスプロジェクト スクールバスの費用削減 実際に行ったこと スクールバスの無料化（2002年10月）により
大学の費用負担が増大していた ほとんど乗客のいないバスを走らせていた 実際に行ったこと 需要を把握 需要を満たすような仮想的なダイヤを作成 →　問題点が浮き彫りに 問題点を解決するためのシナリオを作成 →　山崩し法

20 スクールバスプロジェクト 聖霊中学校、高等学校と大学の講義開始時刻 間隔をあと20分ひろげればスクールバスの台数 を5台減らせる
大学の講義開始時刻を９：３０から９：５０に スクールバス運行の委託業者との交渉 事務方が交渉

21 スクールバスプロジェクトの成果 バス購入費の節約 運行費の節約 5億1千万円の購入費が必要とされていた 3億4千万円の買替えのみ（20台）
7千万円の新規購入（4台） 4億4千万円の買替え（NOXPM法による）（26台） 3億4千万円の買替えのみ（20台） 運行費の節約 年間3億4千万円の運行費が必要とされていた 年間2億2千万円に削減

22 入試監督自動割当システムの作成 手動による割当の問題点 手間 不完全な割り当て 改善の方法が見つからない 1人が3日間 当日の混乱
スクールバスプロジェクトの後，もう１件，副学長から依頼が来ました。それが，入試監督の自動割り当てはできないかというものでした。

23 複雑な条件の下での割り当て 割当の条件 5日間の試験 1日3科目 40試験室 のべ1万2千人の受験者 200人以上の監督者 多国籍の教員
さて，なぜ，人手だとこんなに問題がおきてしまうのでしょうか。

24 数理計画法の問題として定式化 第1段階： 第2段階： 年齢の高い教員ほど負担が軽くなるように 監督者を試験日、試験時間ごとに割当 →輸送問題
各試験日、試験時間に割当られた監督者を試験室に割当 →貪欲算法 年齢の高い教員ほど負担が軽くなるように

25 入試監督自動割り当て 成果 3日間の作業が まちがいのない割り当て ORの威力を証明 2004年度：6時間 2005年度：3時間
2006年度：30秒 2007年度：30秒 （実際の作業時間は10分、確認に30分） 2008年度からは事務職員単独で割当ができるように まちがいのない割り当て ORの威力を証明 このシステムの作成に２００３年度から取組み，２００４年度入試からこのシステムを用いて割り当てを行っています。

26 講義開始時間の変更 講義時間開始9時の問題点 劣悪な通学の条件 低い教室の使用率 学生の通学範囲が拡がらない ラッシュの真只中 遅刻学生
スクールバスプロジェクトの成功を見て，副学長から次の依頼が来ました。それが，講義開始時間の変更の検討です。

27 講義開始時間を9時20分に メリット 学生の通学条件の改善 教室の使用率の改善 学生の通学範囲の拡大 20分遅らせると乗車率は５０％減少
新しく計画されている教室棟の縮小 学生の通学範囲の拡大 9:20までに大学に到着できる駅の数が70 % 増加 →　「駅すぱあと」を用いて計算 調べてみると，講義時間を遅らせることのメリットがたくさんあることがわかりました。

28 ORを改革の道具に 学長をはじめとする大学執行部が ORの価値を認めた！ 改革に消極的な教員を説得する道具に！ 3つのプロジェクトの成果
講義開始時間を9時20分にする案は前年度却下されていた ORによる根拠付けで2006年度から実施 現在，ORは大学内で高く評価されています。３つのプロジェクトで挙げた成果，それが，米国のOR学会でも評価されたこと。これが大きなインパクトとして大学に影響を与えました。 それと，特に，講義時間の変更の際に，執行部が感じたことですが，改革に消極的な教員を説得するツールとしてORを使っています。

29 INFORMS Franz Edelman Finalist賞 南山大学 プロジェクトN ホームセンターでの事例 おわりに
講演内容 はじめに INFORMS Franz Edelman Finalist賞 南山大学　プロジェクトN ホームセンターでの事例 おわりに

30 プロジェクトN OR、統計の専門家と事務職員からなる 業務改善チーム（教員4名、事務職員5名） 図書館雑誌の見直し
東海地震の注意情報発令時の対策 名古屋キャンパス 瀬戸キャンパス 数理情報学部受験者数の予測 インターンシップ報告会のスケジューリング 入試監督アルバイトのスケジューリング これらのORの成果を大学内のいろんな部署に展開するためにプロジェクトNが発足しました。現在は，５人のORと統計の教授と，４人の事務職員で業務改善に取り組んでいます。与えられた課題のうち，もっとも困難で，重要なのはこの２つです。 ・・・

31 図書館雑誌見直し 問題点 雑誌価格の高騰・予算の削減（５％） 教員に雑誌の停止を要望 何年にもわたって見直しができない
プロジェクトNが最初に取り組んだ課題

32 図書館雑誌見直し 雑誌購入見直しの効率化 雑誌購入予算の公平化 予算の削減 満足度ポイントの導入 1人で高額な雑誌を独占することをなくす
瀬戸キャンパス図書館　 2000万円中300万円削減 名古屋キャンパス図書館 8000万円中1200万円削減 図書館の雑誌購入の見直しは，・・・

33 図書館雑誌見直し 与えられた予算を削減することを制約条件に、教員の満足度ポイントの総和を最大にする削減案を提案 ナップザック問題
EXCELのソルバーで解を求めた 事務職員単独でできるように

34 東海地震注意情報発令時の対策 名古屋キャンパス ⇒ 学生を帰宅させる 事務職員の人員配置問題 学生の誘導 重要書類の保管 施設の管理業務
名古屋キャンパス　⇒　学生を帰宅させる 事務職員の人員配置問題 学生の誘導 重要書類の保管 施設の管理業務 事務職員を順次帰宅させる 東海地震の注意情報が発令されたとき、どのようにすればよいか、南山大学では、具体的な対策はまだできていません。ごく 観念的に全力をあげて学生の安全を確保する、というようなお題目はあるのですが、では、具体的にどの職員がどのような 仕事をして、というようなことはまだ手付かずです。そこで、われわれは、これをプロジェクトNでとりあげ、現在、検討中です。 名古屋キャンパスでは、・・・

35

36 Ａ B 本部棟 Ｄ棟 Ｊ棟 図書館 大学会館 Ｎ棟 C D F E

37 東海地震注意情報発令時の対策 瀬戸キャンパス 帰宅させる学生に対して 大学に残留する学生に対して スクールバスの運行計画 必要な物資の計画
瀬戸キャンパス　 帰宅させる学生に対して スクールバスの運行計画 大学に残留する学生に対して 必要な物資の計画 水，食料，防寒具など 学生の組織 瀬戸キャンパスは、交通の便の悪いところにあり、2時間以上かけて通学している学生もいます。そこで、 ・・・

38 スクールバスの運行計画 スクールバスは中学校・高校と大学で共有 聖霊中学校・高校 運行路線は１１路線 通常の朝の運行を基準 運行方法
通常通り 座席数から計算する方法 非常時を考慮 乗車定員から計算する方法

39 スクールバスの運行計画 大学 運行路線は２路線（本郷，平針） バスの利用者数は、日時・時期によって違う 運行方法
中学校・高校の 使用後 大学 　運行路線は２路線（本郷，平針） 　バスの利用者数は、日時・時期によって違う 　運行方法 　　座席定員で求めた結果を基にした方法 　　定員で求めた結果を基にした方法

40 高等学校・中学校の最適配車計画 大学でより早く使用したい 目的関数 最大所要時間 小さくする 所要時間とは スクールバス１台が使用した時間
最大所要時間とは 全スクールバスの所要時間の中で最大のもの

41 高等学校・中学校の結果 使用開始可能時刻 大学での 各バス停から 大学へ移動

42 第１段階　　　　　　　　　　　　シナリオ６（尾張瀬戸・八草） 最大所要時間

43 実行結果とまとめ シナリオ６（尾張瀬戸・八草）
実行結果とまとめ　　　　　　　シナリオ６（尾張瀬戸・八草）

44

45 プロジェクトNの今後の展開 種々の問題が持ち込まれるように 学生の発表会のスケジューリング 時間割編成
→　キャンパスベンチャーグランプリ中部 （日刊工業新聞主催）で 　　中部経済産業局長賞 →　全国大会へ →　起業の勧誘

46 時間割編成問題 クラス 時間割パネル 教員 時間割パネル

47 時間割編成問題 私立Ｓ高等学校３学年１８クラス分 2008年4月開設予定の南山小学校の時間割編成 整数計画法の問題として定式化
最適化ソフトウェアを用いて約８５秒の計算時間 2008年4月開設予定の南山小学校の時間割編成 教員の人数 カリキュラムの実現性 特別教室の数

48 委託研究：店舗の最適構成 数理計画法を用いて店舗の棚の最適構成 ⇒約３％の売り上げ増 ホームセンターでの事例 [現在] 店舗のシフト作成
　⇒約３％の売り上げ増 [現在] 店舗のシフト作成 最適品揃え問題 競争下での最適価格の決定 棚の最適配置