最適化理論について基本的な知識を身につける．特に線形計画問題とそのアルゴリズム，分割統治法，動的計画法，グラフ・ネットワークに関連した様々な最適化アルゴリズムについて述べる．
関西学院大学 理工学部 情報科学科
履修基準年度：3年
担当：巳波・西関
講義目的
最適化理論について基本的な知識を身につける．特に線形計画問題とそのアルゴリズム，分割統治法，動的計画法，グラフ・ネットワークに関連した様々な最適化アルゴリズムについて述べる．
講義内容
１：概要
２：線形計画問題の幾何学的構造
３：線形計画問題に対するシンプレックス法（１）
４：線形計画問題に対するシンプレックス法（２）
５：線形計画問題に対するシンプレックス法（３）
６：双対理論
７：現実の様々な最適化問題
８．欲張り法
９．分割統治法
１０．第ｐ要素の選択
１１．動的計画法
１２・Ｂｅｌｌｍａｎ－Ｆｏｒｄアルゴリズム
１３．最大フローアルゴリズム
１４．マッチングアルゴリズム
１５：演習
成績評価の方法
定期試験
参考・推薦図書
教科書は特に使用しない．
参考書として以下のものを挙げる．
受講上の注意
「離散数理」，「グラフ・ネットワーク理論」を習得していることが望ましい．