経営情報学科 専門科目・2年生以上対象
担当：根本 俊男 （研究室：3号館２階3209研究室）
受講生：約60人（教室：4202）
|
平成23年度 ネットワークモデル分析 REVIEW |
|
経営情報学科 専門科目・2年生以上対象 |
|
2011年度の講義が始まるよ．
|
|||
実施した講義内容と配布資料(予定を含む) |
オリエンテーション | |||
| Keyword | ||||
| 問題を解決するとは | ||||
|
課題への取り組み方 |
 |
|||
|
グラフと最適化 理論は問題解決の大切な柱 |
|
 |
|
| Keyword | 一筆書きの数理 | |||
| オイラー閉路 | ||||
| 理論から現実の問題解決へ，現実の問題解決から理論へ | ||||
| 枝巡回路問題・(中国人)郵便配達人問題 | ||||
| グラフの種類(1) 完全グラフ | ||||
| 実際の郵便配達人問題 | ||||
| 様々な枝巡回路問題 | ||||
| マッチング・最大マッチング･最小重みマッチング | ||||
| グラフの種類(2) 有向･混合･無向グラフ | ||||
| グラフの種類(3) 2部グラフ | ||||
| [応用例]プロッター動作の最適化 | ||||
| [演習]円卓問題,畳敷き詰め可能性判定問題 | ||||
|
解説記事：ネットワーク計画(オイラー閉路) |
||||
|
↑解説記事は研究室で入手できます |
||||
|
|
配属の数理（１） ペアを決めよう |
|
||
| Keyword | 2部グラフ上の最大マッチング問題 | |||
| 最大マッチング問題を解く方法（増加道法） | ||||
| 2部グラフ上の点被覆 | ||||
| マッチングと点被覆，最大マッチング・最小被覆定理 | ||||
| ケニグ＝エゲルバーリの定理 | ||||
| 割当問題 | ||||
| 割当問題を解く解法 ハンガリアン法 | ||||
| オークション法 | ||||
| 増加道の発見法（グラフの探索：奥優先探索，幅優先探索） | ||||
| FIFO,スタック,FILO,キュー | ||||
| 前順(先行順)，後順(後行順)，中間順，幅優先順 | ||||
|
解説記事：割当問題 |
||||
|
↑解説記事は研究室で入手できます |
||||
|
|
配属の数理（1-2） マッチングやグラフの構造を観てみよう |
|
|
|
| Keyword | グラフの構造を眺める | |||
| パス(道)，連結，間接点，2連結，有向道，強連結 | ||||
| 2連結成分，2連結成分分解 | ||||
| 強連結成分，強連結成分分解 | ||||
| Hasse図，半順序集合 | ||||
| 最大マッチングにいつでも含まれるペア，決して含まれないペア | ||||
| 最大マッチングの構造を眺めよう | ||||
| DM分解（Dulmage-Mendelsohn分解，ダルメジ=メンデルゾーン分解） | ||||
|
|
配属の数理（２） ゼミナールの配属を決めよう |
|
|
|
| Keyword | ゼミ配属問題 | |||
| 全体満足度最大方式 | ||||
| 安定配属方式 | ||||
| 安定結婚問題 | ||||
| [応用例]研修医配属問題 | ||||
| Gale-Shapleyの解法 | ||||
| 安定マッチング問題 | ||||
| 安定結婚グラフ | ||||
| グラフの表現 | ||||
| 接続行列，隣接行列，リスト表現 | ||||
|
|
小テスト（1回目） 力試し！ | |
||
| Keyword | オイラーの定理，一筆書き，郵便配達人問題，枝巡回路問題 | |||
| 最大マッチング，最小被覆，ケニグ＝エゲルバリの定理 | ||||
| 連結性，割当問題，奥優先探索，幅優先探索，安定マッチング | ||||
| 研修医配属問題，隣接行列，接続行列，リスト表現，強連結性， | ||||
| Hasse図 | ||||
|
|
ネットワーク上の最適化問題(1) 街に安くガス管を張りめぐらそう |
|
|
|
| Keyword | 最小木(最大木）問題 | |||
| クラスター分析手法の実現 | ||||
| クラスカルの解法・プリムの解法 | ||||
| 急に枝が増えた(減った)場合の再計算 | ||||
| ミニマックス道問題 | ||||
|
解説記事：最大木・最小木 |
||||
|
↑解説記事は研究室で入手できます |
||||
|
|
ネットワーク上の最適化問題(2) 湘南台-新横浜の最短経路は？ |
|
|
|
| Keyword | 最短路問題 | |||
| ダイクストラ法 | ||||
| 無向グラフでの最短路問題 | ||||
| 負の長さの枝がある場合の最短路問題 | ||||
| 全点間最短路問題，1始点‐1終点最短路問題 | ||||
| 最安でのリース計画を作る | ||||
| ダイクストラ法の高速化 | ||||
|
解説記事：最短路問題 |
||||
|
↑解説記事は研究室で入手できます |
||||
|
|
ネットワーク上での流れの最適化（1） なるべく多く流してみよう |
|
|
|
| Keyword | ネットワーク上での流れ（フロー）とは | |||
| 一般のネットワークと2端子ネットワーク，需要点，供給点 | ||||
| フローとフローの流量 | ||||
| フローの表現方法：残余ネットワーク | ||||
| フローに関する最適化問題 | ||||
| 最大フロー問題・最大流問題 | ||||
| 解法1：増加道法 | ||||
| 増加道法の欠点⇒解法2：ディニッツ(Dinic)の解法 | ||||
| 解法3：プリフロー・プッシュ(preflow-push)解法 | ||||
| 最大フローと最小カット | ||||
| 強連結成分分解，ハッセ（Hasse）図 | ||||
| 最大マッチング問題と最大フロー問題 | ||||
| 演習問題7，演習問題8 | ||||
|
|
ネットワーク上での流れの最適化（2） なるべく安く流してみよう |
|
|
|
| Keyword | 最小費用フロー問題・最小費用流問題 | |||
| フローに対する費用 | ||||
| 最小費用フローの求め方（1）最短路繰り返し法 | ||||
| 最短路繰り返し法の欠点 | ||||
| 残余費用，改訂最短路繰り返し法 | ||||
| 割当問題と最小費用フロー問題 | ||||
| 輸送問題 | ||||
| 割当問題⊆輸送問題⊆最小費用フロー問題 | ||||
| 輸送問題の古典的な解法：飛び石法 | ||||
| 初期解の発見法：ハウタッカールール，北西隅法 | ||||
| サイクルが見つからない（退化）トラブルへの対処 | ||||
| 演習問題7，演習問題8 | ||||
|
解説記事：輸送問題（１），輸送問題（2） |
||||
|
↑解説記事は研究室で入手できます |
||||
|
|
小テスト（2回目） 力試し！ | |
||
| Keyword | 最短路問題，点に重みがある場合のネットワーク問題 | |||
| 最小木，プリム法，最大フロー=最小カット定理 | ||||
| 増加道法，最小費用フロー問題 | ||||
| 割当問題，輸送問題，最小費用フロー問題の関係 | ||||
 |
講義に関するアンケートの集計結果 | |||
IE6以上のブラウザの使用を推奨します．
PDFファイル閲覧にはアドビリーダー
が必要です．お持ちでない方はこちらをご覧ください。
更新日時: 2012年4月13日