 |
オリエンテーション |
|
|
|
|
|
|
|
科学的な問題解決とは，オペレーションズ・リサーチ |
|
|
| |
|
|
|
 |
ネットワーク上の最適化問題(1) 街に安くガス管を張りめぐらそう |
|
 |
|
最小木(最大木）問題 |
|
|
|
クラスター分析手法の実現 |
|
|
|
クラスカルの解法・プリムの解法 |
|
|
|
急に枝が増えた(減った)場合の再計算 |
|
|
|
ミニマックス道問題 |
|
|
|
解説記事：最大木・最小木 |
|
|
|
↑解説記事は研究室で入手できます |
|
|
|
|
|
|
|
|
ネットワーク上の最適化問題(2) 最短経路は？ |
|
|
|
最短路問題 |
|
|
|
ダイクストラ法 |
|
|
|
無向グラフでの最短路問題 |
|
|
|
負の長さの枝がある場合の最短路問題 |
|
|
|
全点間最短路問題，1始点‐1終点最短路問題 |
|
|
|
(応用)最安でのリース計画を作る |
|
|
|
ダイクストラ法の高速化 |
|
|
|
解説記事：最短路問題 |
|
|
|
↑解説記事は研究室で入手できます |
|
|
|
|
|
|
|
|
ネットワーク上での流れの最適化（1） なるべく多く流してみよう |
|
|
|
ネットワーク上での流れ（フロー）とは |
|
|
|
一般のネットワークと2端子ネットワーク，需要点，供給点 |
|
|
|
フローとフローの流量 |
|
|
|
フローの表現方法：残余ネットワーク |
|
|
|
フローに関する最適化問題 |
|
|
|
最大フロー問題・最大流問題 |
|
|
|
解法1：増加道法 |
|
|
|
増加道法の欠点⇒解法2：ディニッツ(Dinic)の解法 |
|
|
|
解法3：プリフロー・プッシュ(preflow-push)解法 |
|
|
|
最大フローと最小カット |
|
|
|
残余ネットワークの強連結成分分解，ハッセ（Hasse）図 |
|
|
|
最大マッチング問題と最大フロー問題 |
|
|
|
|
|
|
|
|
ネットワーク上での流れの最適化（2） なるべく安く流してみよう |
|
|
|
最小費用フロー問題・最小費用流問題 |
|
|
|
フローに対する費用 |
|
|
|
最小費用フローの求め方（1）最短路繰り返し法 |
|
|
|
最短路繰り返し法の欠点 |
|
|
|
残余費用，改訂最短路繰り返し法 |
|
|
|
割当問題と最小費用フロー問題 |
|
|
|
輸送問題 |
|
|
|
割当問題⊆輸送問題⊆最小費用フロー問題 |
|
|
|
輸送問題の古典的な解法：飛び石法 |
|
|
|
初期解の発見法：ハウタッカールール，北西隅法 |
|
|
|
サイクルが見つからない（退化）トラブルへの対処 |
|
|
|
解説記事：輸送問題（１），輸送問題（2） |
|
|
|
↑解説記事は研究室で入手できます |
|
|
|
|
|
|
|
|
小テスト 力試し！ |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
 |
講義に関するアンケートの集計結果 |
|
|
|
アンケート（自由記述）集計結果 |
|
|
実施した講義内容と配布資料