2021(令和3)年度 ネットワークモデル分析 REVIEW

経営学部経営学科 専門科目・2年生以上対象
担当：根本 俊男 （研究室：東京あだちキャンパス 3422研究室）
受講生：16人（教室：2307）
　 　 　
　 2021年度の講義は終了しました．ありがとうございました． 　
　 　

実施した講義内容と配布資料

オリエンテーション 　 　
科学的な問題解決とは，オペレーションズ・リサーチ
　   　 　
グラフと最適化　理論は問題解決の大切な柱
一筆書きの数理
オイラー閉路
理論から現実の問題解決へ，現実の問題解決から理論へ
枝巡回路問題・(中国人)郵便配達人問題
グラフの種類(1)　完全グラフ
実際の郵便配達人問題
様々な枝巡回路問題
マッチング・最大マッチング･最小重みマッチング
グラフの種類(2)　有向･混合･無向グラフ
グラフの種類(3)　2部グラフ
[応用例]プロッター動作の最適化
[演習]円卓問題,畳敷き詰め可能性判定問題

解説記事：ネットワーク計画(オイラー閉路)

↑解説記事は研究室で入手できます
配属の数理（１）　ペアを決めよう
2部グラフ上の最大マッチング問題
最大マッチング問題を解く方法（増加道法）
2部グラフ上の点被覆
マッチングと点被覆の関係，最小点被覆の見つけ方
最大マッチング・最小被覆定理, ケニグ＝エゲルバーリ(König-Egerváry)の定理
割当問題
割当問題を解く解法　ハンガリアン法，オークション法
増加道の発見法，グラフの探索：奥優先探索，幅優先探索
FIFO,スタック,FILO,キュー
前順(先行順)，後順(後行順)，中間順，幅優先順

解説記事：割当問題

↑解説記事は研究室で入手できます
割当問題演習

グラフの構造を眺める　マッチングやグラフの構造を観てみよう
グラフの構造を眺める
パス(道)，連結，間接点，2連結，有向道，強連結
2連結成分，2連結成分分解
強連結成分，強連結成分分解
Hasse図，半順序集合
最大マッチングにいつでも含まれるペア，決して含まれないペア
最大マッチングの構造を眺めよう
DM分解（Dulmage-Mendelsohn分解，ダルメジ=メンデルゾーン分解）

配属の数理（２）　ゼミナールの配属を決めよう
ゼミ配属問題
全体満足度最大方式
安定配属方式
安定結婚問題
[応用例]研修医配属問題
Gale-Shapleyの解法
安定マッチング問題
安定結婚グラフ
グラフの表現
接続行列，隣接行列，リスト表現
小テスト（1回目） 力試し！ 　
 
 
 
ネットワーク上の最適化問題(1)　街に安くガス管を張りめぐらそう
最小木(最大木）問題
クラスター分析手法の実現
クラスカルの解法・プリムの解法
急に枝が増えた(減った)場合の再計算
ミニマックス道問題

解説記事：最大木・最小木

↑解説記事は研究室で入手できます

ネットワーク上の最適化問題(2)　最短経路は？
最短路問題
ダイクストラ法
無向グラフでの最短路問題
負の長さの枝がある場合の最短路問題
全点間最短路問題，1始点‐1終点最短路問題
(応用)最安でのリース計画を作る
ダイクストラ法の高速化

解説記事：最短路問題

↑解説記事は研究室で入手できます

ネットワーク上での流れの最適化（1）　なるべく多く流してみよう
ネットワーク上での流れ（フロー）とは
一般のネットワークと2端子ネットワーク，需要点，供給点
フローとフローの流量
フローの表現方法：残余ネットワーク
フローに関する最適化問題
最大フロー問題・最大流問題
解法1：増加道法
増加道法の欠点⇒解法2：ディニッツ(Dinic)の解法
解法3：プリフロー・プッシュ(preflow-push)解法
最大フローと最小カット
残余ネットワークの強連結成分分解，ハッセ（Hasse）図
最大マッチング問題と最大フロー問題
ネットワーク上での流れの最適化（2）　なるべく安く流してみよう
最小費用フロー問題・最小費用流問題
フローに対する費用
最小費用フローの求め方（1）最短路繰り返し法
最短路繰り返し法の欠点
残余費用，改訂最短路繰り返し法
割当問題と最小費用フロー問題
輸送問題
割当問題⊆輸送問題⊆最小費用フロー問題
輸送問題の古典的な解法：飛び石法
初期解の発見法：ハウタッカールール，北西隅法
サイクルが見つからない（退化）トラブルへの対処

解説記事：輸送問題（１），輸送問題（2）

↑解説記事は研究室で入手できます
小テスト（2回目） 力試し！ 　
 
 
講義に関するアンケートの集計結果　
2021年度は自由記述形式で実施⇒全コメント一覧


PDFファイル閲覧にはアドビリーダー が必要です．

更新日時: 2022年2月4日