シラバス
| 授業科目名 | 年度 | 学期 | 開講曜日・時限 | 学部・研究科など | 担当教員 | 教員カナ氏名 | 配当年次 | 単位数 |
|---|---|---|---|---|---|---|---|---|
| 最適化手法 | 2024 | 後期 | 金2 | 理工学部 | 後藤 順哉 | ゴトウ ジュンヤ | 3年次配当 | 2 |
科目ナンバー
SE-AN3-7B15
履修条件・関連科目等
1年次科目「OR第1」、2年次科目「OR第2」「OR演習」の単位修得と内容理解を前提とする。また、微積分のうち微分、線形代数における行列やベクトルの扱いに慣れていることを前提とする。
授業で使用する言語
日本語
授業で使用する言語（その他の言語）
授業の概要
整数計画問題（IP）や混合整数計画（MIP）は、線形計画（LP）のうち変数の全部または一部が整数であることを許した数理最適化問題である。その問題記述力の高さは応用範囲を大幅に広げ、近年の求解ソフトウェアの進歩と相まって、実用性が高まっている。一方、ネットワーク最適化問題は、グラフを用いて定式化される問題群であり、道具立ての簡潔さに反し、多様な応用が可能である。また非線形計画（NLP）は連続的な変数や関数で記述される一般的な問題群であり、機械学習をはじめ、適用範囲は非常に広い。
本授業では、これらの最適化手法を取り上げ、「OR第1」「OR第2」「OR演習」の内容を踏まえ、いくつかの応用例を通じた定式化、代表的な求解アルゴリズム、および、最適性条件の基礎について講義する。演習（宿題）なども取り入れ理解を深める。
科目目的
整数／混合整数最適化、ネットワーク最適化といった離散最適化、および、非線形最適化の基礎に関する理解を深める。
到達目標
* 様々な意思決定問題を整数／混合整数計画問題として定式化する、あるいは、ネットワーク上の最適化問題に帰着することができる
* 整数計画問題に対する代表的な解法である分枝限定法と切除平面法の基礎を理解する
* ネットワーク上の代表的な数理最適化問題に対する基本的なアルゴリズムを理解する
* 非線形最適化のうち、無制約な問題の停留点、および、基礎的な解法である最急降下法の概略について理解する
授業計画と内容
第1回 整数最適化 (1) 線形計画法の復習、IP/MIPによるモデリング（1）
第2回 整数最適化 (2) IP/MIPによるモデリング（2）
第3回 整数最適化 (3) 分枝限定法
第4回 整数最適化 (4) 切除平面法
第5回 ネットワーク最適化 (1) ネットワークによるモデリング
第6回 ネットワーク最適化 (2) 最短路問題（幅優先探索、ダイクストラ法）
第7回 ネットワーク最適化 (3) 最大流問題（増加道法、最大流最小カット定理）
第8回 ネットワーク最適化 (4) 最大流問題（応用例）
第9回 ネットワーク最適化 (5) 最小費用流問題（逐次最短路法）
第10回 ネットワーク最適化 (6) 最小費用流問題（応用例）
第11回 非線形最適化 (1) 非線形関数によるモデリング
第12回 非線形最適化 (2) 無制約問題と停留点，関数の凸性
第13回 非線形最適化 (3) 最急降下法
第14回 非線形最適化 (4) ニュートン法
授業時間外の学修の内容
指定したテキストやレジュメを事前に読み込むこと／授業終了後の課題提出
授業時間外の学修の内容（その他の内容等）
演習問題を積極的に解くことのほか，授業では説明しない理論について専門書で自習したり，自分で問題を作ったりして，本質を理解することも推奨する．また，毎回講義前に前回の内容を見直すと講義の内容の理解が深まるので，これも推奨する．
授業時間外の学修に必要な時間数／週
・毎週１回の授業が半期（前期または後期）または通年で完結するもの。１週間あたり４時間の学修を基本とします。
・毎週２回の授業が半期（前期または後期）で完結するもの。１週間あたり８時間の学修を基本とします。
成績評価の方法・基準
| 種別 | 割合（％） | 評価基準 |
|---|---|---|
| 期末試験（到達度確認） | 70 | 達成基準は到達目標に準じる。単に結果があっているだけでは評価しない。論理をきちんと理解できているか、表現できているかについても重視する。配点については相対評価を取り入れることもある。 |
| 平常点 | 30 | 達成基準は到達目標に準じる。単に結果があっているだけでは評価しない。論理をきちんと理解できているか、表現できているかについても重視する。配点については相対評価を取り入れることもある。 |
成績評価の方法・基準（備考）
試験（70%）、演習・宿題（30%）の得点については相対評価を取り入れる場合がある
課題や試験のフィードバック方法
授業時間内で講評・解説の時間を設ける
課題や試験のフィードバック方法（その他の内容等）
アクティブ・ラーニングの実施内容
実施しない
アクティブ・ラーニングの実施内容（その他の内容等）
授業におけるICTの活用方法
実施しない
授業におけるICTの活用方法（その他の内容等）
実務経験のある教員による授業
いいえ
【実務経験有の場合】実務経験の内容
【実務経験有の場合】実務経験に関連する授業内容
テキスト・参考文献等
テキスト：スライドおよび演習問題をmanabaよりダウンロードしてもらう．
参考文献：
福島雅夫著「新版 数理計画入門」 (朝倉書店 3,360 円)
茨木俊秀著「最適化の数学」 (共立出版 3,360 円)
加藤直樹著「数理計画法」 (コロナ社 2,800 円)
森雅夫・松井知己著「オペレーションズ・リサーチ」 (朝倉書店 4,200円)
繁野麻衣子著「ネットワーク最適化とアルゴリズム」 (朝倉書店 3,570円)
久野誉人・繁野麻衣子・後藤順哉「数理最適化」（オーム社 3,465円）
藤重悟著「グラフ・ネットワーク・組合せ論」 (共立出版 2,940 円)
B. コルテ・J. フィーゲン著「組合せ最適化 第2版」 (丸善出版 12,600 円)
藤澤克樹・後藤順哉・安井雄一郎著「Excel で学ぶOR」 (オーム社 3,360円)
その他特記事項
宿題，演習，試験に誠実に取り組むこと．不正行為（宿題における剽窃，その幇助を含む）についてはマイナス点を与える．