科目名 : 線形計画

科目コード 90690
配当学年 1年
開講期 後期
曜時限 水曜・4時限
講義室 総合研究8号館講義室2
単位数 2
履修者制限
講義形態 講義
言語
担当教員 山下信雄

講義概要

システム最適化の基本的な方法のひとつである線形計画法を中心に、数理計画モデルの構築法や数理計画問題の解法について講述する。

評価方法

期末試験の成績による.

最終目標

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

講義計画

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

教科書

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

参考書

予備知識

授業URL

その他