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