数理最適化特論｜シラバス情報

授業コード

220478

オムニバス

科目名

数理最適化特論

科目名（英語）

Advanced Mathematical Optimization

配当学年

1年

単位数

2単位

年度学期

2025年度秋学期

曜日時限

金曜2限

対象学科

博前_電子

コース

科目区分

大学院科目

必選の別

選択科目

担当者

松浦　隆文

教室

実務家教員担当授業

授業の目的と進め方

「実社会の問題を数理最適化で解決する」というテーマのもと，本講義は，実社会の解決すべき問題を最適化問題として数学的に定式化する方法を習得することを目標とする．また，これらの問題を汎用ソルバーにより解決する方法を実践的に学ぶとともに，代表的なメタヒューリスティクスを理解し，これらを適用して問題を解決する技術を習得することが目標である．

達成目標１

数理モデルについて説明ができるようになり、線形計画問題が解けるようになる　【25%】。

達成目標２

与えられた現実問題に対して適切な数理モデルが記述できる【25%】。

達成目標３

ソルバーを用いて数理計画問題を解くことができる【25％】。

達成目標４

発見的解法について基本的な考え方を理解し、最適化問題に適用ができる【25%】。

達成目標５

達成目標６

達成目標７

アクティブラーニング

ディスカッション

ディベート

グループワーク

プレゼンテーション

実習

○

フィールドワーク

その他課題解決型学習

授業計画

授業時間外課題（予習および復習を含む）

第１回

ガイダンスと数理最適化とは

授業で取り扱う内容の概説、輪講の進め方について説明します。数理化問題が実社会のどんな場面で利用されているのか調べておくこと（2時間）。

第２回

線形計画問題（１）標準形、標準形への変換

線形計画法標準形、標準形への変換方法について学びます。
線形計画問題の特徴、標準形について予習しておくこと（2時間）。

第３回

線形計画問題（２）最適解の条件，単体法

線形計画問題の最適解の条件について学びます。線形計画問題の標準形への変換について復習し、単体法について予習しておくこと（２時間）。

第４回

線形計画問題（３）退化と巡回，２段解法

退化と巡回、2段階法について学びます。退化、巡回とは何か、どのような場合におこるのか、その解決方法について予習しておくこと（2時間）。

第５回

線形計画問題（４）緩和問題と双対定理

双対性について学びます。双対問題と双対定理について予習しておくこと（２時間）。

第６回

実装（１）汎用ソルバーの利用

汎用ソルバーglpkを用いて線形計画問題、組合せ最適化問題の最適解を求めます。各自の計算機にglpkをインストールしておくこと（2時間）。　

第７回

組合せ最適化問題（１）定式化

代表的な組合せ最適化問題について学びます。ナップサック問題、巡回セールスマン問題の定式化を調べてその式の意味について予習しておくこと（２時間）。

第８回

組合せ最適化問題（２）列挙法と分枝限定法

分枝限定法について学びます。組合せ最適化問題の組合せ爆発について予習しておくこと。ナップサック問題に対する分枝限定法について予習しておくこと（2時間）。

第９回

組合せ最適化問題（３）貪欲法と局所探索法

貪欲法，局所探索法について学びます。巡回セールスマン問題に対してどのようは方法があるかを予習しておくこと（2時間）。

第10回

実装（２）貪欲法

巡回セールスマンに対する貪欲法を実装します．巡回セールスマン問題に対する貪欲法を復習しておくこと（2時間）。　

第11回

実装（３）局所探索法

巡回セールスマンに対する局所探索法を実装します．巡回セールスマン問題に対する2-opt法，Or-opt法を復習しておくこと．また，貪欲法を完成させておくこと（2時間）。　

第12回

組合せ最適化問題（４）メタヒューリスティクス

メタヒューリスティクスについて学びます。組合せ最適化問題に対してどのようは方法があるかを予習しておくこと（2時間）。　

第13回

実装（４）メタヒューリスティクス

巡回セールスマンに対する局所探索法を実装します．巡回セールスマン問題に対する焼きなまし法，タブー探索法を復習しておくこと．また，局所探索法の実装を完成させておくこと（2時間）。　

第14回

実装（５）メタヒューリスティクスの実装と性能を検証

メータヒューリスティクスの実装を完了しておくこと（2時間）。

課題等に対するフィードバック

必要に応じて、解答例となるサンプルコードを配布する。

評価方法と基準

全ての演習課題を提出している場合をC評価以上とする。

テキスト

開講時に指示する。その他、適宜資料プリントを配布する。　

参考図書

・福島雅夫、新版　数理計画入門、朝倉書店【ISBN: 978-4-254-28004-3】
・金谷健一、これなら分かる最適化数学、共立出版【ISBN： 978-4-320-01786-3】

科目の位置づけ（学習・教育目標との対応）

本授業では、現実社会に現れる問題を数理的な手法で解決するための基礎・理論を学びます。これにより、実社会の課題を解決する際に、数理モデルを構築し、適切な手法を用いて解決をする技術が得られる。　

履修登録前の準備

線形代数、微分・積分など、基礎的な数学の知識が必要となるため復習しておくこと。　