経営学部経営学科 専門科目・2年生以上対象
担当：根本 俊男 （研究室：東京あだちキャンパス 3422研究室）
受講生：31人
|
2022(令和4)年度 ネットワークモデル分析B REVIEW |
経営学部経営学科 専門科目・2年生以上対象 |
| 2022年度から新科目「ネットワークモデル分析B」が始まります．秋学期の開設です．春学期開設の「ネットワークモデル分析A」の履修もお勧めします．学習効果が上がります．楽しんでください． | ||
実施した講義内容と配布資料 |
オリエンテーション | ||
| 科学的な問題解決とは，オペレーションズ・リサーチ | |||
 |
ネットワーク上の最適化問題(1) 街に安くガス管を張りめぐらそう |
 |
|
| 最小木(最大木）問題 | |||
| クラスター分析手法の実現 | |||
| クラスカルの解法・プリムの解法 | |||
| 急に枝が増えた(減った)場合の再計算 | |||
| ミニマックス道問題 | |||
|
解説記事：最大木・最小木 |
|||
|
↑解説記事は研究室で入手できます |
|||
|
|
ネットワーク上の最適化問題(2) 最短経路は？ |
|
|
| 最短路問題 | |||
| ダイクストラ法 | |||
| 無向グラフでの最短路問題 | |||
| 負の長さの枝がある場合の最短路問題 | |||
| 全点間最短路問題，1始点‐1終点最短路問題 | |||
| (応用)最安でのリース計画を作る | |||
| ダイクストラ法の高速化 | |||
|
解説記事：最短路問題 |
|||
|
↑解説記事は研究室で入手できます |
|||
|
|
ネットワーク上での流れの最適化（1） なるべく多く流してみよう |
|
|
| ネットワーク上での流れ（フロー）とは | |||
| 一般のネットワークと2端子ネットワーク，需要点，供給点 | |||
| フローとフローの流量 | |||
| フローの表現方法：残余ネットワーク | |||
| フローに関する最適化問題 | |||
| 最大フロー問題・最大流問題 | |||
| 解法1：増加道法 | |||
| 増加道法の欠点⇒解法2：ディニッツ(Dinic)の解法 | |||
| 解法3：プリフロー・プッシュ(preflow-push)解法 | |||
| 最大フローと最小カット | |||
| 残余ネットワークの強連結成分分解，ハッセ（Hasse）図 | |||
| 最大マッチング問題と最大フロー問題 | |||
|
|
ネットワーク上での流れの最適化（2） なるべく安く流してみよう |
|
|
| 最小費用フロー問題・最小費用流問題 | |||
| フローに対する費用 | |||
| 最小費用フローの求め方（1）最短路繰り返し法 | |||
| 最短路繰り返し法の欠点 | |||
| 残余費用，改訂最短路繰り返し法 | |||
| 割当問題と最小費用フロー問題 | |||
| 輸送問題 | |||
| 割当問題⊆輸送問題⊆最小費用フロー問題 | |||
| 輸送問題の古典的な解法：飛び石法 | |||
| 初期解の発見法：ハウタッカールール，北西隅法 | |||
| サイクルが見つからない（退化）トラブルへの対処 | |||
|
解説記事：輸送問題（１），輸送問題（2） |
|||
|
↑解説記事は研究室で入手できます |
|||
|
|
小テスト 力試し！ | |
|
 |
講義に関するアンケートの集計結果 | ||
| アンケート結果 |
PDFファイル閲覧にはアドビリーダー
が必要です．
更新日時: 2022年4月14日