数理計画法
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. | 定期試験 |
評価
毎回出題するレポートの結果と定期試験の結果を10:90の割合で評価する.
対象学生
開講コース学生のみ履修可能
教科書
特に指定しない. 配布資料とスライドによって講義を進める.
参考資料
馬場則夫·坂和正敏 著「数理計画法入門」共立出版
今野 浩「線形計画法」日科技連
連絡先
池田(C403, 088-656-7504, ikeda@is.tokushima-u.ac(no-spam).jp)
- オフィスアワー: 水曜日 15:00--18:00
備考
1. | 授業を受ける際には,2時間の授業時間毎に2時間の予習と2時間の復習をしたうえで授業を受けることが,授業の理解と単位取得のために必要である. |
2. | 授業計画1∼14は, レポートおよび最終試験により達成度評価を行う. |