先週のベスト感想 ( 講義で分った事 ) 組合せ最適問題を解くときは条件を厳しくしすぎるとコンピュータでも時間がかかりすぎるのでどの程度の条件にするのかが大切である 2017/6/15 2

Size: px

Start display at page:

Download "先週のベスト感想 ( 講義で分った事 ) 組合せ最適問題を解くときは条件を厳しくしすぎるとコンピュータでも時間がかかりすぎるのでどの程度の条件にするのかが大切である 2017/6/15 2"

ときかみこ
5 years ago
Views:

1 OR の手法 ( 組合せ最適化 ) 社会情報特講 Ⅲ 大堀隆文 ( 非常勤講師 ) 1

2 先週のベスト感想 ( 講義で分った事 ) 組合せ最適問題を解くときは条件を厳しくしすぎるとコンピュータでも時間がかかりすぎるのでどの程度の条件にするのかが大切である 2017/6/15 2

3 先週のベスト感想 ( 講義課題で難しかった事 ) 変数が 2 個存在していいのか添え字で 1 個にしておくべきか分かりませんでした説明を詳しくして欲しいです課題の 1 問目くらいは例題と似たような問題にしてほしいです次回のとき課題の解説をして欲しい教室が暗くて手元が見えずらかったのでもう少し耀越していただけると助かります 2017/6/15 3

4 先週のベスト感想 ( その他何でも ) 今の巨人が弱すぎて逆に金曜日からの日ハム戦で息を吹き返しそうで心配です問題を解くとき席を回ってくださってありがたいです商大祭が 6/24-25 にありますぜひ来てください YOSAKOI 企画もありますよさこい今年未にいけたらいいですよさこい晴れるといいですね日ハム近藤早くスタメン復帰してほしいですよさこい TV でしか見たことないので生で見てみたいです 2017/6/15 4

5 先週の課題 1: レポート収集問題下記の表は各先輩から借りるコストと保存しているレポートの種類を示す最小のコストで全てのレポートを集めるにはどの先輩達に頼むのが良いかを求める組合せ最適化問題を定式化しなさい表 1 各先輩のコストと保存レポート 5

6 先週の課題 1 解答レポート収集問題の定式化変数定義 : 先輩 iに依頼を1 非依頼を0とする変数をxi(i=1~8) とする目的関数 :2000x1+4300x2+5700x3+2500x x5+2800x6+5200x7+2300x8 min 制約式 :x1+x2+x3 1, x3+x4+x7 1 x3+x6+x8 1, 表 1 各先輩のコストと保存レポート x1+x5+x6 1, x2+x4+x5+x7 1. x1+x5+x6+x7 1, xi=0 or 1(i=1~8) 6

7 先週の課題 2: コンサート警備問題嵐のコンサートが札幌ドームで開催される人気グループなので大勢のファンが殺到するので事故防止のために厳重な警備が必要であるそこで札幌ドームではどこに警備員を配置するかを検討する会場担当者は会場全体を小さなブロック i=1~7 に分け警備員を候補地点 j=1~7 に配置することにした 7

8 先週の課題 2: コンサート警備問題各候補地の担当ブロックを下記表に示す会場全体を最小人数の警備員で警備するときの警備員配置を求める組合せ最適化問題を定式化しなさい表 2 各候補地の担当ブロック表 2 各候補地の担当ブロック 8

9 先週の課題 2 の解答 : コンサート警備問題の定式化変数定義 : 候補地 iの選定を1 非選定を0とする変数をxi(i=1~8) とする目的関数 :x1+x2+x3+x4+x5+x6+x7+x8 min 制約式 :x1+x3 1, x1+x2+x7 1 x2+x3 1, 表 2 各候補地の担当ブロック x4+x7 1, x4+x5 1. x6 1, x5+x6+x7 1 xi=0 or 1(i=1~8) 9

10 今日の課題 3: 派生ユニット編成問題乃木坂 46 のメンバーから派生ユニットを編成したいメンバーの人気度と出演料を右表に示す予算が 500 を超えない範囲で人気度和が最大になるメンバーを選定し派生ユニットを編成しなさい表 3 人気度と出演料 10

11 先週の課題 3 の解答 : 派生ユニット編成問題の定式化変数定義 :x1( 秋元 )x2( 生田 )x3( 生駒 )x4( 斎藤 ) x5( 桜井 )x6( 白石 )x7( 高山 )x8( 西野 )x9( 松村 )x10 ( 若月 ) は選抜で1 非選抜で0 表 3 人気度と出演料目的関数 :50x1+60x2+40x3 +80x4+45x5+70x6+35x7 +100x8+40x9+45x10 max 制約式 :140x1+120x2+50x3 +40x4+70x5+150x6+90x7 +170x8+90x9+70x xi=0 or 1(i=1~10) 11

