2010年度 工学部 知能情報工学科 昼間コース — [選択] 2年(後期)

数理計画法

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