2024年度学院等開講科目情報理工学院情報工学系

最適化基礎

開講元: 情報工学系
担当教員: 小野功
授業形態: 講義 (対面型)
メディア利用科目: -
曜日・時限 (講義室): 火7-8 (W9-326(W935)) / 金7-8 (W9-326(W935))
クラス: -
科目コード: CSC.T342
単位数: 200
開講時期: 2024年度
開講クォーター: 4Q
シラバス更新日: 2025年3月14日
使用言語: 日本語

シラバス

授業の目的（ねらい）、概要

本講義では，システムの解析や設計において必要となる最適化のモデルと方法論について学びます．具体的には，線形計画モデル，線形計画法，非線形計画モデル，非線形計画法，多目的最適化手法，整数計画法，組合せ最適化手法など，最適化のためのモデル化と方法論について講義します．本講義を履修することによって，システムの解析や設計において必要となる最適化に関する知識を習得し，実世界の問題に応用できるようになることを到達目標とします．

到達目標

本講義を履修することによって次の能力を習得する．
1) 最適化問題について説明でき，実世界の問題を最適化問題として定式化できる．
2) 線形／非線形計画問題と線形／非線形計画法について説明でき，線形／非線形計画問題を解くことができる．
3) 多目的最適化と代表的な多目的最適化手法を説明できる．
4) 整数計画と組合せ最適化について説明でき，整数計画／組合せ最適化問題を解くことができる．

キーワード

線形計画，非線形計画，多目的最適化，整数計画，組合せ最適化

学生が身につける力

専門力
教養力
コミュニケーション力
展開力 (探究力又は設定力)
展開力 (実践力又は解決力)

授業の進め方

講義に加えて講義内容の理解を促すための演習もしくはレポートを出題します．

授業計画・課題

	授業計画	課題
第1回	イントロダクション	講義の背景，目的の理解
第2回	線形計画（１）：線形計画問題，シンプレックス法	線形計画問題，シンプレックス法の理解
第3回	線形計画（２）：2段階法	2段階法の理解
第4回	非線形計画（１）：無制約非線形計画問題，最適性の条件，最急降下法	無制約線形計画問題，最適性の条件，最急降下法の理解
第5回	非線形計画（２）：大域的収束性と収束率，共役勾配法，準ニュートン法	大域的収束性，収束率，共役勾配法，ニュートン法，準ニュートン法の理解
第6回	非線形計画（３）：制約付き非線形計画問題，最適性の条件	制約付き線形計画問題，最適性の条件の理解
第7回	非線形計画（４）：制約付き非線形計画問題のための反復法	代表的な制約付き非線形計画問題のための反復法の理解
第8回	多目的最適化	多目的最適化問題と代表的な手法の理解
第9回	整数計画と組合せ最適化（１）：代表的な整数計画問題の例と定式化	代表的な整数計画問題の例と定式化手法についての理解
第10回	整数計画と組合せ最適化（２）：整数計画問題の定式化と困難さの評価	整数計画問題の定式化手法と問題の困難さの評価についての理解
第11回	整数計画と組合せ最適化（３）：効率的に解ける組合せ最適化問題（１）	貪欲法，動的計画法についての理解
第12回	整数計画と組合せ最適化（４）：効率的に解ける組合せ最適化問題（２）	ネットワークフローについての理解
第13回	整数計画と組合せ最適化（５）：分枝限定法，切除平面法	分枝限定法と切除平面法についての理解
第14回	整数計画と組合せ最適化（６）：近似解法・局所探索法・メタヒューリスティクス	近似解法・局所探索法・メタヒューリスティクスについての理解

準備学修(事前学修・復習)等についての指示

学修効果を上げるため，教科書や配布資料等の該当箇所を参照し，「毎授業」授業内容に関する予習と復習（課題含む）をそれぞれ概ね100分を目安に行うこと。

教科書

各講義で必要な資料を配布する．

参考書、講義資料等

なし

成績評価の方法及び基準

各講義で出題する課題で評価する．

履修の条件・注意事項

特になし