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

Presentation on theme: "ORの手法(組合せ最適化) 社会情報特講Ⅲ 大堀隆文(非常勤講師)."— Presentation transcript:

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

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

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

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

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

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

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

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

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, x4+x7≧1, x4+x5≧1. x6≧1, x5+x6+x7≧1 xi=0 or 1(i=1～8) 表2 各候補地の担当ブロック

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

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

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

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

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

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

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)

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)

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)

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)

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)

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

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

23 プロ野球ドラフト問題の定式化 変数定義：選手iの契約を1、非契約を0とする変数をxi(i=1～8)とする。
目的関数：1000x1+2300x2+1700x3+1500x4 +1100x5+2100x6+2800x7+1800x8 ⇒ min 制約式：x1+x3+x6+x7≧1, x2+x3+x5≧1 x2+x3+x6+x8≧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) 表1 各選手の契約金と可能守備

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

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

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

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

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

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

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 予想利益 160 170 100 150 70 予算 600 550 400 250 200

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 予想利益 160 170 100 150 70 予算 600 550 400 250 200 利益/予算 0.27 0.31 0.25 0.60 0.35

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

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

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

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

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

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

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

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