数理計画法

Google classroomを用いる

(a) 主題:
日常の身近な行動から、社会・経済活動、工学、そして生命・物理現象に至る様々な場面で「〇〇をうまく決めて◻︎◻︎を最適化したい」という欲求が現れる。このような問題を意識して、数理モデルとして定式化したものを「数理計画問題」もしくは「数理最適化問題」といい、それを解くことを単に「最適化」という。

この講義では、数理計画問題の基本である線形計画問題と、その離散版である整数計画問題を扱います。本講義の目指すところは、問題を解くという視点のみならず、問題を数理モデルで表現できる、そのための理解を深めることです。

この講義では、座学だけではなく、問題を解くためのソルバーと言われるソフトウエアを用いた実装による演習も行います。

2年後期の科目「オペレーションズ・リサーチ基礎」において線形計画問題を学んだ方も多いかと思いますが、本講義では線形計画問題の数理的・理論的側面をより深く学びます。

「オペレーションズ・リサーチ基礎」を履修していなくても理解できるように授業は設計されています。

(b) 達成目標:

いろいろな最適化問題の種類の違いを理解すること。また各種最適化問題への定式化に関する基本を身につけること。
線形計画問題について、その数学的構造および主要なアルゴリズムの一つである単体法について理解すること。
整数計画問題について、線形計画問題との関係を理解し、基本的な解法を理解すること。
具体的な問題に対して、数理モデルを構築できること、ソルバーを使えるようになること。

数値計算、離散数学、線形代数学第一、線形代数学第二

オペレーションズ・リサーチ基礎、グラフとネットワーク、アルゴリズム論第一

教科書等は指定しないが、参考文献として次のものを挙げる。

1. 「最適化法」 田村明久・村松正和 著、共立出版
2. 「IT Text 数理最適化」 久野誉人・繁野麻衣子・後藤順哉 著、オーム社
3. 「しっかり学ぶ数理最適化 モデルからアルゴリズムまで」 梅谷俊治 著、講談社
4. 「Pythonではじめる数理最適化: ケーススタディでモデリングのスキルを身につけよう」 岩永二郎・石原響太・西村直樹・田中一樹 著、オーム社

(a) 授業内容

1:数理計画問題とは
2:線形計画問題の理論的側面:双対定理
3:線形計画問題に対するアルゴリズム:単体法
4:整数計画問題とは
5:整数計画問題の解法
6:整数計画問題の使用例

(b) 授業の進め方:

最適化、数理計画に関する知識を得るだけではなく、その背後にある論理を自在に操れるようになってほしいと願って授業を設計しています。最適化は論理の宝庫であり、最適化を適用・応用しようと思ったらどうしてもそういう力が必要となるからです。

そのためには、まずは自分の手を動かすことです。ほぼ毎回課題を出します。課題の達成には毎週2〜3時間程度費やすことになると思われます。わからない場合には Classroom で遠慮なく質問してください。少しのアドバイスで見通しが良くなるものです。

基本的にスライドを用いた対面授業です。必要に応じて追加資料等をClassroomにアップします。

内容は以下のとおりです。

1. 数理最適化問題とは
2. 標準形の線形計画問題とブロック行列表示
3. 双対問題と諸定理
4. 数理最適化ソルバーの整備と演習
5. 単体法および演習
6. 2段階単体法と退化および演習
7. 改訂単体法、双対単体法および演習
8. 前半の振り返り
9. ネットワーク計画問題
10. 最短経路問題、最大流問題
11. 多面体
12. 整数計画問題
13. 分枝限定法および演習
14. 分枝カット法
15. 全体のまとめ

授業は積み重ねの部分が多いので、毎回出席し、課題を必ず提出することが大切です。週に2〜3時間は課題に費やしてください。課題について友人と相談・議論することは構わないし、むしろ推奨します。しかし、理解しないままに他人の回答をコピーしていては試験が通らないでしょう。もし課題が自分たちだけではできなければ、授業が終わったあとに聞いてください。

(a) 評価方法:
毎回の宿題20%
中間試験40%
期末試験40%
(ただし、どちらか一方でも対面による試験が不可能となった場合には、毎回の宿題の割合を上げることがある。)

(b) 評価基準:以下は最低達成基準である。

ブロック行列で表現される線形計画問題について、その双対問題を書けること。
線形計画問題について、宿題における基本レベル程度の問題が解けること。
簡単な問題を整数計画問題として定式化できること。
整数計画問題について、宿題における基本レベル程度の問題が解けること。
ソルバーを用いて実践レベルの問題を解くためのプログラミングができること。

授業の終わりに質問時間を設けるので、まずはそのときに相談してください。それ以外の時間に質問したいときには、Google Classroom でお願いします。

線形最適化は実社会の身近な問題から巨大なプロジェクトまで扱うことができます。
近年ではAIにおけるパラメータの最適化や評価関数の最適化といった応用があります。いちユーザで終わることなく、その中身について深い知見を得たい方はぜひ。

特になし

None