到達目標
１．計算量の概略を示すことができる。
２．簡単な線形計画問題を解ける。
３．線形計画問題の双対問題を解ける。
４．簡単な組合せ最適化問題を解ける。
５．簡単な動的計画問題を解ける。
６．現実の問題を数理計画法の視点から定式化できる。
ルーブリック
| 理想的な到達レベルの目安 | 標準的な到達レベルの目安 | 未到達レベルの目安 |
| 評価項目1 | 計算量の概念を理解し、計算量のオーダーが与えられたときに現実的な時間内に最適解を求めることが出来るか判断できる | 計算量の概念を説明できる | 計算量について理解していない |
| 評価項目2 | 線形計画問題に定式可能な問題を、自ら定式化させて解くことが出来る。 | 単体法を用いて線形計画問題を解くことができる | 線形計画問題の最適解を求めることが出来ない。 |
| 評価項目3 | 簡単な組み合わせ最適化問題を定式化して解くことができる | 簡単な組み合わせ最適化問題が解ける | 簡単な組み合わせ最適化問題が解けない |
| 評価項目4 | PERTについて、先行制約付問題について、PERT図を作成して最小所要時間およびクリティカルパスを求めることができる | PERTについて、PERT図を作成して最小所要時間およびクリティカルパスを求めることができる | PERTについて、最小所要時間およびクリティカルパスを求めることができない |
学科の到達目標項目との関係
教育方法等
概要:
本科目では、組み合わせ最適化問題に対する数理計画的手法、およびそのアルゴリズムについて概説する。
PERTアルゴリズムを用いたプロジェクトマネジメント技法についても取り扱う。
また、定式化した問題について、コンピュータに解かせるといったことも随時実施する。
授業の進め方・方法:
・教科書を用いた、講義形式で進める。
・第８回に、通常授業週であるが、中間試験を実施する。この中間試験は、成績評価においては学期末の定期試験と同等の比率に取り扱う。
注意点:
・第1回と教科書記載外の内容はプリントを用意するが、それ以外は教科書を使用し、講義を進める。教科書を持参しないことに因る不利益については対応しない。
・高度なプログラムの作成技術は必要としないが、プログラムの制御構造やアルゴリズムに関する初歩的な知識は必要となる。
・代数幾何の知識が必要となる。本科および必修科目での学習内容は習得済みを前提として講義を進めるので、復習しておくこと。（例：直線/平面の式、３×３程度までの行列の掛け算、逆行列の計算、などは既習を前提に進める）
・課題等提出物において、剽窃やデータ複製等の不正が発覚した場合、誰が写した写させたに関わらず、あとから提出された解答の評価を大きく減点する。
授業計画
|
|
週 |
授業内容 |
週ごとの到達目標 |
| 後期 |
| 3rdQ |
| 1週 |
ガイダンス
グラフ理論 |
グラフ理論について、有効グラフ、無向グラフ、閉路、経路、を説明できる。
最小全域木を求めることが出来る
|
| 2週 |
計算量理論 |
NP困難問題、および、計算時間のオーダーについて説明できる。
|
| 3週 |
線形計画問題
線形計画問題の幾何学的解法 |
３次程度の規模の問題を線形計画問題として定式化し、幾何学的解法により解を求めることが出来る
|
| 4週 |
線形計画問題と単体法 |
線形計画問題について、単体法を用いて解くことができる。
|
| 5週 |
線形計画問題の双対問題 |
線形計画問題の双対問題を 求めて解くことが出来る
|
| 6週 |
ラグランジュ緩和（１） |
ラグランジュ緩和、相補性条件、弱双対定理、強双対定理について説明できる
|
| 7週 |
線形計画問題の演習 |
線形計画問題をコンピュータ上（Excel、もしくは、汎用ソルバー）で解かせることができる
|
| 8週 |
中間試験 |
グラフ理論、計算量に関する設問に解答できる
線形計画問題を机上で解くことができる。
|
| 4thQ |
| 9週 |
最短経路問題 |
ベルマン・フォード法を用いて、最短経路問題を解くことができる
|
| 10週 |
最大流問題
最小費用流問題 |
最大流問題、最小費用流問題を解くことができる
|
| 11週 |
分枝限定法
動的計画法 |
ナップサック問題を解くことができる
|
| 12週 |
切除平面
ラグランジュ緩和（２） |
切除平面法について説明できる
|
| 13週 |
主双対アルゴリズム |
主双対法を用いて点被覆問題を解くことができる
|
| 14週 |
ＰＥＲＴ（１） |
PERTを用いて、クリティカルパスと最短所要時間を求めることが出来る
|
| 15週 |
ＰＥＲＴ（２） |
PERTを用いて、先行制約付の問題について、クリティカルパスと最短所要時間を求めることが出来る
|
| 16週 |
期末試験 |
各種最適化問題およびPERTに関する設問に解答することが出来る
|
評価割合
| 試験 | 発表 | 相互評価 | 態度 | 課題・レポート | その他 | 合計 |
| 総合評価割合 | 60 | 0 | 0 | 10 | 30 | 0 | 100 |
| 基礎的能力 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 専門的能力 | 60 | 0 | 0 | 10 | 30 | 0 | 100 |
| 分野横断的能力 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |