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

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

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

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

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

4 プロジェクト選択問題の定式化 目的関数160x1+170x2+100x3+150x4+70x5→最大
目的関数はプロジェクト採用の場合，対応変数が1となりプロジェクト予想利益を加算する。 1番目の制約条件は予算限度1300万円以内に収める条件で，2番目は変数が0か1に制限する．

5 10.5 プロジェクト選択問題を エクセルで解く1 上記シートのセルには次の値や関数を入力する。 B2:F2：各プロジェクトの予想利益の入力
10.5　プロジェクト選択問題を エクセルで解く1 上記シートのセルには次の値や関数を入力する。 B2:F2：各プロジェクトの予想利益の入力 B3:F3：各プロジェクトにかかる予算の入力 B4:F4：各プロジェクトに対する変数xiのセル（解が保持される）

6 10.5　プロジェクト選択問題を エクセルで解く2 G2：目的関数値とし下記の式を入力する。「=SUMPRODUCT(B2:F2,B$4:F$4)」 G3：1番目の制約条件の左辺を入力する。「=SUMPRODUCT(B3:F3,B$4:F$4)」 H3：1番目の制約条件の右辺の値を入力する。

7 10.5 プロジェクト選択問題を エクセルで解く3 ソルバー起動し「ソルバーの パラメータ」ダイアログで以下の 設定をする（右図参照）．
10.5　プロジェクト選択問題を エクセルで解く3 ソルバー起動し「ソルバーの パラメータ」ダイアログで以下の 設定をする（右図参照）． 「目的セルの設定」：$G$2　　 「目標値」：最大値 「変数セルの変更」：$B$4:$F$4 「解決方法の選択」：シンプレックスLP 「制約条件の対象」：$G$3 <= $H$3を追加

8 10.5 プロジェクト選択問題を エクセルで解く4 変数0-1条件を追加するために
「制約条件の追加」：$B$4:$F$4に対し「<=」の選択リストで「bin」を選び条件に加えると変数がバイナリ（0-1）制約となる。 「int」選択で整数制約。 「解決方法の選択」で シンプレックスLPと選択 すると整数計画では分 枝限定法が用いられる。

9 10.5 プロジェクト選択問題を エクセルで解く5 結果は下図に示し、プロジェクトC，D，Eを採用し，予想利益が420万円となる．

10 10.5 プロジェクト選択問題を エクセルで解く6 ソルバーパラメータ画面をExcel結果Sheetに貼り付ける。
ソルバーパラメータ画面はSnippingツールかPrintScreen等の画面複写により複写し、ExcelSheetに貼り付ける。

11 課題2(レポート収集問題) 社会情報実験を履修する二宮君は優れたレポートを書こうと過去レポートを集める。
先輩により過去レポートを保管していなかったり、レポートを返却しない年があったりで、保存レポートにばらつきがある。 下表は各先輩から借りるコストと保存レポートの種類を示す。 最小コストで全レポートを集めるにはどの先輩達に頼むのが良いか。例題と下記の定式化を参考にExcelソルバーで解をSheet2に求めなさい。 プロジェクト A B C D E 予想利益 160 170 100 150 70 予算 600 550 400 250 200

12 レポート収集問題の定式化 先輩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)

13 レポート収集問題を Excelソルバーで解く1
B2:I2：各先輩のコスト(費用)を入力。 B3:I4：各先輩のレポート採用可否変数xiのセル（解が保持される）

14 レポート収集問題を Excelソルバーで解く2
J2：目的関数とし下記の式を入力する。「=SUMPRODUCT(B2:I2,B3:I3)」 J4：1番目の制約条件の左辺を入力する。「=SUMPRODUCT(B4:I4,B$3:I$3)」 J4をJ5～J9に複写。 K4～K9：制約条件の右辺(1)を入力。

15 レポート収集問題を Excelソルバーで解く3
「ソルバーパラメータ」ダイアロ グで以下の設定をする。 「目的セルの設定」：$J$2　　 「目標値」：最小値 「変数セル変更」：$B$3:$I$3 「解決方法の選択」：シンプレックスLP

16 レポート収集問題を Excelソルバーで解く4
「制約条件対象」 制約条件$J$4 >=1 ～ $J$9>=1を追加するために、「<=」の選択リストで 　 「>=」を選ぶ。 0-1条件を追加するため に$B$3:$I$3に対し「<=」 の選択リストで「bin」を選 ぶと変数がバイナリ （0-1）制約となる。

17 レポート収集問題を Excelソルバーで解く5
「解決」ボタンを押すと、 　 右上図が出るので「OK」ボタンを押す。 結果は右下図で、最適解では先輩1，4，8のレポートを採用。 最適費用は、 =6800円となった。

18 レポート収集問題を Excelソルバーで解く6
ソルバーパラメータ画面をExcel結果Sheetに貼り付ける。 ソルバーパラメータ画面はSnippingツールかPrintScreen等の画面複写により複写し、ExcelSheetに貼り付ける。

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

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

21 コンサート警備問題の定式化 変数定義：候補地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 各候補地の担当ブロック

22 課題1(派生ユニット編成問題) 東北震災復興支援のために乃木坂46のメンバーから派生ユニットを編成したい。
メンバーの人気度と出演料を右表に示す。 予算が500を超えない範囲で、人気度の和が最大になるメンバーを選定し派生ユニットを編成する、組合せ最適化問題を定式化しなさい。 表 人気度と出演料

23 派生ユニット編成問題の定式化 変数定義：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 人気度と出演料

24 ソルバーで解けない問題 Excelソルバーでは、変数の数，制約式の数が制限され実用的問題は解けない。
最近性能の良い最適化ソルバーも開発されている。 問題のタイプ，問題の大きさなどで解けない問題も存在する． TSPなどは定式化は可能であるが制約式が指数的に増大するので、ソルバーで直接解くのは難しい。