12 例題 10.1( 巡回セールスマン問題 ) あるセールスマンがアメリカの 5 都市 ( シアトル, デンバー, ラスベガス, ニューヨーク, マイアミ : 下図 ) を訪ね, ビジネスの商談に行くヘリコプターで回るが移動距離を最小にし経費を抑えるためにシアトルを出発し全都市を一回ずつ周りシアトルに方法 ( 巡回路 ) を示せ 12

13 10.2 巡回セールスマン問題例題 10.1 は分かり易く簡単に解ける [ シアトル, ラスベガス, デンバー, マイアミ, ニューヨーク, シアトル ] [ シアトル, デンバー, ラスベガス, マイアミ, ニューヨーク, シアトル ] の 2 巡路長は前者 10784km 後者 11798km で前者が短い ( 解 ) である人間は図から 2 候補を直感的に導くコンピュータは図から直感的に候補を選ぶ作業が苦手なため, 全巡路を調べ一番良い答えを導く 13

14 例題 10.4 TSP の近似解アルゴリズムアルゴリズムは計算の手順やり方を考えること OR でも解の求め方は重要課題であるアルゴリズムを工夫して良い解き方を考える問題に対し様々なアルゴリズムがあるがその優劣は見方によって異なる解の精度計算速度作り易さを考える貪欲法は一番簡単な方法である 14

15 貪欲法による TSP の解法ステップ 0 出発都市を一つ選ぶステップ 1 出発都市から一番近い都市を選ぶステップ 2 現都市から, 未訪問都市で一番近い都市を選び進むステップ 3 未訪問都市があればステップ 2 に戻る全都市を回れば出発点に戻り巡回路を作るステップ 4 出発都市を変えステップ 1 へ戻るステップ 5 出発都市の中で経路長が最も短い都市を選びそのときの最短経路長を求める 15

16 貪欲法による TSP 解法の実際 ( 出発 A) S0: 出発 A とする S1:A に一番近い B を選ぶ S2: 未訪問で B に一番近い D を選ぶ S2: 同 D に一番近い E を選ぶ S2: 同 E に一番近い C を選ぶ S3:A に戻り全都市巡回完成巡路 A=(A-B-D-E-C-A) 巡路長 A =(AB+BD+DE+EC+CA= =23) 16

17 貪欲法による TSP 解法の実際 ( 出発 B) S0: 出発 B とする S1:B に一番近い A を選ぶ S2: 未訪問で A に一番近い D を選ぶ S2: 同 D に一番近い E を選ぶ S2: 同 E に一番近い C を選ぶ S3:B に戻り全都市巡回完成巡路 B=(B-A-D-E-C-B) 巡路長 B =(BA+AD+DE+EC+CB= =23) 17

18 貪欲法による TSP 解法の実際 ( 出発 C) S0: 出発 C とする S1:C に一番近い E を選ぶ S2: 未訪問で E に一番近い D を選ぶ S2: 同 D に一番近い B を選ぶ S2: 同 B に一番近い A を選ぶ S3:C に戻り全都市巡回完成巡路 C=(C-E-D-B-A-C) 巡路長 C =(CE+ED+DB+BA+AC= =23) 18

19 貪欲法による TSP 解法の実際 ( 出発 D) S0: 出発 D とする S1:D に一番近い E を選ぶ S2: 未訪問で E に一番近い C を選ぶ S2: 同 C に一番近い B を選ぶ S2: 同 B に一番近い A を選ぶ S3:D に戻り全都市巡回完成巡路 D=(D-E-C-B-A-D) 巡路長 D =(DE+EC+CB+BA+AD= =23) 19

20 貪欲法による TSP 解法の実際 ( 出発 E) S0: 出発 E とする S1:E に一番近い D を選ぶ S2: 未訪問で D に一番近い B を選ぶ S2: 同 B に一番近い A を選ぶ S2: 同 A に一番近い C を選ぶ S3:E に戻り全都市巡回完成巡路 E=(E-D-B-A-C-E) 巡路長 E =(ED+DB+BA+AC+CE= =23) 20

