シラバスPDF版

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