授業科目名 : 線形計画

科目コード 90690
配当学年 1年
開講年度・開講期 平成30年度・後期
曜時限 木曜・4時限
講義室 総合研究8号館講義室2
単位数 2
履修者制限
授業形態 講義
使用言語 日本語
担当教員    所属・職名・氏名 情報学研究科・教授・山下信雄

授業の概要・目的

数理最適化は,データ解析や機械学習,金融工学など様々な分野で使われる基礎的技術である. 数理最適化の基本的な方法のひとつである線形計画法を中心に、数理最適化モデルの構築法や線形計画問題の解法について講述する。

成績評価の方法・観点及び達成度

期末試験の成績による.

到達目標

基本的な最適化モデルの考え方と定式化手法を習得するとともに,線形計画問題の理論的性質と解法を理解する.

授業計画と内容

項目 回数 内容説明
数理最適化とは 1 数理最適化の概要を紹介する.また,本授業で必要となる数学的事項,特に線形代数について復習する.
数理最適化モデル 4 代表的な数理最適化モデルである線形計画モデル、ネットワーク最適化モデル、非線形最適化モデル、組合せ最適化モデルを,機械学習などにあらわれる簡単な例を用いて紹介する。
線形計画問題と基底解 2 線形計画問題を標準形に定式化し、基底解、実行可能基底解、最適基底解などの基本的な概念を説明する。
シンプレックス法(単体法) 3 線形計画問題の古典的な解法であるシンプレックス法(単体法)の基本的な考え方とその具体的な計算法について述べる。さらに、実行可能解を見出すための二段階法を説明し、時間が許せば、上限付き変数を扱う方法、ネットワーク・シンプレックス法にも言及する。
双対性と感度分析 3 線形計画問題の重要な数学的性質である双対性について述べ、さらに問題を総合的に分析し意思決定を行う際に非常に有力な手段である感度分析の考え方を説明する。
内点法 1 線形計画問題に対する多項式時間アルゴリズムである内点法の考え方と計算法について述べる。
補足とまとめ 1 講義内容のまとめ、補足および学習到達度の確認を行う。

教科書

福島雅夫 : 新版・数理計画入門、朝倉書店

参考書等

履修要件

授業外学習(予習・復習)等

授業URL

その他(オフィスアワー等)