21 10.4 色々な組合せ最適化問題組合せ最適化問題は, ビジネスや公共政策の世界で数多く適用され意志決定問題が組合せ最適化問題としてモデル化される組合せ最適化の適用例とモデル化をまとめるモデル化は問題に無関係なものをカットし極力単純化し現実世界の問題を単純明快なモデルとして置き換える定式化はその一つである. 問題をあやふやに考えずモデル化し問題自身を明快にする 21

22 プロ野球ドラフト問題ドラフト会議で内野 (1 塁 2 塁 3 塁遊撃 ) と外野 ( 左翼中堅右翼 ) の選手を獲得したい下表に各選手の可能守備位置と契約金を示す全守備位置をカバーし契約金総和が最小になる選手を選択しなさい表 1 各選手の契約金と可能守備 22

23 プロ野球ドラフト問題の定式化変数定義 : 選手 iの契約を1 非契約を0とする変数をxi(i=1~8) とする目的関数 :1000x1+2300x2+1700x3+1500x x5+2100x6+2800x7+1800x8 min 制約式 :x1+x3+x6+x7 1, x2+x3+x5 1 x2+x3+x6+x8 1, 表 1 各選手の契約金と可能守備 x2+x3+x5 1, x1+x4+x7+x8 1. x1+x4+x6+x7+x8 1, x2+x4+x7 1, xi=0 or 1(i=1~8) 23

24 プロ野球ドラフト問題の近似解 1 近似解法 1( 契約金の降順 ) 契約金の小さい順に選手 (P) を選び全守備をカバーしたら終える S1: 最小契約金は P1-1000( 守備 1, 左, 中 ) S2: 次は P5-1100( 守備 3, 遊 ) S3: 次は P4-1500( 守備左, 中, 右 ) S4: 次は P3-1700( 守備 1,2,3, 遊 ) 全カバー表 1 各選手の契約金と可能守備 24

25 プロ野球ドラフト問題の近似解 2 近似解法 2( 守備位置数の降順 ) 守備位置数の多い順に選手 (P) を選び全守備をカバーしたら終える S1: 最大守備数は P2-2300( 守備 2,3, 遊, 右 ) S2: 次は P3-2300( 守備 1,2,3, 遊 ) S3: 次は P7-2800( 守備 1, 左, 中, 右 ) カバー表 1 各選手の契約金と可能守備 25

26 例題 10.5( プロジェクト選択問題 ) ある会社で下表のプロジェクトが採用候補である予算 1,300 万円以内で, 予想利益 ( 純利益 ) が最大になるようプロジェクトを採用したい本問題を定式化しモデル化せよ ( 単位 : 万円 ) プロジェクト A B C D E 予想利益予算

27 プロジェクト選択問題の変数定義定式化では x 1, x 2,,x 5 の 5 変数を用意する x 1 はプロジェクト A,x 2 は B に対応する x 1 はプロジェクト A を採用で 1, 不採用で 0 とする同様に変数が 1 か 0 でプロジェクトの採否を表す組合せ最適化の内変数が整数に限る問題を整数計画といい特に変数が 0 か 1 に限る問題を 0-1 整数計画という 27

28 プロジェクト選択問題の定式化定式化された式は, 目的関数 160x1+170x2+100x3+150x4+ 70x5 最大制約条件 1 600x1+550x2+400x3+250x4+200x 制約条件 2 x1, x2,, x5 = 0 または 1 目的関数はプロジェクトが採用の場合, 対応する変数が 1 となりプロジェクト予想利益が加算される制約条件の 1 番目は予算限度 1,300 万円以内に収まる条件式である 2 番目は変数が 0 か 1 に制限する条件式である 28

29 プロジェクト選択問題の近似解 1 近似解法 1( 予想利益の降順 ) 利益の大きい順にプロジェクト (P) を選び予算 (1300 万 ) をオーバーしたら終える S1: 最大利益は PB( 利益 170 予算 550) S2: 次は PA( 利益 160 予算 600 計 1150) S3: 次は PD( 利益 150 予算 250 計 1400 オーバー ) プロジェクト A B C D E 予想利益予算

30 プロジェクト選択問題の近似解 2 近似解法 2( 予算の昇順 ) 予算の小さい順にプロジェクト (P) を選び予算 (1300 万 ) をオーバーしたら終える S1: 最小予算は PE( 利益 70 予算 200) S2: 次は PD( 利益 150 予算 250 計 450) S3: 次は PC( 利益 100 予算 400 計 850) S3: 次は PB( 利益 170 予算 550 計 1400 オーバー ) プロジェクト A B C D E 予想利益予算

