問題解決の数理(’17):シラバス概要
■ 講座情報
問題解決の数理(’17)
Mathematical Approaches to Problem Solving ('17)
【主任講師】
大西 仁(放送大学教授)
【教材・資料】
・インターネット視聴
■ 講義概要
本講義では、主に決定問題を数理モデルを用いて解く方法を解説する。
問題の目的や制約条件を数理モデルで定式化することにより、
計算機に問題を解かせることが可能になり、
手計算では解けない複雑な問題でも解けるようになる。
決定問題は、工学のみならず、日常生活、経営、行政等のあらゆる場面に現れる。
実用レベルの問題は計算機で解く必要があり、
そのためのソフトウエアも普及していることから、
解法の数学的詳細より、
具体的な問題を簡単な数式により定式化することに重点をおく。
【授業の目標】
問題を解く計算は計算機に任せることができるが、
問題を数理モデルとして定式化するのは問題を解決する人間が行う必要がある。
したがって、具体的な問題を数理モデルとして定式化できるようになることが、
全受講生の最初かつ最大の目標である。
問題の解法の特徴を理解していると、より効率的に解を得られることがある。
また、より専門的な学習を円滑にすることから、
解法の考え方と特徴を理解し、問題に対して適切な方法を選択できるようになることが、
特に問題の解法に興味を持つ受講生の一歩進んだ目標となる。
【講義項目】
- 第1回 線形最適化法(1):一次式による問題の定式化
- 第2回 線形最適化法(2):線形最適化問題の解法
- 第3回 ネットワーク最適化法
- 第4回 スケジューリング:プロジェクトの管理
- 第5回 在庫管理
- 第6回 階層分析法:主観と勘を有効活用する意思決定
- 第7回 ゲーム理論:協調と競合の数理(1)
- 第8回 ゲーム理論:協調と競合の数理(2)
- 第9回 統計的決定:不確実状況下での決定
- 第10回 問題の状態空間モデルと探索
- 第11回 待ち行列理論:待ちの数理
- 第12回 非線形最適化法
- 第13回 統計モデル
- 第14回 組み合わせ最適化法
- 第15回 メタヒューリスティクス
■ 講義内容
各講義回の概要とキーワード
第1回 線形最適化法(1):一次式による問題の定式化
線形最適化法(線形計画法)は、目的と制約条件を一次式で記述し、
制約を満たす最適解を求める手法である。
制約のある資源で最大の効果を得たり、
最小のコストで目的を達成するために用いられる。
線形最適化問題について応用例を交え解説する。
■ 【キーワード】
線形最適化問題、生産計画問題、食事問題、輸送問題
第2回 線形最適化法(2):線形最適化問題の解法
線形最適化問題の最適解を求める代表的なアルゴリズムである
シンプレックス法について解説する。
■ 【キーワード】
線形最適化法、標準形、シンプレックス法
第3回 ネットワーク最適化法
ネットワーク最適化問題は、
点と点が線で結ばれたネットワーク上で、
特定の目的に関する最適解を求める問題で、
カーナビゲーションシステムにおける最短経路の発見など幅広く応用されている。
ネットワーク最適化問題とその解法について応用例を交え解説する。
■ 【キーワード】
グラフ、ネットワーク、最短路問題、最大流問題
第4回 スケジューリング:プロジェクトの管理
プロジェクトとは特定の目的を達成するための作業群のことであり、
プロジェクトを構成する各作業の開始時刻を定めた計画をスケジュールと呼ぶ。
本章では、
プロジェクトを効果的・効率的に遂行するための
スケジュールを作成する方法について解説する。
■ 【キーワード】
プロジェクト、スケジューリング、PERT、CPM
第5回 在庫管理
在庫管理問題とその解法について解説する。
工場や小売店で在庫を余計に抱えることは、
保管コストの増加や時間経過による商品の価値低下を招く。
一方、在庫切れは利益を得る機会の損失である。
在庫を適切に管理することが経営において重要である。
基本的な在庫管理モデルについて解説する。
■ 【キーワード】
在庫管理、経済発注量、定量発注方式、定期発注方式、ABC分析、
ロットサイズ決定問題
第6回 階層分析法:主観と勘を有効活用する意思決定
階層分析法の代表的な方法について解説する。
階層分析法(Analytic Hierarchy Process;AHP)は、
複数の選択基準からなる代替案の選択問題において、
問題を目標、選択基準、代替案の3階層に分け、各階層において比較評価を行い、
総合評価にまとめる。
客観評価ができずに、決定者の主観や勘に頼らざるを得ない場面で特に威力発揮する。
■ 【キーワード】
階層分析法、AHP (Analytic Hierarchy Process)、一対比較
第7回 ゲーム理論:協調と競合の数理(1)
ゲーム理論の初歩的な事項について解説する。
ゲーム理論は、利害の必ずしも一致しない状況における合理的意思決定や
合理的配分方法を数理的に分析する方法である。
政治、経済、軍事、経営、社会など幅広い応用分野を持つ。
■ 【キーワード】
ゲーム理論、ナッシュ均衡解、マキシミン戦略、混合戦略
第8回 ゲーム理論:協調と競合の数理(2)
前回に引き続きゲーム理論について解説する。
展開型ゲーム、無限繰り返しゲームによる協調の出現、
ゲーム理論によるオークションの分析について述べる。
■ 【キーワード】
展開型ゲーム、先読み推論(逆向き推論)、繰り返しゲーム、協調、オークション
第9回 統計的決定:不確実状況下での決定
統計的意思決定の方法について解説する。
現実世界では、決定に関わる状況に不確実性が伴うことが多い。
不確実性が伴う状況で合理的に決定を行うためには、
統計的なアプローチが必要である。
統計的決定法として期待効用最大化原理について解説する。
次いで、パタン認識と信号の検出について統計的決定の観点から述べる。
■ 【キーワード】
効用、主観確率、期待効用最大化原理、パタン認識、信号検出理論
第10回 問題の状態空間モデルと探索
問題の解決の状態空間モデルと状態空間を含むグラフの探索法について解説する。
問題解決は、状態空間を探索して
初期状態からゴールへ至る系列を発見することと定式化することもできる。
パズルやゲームなどを状態空間の探索により解くことは、
人工知能の最初期からの研究課題であったが、
1990年代にはチェスの世界チャンピオンに勝利するほど探索の技法は高度化した。
探索技法はパズルやゲームに限らず、様々な問題解決のツールとして利用できる。
■ 【キーワード】
状態空間モデル、系統的探索、ヒューリスティック探索
第11回 待ち行列理論:待ちの数理
待ち行列理論とは、
店舗におけるレジ待ちの行列や電話回線の混雑による着信拒否といった
現象を確率論に基づくモデルにより解析するための理論である。
初歩的な待ち行列モデルと解析法について解説する。
■ 【キーワード】
待ち行列、ケンドールの記号、リトルの公式、M/M/cシステム
第12回 非線形最適化法
現実世界の問題では線形式で定式化できない問題が多い。
また、統計モデルのパラメタ推定や機械学習の多くも非線形最適化問題である。
非線形最適化法のうち基本的な手法について解説する。
■ 【キーワード】
非線形最適化問題、最急降下法、ニュートン法
第13回 統計モデル
統計モデルは、誤差を含むデータの背後にある規則性、
そのようなデータを発生させる仕組みを数式で表したものである。
統計モデルにより誤差を含む観測データから現象を分析したり、
予測を行うことができる。
代表的な統計モデルとパラメタの推定法について解説する。
■ 【キーワード】
統計モデル、回帰モデル、パラメタ推定、最小二乗法、尤度、最尤推定法
第14回 組み合わせ最適化法
組み合わせ最適化問題とは、
条件を満たす変数の組み合わせの中で最適なものを求める問題である。
組み合わせ最適化問題は実世界にあふれている。
その多くは解くための計算量が莫大になり、
素朴な探索では解くことができないが、
様々な工夫が施され、年々規模の大きな問題を解くことができるようになっている。
代表的な組み合わせ最適化問題と解法について解説する。
■ 【キーワード】
組み合わせ最適化問題、分枝限定法、欲張り法、動的計画法
第15回 メタヒューリスティクス
メタヒューリスティクスの代表的な手法を解説する。
数理的な問題を解くための計算技術や計算機の性能向上により、
複雑な問題を解くことができるようになった。
しかし、現実の問題にはさらに複雑な問題があふれている。
そこで、質の良い近似解を高速に得る方法である
メタヒューリスティクスが盛んに研究されている。
■ 【キーワード】
メタヒューリスティクス、局所探索法、タブー探索法、遺伝的アルゴリズム
以上