科目分野	理工学部
選必区分	選択
担当教員 ［ローマ字表記］	永田　裕一　[NAGATA YUICHI]
授業形態	講義

授業の目的

{ol}
{.}種々の問題を最適化問題に定式化する能力を習得する{/.}
{.}線形計画問題に定式化された問題をシンプレックス法で解く手法とその原理を理解する{/.}
{.}非線形関数の極値を勾配法で発見する方法（ニュートン法，共役勾配法，準ニュートン法）の手法と原理を理解する{/.}
{.}動的計画法と分岐限定法の基本原理を理解する{/.}
{/ol}

授業概要

授業では非線形最適化問題を取り扱うが，その理解に必要な数学的概念として関数の2次形式とその標準形および極値問題について解説する．次に，非線形最適化問題の極値を勾配法に基づいて求める手法を解説する．講義では最も単純な勾配法である最急降下法に始まり，より高度な手法であるニュートン法，共役勾配法および準ニュートン法について説明する．次に線形計画問題を効率的に解くための代表的な手法であるシンプレックス法や双対問題について学ぶ．最後に組合せ最適化問題の代表的最適化手法である動的計画法と分岐限定法のについて学ぶ．

到達目標

{.}種々の問題を最適化問題に定式化する能力を習得する{/.}
{.}線形計画問題に定式化された問題をシンプレックス法で解く手法とその原理を理解する{/.}
{.}非線形関数の極値を勾配法で発見する方法（ニュートン法，共役勾配法，準ニュートン法）の手法と原理を理解する{/.}
{.}動的計画法と分岐限定法の基本原理を理解する{/.}

授業計画

第１回：最適化問題の定式化
第２回：数学的準備，2次形式
第３回：関数の極値：2次関数の極値
第４回：関数の極値：関数の2次近似，ラグランジュの未定乗数法
第５回：関数の極値：ラグランジュの未定乗数法（制約がある場合）
第６回：関数の最適化：勾配法，ニュートン法
第７回：関数の最適化：共役勾配法
第８回：関数の最適化：準ニュートン法
第９回：線形計画法：不等式標準形，等式標準形
第１０回：線形計画法：シンプレックス法
第１１回：線形計画法：双対問題
第１２回：組合せ最適化：動的計画法
第１３回：組合せ最適化：分岐限定法
第１４回：組合せ最適化：種々の問題
第１５回：演習
定期試験

キーワード

最適化問題, 非線形計画法，勾配法，ニュートン法，線形計画法，分岐限定法，動的計画法