数理計画法
Mathematical Programming
准教授・池田 建司
2単位
目的
本講義は2つの部分からなる. 前半は線形計画法であり，その理論と計算法について 解説する. 後半では，ネットワーク上の最適化を論じる. 基礎理論を厳密に展開し， 理解させることを目的としているが，同時に，理解をより容易にするため，理論の 意味を幾何学的に把握できるよう配慮している. また，例題を取り上げ，演習を 実施している.
概要
線形計画法とネットワーク最適化について講義している. 線形計画法では，その定式 化の方法，シンプレックス解法を中心とした計算法，シンプレックス法の有効性を保 証する基本定理，理論的背景であり，かつ線形計画法の幾何学的解釈を示している 双対定理とファーカスの補題などについて述べる. ネットワーク最適化では，代表的な問題として，最短経路問題，最小木問題，最大流問題を扱う.
キーワード
線形計画法，双対性，ネットワーク最適化
先行科目
基礎数学 / 線形代数学I，基礎数学 / 線形代数学II
関連科目
要件
必要な予備的知識は講義の中で一応述べるが，線形代数の知識(ベクトルの一次独立性， 行列の階数)をもっていることが望ましい.
目標
| 1. | 数理モデルにもとづくシステマティックな解析·設計能力を養い， 最適化理論やシステム工学といった学問体系の基礎となす． |
計画
| 1. | 線形計画法の導入 |
| 2. | 図的解法から代数的解法へ |
| 3. | 線形代数の復習 |
| 4. | 線形計画法の基本定理 |
| 5. | シンプレックス法 |
| 6. | 2段階法 |
| 7. | 行列表現と改訂シンプレックス法 |
| 8. | 双対問題，双対定理，ファーカスの補題 |
| 9. | グラフ理論の復習 |
| 10. | 最短経路問題(Dijkstra法) |
| 11. | 最小木問題(Krukal 法) |
| 12. | 最小木問題(Prim 法) |
| 13. | 最大流·最小カット問題 |
| 14. | 最大マッチング·最小カバー定理 |
| 15. | 模擬試験 |
| 16. | 定期試験 |
評価
毎回出題するレポートの結果と定期試験の結果を20:80の割合で評価する．
対象学生
開講コース学生のみ履修可能
教科書
特に指定しない. 配布資料とスライドによって講義を進める.
参考資料
馬場則夫·坂和正敏 著「数理計画法入門」共立出版
今野 浩「線形計画法」日科技連
連絡先
池田(C403, 088-656-7504, ikeda@is.tokushima-u.ac(no-spam).jp)
- オフィスアワー: 水曜日 15:00--18:00