講義科目

数理計画法 (平成21年度冬学期 2009年10月〜2010年2月)

教員名

室田一雄　教授
土谷　隆　統計数理研究所 教授

対象

3年生

時間帯

冬学期・水・２ 限（10時15分〜11時45分）
2009年10月7日開講

キーワード

最適化問題， 単体法， 双対定理， 凸集合， 凸最適化， KKT条件， 降下法， 動的計画法， 整数計画法， 整数計画問題， 分枝限定法

前提知識

線形代数と微積分の基礎知識

講義の意義、目的、応用分野等

工学的な問題の数理的な構造をとり出して最適化問題として定式化し， さらにそれを解くための考え方と手法を解説する．

講義の内容

線形計画，非線形計画，組合せ最適化を中心に講義を行う．

1. 最適化概観(モデル，凸関数，双対性) 　　[室田]
2. 最適化モデル　　[土谷]
3. 線形計画法　　[土谷]
   1. 線形計画モデル
   2. 単体法
   3. 双対定理
   4. 内点法
4. 凸解析と凸計画　　[土谷]
   1. 凸集合，凸関数
   2. 双対性
   3. 凸多面体
   4. 2次計画法
   5. 半正定値計画法
5. 非線形計画法　　[土谷]
   1. KKT条件
   2. ニュートン法
6. 組合せ最適化　　[土谷]
   1. 整数計画法
   2. 分枝限定法
7. ネットワーク計画法　　[室田]
   1. ネットワーク型最適化問題
   2. 最短経路問題
   3. 最小費用流問題（輸送計画，日程計画）

参考書

田村明久，村松正和：最適化法，工系数学講座，共立出版，2002.

成績評価方法

通常の形式の試験を行う． 下の過去問のパスワードは講義で知らせます．
　過去問(平成20年度;土谷＋室田)
　過去問(平成19年度;土谷＋室田)
　過去問(平成18年度;土谷＋室田)
　過去問(平成17年度;土谷＋室田)
　過去問(平成16年度;松井先生)
　過去問(平成15年度;土谷＋室田)
　過去問(平成14年度;松井先生)
　過去問(平成13年度;松井先生)
　過去問(平成12年度;松井先生)
　過去問(平成11年度;松井先生)

講義の進め方

論理が追えるように，板書を中心とし，時に，プロジェクタを用いる． また，質問の時間を途中に設けるなど，インタラクティブにする．