経営情報学科 専門科目・2年生以上対象
担当：根本 俊男 （研究室：3号館２階3209研究室）
受講生：約25人（教室：6105）
|
平成16年度 ネットワークモデル分析 REVIEW |
|
経営情報学科 専門科目・2年生以上対象 |
| 今学期の講義は終了しました．お疲れ様でした． | ||
実施した講義内容と配布資料 |
オリエンテーション | |||
| Keyword | 最長しりとり問題 | |||
| 最長片道切符問題 | ||||
|
課題への取り組み方 |
 |
|||
|
|
グラフと最適化 理論は問題解決の大切な柱 |
|
 |
|
| Keyword | 一筆書きの数理 | |||
| オイラー閉路 | ||||
| 理論から現実の問題解決へ，現実の問題解決から理論へ | ||||
| 枝巡回路問題・(中国人)郵便配達人問題 | ||||
| グラフの種類(1) 完全グラフ | ||||
| 実際の郵便配達人問題 | ||||
| 様々な枝巡回路問題 | ||||
| マッチング・最大マッチング･最小重みマッチング | ||||
| グラフの種類(2) 有向･混合･無向グラフ | ||||
| グラフの種類(3) 2部グラフ | ||||
|
解説記事：ネットワーク計画(オイラー閉路) |
||||
|
↑解説記事は研究室で入手できます |
||||
|
配属の数理（１） ペアを決めよう |
|
|
|
| Keyword | 2部グラフ上の最大マッチング問題 | |||
| 最大マッチング問題を解く方法（増加道法） | ||||
| 増加道の発見法（グラフの探索：奥優先探索，幅優先探索） | ||||
| 割当問題 | ||||
| 割当問題を解く解法 ハンガリアン法 | ||||
|
解説記事：割当問題 |
||||
|
↑解説記事は研究室で入手できます |
||||
|
配属の数理（２） 配属を決めよう |
|
|
|
| Keyword | ゼミ配属問題 | |||
| 全体満足度最大方式 | ||||
| 安定配属方式 | ||||
| 安定結婚問題 | ||||
| Gale-Shapleyの解法 | ||||
| 安定マッチング問題 | ||||
| 安定結婚グラフ | ||||
| グラフの表現 | ||||
| 接続行列，隣接行列，リスト表現 | ||||
|
グラフ上の最適化問題(1) 街に安くガス管を張りめぐらそう |
|
|
|
| Keyword | 最小木(最大木）問題 | |||
| クラスター分析手法の実現 | ||||
| クラスカルの解法・プリムの解法 | ||||
| 急に枝が増えた(減った)場合の再計算 | ||||
| ミニマックス道問題 | ||||
|
解説記事：最大木・最小木 |
||||
|
↑解説記事は研究室で入手できます |
||||
|
グラフ上の最適化問題(２) 湘南台，新横浜間の最短経路を見つけよう |
|
|
|
| Keyword | 最短路問題 | |||
| ダイクストラ法 | ||||
| 無向グラフでの最短路問題 | ||||
| 最安でのリース計画を作る | ||||
|
解説記事：最短路問題 |
||||
|
↑解説記事は研究室で入手できます |
||||
|
中間試験 |
|
||
| Keyword | 問題1：最大木・最短路木 | |||
| 問題2：飛行機の乗務員計画（マッチング・割当） | ||||
| 問題3：最適な清掃順路（オイラー閉路・最小重みマッチング） | ||||
| 問題4：インターンと病院の安定なマッチング，テレビクルー割当 | ||||
| 中間試験問題1・4の略解と試験結果 |
|
|||
|
ネットワーク上での流れの最適化（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ファイル閲覧にはアドビリーダー
が必要です．お持ちでない方はこちらをご覧ください。
更新日時: 2004年7月14日