31 プロジェクト選択問題の近似解 3 近似解法 3( 欲張り法降順 ) 予算当りの利益の大きい順にプロジェクト (P) を選び予算 (1300 万 ) をオーバーしたら終える S1: 最大効率は PD( 利益 150 予算 250) S2: 次は PE( 利益 70 予算 200 計 350) S3: 次は PB( 利益 170 予算 550 計 900) S3: 次は PA( 利益 150 予算 600 計 1500 オーバー ) プロジェクト A B C D E 予想利益予算利益 / 予算

32 さらに勉強するためにさらに組合せ最適化問題を勉強するために幾つかの参考文献を示す組合せ最適化問題の全体像の把握, 他の実用的なソルバーに関しては [2] に記する巡回セールスマン問題を勉強するなら [6] を見ると初心者向けに面白く説明しているメタヒューリスティクスは [1][5] が良い整数計画の定式化に関しては [4],Excel ソルバーの利用に関しては [3] を勧める 32

33 参考文献 [1] 相吉英太郎, 安田恵一郎メタヒューリスティクスと応用電気学会 (2007) [2] 梅谷俊治組合せ最適化入門 : 線形計画から整数計画まで自然言語処理,Vol.21,No.5,2014 [3] 後藤順哉 Excel で始める数理最適化オペレーションズリサーチ : 経営の科学 57(4), [4] 藤江哲也整数計画法による定式化入門オペレーションズリサーチ : 経営の科学 57(4),2012. [5] 柳浦睦憲, 茨木俊秀組合せ最適化メタ戦略を中心として朝倉書店 (2001) [6] 山本芳嗣, 久保幹雄巡回セールスマン問題への招待朝倉書店 (1997) 33

34 今日の課題 1: レポート収集問題実験を履修する二宮君はレポートを書こうと過去の先輩のレポートを集める先輩はレポートを保管しないレポートを返却しない年など人により保存レポートにばらつきがある二宮君は全レポートを先輩から借りるがコストがかかる右表は各先輩から借表 1 各先輩のコストと保存レポートりるコストと保存レポートの種類を示す最小のコストで全てのレポートを集めるにはどの先輩達に頼むのが良いか 34

35 今日の課題 1: レポート収集問題 1. 近似解法 1( 費用の昇順 ) 2. 近似解法 2( 保存レポート数のの降順 ) 表 1 各先輩のコストと保存レポート 35

36 今日の課題 2: 巡回セールスマン問題下表に 6 都市間の移動距離を示す同じ都市を 2 回以上通らないで 6 都市を全部回り出発都市に戻るルートの中で総移動距離が最小の経路を貪欲法を用いて求めなさい表 2 都市から都市への移動距離 36

37 今日の課題 3: 派生ユニット編成問題乃木坂 46 のメンバーから派生ユニットを編成したいメンバーの人気度と出演料を右表に示す予算が 500 を超えない範囲で人気度和が最大になるメンバーを選定し派生ユニットを編成しなさい表 3 人気度と出演料 37

38 今日の課題 3: 派生ユニット編成問題 1. 近似解法 1( 人気の降順 ): 表 3 人気度と出演料 2. 近似解法 2( 出演料の昇順 ): 3. 近似解法 3( 欲張り法 ( 降順 )): 38

39 今日の課題 4: 講義課題の感想学生番号と氏名 (1 枚目 2 枚目とも ) 今日の講義課題の感想講義で分ったこと講義で難しかったこと課題で難しかったことその他 ( 何でも ) 社会情報特講 Ⅲ 39

Microsoft PowerPoint - mp11-06.pptx

Microsoft PowerPoint - mp11-06.pptx 数理計画法第 6 回塩浦昭義情報科学研究科准教授 shioura@dais.is.tohoku.ac.jp http://www.dais.is.tohoku.ac.jp/~shioura/teaching 第 5 章組合せ計画 5.2 分枝限定法組合せ計画問題組合せ計画問題とは : 有限個のものの組合せの中から, 目的関数を最小または最大にする組合せを見つける問題例 1: 整数計画問題全般

先週のベスト感想 ( 講義で分った事 ) 組合せ最適問題を解くときは 条件を厳しくしすぎるとコンピュータでも時間がかかりすぎるので どの程度の条件にするのかが大切である 2017/6/15 2

先週のベスト感想 ( 講義で分った事 ) 組合せ最適問題を解くときは条件を厳しくしすぎるとコンピュータでも時間がかかりすぎるのでどの程度の条件にするのかが大切である 2017/6/15 2