情报数理学：数理计画法 第1回 数理计画モデル情报数理学：数理计画法 第1回 数理计画モデル.pdf

情報数理学：数理計画法 第4回：組合せ最適化問題 梅谷 俊治 大学院情報科学研究科 情報数理学専攻 2008年6月5 日 組合せ最適化問題 • 探索空間が離散的であるもしくは離散的な集合に減らせる最適化問題． 解が集合，順序，割当て，グラフ，論理，整数など離散的な構造を持つ場 合が多い． • 組合せ最適化問題の例 – 最短路問題（カーナビ・乗換案内のルート検索など） – ネットワーク設計問題（ライフライン，交通網，通信網，石油パイプラインなど の設計） – 配送計画問題（宅配便，店舗への商品配送，ゴミ収集など） – 施設配置問題（工場，店舗，公共施設の配置など） – スケジューリング問題（工場の操業計画，乗務員・看護師の勤務表作成，ス ポーツなどの日程・対戦表の作成，時間割の作成など） 現実世界の多くの問題が組合せ最適化問題として定式化できる！ 割当て問題 • m人の学生をn個のクラスに割当てる．ただし，各クラスの受講者には上 下限が与えられている．学生の満足度を最大にするクラス編成は？ u : クラスiの受講者数の上限（定数） i l ji : クラスの受講者数の下限 （定数） p j i ij : 学生のクラスに対する満足度（定数） x i j ij : 学生をクラスに割当てる=⇒ xij 1，割当てない=⇒ xij 0 （変数） m n max p x ∑∑ ij ij i 1 j 1 n l x u≤ i =≤s.t. m ( 1,2, , ), K i ∑ ij i j 1 m x 1 j ( 1,2, n , ), K