離散最適化基礎論 (1) 演習問題 2015 年 10 月 9 日岡本吉央提出締切： 2015 年 10 月 23 日講義終了時復習問題 1.1 次のような入力を持つナップサック問題を考追加問題 1.3 次のような入力を持つナップサック問題を考える．える． • ナップサックの積載重要制限は 4 (kg) ． • ナップサックの積載重要制限は 4 (kg) ． • 商品は 4 つあり，商品の集合を {1, 2, 3, 4} とする． • 商品は 4 つあり，商品の集合を {1, 2, 3, 4} とする． • 各商品の収入と重さは以下の通り． • 各商品の収入と重さは以下の通り．商品 1 2 3 4 商品 1 2 3 4 収入 [万円] 3 4 1 2 収入 [万円] 4 5 2 3 重さ [kg] 2 3 1 3 重さ [kg] 2 3 1 1 以下の問いに答えよ．以下の問いに答えよ． 1. この問題の許容集合 F が何であるか，その要素をすべて並べることで答えよ． 1. この問題の許容集合 F が何であるか，その要素をすべて並べることで答えよ． 2. 許容集合 F の各要素の目的関数値を答えよ． 2. 許容集合 F の各要素の目的関数値を答えよ． 3. この問題の最適解と最適値を答えよ． 3. この問題の最適解と最適値を答えよ． 4. この問題に対して貪欲アルゴリズムを適用した際に得られる出力と，その目的関数値を答えよ．復習問題 1.2 次の無向グラフを入力とする最大重みマッチング問題を考える． b 3 a2 追加問題 1.4 集合 E = {a} 上の独立集合族をすべて挙げよ． 3c 追加問題 1.5 集合 E = {a, b} 上の独立集合族をすべて挙 1 d げよ．辺集合が {a, b, c, d} であり，それぞれに重みが与えられて追加問題 1.6 非空な有限集合 E と有限集合族 F ⊆ 2E をいる．重みはその辺上に書かれた数で表されている．考える．このとき，F が独立集合族であるとき，そのとき以下の問いに答えよ．に限り，F が次の 2 条件をともに満たすことを証明せよ． 1. この問題の許容集合 F が何であるか，その要素をす 1. F 6= ∅．べて並べることで答えよ． 2. X ∈ F かつ Y ⊆ X ならば，Y ∈ F ． 2. 許容集合 F の各要素の目的関数値を答えよ．追加問題 1.7 非空な有限集合 E と独立集合族 F ⊆ 2E を 3. この問題の最適解と最適値を答えよ．考える．任意の要素 e ∈ E に対して集合族 F 0 を F 0 = {X | X ∪ {e} ∈ F} として定義する．このとき，{e} ∈ F ならば，F 0 も独立集合族であることを証明せよ． 1