ORWiki - 利用者の投稿記録 [ja]

《モデル管理》

2007-08-10T08:15:16Z

H.Yamaguchi:

'''【もでるかんり (model management) 】'''

　[[モデル]] (model)には, 一般に, 形を真似る像的モデル, 物理的性質の類似性を利用する類似モデル, 論理的抽象的な記述をする記号モデルがある. [[モデル管理]] (modelmanagement)においてモデルといえば意思決定問題を記述する記号モデルを指すが, 数式モデル, 計算手続き, データモデルなどが含まれ, その含意は多様である.

　モデル管理とはモデルの作成から廃棄に至る[[モデルライフサイクル]] (modeling life cycle)の全過程にわたるあらゆる活動(モデルの作成, 活用, 蓄積, 変更, 再利用, 合成, 統合等を含む)に関する支援を構築し提供することである. モデルライフサイクルが意思決定の過程と並行することから容易に想像されるように, モデル管理は1975年頃から意思決定支援システム研究のなかで議論され始めたが, 1980年代中期以降, 特に, [[構造化モデリング]](structured modeling) [3] が提唱されて以来, オペレーションズ・リサーチによる意思決定支援のための情報システム環境という意味あいが強くなった.

　この間, モデル管理の対象としてのモデルの具体的内容は次第に変化してきた [2]. すなわち, 初期にはモデルを解く計算手続き, ないし, 計算プログラムの記述を指すのが主流であったが, 次第に, モデルを解く手続きへの入出力データの記述を指すようになり, 近年は, モデル型とその数値データの記述を指すことが多い. モデルライフサイクルの重要な成果物に, 問題記述, モデル, [[ソルバー]] (solver), 解および関連ドキュメントがある. ソルバーを管理対象としてその利用に係るすべての知識や作業を利用者に依存するのが第一の, 必要な形式でのデータの準備だけを利用者に依存するのが第二の, モデルの構築とデータの作成だけを依存するのが第三のモデル管理である.

　ソルバーによって解かれるモデルは決定変数と様々な数値データによって記述され, もっとも具体的かつ個別的である. これを[[モデル具体例]] (model instance)という. モデル具体例の数値データの一部あるいは全部をパラメータとして代数的に表現したものが[[モデル型]] (model type)である. モデル型のパラメータに特定の数値データを割り当てることによって様々なモデル具体例を作ることができるから, モデル型はモデル具体例の集合を記述するものと解釈できる. モデル型は大きな集合を記述できるほど一般性が高いと言える. 割り当て問題のモデルに比べて輸送問題のモデルはより一般的であり, 標準的な線形計画問題のモデルはさらに一般性が高い.

　情報技術を活用してモデル管理を実現するためには, モデルライフサイクルにおける様々な活動を形式的に記述し, 情報システム上で実施することができなければならない. この意味で[[モデル記述言語]] (model descriptionlanguage)とソルバーは重要な要素である. ソルバーを起動して問題を解くには, モデルの数値データをソルバーの仕様にあった形式で入力することが必要になる. この入力データはモデル具体例の1つの記述形式と考えられるので, ソルバー形式(solver-form)モデルと呼ばれる. これに対して, 第三の意味のモデルはモデル作成者の記述形式と考えることができるので, ユーザ定義(user-defined)モデルと呼ばれる. モデル記述言語はユーザ定義モデルを記述する人工言語である. モデル記述において, モデル型の記述とは独立にモデル具体例を記述できるという[[モデル/データ独立|モデル／データ独立]] (model/data independence), モデルを複数のソルバーへのデータ入力に利用できる[[モデル/ソルバー独立|モデル／ソルバー独立]] (model/solver independence)はモデルやソルバーの情報資源としての価値を高める上で重要である.

　代表的なモデル記述言語にはその処理システムが付随しており, 正確性や完全性を自動チェックできるばかりでなく, 特定のソルバー向けにはソルバー形式モデルを自動生成する機能も持つ. このことからわかるように, モデル管理の研究では, モデルライフサイクルを問題記述から解まで, 意思決定問題の記述としてのモデルを次々に変換する過程ととらえることもできる. モデル記述言語はモデル構築の初期段階の情報を記述するものから完成したモデルを記述するものまで様々である. その中には, 数式モデルを構造化したテキスト形式に記述するもの, 実体－関連(entity-relationship)構造などのデータモデルを応用するもの, 述語論理など知識表現を応用するもの, グラフ文法などに基づいてグラフやネットワークを利用するもの, などがある [1].

　モデル管理の研究は, 線形計画問題やネットワーク計画問題など, 効率的で汎用的な解法の知られた分野の数式モデル構築からソルバーによる解の導出までの過程という極めた限られた範囲に集中している. この範囲を拡大するとともに, さらに高度な支援を可能にすることが望まれる.

　特定の問題を対象にモデルを構築し解く, いわゆる, 小規模モデル構築(modeling in-the-small)を対象にする研究ではモデル記述言語の記述能力を組み合わせ問題等に拡張する試み, モデル記述にモデルに関する情報(変数やパラメータの単位や次元, 式の意味, 対応するソルバー, 作成者など)を組み込む試み, より問題記述に近い記述から数式モデルを自動生成する試みなどが行われている. 既存のいくつかのモデルを組み合わせてより複雑大規模なモデルを構築して解く過程を対象にする大規模モデル構築(modelingin-the-large)の研究では, オブジェクト指向技術を応用するなどした[[モデル合成]] (model composition)や[[モデル統合]] (model integration)の研究, 合成や統合によって構築されたモデルとソルバーを結びつける研究, それらを支援するモデルやソルバーのデータベース化の研究, などがある [5]. モデル管理は意思決定支援の情報システム環境として実現されるのであり, 対話や視覚化といったインターフェースの研究も重要な分野である [4].

　モデルを情報資源としてその利用を支援することは, 企業における知識管理の意味からも, 重要である. モデルの再利用にはモデルの等価性, モデルに対応する問題の等価性の判定が基本的条件となるが, その理論や技術はいまだ極めて不十分である.

----

'''参考文献'''

[1] A. Bharadwaj, J. Choobineh, A. Lo and B. Shetty, "Model Management Systems: A Survey," ''Annals of Operations Research'', '''38''' (1992), 17-67.

[2] A. -M. Chang, C. W. Holsapple and A. B. Whinston, "Model Management Issues and Directions," ''Decision Support Systems'', '''9''' (1993), 19-37.

[3] A. M. Geoffrion, "An Introduction to Structured Modeling," ''Management Science'', '''33''' (1987), 547-588.

[4] C. V. Jones, ''Visualization and Optimization'', Kluwer Academic Publishers, Dordrecht, The Netherlands, 1996.

[5] R. Krishnan, "Model Management: Survey, Future Research Directions and a Bibliography," ''ORSA CSTS Newsletter,'' '''14''' (1993), 1-8.

[[category:システム分析・意思決定支援・特許|もでるかんり]]

トーク:《モデリング》

2007-08-10T08:11:24Z

H.Yamaguchi: 新しいページ: '冒頭の　「モデリング」と　中盤の「数理計画法」のリンクが赤いままで，どのような対処をしたらいいのかわかりません．山...'

冒頭の　「モデリング」と　中盤の「数理計画法」のリンクが赤いままで，
どのような対処をしたらいいのかわかりません．

山口

モデル型

2007-08-10T08:04:26Z

H.Yamaguchi:

'''【もでるがた (model type)】'''

定数や係数といったモデルの決定変数以外のパラメータを記号で表現したモデルをいう. 決定変数以外のどの範囲のパラメータを記号で表現し, 逆に, どのパラメータを具体的に数値で指定するかによって, そのモデル型に属するモデル具体例の範囲が左右される. モデルの一種であって, モデル具体例との対比でこのように呼ばれる.

同義語：モデルクラス（model class）

モデル

2007-08-10T08:02:09Z

H.Yamaguchi:

'''【もでる (model)】'''

対象を何らかの方法で操作的構造的に表現したものをいう．物理モデル, 記号モデルに大きく分けられるが, 一般的にモデル管理の文脈では記号モデルを指し, 中でも数式モデルを指すことが多い．線形計画モデル, ネットワーク・モデル, 待ち行列モデルなどという．モデル具体例やモデル型を総称する．

《意思決定支援システム》

2007-08-10T04:47:52Z

H.Yamaguchi:

'''【いしけっていしえんしすてむ (decision support system)】'''

　経営組織におけるコンピュータの利用は, 1950年代の受注処理や給与計算といった, いわゆるトランザクション処理を行うEDP(電子データ処理)からはじまり, 1960年代には, 意思決定に必要な情報を定期的にマネージャに報告することを目的とする, MIS([[経営情報システム]])の考え方へと発展した. MISの基本的な考え方は, 意思決定者が情報を処理するものに意思決定に必要な情報がどのようなものであるかを伝えて報告を依頼し, 情報処理者はそれにしたがって, 定期的に報告を行うというものであった. しかし, 意思決定者は予めどのような情報が意思決定に必要であるかについて十分に知ってはおらず, また, 静的な情報よりもやりとりの中で動的に生み出される情報が重要であるということなどから, このような形式ではよりよい意思決定にはつながらないことが明らかになってきた. 問題を引き起こしているのは, 意思決定と情報処理の分離である. そこで, [[意思決定過程]](decision making process)において意思決定者が自ら情報処理を行って, 意思決定に必要な情報を動的に獲得するという考えが生まれた. これが[[意思決定支援システム]](DSS, decision support system)の始まりである.

　DSSは歴史的には, 1967年のスコットモートンによる博士論文とそれが基礎となった著書Management Decision Systems[1]に逆のぼることができるとされている. そこでは, "DSS"という用語ではなく, "MDS(Management Decision Systems)"という用語が用いられていた. MDSは, 「コンピュータを用いた対話的なシステムで, [[非構造化問題]]を解決するために, 意思決定者がデータやモデルを利用する手助けをするもの(interactive computer-based systems, which helpsdecision makers utilize data and models to solve unstructuredproblems)」と定義されている. この定義には, 後にDSSの際立った特徴となる, いくつかのキーワードが出てきている. それらは, 「対話的(interactive)」, 「データとモデルの利用」, そして, 「非構造化(unstructured)」という概念である. ここで, 「非構造化」問題とは, 変数を言葉でしか表現できず, 目標があいまいで,　解を求める手続きがはっきりしない問題のことを指している.

　スコットモートンがManagement Decision Systemsを出版したのと同じ1971年に, 彼はゴーリーと"A Framework for Management Information Systems"という論文を発表した. この論文の中で, 彼らは「[[構造化問題]]／[[非構造化問題]]」というサイモンに依拠する分類と, 「戦略的計画(strategic planning)／マネジメントコントロール(managementcontrol)／オペレーショナルコントロール(operational control)」という, アンソニーによる経営活動における管理階層にもとづく分類を結び付けて, DSSの概念を明らかにした. アンソニーの分類において, 「戦略的計画」とは, 「資源配分に関わる長期的な目標と政策についてのもの」であり, 「マネジメントコントロール」は, 「組織目標を達成するために資源を獲得し, 有効利用することについてのもの」であり, 「オペレーショナルコントロール」は, 「タスクを効率的で, しかも効果的に実施することに関するもの」であるとされている.

<center><table><tr><td align=center>[[画像:0216-C-A-04-kiso-zu1.png|center|図1: アンソニーの管理階層]]</td></tr>
<td align=center>図1: アンソニーの管理階層</td></table></center>

　ゴーリーとスコットモートンは, サイモンによる問題に対する2分類に, さらに中間的な問題として, 「半構造化(semi-structured)」問題も考え, 問題を3つに分類した. このような問題に対する分類を, アンソニーによる管理階層の3分類とは独立な軸であると考えると, 表1にある<math>3\times 3=9 \, </math>のセルができる. 表1において, ゴーリーとスコットモートンは, 半構造化問題, 非構造化問題に対しては, 従来のMISや経営科学的なアプローチは有効ではなく, 利用者を支援する情報システム, すなわちDSSが有用であると主張した.

<center>
<caption>表1: ゴーリーとスコットモートンによるDSSの枠組み</caption>
<table width="700" border="1" cellspacing="2" cellpadding="0">
<tr>
<td rowspan="2" colspan="2"><br></td>
<td colspan="3" align="center" width="548">管理のタイプ</td>
</tr>
<tr>
<td align="center" width="180">オペレーショナル<br>
コントロール</td>
<td align="center" width="180">マネジメント<br>
コントロール</td>
<td align="center" width="180">戦略的計画</td>
</tr>
<tr>
<td rowspan="3" align="center">意<br>思<br>の<br>決<br>定<br>の<br>タ<br>イ<br>プ
</td>
<td align="center" width="100">構造的</td>
<td align="center" width="180">会計<br>
売掛金処理<br>
受注処理</td>
<td align="center" width="180">予算分析<br>
短期予測<br>
人事報告など </td>
<td align="center" width="180">財務, 投資<br>
倉庫立地<br>
流通システム</td>
</tr>
<tr>
<td align="center" width="100">半構造的</td>
<td align="center" width="180">生産スケジューリング<br>
在庫管理<br>
</td>
<td align="center" width="180">信用評価, 予算編成<br>
プラント配置, プロジェクト<br>
スケジューリングなど</td>
<td align="center" width="180">新プラントの設置<br>
M&A, 新製品計画<br>
QA計画など</td>
</tr>
<tr>
<td align="center" width="100">非構造的</td>
<td align="center" width="180">ソフトウェアの購入<br>
貸付承認など</td>
<td align="center" width="180">交渉<br>
ハードウェアの購入<br>
陳情活動など</td>
<td align="center" width="180">R&D計画<br>
新技術開発など</td>
</tr>
</table></center>

　DSSの分類も様々な観点から行なわれている. オルターは, システムの出力と意思決定との結びつきの強さという観点から, 「データ指向のDSS」と「モデル指向のDSS」に分類している. また, ハッカソーンとキーンは, DSSの支援の対象とする利用者を基準として, 個人(personal), グループ(group), 組織(organization)の3つに分類している[2]. 一方, スプレーグとカールソンは, DSSに関わる技術レベルに関して, DSSを次の3つに分類している[3]. すなわち,

1) DSSツール:グラフィックス, 問合せシステム, 乱数発生器, スプレッドシート, プログラミング言語, データベースシステム, エディタなどの, DSSを構築するために必要とする基本的な機能単位を実現しているソフトウェア

2) DSSジェネレータ:IFPS(対話型財務計画支援システム)に代表される, ある問題についてのデータやモデルを登録すれば, DSSとして利用できるような, DSS構築環境. 表計算ソフトもこれに分類されると考えられる.

3) 特定DSS:ある特定の問題における[[意思決定支援]](decision support)を行うために, データやモデルがすでに登録されたDSS環境.

である.

　DSSは, 図2にあるように, 次の3つの構成要素からなるとするのが一般的である[4].

<center><table><tr><td align=center>[[画像:0216-C-A-04-kiso-zu2.png|center|図2: DSSの構造]]</td></tr>
<td align=center>図2: DSSの構造</td></table></center>

1) データ管理:状況に関連するデータを持ち, [[データベース管理]] (databasemanagement)システムと呼ばれるソフトウェアによって管理されるデータベースを含むもの

2) モデル管理:システムの分析機能を提供する, 財務, 統計, 経営科学などの定量的モデルを含むソフトウェアパッケージとそれに関するソフトウェアの管理を行なうもの. モデル管理は[[モデルベース管理]] (model-base management)システムにより行う.

3) コミュニケーション([[対話管理]]):利用者がDSSとコミュニケートし, 命令を与えるための, 利用者とシステムの間の仲介を行なうもの.

　各々の管理システムには, 管理の対象となる, データやモデルの群があり, 各々データベース, モデルベースと読んでいる. 実現形態でいうと, これらは, 通常補助記憶装置内でファイル群として存在する. そこで, 図2では円柱で表示してある. 各々のサブシステムの詳細については, 文献[5] などを参照されたい.

　このような基本構造の下で, たとえば, シミュレーションモデルを用いて企業活動の予測を行ったり, 数理計画法のソルバーを用いて最適解を求めたり, 統計分析のソフトウェアを用いて, 平均値, 分散, 標準偏差, 共分散などの統計量を求めることができる. これらは, モデルベースにあるモデルを用いることによって実現される. また, 「what-if分析」, 「感度分析」, 「目標追求分析」は, 変数の値を様々にかえながら, シミュレーションを行うことによって実現される. これらの変数の値は, もちろんデータベースに貯えられている.

　計算の結果を, 表やグラフによって表示するのは, 対話管理システムの役割である. この他にも, 利用者の意図をシステムに反映させることと, システムの出力を利用者の理解しやすい形式で提示することが, 対話管理システムに求められる機能である.

　DSS研究は, 1980年代はじめまでの概念についての議論やアーキテクチャの提案の時代を経て, 実装が進み, その後コンピュータ技術の発展に伴い, データウェアハウスと呼ばれる, データを格納し, 問合せに対応する中央集権化された構造を経て, OLAP（On-Line Analytical Processing, オンライン分析による処理）の発展につながっている.
　OLAPでは, データをさまざまな方向から“切り刻む”ことが可能である.
たとえば, 多次元のデータの一部分を取り出すダイスや, ある側面を切り出すスライス, ある次元のデータをさらに細分化して次元を拡張するドリルダウンなどがある[6].

----
'''参考文献'''

[1] M.S. Scott-Morton, ''Management Decision Systems: Computer-Based Supportfor Decision Making'', Cambridge, Mass, Division of Research, HarvardUniv., 1971.

[2] R.D. Hackarthorn and P.G.W. Keen, "Organizational Strategies forPersonal Computing in Decision Support Systems," ''MIS Quarterly'', September, 1981.

[3] R.H. Sprague and E.D. Carlson, ''Building Effective Decision SupportSystems'', Englewood Cliffs, N.J., Prentice-Hall, 1982.

[4] E. Turban, ''Decision Support and Expert Systems (2nd ed.),'' Macmillan, (1990).

[5] 飯島淳一, 『意思決定支援システムとエキスパートシステム』, 日科技連出版社, 1993.

[6] George Chang, Marcus J.Healey, James A.M.McHugh, Jason T.L.Wang, Mining the World Wide Web, Kluwer Academic Press, 2001, （武田善行, 梅村恭司, 藤井敦　訳, 『Webマイニング』, 共立出版, 2004.）

[[category:システム分析・意思決定支援・特許|いしけっていしえんしすてむ]]

《意思決定支援システム》

2007-08-10T04:19:07Z

H.Yamaguchi:

'''【いしけっていしえんしすてむ (decision support system)】'''

　経営組織におけるコンピュータの利用は, 1950年代の受注処理や給与計算といった, いわゆるトランザクション処理を行うEDP(電子データ処理)からはじまり, 1960年代には, 意思決定に必要な情報を定期的にマネージャに報告することを目的とする, MIS([[経営情報システム]])の考え方へと発展した. MISの基本的な考え方は, 意思決定者が情報を処理するものに意思決定に必要な情報がどのようなものであるかを伝えて報告を依頼し, 情報処理者はそれにしたがって, 定期的に報告を行うというものであった. しかし, 意思決定者は予めどのような情報が意思決定に必要であるかについて十分に知ってはおらず, また, 静的な情報よりもやりとりの中で動的に生み出される情報が重要であるということなどから, このような形式ではよりよい意思決定にはつながらないことが明らかになってきた. 問題を引き起こしているのは, 意思決定と情報処理の分離である. そこで, [[意思決定過程]](decision making process)において意思決定者が自ら情報処理を行って, 意思決定に必要な情報を動的に獲得するという考えが生まれた. これが[[意思決定支援システム]](DSS, decision support system)の始まりである.

　DSSは歴史的には, 1967年のスコットモートンによる博士論文とそれが基礎となった著書Management Decision Systems[1]に逆のぼることができるとされている. そこでは, "DSS"という用語ではなく, "MDS(Management Decision Systems)"という用語が用いられていた. MDSは, 「コンピュータを用いた対話的なシステムで, [[非構造化問題]]を解決するために, 意思決定者がデータやモデルを利用する手助けをするもの(interactive computer-based systems, which helpsdecision makers utilize data and models to solve unstructuredproblems)」と定義されている. この定義には, 後にDSSの際立った特徴となる, いくつかのキーワードが出てきている. それらは, 「対話的(interactive)」, 「データとモデルの利用」, そして, 「非構造化(unstructured)」という概念である. ここで, 「非構造化」問題とは, 変数を言葉でしか表現できず, 目標があいまいで,　解を求める手続きがはっきりしない問題のことを指している.

　スコットモートンがManagement Decision Systemsを出版したのと同じ1971年に, 彼はゴーリーと"A Framework for Management Information Systems"という論文を発表した. この論文の中で, 彼らは「[[構造化問題]]／[[非構造化問題]]」というサイモンに依拠する分類と, 「戦略的計画(strategic planning)／マネジメントコントロール(managementcontrol)／オペレーショナルコントロール(operational control)」という, アンソニーによる経営活動における管理階層にもとづく分類を結び付けて, DSSの概念を明らかにした. アンソニーの分類において, 「戦略的計画」とは, 「資源配分に関わる長期的な目標と政策についてのもの」であり, 「マネジメントコントロール」は, 「組織目標を達成するために資源を獲得し, 有効利用することについてのもの」であり, 「オペレーショナルコントロール」は, 「タスクを効率的で, しかも効果的に実施することに関するもの」であるとされている.

<center><table><tr><td align=center>[[画像:0216-C-A-04-kiso-zu1.png|center|図1: アンソニーの管理階層]]</td></tr>
<td align=center>図1: アンソニーの管理階層</td></table></center>

　ゴーリーとスコットモートンは, サイモンによる問題に対する2分類に, さらに中間的な問題として, 「半構造化(semi-structured)」問題も考え, 問題を3つに分類した. このような問題に対する分類を, アンソニーによる管理階層の3分類とは独立な軸であると考えると, 表1にある<math>3\times 3=9 \, </math>のセルができる. 表1において, ゴーリーとスコットモートンは, 半構造化問題, 非構造化問題に対しては, 従来のMISや経営科学的なアプローチは有効ではなく, 利用者を支援する情報システム, すなわちDSSが有用であると主張した.

<center>
<caption>表1: ゴーリーとスコットモートンによるDSSの枠組み</caption>
<table width="700" border="1" cellspacing="2" cellpadding="0">
<tr>
<td rowspan="2" colspan="2"><br></td>
<td colspan="3" align="center" width="548">管理のタイプ</td>
</tr>
<tr>
<td align="center" width="180">オペレーショナル<br>
コントロール</td>
<td align="center" width="180">マネジメント<br>
コントロール</td>
<td align="center" width="180">戦略的計画</td>
</tr>
<tr>
<td rowspan="3" align="center">意<br>思<br>の<br>決<br>定<br>の<br>タ<br>イ<br>プ
</td>
<td align="center" width="100">構造的</td>
<td align="center" width="180">会計<br>
売掛金処理<br>
受注処理</td>
<td align="center" width="180">予算分析<br>
短期予測<br>
人事報告など </td>
<td align="center" width="180">財務, 投資<br>
倉庫立地<br>
流通システム</td>
</tr>
<tr>
<td align="center" width="100">半構造的</td>
<td align="center" width="180">生産スケジューリング<br>
在庫管理<br>
</td>
<td align="center" width="180">信用評価, 予算編成<br>
プラント配置, プロジェクト<br>
スケジューリングなど</td>
<td align="center" width="180">新プラントの設置<br>
M&A, 新製品計画<br>
QA計画など</td>
</tr>
<tr>
<td align="center" width="100">非構造的</td>
<td align="center" width="180">ソフトウェアの購入<br>
貸付承認など</td>
<td align="center" width="180">交渉<br>
ハードウェアの購入<br>
陳情活動など</td>
<td align="center" width="180">R&D計画<br>
新技術開発など</td>
</tr>
</table></center>

　DSSの分類も様々な観点から行なわれている. オルターは, システムの出力と意思決定との結びつきの強さという観点から, 「データ指向のDSS」と「モデル指向のDSS」に分類している. また, ハッカソーンとキーンは, DSSの支援の対象とする利用者を基準として, 個人(personal), グループ(group), 組織(organization)の3つに分類している[2]. 一方, スプレーグとカールソンは, DSSに関わる技術レベルに関して, DSSを次の3つに分類している[3]. すなわち,

1) DSSツール:グラフィックス, 問合せシステム, 乱数発生器, スプレッドシート, プログラミング言語, データベースシステム, エディタなどの, DSSを構築するために必要とする基本的な機能単位を実現しているソフトウェア

2) DSSジェネレータ:IFPS(対話型財務計画支援システム)に代表される, ある問題についてのデータやモデルを登録すれば, DSSとして利用できるような, DSS構築環境. 表計算ソフトもこれに分類されると考えられる.

3) 特定DSS:ある特定の問題における[[意思決定支援]](decision support)を行うために, データやモデルがすでに登録されたDSS環境.

である.

　DSSは, 図2にあるように, 次の3つの構成要素からなるとするのが一般的である[4].

<center><table><tr><td align=center>[[画像:0216-C-A-04-kiso-zu2.png|center|図2: DSSの構造]]</td></tr>
<td align=center>図2: DSSの構造</td></table></center>

1) データ管理:状況に関連するデータを持ち, [[データベース管理]] (databasemanagement)システムと呼ばれるソフトウェアによって管理されるデータベースを含むもの

2) モデル管理:システムの分析機能を提供する, 財務, 統計, 経営科学などの定量的モデルを含むソフトウェアパッケージとそれに関するソフトウェアの管理を行なうもの. モデル管理は[[モデルベース管理]] (model-base management)システムにより行う.

3) コミュニケーション([[対話管理]]):利用者がDSSとコミュニケートし, 命令を与えるための, 利用者とシステムの間の仲介を行なうもの.

　各々の管理システムには, 管理の対象となる, データやモデルの群があり, 各々データベース, モデルベースと読んでいる. 実現形態でいうと, これらは, 通常補助記憶装置内でファイル群として存在する. そこで, 図2では円柱で表示してある. 各々のサブシステムの詳細については, 文献[5] などを参照されたい.

　このような基本構造の下で, たとえば, シミュレーションモデルを用いて企業活動の予測を行ったり, 数理計画法のソルバーを用いて最適解を求めたり, 統計分析のソフトウェアを用いて, 平均値, 分散, 標準偏差, 共分散などの統計量を求めることができる. これらは, モデルベースにあるモデルを用いることによって実現される. また, 「what-if分析」, 「感度分析」, 「目標追求分析」は, 変数の値を様々にかえながら, シミュレーションを行うことによって実現される. これらの変数の値は, もちろんデータベースに貯えられている.

　計算の結果を, 表やグラフによって表示するのは, 対話管理システムの役割である. この他にも, 利用者の意図をシステムに反映させることと, システムの出力を利用者の理解しやすい形式で提示することが, 対話管理システムに求められる機能である.

----
'''参考文献'''

[1] M.S. Scott-Morton, ''Management Decision Systems: Computer-Based Supportfor Decision Making'', Cambridge, Mass, Division of Research, HarvardUniv., 1971.

[2] R.D. Hackarthorn and P.G.W. Keen, "Organizational Strategies forPersonal Computing in Decision Support Systems," ''MIS Quarterly'', September, 1981.

[3] R.H. Sprague and E.D. Carlson, ''Building Effective Decision SupportSystems'', Englewood Cliffs, N.J., Prentice-Hall, 1982.

[4] E. Turban, ''Decision Support and Expert Systems (2nd ed.),'' Macmillan, (1990).

[5] 飯島淳一, 『意思決定支援システムとエキスパートシステム』, 日科技連出版社, 1993.

[[category:システム分析・意思決定支援・特許|いしけっていしえんしすてむ]]

構造化問題

2007-08-10T04:11:43Z

H.Yamaguchi:

'''【こうぞうかもんだい (structured problem) 】'''

サイモンは, 問題を構造化されたものと非構造化なものにわけた.問題の構造化は, 次の3点を基準に論じることができ, これらの基準を満足する問題が構造化された問題である.

:1) 問題がスカラーやベクトルなどの数値を表す変数を用いて記述できる.

:2) 達成されるべき目標が, 明確に定義された目的関数によって表現できる.

:3) 問題の解を見つけ,定量的に(数値で)表現できるアルゴリズムがある.

構造化問題

2007-08-10T04:11:25Z

H.Yamaguchi:

'''【こうぞうかもんだい (structured problem) 】'''

サイモンは, 問題を構造化されたものと非構造化なものにわけた.問題の構造化は, 次の3点を基準に論じることができ, これらの基準を満足する問題が構造化された問題である.

:(1) 問題がスカラーやベクトルなどの数値を表す変数を用いて記述できる.

:(2) 達成されるべき目標が, 明確に定義された目的関数によって表現できる.

:(3) 問題の解を見つけ,定量的に(数値で)表現できるアルゴリズムがある.

意思決定支援システム

2007-08-10T04:05:35Z

H.Yamaguchi:

'''【いしけっていしえんしすてむ (decision support system (DSS))】'''

MISがうまく機能しなかったことを踏まえて, 意思決定者が対話的にデータやモデルを操作して情報を獲得し, 意思決定を行うことを狙った情報システムで, DSSと略記される. 対話管理, データ管理, モデル管理の3部分システムから構成される. 1960年代末に提案され, その後ネットワーク技術の発展に伴い, 個人レベルの意思決定支援からグループレベル, さらに, 情報資源をネットワーク上に求めるWWWベースのものにまで広がってきている.

詳しくは[[《意思決定支援システム》|基礎編：意思決定支援システム]]を参照.

《スケジューリング理論》

2007-08-10T04:02:27Z

H.Yamaguchi:

'''【すけじゅーりんぐりろん (scheduling theory) 】'''

　スケジュールとは, 時間軸上で設備(ないし資源)に1つ以上の活動を割り当てたものをいう. スケジューリングとは, スケジュールを決めることであって, [[スケジューリング理論]] (scheduling theory) は, 広義にはスケジューリング問題のモデル化, 分析, 解法の開発・分析, スケジューリングシステム, 実際問題への応用などの分野にまたがる理論である. 1つの設備には同時に1つの活動だけを割り当てることができ, 1つの活動は同時に1つの設備にのみ割り当てることができるとするとき, 1つ以上の設備から成るシステムを[[ジョブショップ]] (job shop) という. 各設備に割り当てる活動を作業 (operation) と呼び, いくつかの作業の集合をジョブ (job) と呼ぶ. ジョブショップの設備は一般に機械 (machine) と呼ばれ, 機械はその種類によって工程 (process) に分けられる. ジョブショップは機能別配置 [1] の機械加工工場のモデルと考えられるが, 機械を様々な生産資源に置き換えることによって広い応用分野に対応する. 各工程が1つの機械から成るのが基本的なジョブショップである. あるジョブを構成する作業の間に技術的観点から指定された順序を技術的順序 (technological order) という. 技術的順序に従って各作業を工程に割り付けたときに得る工程の順序を[[工程順序]]（routing）という．各機械において処理する作業の順序をその機械におけるジョブの (あるいは同じことであるが作業の) 処理順序 (sequence) と呼ぶ.

<center><table><tr><td align=center>[[画像:0037-c-a-08+1.png|center|図１：ガントチャート]]</td></tr>
<td align=center><br>図１：ガントチャート</td></table></center>

　ジョブショップにおいて1つのスケジュールが与えられるとき, 横軸に時間をとり縦軸に機械をとって, 各機械ごとに作業を処理する期間を帯状に表示したものを機械向き (machine oriented) ガントチャート (Gantt chart), 縦軸にはジョブを取りその作業の処理期間を帯状に表示したものをジョブ向き (job oriented) [[ガントチャート]]という (図1). スケジュールは本来, 各作業の着手と完了の時刻の集合である. しかし, 各機械が同時には1つの作業しか処理できないことから, 着手順に作業を整列すれば1つの順列を得る. これは処理順序に対応する. 従って, 処理順序が決まれば各作業の着手時刻が自動的に決定されるような状況では, スケジュールと処理順序は実質的に同じ意味である. このためスケジューリング理論は狭義には順序づけ理論(sequencing theory)の意味で使われる. 以下, この狭義のスケジューリング理論の基礎概念を説明する. 関連項目としてスケジューリング問題, スケジューリング・アルゴリズムを参照されたい.

　[[順序付け]] (sequencing) の研究においては処理順序の評価基準を関数表現したものを[[順序付け関数]] (sequencing function) という。理論的には評価基準として各作業の完了時刻に関して非減少な尺度がよく利用される. このような尺度を[[正則尺度]] (regular measure) と呼ぶ。実用的には正則でない尺度も多用される。正則尺度の下では処理順序ごとに, 各作業を工程順序に違反しないでできるだけ早期に着手するただ1つのスケジュールが検討対象となる. すべてのスケジュールに対して、任意の作業をそれより遅くなることなく完了するスケジュールが少なくとも1つは含まれているようなスケジュールの集合を, スケジュールの[[優越集合 (スケジュールの)|優越集合]] (dominant set) と呼ぶ. 正則尺度の下で優越集合はすべての処理順序から上記のように「各作業にできるだけ早期に着手する」ものとして生成されるスケジュールの集合であり, その中の最良のスケジュール(処理順序)が最適である. 次のような[[活性スケジュール]] (active shedule) 全体の集合が優越集合であることは知られているが, 最小の優越集合はまだ知られていない.

　1つの処理順序が与えられるとする. この時, この処理順序に従いできるだけ早期に各作業を処理開始するスケジュールを準活性スケジュールと呼ぶ. 準活性スケジュールにおいて, 他のどの作業の処理開始時刻にも影響を与えないで他の作業を飛び越してより早く着手できる作業を順次前に移動することによって, 他の作業の着手を遅らせるのでなければもはやどの作業も前に移動できないスケジュールが生成される. これが活性スケジュールである. 活性スケジュールを系統的に生成するアルゴリズム [3] は知られているが, 一般に活性スケジュールは極めて多数存在するので, これを完全列挙することによって最適処理順序を決定するのは実際上困難である.

　ジョブの処理順序に関する制約を[[先行関係]] (precedence relation) 制約という. 多くの先行関係は2項関係を用いて記述できるが, 特定のジョブを処理順序の先頭にしてはいけない, などのように, 2項関係では表現できないものもある. 着手可能時刻 (release time) あるいは最早着手可能時刻はジョブの最初の作業の処理を開始できる最早時刻をいう. 順序づけするすべてのジョブの着手可能時刻が既知の状況を静的 (static), そうでない場合を動的順序づけという. 各ジョブに納期が指定される場合もある. 各作業の処理に要する時間を処理時間 (processing time) という. 各作業にはこの他, 段取り時間 (setup time), 後始末時間 (removal time), 前後の作業の間の完了と着手の最小（あるいは最大）の時間間隔である遅れ時間 (delay time) などが指定されることがある.

<center><table><tr><td align=center>[[画像:0037-c-a-08+2.png|center|図2：離接グラフ(機械3, ジョブ3)]]</td></tr>
<td align=center>図２：離接グラフ(機械3, ジョブ3)</td></table></center>

　ジョブやその作業に様々な条件が付加されることがあるが, ジョブショップにおける順序づけの基本は, 工程順序, 先行関係と整合するような処理順序の中から順序づけ関数を最適化するものを決定することである. これを表示するのに図2のような[[離接グラフ]] (disjunctive graph) が利用される. この図の両方向の矢線の各々に対して一方向を選択しアサイクリックな[[接続グラフ]] (conjunctive graph) を作成すると, 実行可能な処理順序が得られる. 順序づけとは様々な付加的条件の下で, 離接グラフから最適な接続グラフを構成することである, ということもできる. 処理順序 (接続グラフ) を生成する効率的な手続きを[[順序付け規則]] (sequencing rule) と呼び, それが所与の順序づけ関数に関して最適な接続グラフを生成するとき, 最適であるという. 順序づけ規則やスケジューリング・アルゴリズムを構成する際に, [[合成ジョブ]] (composite job) と呼ばれる架空のジョブを導入することがある。

----
'''参考文献'''

[1] 秋庭雅夫編, 『生産管理』, 日本規格協会, 1980.

[2] K. R. Baker, ''Introduction to Sequencing and Scheduling,'' Wiley, New York, 1974.

[3] B. Giffler and G. L. Thompson, "Algorithms for Solving Production Scheduling Problems," ''Operations Research,'' '''8''' (1960), 487-503.

[[Category:スケジューリング|すけじゅーりんぐりろん]]

工程順序

2007-08-09T22:12:33Z

H.Yamaguchi: 新しいページ: ''''【こうていじゅんじょ (routing)】''' １つのジョブを構成する各作業を技術的順序に従って工程に割り付けたときに得られる工程...'

'''【こうていじゅんじょ (routing)】'''

１つのジョブを構成する各作業を技術的順序に従って工程に割り付けたときに得られる工程の順序をいう．

技術的順序

2007-08-09T22:11:04Z

H.Yamaguchi: 新しいページ: ''''【ぎじゅつてきじゅんじょ (technological ordering)】''' １つのジョブを構成する各作業の間に指定された実施順序をいう．製造技術...'

'''【ぎじゅつてきじゅんじょ (technological ordering)】'''

１つのジョブを構成する各作業の間に指定された実施順序をいう．製造技術的な制約に基づいて指定されることが多い．

用語編：和文項目一覧

2007-08-09T22:08:31Z

H.Yamaguchi: /* き */

= 和文項目一覧 =

== 0-9 ==
[[0-1整数計画]]　　　[[1機械問題]]　　　[[1次の最適性条件]]　　　[[2-3木]]　　　[[2のべき乗方策]]　　　[[2レベル計画問題]]　　　[[2回投票制]]　　　[[2項分布]]　　　[[2次の最適性十分条件]]　　　[[2次の最適性必要条件]]　　　[[2次割当問題]]　　　[[2次計画問題]]　　　[[2次錐計画]]　　　[[2重積形式]]　　　[[2色木]]　　　[[2人ゼロ和ゲーム]]　　　[[2人交渉問題]]　　　[[2段階計画問題]]　　　[[2部グラフ]]　　　[[3つ組み記法 (スケジューリング問題の)]]　　　[[3乗法則]]　　　[[3点見積法]]　　　[[5S (生産システムにおける)]]　　　[[5フォースモデル]]　　　[[8の字哨戒]]

== A-Z ==
[[ABC分析]]　　　[[AHP]]　　　[[AHP外部従属法]]　　　[[AHP順位逆転現象問題]]　　　[[AHP絶対評価法]]　　　[[AHP相対評価法]]　　　[[AHP多数代替案評価問題]]　　　[[AHP内部従属法]]　　　[[AHP不完全情報問題]]　　　[[ALM]]　　　[[ANP]]　　　[[APT]]　　　[[APV法]]　　　[[ARCHモデル]]　　　[[ARIMAモデル]]　　　[[ARIMAモデル]]　　　[[ARモデル]]　　　[[AVL木]]　　　[[BCCモデル]]　　　[[BCMPネットワーク]]　　　[[BIS規制]]　　　[[B-S公式]]　　　[[CALS]]　　　[[CAPM]]　　　[[CAPM]]　　　[[CCRモデル]]　　　[[CFA]]　　　[[CIM]]　　　[[CIミニマム法]]　　　[[CPM]]　　　[[CSCW]]　　　[[DBR]]　　　[[DC計画問題]]　　　[[DEA]]　　　[[DEA加法モデル]]　　　[[DEA乗法モデル]]　　　[[DFR]]　　　[[DFRA]]　　　[[DMU]]　　　[[DM分解]]　　　[[DSS]]　　　[[EDI]]　　　[[EOQ]]　　　[[ERP]]　　　[[FMEA]]　　　[[FMSスケジューリング]]　　　[[FTA]]　　　[[IDEF]]　　　[[IFR]]　　　[[IFRA]]　　　[[ISO9000シリーズ]]　　　[[JIT]]　　　[[JIT]]　　　[[JIT生産システム]]　　　[[k-d木]]（<math>k-d</math>木）　　[[k-opt法 (巡回セールスマン問題の)]] （<math>k</math>-opt法 (巡回セールスマン問題の)）　　　[[L凸関数]]　　　[[M&A]]　　　[[MAP]]　　　[[MAモデル]]　　　[[MIS]]　　　[[MM理論]]　　　[[MRP]]　　　[[MRP II]]　　　[[MTBF]]　　　[[MTTF]]　　　[[MTTR]]　　　[[MVA]]　　　[[M系列法]]　　　[[M凸関数]]　　　[[NBU]]　　　[[NP困難]]　　　[[NWU]]　　　[[ODの調査]]　　　[[OLAP]]　　　[[PASTA]]　　　[[PDPC]]　　　[[PERT]]　　　[[PERTネットワーク]]　　　[[PTAS]]　　　[[p-センター問題]] （<math>p</math>-センター問題）　　　[[p-メディアン問題]] （<math>p</math>-メディアン問題）　　　[[QCサークル]]　　　[[QCストーリー]]　　　[[QC七つ道具]]　　　[[QNA]]　　　[[RAS法]]　　　[[SCM]]　　　[[SIS]]　　　[[SQC]]　　　[[(s,S)方策]] （<math>(s,S)</math>方策）　　　[[TDI性]]　　　[[TOC]]　　　[[TQC]]　　　[[TQM]]　　　[[TSP多面体]]　　　[[U字型生産ライン]]　　　[[VaR]]　　　[[ε-近似アルゴリズム]] （<math>\epsilon</math>-近似アルゴリズム）　　　[[VR]]

== あ行 ==

=== あ ===
[[アーラン, アグナー・K]]　　　[[アーランの損失式]]　　　[[アーラン分布]]　　　[[アウトソーシング]]　　　[[赤黒木]]　　　[[アクティビティ (離散型シミュレーションの)]]　　　[[アクティビティネットワーク]]　　　[[アクティブ運用]]　　　[[アセットアロケーション]]　　　[[後工程引き取り後補充生産方式]]　　　[[穴あきバケツモデル]]　　　[[アニーリング法]]　　　[[アニメーション (シミュレーションにおける)]]　　　[[アノマリー]]　　　[[アフィン変換法]]　　　[[溢れ確率]]　　　[[アベイラビリティ]]　　　
[[アラバマパラドックス]]　　　[[アルゴリズム]]　　　[[アルゴリズム特許]]　　　[[アレンジメント]]　　　[[アローダイヤグラム]]　　　[[アロー・ドブローモデル]]　　　[[安定結婚問題]]　　　[[安定集合]]　　　[[安定性理論 (数理計画の)]]　　　[[鞍点定理]]

=== い ===
[[イールドカーブ]]　　　[[意思決定過程]]　　　[[意思決定支援]]　　　[[意思決定支援システム]]　　　[[意思決定主体]]　　　[[位相優先法]]　　　[[板取り問題]]　　　[[一様化]]　　　[[一様分布]]　　　[[一様並列機械問題]]　　　[[一様乱数]]　　　[[一対比較]]　　　[[一対比較 (投票理論における)]]　　　[[一対比較行列]]　　　[[一対比較評価 (AHPにおける)]]　　　[[一般化ジャクソンネットワーク]]　　　[[一般化セミマルコフ過程]]　　　[[一般化ニュートン法]]　　　[[一般化割当法 (運搬経路問題における)]]　　　[[一般化割当問題]]　　　[[一般距離ボロノイ図]]　　　[[一般政策 (逐次決定過程における)]]　　　[[遺伝アルゴリズム]]　　　[[伊藤過程]]　　　[[伊藤の補題]]　　　[[移動平均法]]　　　[[移動平均モデル]]　　　[[移動目標問題]]　　　[[医療政策]]　　　[[入れ子方策]]　　　[[因子分析]]　　　[[インバーテドDEA]]

=== う ===
[[ウィーナー, ノーバート]]　　　[[ウィーナー過程]]　　　[[ウィーナー・ホップの方程式]]　　　[[ウィルソンのEOQモデル]]　　　[[ウィンドー分析 (DEAの)]]　　　[[ウェーバー問題]]　　　[[ウォードロップの原理]]　　　[[売上効率性]]　　　[[運転資金管理]]　　　[[運搬経路問題]]　　　[[運搬車スケジューリング問題]]

=== え ===
[[影響力係数]]　　　[[エージェント理論]]　　　[[エージング]]　　　[[エキスパートシステム]]　　　[[エキゾチックオプション]]　　　[[エシェロンの在庫]]　　　[[枝]]　　　[[エドモンズ, ジャック]]　　　[[エネルギー経済モデル]]　　　[[エネルギー代替]]　　　[[エネルギーモデル]]　　　[[エラーバウンド (数理計画における)]]　　　[[エルゴード定理]]　　　[[エルゴード的マルコフ連鎖]]　　　[[エントロピーモデル]]

=== お ===
[[応答時間]]　　[[往復哨戒]]　　　[[オートポイエシス]]　　　[[大野耐一]]　　　[[オープンショップ問題]]　　　[[押し出し型システム]]　　　[[オブジェクト指向]]　　　[[オプション]]　　　[[オプションの役割]]　　　[[オペレーションズ・リサーチ]]　　　[[重み最小三角形分割]]　　　[[重み付けシナリオ法 (探索における)]]　　　[[オルンシュタイン・ウーレンベック過程]]　　　[[オンラインアルゴリズム]]

== か行 ==

=== か ===
[[カーネル (ゲーム理論における)]]　　　[[カープ, リチャード・M]]　　　[[カーマーカー, ナレンドラ]]　　　[[カーマーカー特許]]　　　[[カーマーカー法]]　　　

[[回帰分析]]　　　[[回収期間]]　　　[[階数関数]]　　　[[改善]]　　　[[回線交換網]]　　　[[回線留保]]　　　[[階層図 (AHPにおける)]]　　　[[解の計算 (ゲーム理論における)]]　　　[[開発リスク]]　　　[[回復技術]]　[[開放型ネットワーク]]　　[[開放型待ち行列ネットワーク]]　　　[[ガウス過程]]　　　[[ガウス・ザイデル法]]　　　[[価格]]　　　[[価格設定モデル]]　　　[[拡散過程]]　　　[[拡散近似]]　　　[[拡散方程式]]　　　[[拡散目標分布 (探索における)]]　　　[[学習 (ゲーム理論における)]]　　　[[拡張ラグランジュ関数]]　　　[[格付け (倒産リスクの)]]　　　[[確定的シミュレーション]]　　　[[確率アルゴリズム]]　　　[[確率解の価値]]　　　[[確率過程]]　　　[[確率過程のタイト性]]　　　[[確率関数]]　　　[[確率計画]]　　　[[確率ゲーム]]　　　[[確率最適化 (多段決定過程における)]]　　　[[確率順序]]　　　[[確率制約計画問題]]　　　[[確率積分]]　　　[[確率打点法]]　　　[[確率的安定均衡 (ゲーム理論の)]]　　　[[確率的経路選択]]　　　[[確率的シミュレーション]]　　　[[確率的進化 (ゲーム理論における)]]　　　[[確率的DEA法]]　　　[[確率的分解定理]]　　　[[確率動的計画]]　　　[[確率微分方程式]]　　　[[確率分布]]　　　[[確率分布の選択]]　　　[[確率密度関数]]　　　[[隠れマルコフ連鎖法]]　　　[[可視グラフ]]　　　[[加重平均資本コスト]]　　　[[過剰緩和法]]　　　[[ガス, サウル・I]]　　　[[仮想的出力 (DEAの)]]　　　[[仮想的入力 (DEAの)]]　　　[[仮想プレイ]]　　　[[価値関数]]　　　[[価値工学]]　　　[[活性スケジュール]]　　　[[カッティングストック問題]]　　　[[カット (数理計画における)]]　　　[[活動基準原価計算]]　　　[[活動作用因]]　　　[[活動分析]]　　　[[カップリング]]　　　[[合併効果分析]]　　　[[過程決定計画図]]　　　[[カテゴリーマネジメント理論]]　　　[[カバレッジファクター]]　　　[[株価変動モデル]]　　　[[ガブリエルグラフ]]　　　[[可変近傍法]]　　　[[加法型効用関数]]　　　[[カライ・スモルディンスキー解]]　　　[[カルーシュ・キューン・タッカー条件]]　　　[[カルマンフィルター]]　　　[[間接費]]　　　[[間接費管理]]　　　[[完全記憶ゲーム]]　　　[[完全均衡]]　　　[[完全グラフ]]　　　[[完全情報ゲーム]]　　　[[完全情報の期待価値]]　　　[[ガント, ヘンリー・L]]　　　[[ガントチャート]]　　　[[感度分析 (システム分析における)]]　　　[[感度分析 (数理計画の)]]　　　[[感応度係数]]　　　[[カンパニー制]]　　　[[かんばん方式]]　　　[[完備市場]]　　　[[完備情報ゲーム]]　　　[[管理図]]

=== き ===
[[木]]　　　[[機械修理工モデル]]　　　[[機会損失]]　　　[[幾何グラフ]]　　　[[幾何計画問題]]　　　[[幾何ブラウン運動]]　　[[幾何分布]]　　　[[幾何平均法 (AHPの)]]　　　[[期間構造]]　　　[[危機管理]]　　　[[企業価値評価]]　　　[[企業財務]]　　　[[企業戦略]]　　　[[企業モデル]]　　　[[危険施設配置問題]]　　　[[記号摂動]]　　　[[記号論理学]]　　　[[技術効率性]]　　　[[技術的順序]]　　　[[技術予測]]　　　[[基準生産計画]]　　　[[基数尺度]]　　　[[季節調整法]]　　　[[基族]]　　　[[期待値]]　　　[[期待値最適化 (多段決定過程における)]]　　　[[基多面体]]　　　[[基底解]]　　　[[機能価格分析]]　　　[[機能別管理]]　　　[[木の総容量]]　　　[[規模の効率性]]　　　[[規模の収穫]]　　　[[基本分割]]　　　[[既約]]　　　[[客]]　　　[[逆n乗発見法則]] （逆<math>n</math>乗発見法則）　　　[[逆過程]]　　　[[逆定理 (動的計画法における)]]　　　[[逆伝播学習アルゴリズム]]　　　[[逆伝播法]]　　　[[逆凸計画問題]]　　　[[客のクラス]]　　　[[キャリアディベロップメント]]　　　[[吸収的マルコフ連鎖]]　　　[[キューン, ハロルド・W / タッカー, アルバート・W]]　　　[[キューン・タッカー条件]]　　　[[狭義ナッシュ均衡]]　　　[[競争均衡]]　　　[[鏡像原理]]　　　[[共通マトロイド問題]]　　　[[共通乱数法]]　　　[[競売]]　　　[[共分散]]　　　[[強マルコフ性]]　　　[[共役関数]]　　　[[共役勾配法]]　　　[[共有知識]]　　　[[協力ゲーム]]　　　[[協力ゲーム理論]]　　　[[行列幾何形式解]]　　　[[行列ゲーム]]　　　[[行列分割法]]　　　[[極限定理 (ゲームのコアの)]]　　　[[極限分布]]　　　[[局所最適解]]　　　[[局所戦略]]　　　[[局所探索法]]　　　[[局所的最適解]]　　　[[局所点連結度]]　　　[[局所平衡方程式]]　　　[[局所辺連結度]]　　　[[極変換]]　　　[[虚探知]]　　　[[許容解]]　　　[[許容集合]]　　　[[距離対探知確率曲線]]　　　[[キングマン, ジョン・F・C]]　　　[[均衡制約計画問題]]　　　[[均衡問題 (ゲーム理論における)]]　　　[[近似アルゴリズム]]　　　[[近似アルゴリズム (スケジューリングの)]]　　　[[近接可能領域]]　　　[[近接点法]]　　　[[均等解]]　　　[[勤務スケジューリング]]　　　[[金融資産]]　　　[[金融派生証券]]　　　[[金利変動モデル]]　　[[QNA]]

=== く ===
[[区域探索]]　　　[[空間相互作用モデル]]　　　[[クープマン, ベルナード・O]]　　　[[クープマン問題]]　　　[[区間AHP]]　　　[[区間木]]　　　[[クヌース, ドナルド・E]]　　　[[組合せ最適化問題]]　　　[[組合せ的爆発]]　　　[[組立ラインのバランシング]]　　　[[クラーク・ライト法]]　　　[[クラインロックの保存則]]　　　[[クラスR]]　　　[[クラスNC]]　　　[[クラスカル法]]　　　[[クラスター分析]]　　　[[クラスMAX SNP]]　　　[[グラビティーモデル]]　　　[[グラフ (QC七つ道具の)]]　　　[[グラフ (グラフ理論の)]]　　　[[グラフ彩色問題]]　　　[[繰り返しゲーム]]　　　[[繰り返し法 (動的計画法における)]]　　　[[クリティカルパス]]　　　[[グループ意思決定]]　　　[[グループウエア]]　　　[[グループAHP]]　　　[[グループスケジューリング]]　　　[[クロス効率値]]　　　[[クロス縮約法]]　　　[[軍事モデル]]

=== け ===
[[経営意思決定]]　　　[[経営計画]]　　　[[経営計画モデル]]　　　[[経営財務]]　　　[[経営情報システム]]　　　[[経営の総合評価]]　　　[[経営評価指標]]　　　[[経営評価の多面性]]　　　[[経営分析]]　　　[[経営モデル]]　　　[[計画期間]]　　　[[計画評価]]　　　[[経済計算]]　　　[[経済性の比較原則]]　　　[[経済発注量公式]]　　　[[経済発注量モデル]]　　　[[経済予測]]　　　[[計算幾何学]]　　　[[計算の複雑さ]]　　　[[計算利率]]　　　[[系統図法]]　　　[[系内人数]]　　　[[軽負荷近似]]　　　[[計量経済モデル]]　　　[[経路選択確率]]　　　[[ゲームの値]]　　　[[ゲームの木]]　　　[[ゲーム理論]]　　　[[ゲーム理論の応用]]　　　[[結合ルール]]　　　[[結託]]　　　[[決定木]]　　　[[ケリーネットワーク]]　　　[[ゲリマンダー]]　　　[[原価企画]]　　　[[原価作用因]]　　　[[研究開発]]　　　[[研究開発課題選択]]　　　[[研究開発費管理]]　　　[[原始政策]]　　　[[限定合理性]]　　　[[ケンドール, デイビッド・G]]　　　[[ケンドールの記号]]　　　[[厳密計算法]]　　　

=== こ ===
[[コア]]　　　[[高階ボロノイ図]]　　　[[公共財供給ゲーム]]　　　[[公共施設配置問題]]　　　[[公共政策]]　　　[[交互オファーゲーム]]　　　[[広告]]　　　[[広告調査]]　　　[[交渉解]]　　　[[交渉ゲーム]]　　　[[交渉集合]]　　　[[工場立地問題]]　　　[[合成ジョブ]]　　　[[構造化モデリング]]　　　[[構造化問題]]　　　[[交代制]]　　　[[後着順サービス]]　　　[[交通政策]]　　　[[工程順序]]　　　[[行動戦略]]　　　[[勾配]]　　　[[購買行動モデル]]　　　[[勾配法]]　　　[[公比行列]]　　　[[公平性基準]]　　　[[効用]]　　　[[効用関数]]　　　[[効用関数と確率優越]]　　　[[効率的市場]]　　　[[効率的フロンティア (DEAの)]]　　　[[効率的フロンティア (ポートフォリオの)]]　　　[[コール]]　　　[[コーンレシオモデル]]　　　[[顧客満足]]　　　[[国際分散投資]]　　　[[故障データ解析]]　　　[[故障率]]　　　[[個人合理性]]　　　[[コスト効率性 (DEAにおける)]]　　　[[コスト分析]]　　　[[呼損率]]　　　[[コックス型分布]]　　　[[固定ロットサイズ]]　　　[[コヒーレントシステム]]　　　[[コペロウィッツのアルゴリズム]]　　　[[固有ベクトル法 (AHPの)]]　　　[[コルモゴロフの後退方程式]]　　　[[コルモゴロフの前進方程式]]　　　[[コンカレントエンジニアリング]]　　　[[混合型待ち行列ネットワーク]]　　　[[混合整数計画]]　　　[[混合戦略]]　　　[[混合品種組立ライン]]　　　[[混合品種順序付けアルゴリズム]]　　　[[混合品種の順序付け]]　　　[[混雑現象]]　　　[[コンベキシティー]]

== さ行 ==

=== さ ===
[[サーティ, トマス・L]]　　　[[サービス]]　　　[[サービス規律]]　　　[[サービス時間分布]]　　　[[サービスシステム]]　　　[[サービス品質]]　　　[[サービス率]]　　　[[最遠点対]]　　　[[再帰確率]]　　　[[再帰式 (動的計画法の)]]　　　[[最急降下法]]　　　[[最近近傍法]]　　　[[最近点対]]　　　[[最近傍グラフ]]　　　[[サイクリックスケジューリング (勤務体制の)]]　　　[[サイクリックスケジューリング (生産体制の)]]　　　[[債券価格]]　　　[[債券格付け]]　　　[[在庫運搬経路問題]]　　　[[最後通牒ゲーム]]　　　[[再呼モデル]]　　　[[在庫モデル]]　　　[[最終需要]]　　　[[最小木問題]]　　　[[最小コア (ゲーム理論の)]]　　　[[最小二乗法]]　　　[[最小シュタイナー木]]　　　[[最小全域木]]　　　[[最小費用フロー問題]]　　　[[最小包含円]]　　　[[再生過程]]　　　[[再生過程到着]]　　　[[再生定理]]　　　[[最大エントロピー法 (待ち行列の)]]　　　[[最大カット問題]]　　　[[最大空円]]　　　[[最大クリーク問題]]　　　[[最大剰余数法]]　　　[[最大除数法]]　　　[[最大フローアルゴリズム]]　　　[[最大フロー最小カット定理]]　　　[[最大マッチング最小被覆定理]]　　　[[最短サービス時間順規律]]　　　[[最短最長ルート問題]]　　　[[最短路問題]]　　　[[最適解]]　　　[[最適化問題]]　　　[[最適性条件 (非線形計画における)]]　　　[[最適性の原理]]　　　[[最適停止]]　　　[[最適反応 (ゲーム理論における)]]　　　[[裁判研究のOR]]　　　[[財務管理]]　　　[[財務諸表]]　　　[[財務諸表分析]]　　　[[サイモン, ハーバート・A]]　　　[[先物]]　　　[[作業時間の確率変動]]　　　[[先渡し]]　　　[[作用素分割法]]　　　[[三角形分割]]　　　[[三角速度分布]]　　　[[残業]]　　　[[産業連関分析]]　　　[[参照集合]]　　　[[散布図]]　　　[[サンプリング]]　　　[[三面鏡理論]]

=== し ===
[[視覚化]]　　　[[時間制御方式 (シミュレーションの)]]　　　[[時間枠付き運搬経路問題]]　　　[[時間割]]　　　[[事業価値]]　　　[[事業戦略]]　　　[[事業部業績評価]]　　　[[事業部制]]　　　[[資金運用]]　　　[[資金運用表]]　　　[[資金調達]]　　　[[資金の時間的価値]]　　　[[資金流列]]　　[[シグナル到着ネットワーク]]　[[時系列解析]]　　　[[資源管理モデル]]　　　[[資源作用因]]　　　[[資源制約]]　　　[[資源制約付きスケジューリング]]　　　[[資源ベースの観点]]　　　[[自己回帰移動平均モデル]]　　　[[自己回帰モデル]]　　　[[自己回帰和分移動平均モデル]]　　　[[事後条件付き決定過程]]　　　[[自己整合障壁関数]]　　　[[自己相関関数]]　　　[[自己組織化]]　　　[[仕事量保存型サービス]]　　　[[自己複製子動学]]　　　[[自己変換的障壁関数]]　　　[[事後目標分布]]　　　[[辞書 (線形計画における)]]　　　[[事象 (離散型シミュレーションの)]]　　　[[市場均衡モデル]]　　　[[市場ゲーム]]　　　[[市場構造分析]]　　　[[市場性の予測]]　　　[[市場の摩擦]]　　　[[市場反応分析]]　　　[[事象リスト (離散型シミュレーションの)]]　　　[[指数サービス]]　　　[[指数的爆発]]　　　[[指数分布]]　　　[[指数平滑法]]　　　[[システム構成 (信頼性の)]]　　　[[システムダイナミックス]]　　　[[システムの安全性]]　　　[[システムの信頼性設計]]　　　[[施設設備利用効率管理]]　　　[[施設配置ヒューリスティック (運搬経路問題の)]]　　　[[施設配置問題]]　　　[[事前条件付き決定過程]]　　　[[実験 (ゲーム理論における)]]　　　[[実行可能解]]　　　[[実行可能集合]]　　　[[実行可能性 (モデル記述言語の)]]　　　[[実行可能多面体]]　　　[[実施理論]]　　　[[自働化 (生産システムにおける)]]　　　[[シナジー]]　　　[[支配 (戦略の)]]　　　[[支配 (配分の)]]　　　[[支配戦略]]　　　[[シフティングボトルネック法]]　　　[[四分木]]　　　[[資本構成]]　　　[[資本コスト]]　　　[[資本図表]]　　　[[資本予算]]　　　[[資本利益図表]]　　　[[シミュレーション]]　　　[[シミュレーション言語]]　　　[[シミュレーション実験の計画]]　　　[[シミュレーション実験の統計的解析]]　　　[[シミュレーションソフトウェア]]　　　[[シミュレーションによる最適化]]　　　[[シミュレーションモデルの正当性の検証]]　　　[[シミュレーションモデルの妥当性の検証]]　　　[[シミュレータ]]　　　[[シミュレーテドアニーリング法]]　　　[[シャープレイ, ロイド・S]]　　　[[シャープレイ値]]　　　[[シャープレイのラベル法]]　　　[[射影変換]]　　　[[ジャクソン, ジェームス・R]]　　　[[ジャクソンネットワーク]]　 [[ジャクソン型待ち行列ネットワーク]]　　[[弱定常過程]]　　　[[ジャストインタイム]]　　　[[社内振替価格]]　　　[[集合カバー問題]]　　　[[集合被覆問題]]　　　[[自由処分性]]　　　[[囚人のジレンマ]]　　　[[重相関係数]]　　　[[充足可能性問題]]　　　[[収束率]]　　　[[集団意思決定]]　　　[[集団移動型ネットワーク]]　　　[[集団待ち行列]]　　　[[重点サンプリング]]　　　[[修理]]　　　[[重力モデル]]　　　[[主成分分析]]　　　[[主双対内点法]]　　　[[シュタイナー最小木]]　　　[[出生過程]]　　　[[出生死滅過程]]　　　[[出力指向型モデル]]　　　[[寿命検定]]　　　[[寿命試験]]　　　[[寿命推定]]　　　[[寿命分布]]　　　[[順位相関係数]]　　　[[巡回セールスマン問題]]　　　[[準可逆性]]　　　[[循環型待ち行列]]　　　[[循環フロー]]　　　[[順序尺度]]　　　[[順序付け]]　　　[[順序付け関数]]　　　[[順序付け規則]]　　　[[純戦略]]　　　[[準ニュートン法]]　　　[[準配分]]　　　[[準乱数とモンテカルロシミュレーション]]　　　[[省エネルギー]]　　　[[状況変異分析]]　　　[[証券化]]　　　[[証券市場モデル]]　　　[[商圏・立地モデル]]　　　[[乗算合同法]]　　　[[乗数形式モデル (DEAの)]]　　　[[少数の法則]]　　　[[乗数法 (数理計画の)]]　　　[[小選挙区制]]　　　[[状態空間]]　　　[[状態縮約/非縮約法]]　　　[[状態縮約法]]　　　[[状態劣化システム]]　　　[[冗長性]]　　　[[譲渡可能効用]]　　　[[消費者行動]]　　　[[消費者行動モデル]]　　　[[商品企画七つ道具]]　　　[[乗法型効用関数]]　　　[[情報集合]]　　　[[情報流動モデル]]　　　[[正味現在価値]]　　　[[乗務員スケジューリング問題]]　　　[[職住通勤モデル]]　　　[[職能資格制度]]　　　[[除数法]]　　　[[初到達時間]]　　　[[ジョブショップ]]　　　[[ジョブショップ問題]]　　　[[ジョフリオン, アーサー]]　　　[[ジョルダン代数]]　　　[[自律分散型生産システム]]　　　[[自律分散システム]]　　　[[仁]]　　　[[人員計画]]　　　[[進化ゲーム理論]]　　　[[進化的安定戦略]]　　　[[進化的計算]]　　　[[新QC七つ道具]]　　　[[人口移動モデル]]　　　[[人工現実感]]　　　[[人工生命]]　　　[[人工知能]]　　　[[新製品コンセプト開発]]　　　[[新製品予測モデル]]　　　[[人的資源管理]]　　　[[シンプレックス法]]　　　[[新聞売り子問題]]　　　[[信用評価]]　　　[[信頼性]]　　　[[信頼性試験]]　　　[[信頼度]]　　　[[信頼度配分]]　　　[[信頼領域法]]　　　[[親和図法]]　　　

=== す ===
[[推移]]　　　[[推移確率]]　　　[[推移確率行列]]　　　[[推移速度行列]]　　　[[推移率]]　　　[[酔歩]]　　　[[数理計画]]　　　[[数理計画問題]]　　　[[数量化法]]　　　[[スキーマ定理]]　　　[[スケジューリングアルゴリズム]]　　　[[スケジューリングソフトウェア]]　　　[[スケジューリング問題]]　　　[[スケジューリング理論]]　　　[[スケルトン]]　　　[[スタッフスケジューリング]]　　　[[スポーツのOR]]　　　[[スラック (DEAの)]]　　　[[スラック基準効率値]]　　　[[スラック変数]]　　　[[スラブ法]]　　　[[スループット]]　　　[[スワップ]]

=== せ ===
[[正規分布]]　　　[[制御可能変数]]　　　[[制御不能変数]]　　　[[制御変量法]]　　　[[整合性 (議員定数配分方法の)]]　　　[[整合度 (AHP一対比較の)]]　　　[[整合比 (AHPの)]]　　　[[政策反復アルゴリズム]]　　　[[政策評価]]　　　[[政策分析]]　　　[[生産可能集合]]　　　[[生産関数]]　　　[[生産管理]]　　　[[斉時性]]　　　[[静止目標問題]]　　　[[整数計画]]　　　[[整数計画アプローチ (スケジューリング問題の)]]　　　[[整数多面体]]　　　[[製造連]]　　　[[正則三角形分割]]　　　[[正則尺度]]　　　[[生態学モデル]]　　　[[製番管理]]　　　[[製品]]　　　[[製品企画開発]]　　　[[製品テスト]]　　　[[制約最適化問題]]　　　[[制約充足問題]]　　　[[制約想定]]　　　[[制約付き最適化]]　　　[[制約伝播]]　　　[[制約なし最適化]]　　　[[制約プログラミング]]　　　[[セービング法]]　　　[[積形式解]]　　　[[積形式ネットワーク]]　　　[[積分幾何学]]　　　[[積率母関数]]　　　[[セグメンテーション分析]]　　　[[切除平面法]]　　　[[接続グラフ]]　　　[[絶対偏差分析]]　　　[[節約法]]　　　[[セミマルコフ過程]]　　　[[セルラインシステム]]　　　[[ゼロ在庫発注方策]]　　　[[遷移]]　　　[[先願主義]]　　　[[選挙区割問題]]　　　[[漸近解析]]　　　[[線形行列不等式]]　　　[[線形計画]]　　　[[線形計画問題]]　　　[[線形合同法]]　　　[[線形生産ゲーム]]　　　[[線形相補性問題]]　　　[[先行関係]]　　　[[選好関係]]　　　[[センサー]]　　　[[センサーの探知論]]　　　[[センサス局法]]　　　[[全整数計画]]　　　[[戦争ゲーム]]　　　[[全双対整数性]]　　　[[センター問題]]　　　[[全体合理性]]　　　[[全体効率性]]　　　[[先着順サービス]]　　　[[セントラルサーバモデル]]　　　[[先発明主義]]　　　[[潜伏探索ゲーム]]　　　[[線分ボロノイ図]]　　　[[全ユニモジュラ性]]　　　[[戦略 (ゲーム理論における)]]　　　[[戦略意志]]　　　[[戦略形ゲーム]]　　　[[戦略的情報システム]]

=== そ ===
[[相型分布]]　　　[[相関均衡]]　　　[[相関係数]]　　　[[相関戦略]]　　　[[相関分析]]　　　[[双行列ゲーム]]　　　[[双線形行列不等式]]　　　[[双線形計画問題]]　　　[[相対近傍グラフ]]　　　[[双対性のギャップ]]　　　[[双対性理論]]　　　[[双対定理]]　　　[[双対変換]]　　　[[双対問題 (線形計画の)]]　　　[[相の方法]]　　　[[層別]]　　　[[相補性定理]]　　　[[相補性問題]]　　　[[ゾーン]]　　　[[ゾーン定理]]　　　[[組織学習]]　　　[[組織体]]　　　[[組織知能]]　　　[[ソフトウェア信頼性]]　　　[[ソフトウェア信頼性評価]]　　　[[ソフトウェア信頼度成長モデル]]　　　[[ソフトウェアテスト]]　　　[[ソフトウェア特許]]　　　[[ソフトコンピューティング]]　　　[[ソルバー]]　　　[[ソロー条件]]　　　[[損益分岐分析]]

== た行 ==

=== た ===
[[タージャン, ロバート・E]]　　　[[大域最適解]]　　　[[大域的最適化]]　　　[[大域的最適解]]　　　[[大域的収束性]]　　　[[大域平衡方程式]]　　　[[大規模問題の分解法]]　　　[[ダイクストラ法]]　　　[[滞在時間]]　　　[[対称型サービス規律]]　　　[[対数最小二乗法 (AHPの)]]　　　[[対数障壁関数]]　　　[[大数の法則]]　　　[[対数バリア関数]]　　　[[大選挙区制]]　　　[[ダイナマイゼーション]]　　　[[大偏差理論]]　　　[[タイムバケット]]　　　[[対話型解法 (多目的計画における)]]　　　[[対話管理]]　　　[[楕円体]]　　　[[楕円体法]]　　　[[タカーチ, ラジョス]]　　　[[タクシー乗り場モデル]]　　　[[多元トラヒック]]　　　[[多項式時間アルゴリズム]]　　　[[多項式時間解法]]　　　[[多次元尺度構成法]]　　　[[多次元正規分布]]　　　[[多次元分布]]　　　[[多重積分の解法]]　　　[[多重和の解法]]　　　[[多数決投票]]　　　[[多数決ルール]]　　　[[多スタート局所探索]]　　　[[たたみ込み]]　　　[[たたみ込み法]]　　　[[多段確率決定樹表]]　　　[[多能工]]　　　[[多品種フロー]]　　　[[タブー探索]]　　　[[タブロー (線形計画における)]]　　　[[多変量解析]]　　　[[ダムモデル]]　　　[[多面体理論]]　　　[[多目的計画]]　　　[[ダルメジ・メンデルゾーン分解]]　　　[[単一評価系 (多段決定過程における)]]　　　[[単一品種組立ライン]]　　　[[単位不変 (DEAにおける)]]　　　[[探索ゲーム]]　　　[[探索者]]　　　[[探索努力の最適配分]]　　　[[探索モデル]]　　　[[探索理論]]　　　[[単純施設配置問題]]　　　[[断続ポアソン過程]]　　　[[単体法]]　　　[[探知]]　　　[[探知探索]]　　　[[探知ポテンシャル]]　　　[[ダンツィク, ジョージ・B]]　　　[[ダンツィク・ウルフ分解法]]　　　[[単利]]　　　

=== ち ===
[[チェックシート]]　　　[[逐次均衡]]　　　[[逐次決定過程]]　　　[[逐次2次計画法]]　　　[[知識獲得]]　　　[[知識発見]]　　　[[知識表現]]　　　[[知識ベース]]　　　[[知的財産権]]　　　[[チャーンズ, エイブラハム / クーパー, ウィリアム・W]]　　　[[チャップマン・コルモゴロフの等式]]　　　[[中国郵便配達人問題]]　　　[[仲裁ゲーム]]　　　[[中心極限定理]]　　　[[中心パス]]　　　[[長期依存型入力過程]]　　　[[超行列]]　　　[[調査データの統計処理]]　　　[[超指数分布]]　　　[[調整ゲーム]]　　　[[直接法 (動的計画法における)]]　　　[[直線探索 (数理計画における)]]　　　[[直列型待ち行列]]　　　[[著作権]]　　　[[地理情報システム]]　　　[[地理的最適化]]　　　

=== つ ===
[[追証分析]]

=== て ===
[[定期発注方策]]　　　[[定距離発見法則]]　　　[[提携]]　　　[[提携形ゲーム]]　　　[[停止時]]　　　[[定常過程]]　　　[[定常状態]]　　　[[定常状態確率]]　　　[[定常分布]]　　　[[ディスパッチング規則]]　　　[[定性情報の解析法]]　　　[[定性推論]]　　　[[デイタム時刻]]　　　[[デイタム情報]]　　　[[デイタム探索]]　　　[[デイタム点]]　　　[[ディペンダビリティ]]　　　[[定和ゲーム]]　　　[[データウェアハウス]]　　　[[データ結合]]　　　[[データ構造]]　　　[[データ収集法]]　　　[[データの統計的解析]]　　　[[データの論理的解析]]　　　[[データベース]]　　　[[データベース管理]]　　　[[データマイニング]]　　　[[テクニカル分析]]　　　[[デミング賞]]　　　[[デュレーション]]　　　[[デリバティブ]]　　　[[デリバティブ評価モデル]]　　　[[デルタマトロイド]]　　　[[デルファイ法]]　　　[[点 (グラフの)]]　　　[[点位置決定]]　　　[[展開形ゲーム]]　　　[[点過程]]　　　[[点検]]　　　[[デンプスター・シェファーの証拠理論]]　　　[[点ボロノイ図]]　　　[[点連結度]]　　　

=== と ===
[[同一並列機械問題]]　　　[[投機]]　　　[[動径距離]]　　　[[同形性 (グラフの)]]　　　[[統合モデル (資産運用の)]]　　　[[倒産]]　　　[[倒産分析]]　　　[[投資案件の評価指標]]　　　[[同次自己双対内点法]]　　　[[等質自己双対錐]]　　　[[導出原理]]　　　[[同値マルチンゲール測度]]　　　[[到着]]　　　[[到着過程]]　　　[[到着定理]]　　　[[到着率]]　　　[[動的木]]　　　[[動的計画]]　　　[[動的増分係数]]　　　[[動的ボロノイ図]]　　　[[動的ロットサイズ決定問題]]　　　[[投入係数]]　　　[[逃避探索ゲーム]]　　　[[投票ゲーム]]　　　[[投票のパラドックス]]　　　[[投票方法]]　　　[[投票理論]]　　　[[特性関数 (ゲーム理論の)]]　　　[[特性関数 (確率変数の)]]　　　[[特性関数形ゲーム]]　　　[[特性要因図]]　　　[[独立案]]　　　[[独立集合族]]　　　[[独立性 (確率変数の)]]　　　[[独立増分過程]]　　　[[都市構造分析]]　　　[[凸解析]]　　　[[凸関数]]　　　[[特許]]　　　[[凸計画問題]]　　　[[凸ゲーム]]　　　[[凸集合]]　　　[[凸錐]]　　　[[凸多面体]]　　　[[凸包]]　　　[[ドミナント論理]]　　　[[トラック配送問題]]　　　[[トラヒック]]　　　[[トラフィック方程式]]　　　[[取替え]]　　　[[トレードオフ分析]]　　　[[ドロネー図]]　　　[[貪欲アルゴリズム]]　　　

== な行 ==

=== な ===
[[ナーススケジューリング]]　　　[[内点法]]　　　[[内部収益率]]　　　[[内部推移]]　　　[[内部投資収益率]]　　　[[ナッシュ, ジョン・F]]　　　[[ナッシュ解]]　　　[[ナッシュ均衡]]　　　[[ナッシュ交渉解]]　　　[[ナッシュプログラム]]　　　[[ナップサック問題]]　　　[[ナップザック問題]]

=== に ===
[[二者択一定理]]　　　[[日常管理]]　　　[[入札]]　　　[[入札ゲーム]]　　　[[ニューツ, マーセル・F]]　　　[[ニュートン法]]　　　[[ニューラルネットワーク]]　　　[[ニューラルネットワークによる学習]]　　　[[入力指向型モデル]]　　　[[入力密度]]　　　[[入力率]]　　　[[任意抽出定理]]　 [[2重積形式]]　　　　　

=== ぬ ===
[[抜取検査]]

=== ね ===
[[ネットワーク]]　　　[[ネットワーク構造 (ANPの)]]　　　[[ネットワーク状態分布の正規化定数]]　　　[[ネットワーク信頼性]]　　　[[ネットワークフロー問題]]

=== の ===
[[ノートンの定理]]

== は行 ==

=== は ===
[[バークの定理]]　　　[[バーチャルリアリティ]]　　　[[ハードシステム思考]]　　　[[パーフェクトグラフ]]　　　[[パーフェクトグラフ予想]]　　　[[バーロー, リチャード・E]]　　　[[配送計画問題]]　　　[[配送問題]]　　　[[配当政策]]　　　[[排反案]]　　　[[配分]]　　　[[配分効率性]]　　　[[暴露目標探知確率]]　　　[[バケーション]]　　　[[バケット]]　　　[[バケット法]]　　　[[破産の問題]]　　　[[バスモデル]]　　　[[派生資産]]　　　[[八分木]]　　　[[罰金関数法]]　　　[[発見的探索]]　　　[[発見法則]]　　　[[パッシブ運用]]　　　[[ハッシュ表]]　　　[[発想法]]　　　[[バッファ]]　　　[[ハフ変換]]　　　[[バラシュ, エゴン]]　　　[[ハリス・ウィルソンのモデル]]　　　[[ハリスのモデル]]　　　[[バリヤー哨戒]]　　　[[パルム分布]]　　　[[パレート最適]]　　　[[パレート最適解]]　　　[[パレート支配]]　　　[[パレート図]]　　　[[パワー指数]]　　　[[反射原理]]　　　[[半正定値計画]]　　　[[半正定値計画緩和]]　　　[[反転定理]]　　　[[反復最適化]]　　　[[反復尺度法]]　　　[[反復法]]　　　[[判別関数]]

=== ひ ===
[[非一様乱数]]　　　[[ヒープ]]　　　[[非可分性 (動的計画法における)]]　　　[[非協力ゲーム]]　　　[[非協力ゲーム理論]]　　　[[非許容初期点内点法]]　　　[[非構造化問題]]　　　[[非最適化]]　　　[[ビジネスゲーム]]　　　[[ビジネスプロセス]]　　　[[非集計行動モデル]]　　　[[美術館監視問題]]　　　[[ヒストグラム]]　　　[[非ゼロ和ゲーム]]　　　[[非線形計画]]　　　[[非線形計画問題]]　　　[[非線形相補性問題]]　　　[[非単調推論]]　　　[[ビッグバン]]　　　[[筆順最適化 (地図描画の)]]　　　[[引っ張り型システム]]　　　[[非凸計画問題]]　　　[[被覆 (グラフ理論における)]]　　　[[微分ゲーム]]　　　[[微分不可能最適化]]　　　[[ピボット]]　　　[[ヒューマンファクター]]　　　[[費用]]　　　[[病院管理]]　　　[[評価基準]]　　　[[標準形ゲーム]]　　　[[費用対効果分析]]　　　[[費用分担ゲーム]]　　　[[比率形式モデル]]　　　[[比例代表制]]　　　[[比例的効率性]]　　　[[品質管理]]　　　[[品質機能展開]]　　　[[品質システム審査登録制度]]　　　[[品質保証]]　　　[[品種切替組立ライン]]　　　[[ヒンチン, アレクサンダー・Y]]　　[[BCMPネットワーク]]

=== ふ ===
[[ファイナンシャルエンジニアリング]]　　　[[ファクターモデル]]　　　[[ファジィAHP]]　　　[[ファジィ最適化]]　　　[[ファジィ集合]]　　　[[ファジィ推論]]　　　[[ファジィ数]]　　　[[ファジィDEA]]　　　[[ファジィ動的計画]]　　　[[ファジィ理論]]　　　[[ファジィ論理]]　　　[[ファセット制約]]　　　[[ファットテイル分布]]　　　[[ファルカーソン, D・レイ]]　　　[[ファレルの効率尺度]]　　　[[フィボナッチヒープ]]　　　[[フェイルセーフ]]　　　[[フェンシェル型双対定理]]　　　[[フェンシェルの双対性]]　　　[[フォークジョイン待ち行列]]　　　[[フォーク定理]]　　　[[フォールトアボイダンス]]　　　[[フォールトデバッギング]]　　　[[フォールトトレランス]]　　　[[フォンノイマン, ジョン]]　　　[[フォンノイマン・モルゲンシュテルン解]]　　　[[フォンノイマン・モルゲンシュテルン効用関数]]　　　[[不確定性]]　　　[[不可能性定理]]　　　[[不感性]]　　　[[不完備情報ゲーム]]　　　[[複合評価系 (多段決定過程における)]]　　　[[複利]]　　　[[負相関変量法]]　　　[[負値乗加法型評価系]]　　　[[負値乗法型評価系]]　　　[[付値マトロイド]]　　　[[プッシュ方式]]　　　[[物資流動モデル]]　　　[[プット]]　　　[[物流]]　　　[[不動点アルゴリズム]]　　　[[負の客]]　　　[[部品表]]　　　[[部分ゲーム完全均衡]]　　　[[部分最適化]]　　　[[不偏性]]　　　[[不変埋没原理]]　　　[[ブラウン運動]]　　　[[ブラック, フィッシャー / ショールズ, マイロン・S]]　　　[[ブラック・ショールズ式]]　　　[[ブランドエクイティ理論]]　　　[[ブランド診断]]　　　[[フリーキャッシュフロー]]　　　[[プリム法]]　　　[[プル方式]]　　　[[プレイヤー]]　　　[[フレーム]]　　　[[ブレーンストーミング]]　　　[[フローショップ問題]]　　　[[フロート]]　　　[[プロジェクト管理]]　　　[[プロセッサシェアリング]]　　　[[プロダクション規則]]　　　[[プロダクションシステム]]　　　[[ブロックガウス・ザイデル法]]　　　[[プロビットモデル]]　　　[[プロモーション]]　　　[[プロモーション効果分析]]　　　[[分解近似法]]　　　[[分割アルゴリズム (スケジューリングの)]]　　　[[分岐限定法]]　　　[[分岐切除法]]　　　[[分権管理]]　　　[[分散]]　　　[[分散アルゴリズム]]　　　[[分散減少法]]　　　[[分枝カット法]]　　　[[分枝過程]]　　　[[分枝限定法]]　　　[[分枝限定法 (スケジューリングの)]]　　　[[分枝切除法]]　　　[[分社化]]　　　[[分数計画問題]]　　　[[分布関数]]　　　[[分布問題 (確率計画における)]]　　　[[分離問題]]

=== へ ===
[[ヘア投票]]　　　[[ペイオフ]]　　　[[平均]]　　　[[平均値解析法]]　　　[[平均分散モデル]]　　　[[平均待ち時間]]　　　[[平衡状態]]　　　[[平行探索]]　　　[[平衡分布]]　　　[[平衡方程式]]　[[閉鎖型ネットワーク]]　　[[閉鎖型待ち行列ネットワーク]]　　　[[ベイジアンゲーム]]　　　[[ベイジアンナッシュ均衡]]　　　[[平準化 (JIT生産システムにおける)]]　　　[[ベイズ信頼性]]　　　[[ベイズ信頼性実証試験]]　　　[[ベイズ推定]]　　　[[ベイズ統計]]　　　[[ベイズネットワーク]]　　　[[平面グラフ]]　　　[[並列アルゴリズム]]　　　[[並列アルゴリズム (数理計画問題の)]]　　　[[並列機械問題]]　　　[[並列シミュレーション]]　　　[[並列待ち行列]]　　　[[ページの近似式]]　　　[[ヘッジ]]　　　[[ヘッジファンド]]　　　[[ヘッセ行列]]　　　[[別払い]]　　　[[ペトリネット]]　　　[[ペナルティ関数法]]　　　[[ヘルスケア]]　　　[[ベルマン, リチャード]]　　　[[ベルマン・フォード法]]　　　[[辺]]　　　[[便益]]　　　[[ベンダース分解法]]　　　[[ベンチマーキング]]　　　[[変分不等式問題]]　　　[[辺分離定理]]　　　[[辺連結度]]　　　

=== ほ ===
[[ポアソン過程]]　　　[[ポアソン到着]]　　　[[ポアソン分布]]　　　[[ポアソンモデル (地域モデルとしての)]]　　　[[方位線による目標位置決め問題]]　　　[[方針管理]]　　　[[包摂アーキテクチャ]]　　　[[包絡面 (DEAの)]]　　　[[ホーキンス・サイモン条件]]　　　[[ポートフォリオ]]　　　[[ポーリングモデル]]　　　[[ホールの定理]]　　　[[ホーン節]]　　　[[保健ケア]]　　　[[ポジショニング分析]]　　　[[保証水準]]　　　[[捕食者/被食者モデル]]　　　[[補助変数法]]　　　[[保全性]]　　　[[保存則]]　　　[[ホップフィールドネットワーク]]　　　[[ポテンシャル関数 (内点法の)]]　　　[[ポラチェック・ヒンチンの公式]]　　　[[ポリマトロイド]]　　　[[ボロノイ図]]　　　[[本社費配賦]]　　　

== ま行 ==

=== ま ===
[[マーク付き点過程]]　　　[[マーケットシェアモデル]]　　　[[マーケティング]]　　　[[マーケティング情報]]　　　[[マーコビッツ, ハリー・M]]　　　[[待合室の容量]]　　　[[待ち確率]]　　　[[待ち行列]]　　　[[待ち行列長]]　　　[[待ち行列ネットワーク]]　　　[[待ち行列ネットワークの部分安定性]]　　　[[待ち行列の安定性]]　　　[[待ち行列のコンピュータへの応用]]　　　[[待ち行列の生産システムへの応用]]　　　[[待ち行列の通信への応用]]　　　[[待ち行列のバケーションサーバモデル]]　　　[[待ち行列網]]　　　[[待ち行列モデル]]　　　[[待ち行列モデル M/M/c]] （待ち行列モデル M/M/<math>c</math>）　　　[[待ち行列モデル M/M/c/c]] （待ち行列モデル M/M/<math>c</math>/<math>c</math>）　　　[[待ち行列モデル M/M/1]]　　　[[待ち行列モデル M/G/1]]　　　[[待ち行列モデル MAP/MAP/c]] （待ち行列モデル MAP/MAP/<math>c</math>）　　　[[待ち時間]]　　　[[待ち時間分布]]　　　[[待ち時間分布の裾]]　　　[[マックスマックス定理 (逐次過程における)]]　　　[[マックスミニ戦略]]　　　[[マックスミニ値]]　　　[[松田武彦]]　　　[[マッチング]]　　　[[マッチング (平面上の)]]　　　[[マッチングアルゴリズム]]　　　[[マッチング問題]]　　　[[窓口]]　　　[[窓口の数]]　　　[[マトリックス図法]]　　　[[マトリックスデータ解析法]]　　　[[マトロイド]]　　　[[マルコフ型到着過程]]　　　[[マルコフ過程]]　　　[[マルコフ決定過程]]　　　[[マルコフ性]]　　　[[マルコフ政策]]　　　[[マルコフ変調ポアソン過程]]　　　[[マルコフ両決定過程]]　　　[[マルコフ連鎖]]　　　[[マルコフ連鎖の数値解法]]　　　[[マルチンゲール]]　　　[[マルムクイストの指標]]　　　[[満足化]]　　　

=== み ===
[[ミーンリバージョン]]　　　[[ミックス効率性]]　　　[[密度関数]]　　　[[ミニマックス戦略]]　　　[[ミニマックス値]]　　　[[ミニマックス定理 (ゲーム理論における)]]　　　[[ミニマックス定理 (数理計画における)]]　　　

=== む ===
[[無関連並列機械問題]]　　　[[無記憶性 (指数分布の)]]　　　[[無限小生成作用素]]　　　[[無限窓口モデル]]　　　[[無向グラフ]]　　　

=== め ===
[[銘柄選択モデル]]　　　[[命題論理]]　　　[[メタヒューリスティクス]]　　　[[メディアン問題]]　　　

=== も ===
[[目的関数]]　　　[[目標計画]]　　　[[目標存在分布]]　　　[[目標追跡法 (ラインバランシングの)]]　　　[[目標物]]　　　[[目標分布]]　　　[[モデル]]　　　[[モデル型]]　　　[[モデル型調整法]]　　　[[モデル管理]]　　　[[モデル記述言語]]　　　[[モデル具体例]]　　　[[モデル合成]]　　　[[モデル/ソルバー独立]]　　　[[モデル/データ独立]]　　　[[モデル統合]]　　　[[モデルベース管理]]　　　[[モデルライフサイクル]]　　　[[問題解決]]　　　[[モンテカルロ法]]

== や行 ==

=== や ===
[[ヤコビ行列]]　　　[[矢線図]]　　　[[山崩し]]

=== ゆ ===
[[優越集合 (スケジュールの)]]　　　[[優加法性 (ゲーム理論における)]]　　　[[ユークリッド巡回セールスマン問題]]　　　[[有限呼源待ち行列]]　　　[[有限待合室モデル]]　　　[[有向グラフ]]　　　[[有効探索幅]]　　　[[有効探索率]]　　　[[有効探知距離]]　　　[[優先権]]　　　[[優先権待ち行列]]　　　[[郵便配達人問題]]　　　[[輸送経路問題]]　　　[[輸送問題]]

=== よ ===
[[要因関連図]]　　　[[容量制約付き施設配置問題]]　　　[[容量制約なし施設配置問題]]　　　[[欲張りアルゴリズム]]　　　[[欲張り法]]　　　[[横距離探知確率曲線]]　　　[[予算編成]]　　　[[予算編成モデル]]　　　[[予測]]　　　[[予測子修正子内点法]]

== ら行 ==

=== ら ===
[[ラインバランシング]]　　　[[ラインバランシングアルゴリズム]]　　　[[ラグランジュ関数]]　　　[[ラグランジュ緩和法]]　　　[[ラグランジュの双対性]]　　　[[ラゲール変換法]]　　　[[ラゲールボロノイ図]]　　　[[ラフセット]]　　　[[ラプラス変換]]　　　[[乱数]]　　　[[ランダマイゼーション]]　　　[[ランダムウォーク]]　　　[[ランダムウォーク仮説]]　　　[[ランダム順サービス]]　　　[[ランダム整合度 (AHPの)]]　　　[[ランダム探索 (探索理論における)]]　　　[[ランダム探索法 (最適化における)]]　　　[[ランチェスターの方程式]]　　　[[乱歩]]　　　

=== り ===
[[リー・ロントンの近似式]]　　　[[利益計画モデル]]　　　[[利益効率性]]　　　[[利益図表]]　　　[[リエンジニアリング]]　　　[[離散型シミュレーション]]　　　[[離散型シミュレーション言語]]　　　[[離散型分布]]　　　[[離散最適化問題]]　　　[[離散時間ロットスケジューリング]]　　　[[離散事象]]　　　[[離散凸解析]]　　　[[離散凸関数]]　　　[[離散分離定理]]　　　[[リスク管理]]　　　[[リスク指標]]　　　[[リストスケジューリング]]　　　[[離接グラフ]]　　　[[立体射影]]　　　[[率保存則]]　　　[[利得 (ゲームの)]]　　　[[利得関数]]　　　[[利得行列 (ゲームの)]]　　　[[利得双行列 (ゲームの)]]　　　[[リトル, ジョン・D・C]]　　　[[リトルの公式]]　　　[[流体近似]]　　　[[流通チャネル]]　　　[[領域木]]　　　[[領域限定法]]　　　[[領域探索]]　　　[[領域分割法]]　　　[[両帰式 (動的計画法における)]]　　　[[両的計画]]　　　[[利用率]]　　　[[リンドレーの方程式]]　　　

=== る ===

=== れ ===
[[レオンティエフ逆行列]]　　　[[列挙法]]　　　[[劣勾配]]　　　[[劣勾配法]]　　　[[劣モジュラ関数]]　　　[[劣モジュラ最適化]]　　　[[劣モジュラシステム]]　　　[[劣モジュラフロー問題]]　　　[[レバレッジ]]　　　[[レベル (計算幾何における)]]　　　[[連関図法]]　　　[[連結度 (グラフの)]]　　　[[連結度増大問題]]　　　[[連続型シミュレーション]]　　　[[連続型シミュレーション言語]]　　　[[連続型分布]]　　　[[連続最適化問題]]　　　[[連続時間ロットスケジューリング]]　

=== ろ ===
[[労働条件]]　　　[[ロジスティクス]]　　　[[ロジスティクスネットワーク設計問題]]　　　[[ロジスティックモデル]]　　　[[ロジットモデル]]　　　[[ロッカフェラー, R・ティレル]]　　　[[ロットスケジューリング]]　　　[[ロバース, ラスロー]]　　　[[ロバース数]]　　　[[ロバスト化技術]]　　　[[ロボティックセルスケジューリング]]　　　[[論理推論]]　　　[[論理プログラミング]]　

== わ行 ==

=== わ ===
[[ワークフロー]]　　　[[ワグナー・ウィッティンモデル]]　　　[[割当て市場ゲーム]]　　　[[割当問題]]　　　[[割引き]]　　　[[ワントゥワンマーケティング理論]]

《スケジューリング問題》

2007-08-09T22:05:30Z

H.Yamaguchi:

'''【すけじゅーりんぐもんだい (scheduling problem) 】'''

　[[スケジューリング問題]]は, 多くの仕事あるいは活動 (スケジューリング用語ではジョブ (job) という) を種々の制約のもとで実行しなければならないとき, 実行可能なスケジュールや, 最適なスケジュールを見出す問題である. 従って, 効率的な運用が求められるあらゆる組織においてスケジューリング問題が存在するが, 特に, 生産, 配送, プロジェクト, 要員勤務のスケジューリング問題に対しては理論および実務の両面において高い関心が持たれている [1, 8, 9, 10, 11]. ここではこれらの基本問題の1つである[[ジョブショップ問題]] (job shop problem) を中心に説明する（中項目「スケジューリング理論」参照）.

　多数のジョブが1台以上の機械の一部または全部によって予め指定された順序 (以下では工程順序という) に従って順次処理される. ただし, どのジョブも一時に高々1機械でしか処理されないし, どの機械も一時に高々1ジョブしか処理できない. また, 特に断りのない限り, 作業 (各機械におけるジョブの処理) は, いったん開始されると, 終了まで中断されることはない. このようなシステムはジョブショップと言われる.　ジョブショップにおいて所与の評価基準(目的関数)を最適にするよう, 各機械でのジョブ処理順序を見出す, すなわち, 順序づけの問題はジョブショップ問題（または機械順序づけ問題）と言われる.

　ジョブショップ問題は生産スケジューリング問題の典型的なモデルである [1, 8, 11]. また, 機械をボトルネックとなっている資源の代名詞と考えれば, ジョブショップ問題の適用範囲は極めて広い.

　ジョブショップ問題の仮定を一部変えることによって種々のモデルが考えられる. 代表的な例として, [[1機械問題]] (one-machine problem), [[並列機械問題]] (parallel-machine problem), [[フローショップ問題]] (flow shop problem), [[オープンショップ問題]] (open shop problem) などがある[1, 2, 9].

　1機械問題では, 全てのジョブがたった1台の機械で処理される場合に, ジョブの処理順序を決定する問題である.

　並列機械問題は, 2台以上の機械が存在し, 各ジョブはそれらのうちのいずれか1台で一度だけ処理されるとき, 各ジョブに対する機械の割当てと, 各機械に割当てられたジョブの処理順序を決定する問題である. 特に, 全機械が同一の場合を[[同一並列機械問題]] (identical parallel-machine problem), 機械によって処理速度が異なる場合を[[一様並列機械問題]] (uniform parallel-machine problem), ジョブと機械の組合せによって, 処理時間が異なる場合を[[無関連並列機械問題]] (unrelated parallel-machine problem) と言う.

　ジョブショップ問題において, 工程順序がどのジョブについても同じ場合を特にフローショップ問題という. また, ジョブの一部または全ての工程順序が任意であって, これも最適化の対象となる場合をオープンショップ問題という.

　以上のジョブショップモデルでは, 機械間のジョブ搬送や仕掛かり用バッファの有限性, ジョブ間の段取時間などが考慮されていず, 必ずしも現実を反映していない. その意味ではしばしば古典的モデル [4] と言われる. これをさらに拡張したモデルとして[[フレキシブルフローショップスケジューリング]]　(flexible flow shop scheduling) [11],　[[FMSスケジューリング]] (flexible manufacturing system scheduling) [10], [[ロボティックセルスケジューリング]] (robotic cell scheduling) [5], [[資源制約付きスケジューリング]] (scheduling under resource constraints) [1], [[グループスケジューリング]] (group scheduling) [6] などがしばしば検討されている. フレキシブルフローショップにおいてはフローショップを構成する工程の一部または全てが並列化されている．FMSは, 1台で多種加工が可能なマシニングセンタやAGV (automated guided vehicle), ロボット, AS/RS(automated storage/retrieval system)などの自動物流機器で構成されている. 特に, 1台のロボットと少数のマシニングセンタからなる小規模のFMSはロボティックセル (またはFMC) と言われる. これらのシステムでは加工スケジューリングのみならず, 搬送などの物流のスケジューリングがシステム全体の効率化に大きな影響を及ぼす. ジョブショップにおいて機械以外にボトルネックとなる資源(工作機械の治工具, 計算機のメモリなど) が存在し, それらのスケジューリングも考慮されなければならない場合は資源制約付きスケジューリング問題と言われる. ジョブ間に段取時間が存在するとき, GT (group technology) に基づいて, 段取時間が比較的小さいジョブをグループにまとめ, グループ間で行う順序づけをグループスケジューリングと言う. ジョブショップ問題 (及びその拡張問題) では, ジョブまたは作業に種々の制約が課せられることが多い. 典型的な制約条件として処理順序に関するジョブ間の先行制約, 最早開始時刻または準備時間の制約などがある.
　最適化 (ここでは最小化) すべき目的関数の代表例として, 全ジョブの終了時間を表す最大完了時間 (メークスパン (makespan) と言うことがある), ジョブがシステムに滞留した時間の総和を表す滞留時間和, 納期からの遅れの指標となる最大納期遅れや遅れ和が挙げられる[1, 2, 3, 8, 9, 10]．さらに複数の目的関数を考慮した多目的スケジューリング問題もある[1, 8, 11]．

　以上に述べてきたように, ジョブショップ問題は, ショップ (工程) の構成, ジョブ処理環境及び目的関数によって分類されるので, これらを (待ち行列におけるケンドール (Kendall) 記号風の) [[3つ組み記法 (スケジューリング問題の)|3つ組み記法]] (<math>\alpha |\beta |\gamma\, </math>) によって記述することができる [2, 9]. すなわち, <math>\alpha\, </math>は工程, <math>\beta\, </math>はジョブ処理環境, <math>\gamma\, </math>は目的関数である.

　表1にそれぞれの項目における記号例とその表示意味を示す．
<math>\alpha |\beta |\gamma\, </math>による問題表規の例である.

<div align="center">
表 1: 3つ組み記法によるジョブショップ問題の分類
<table width="620" border="0" cellspacing="2" cellpadding="0">
<tr>
<td align="center" valign="top">
<table width="300" border="1" cellspacing="2" cellpadding="0">
<tr>
<td align="center">項目</td>
<td align="center">表示</td>
<td>意味</td>
</tr>
<tr>
<td rowspan="7" align="center" valign="top"><math>\alpha\, </math></td>
<td align="center"><math>1\, </math></td>
<td align="left">1機械</td>
</tr>
<tr>
<td align="center"><math>P\, </math></td>
<td align="left">同一並列機械</td>
</tr>
<tr>
<td align="center"><math>Q\, </math></td>
<td align="left">一様並列機械</td>
</tr>
<tr>
<td align="center"><math>R\, </math></td>
<td align="left">無関連並列機械</td>
</tr>
<tr>
<td align="center"><math>F\, </math></td>
<td align="left">フローショップ</td>
</tr>
<tr>
<td align="center"><math>O\, </math></td>
<td align="left">オープンショップ</td>
</tr>
<tr>
<td align="center"><math>J\, </math></td>
<td align="left">ジョブショップ</td>
</tr>
</table>
</td>
<td align="center" valign="top">
<table width="300" border="1" cellspacing="2" cellpadding="0">
<tr>
<td align="center">項目</td>
<td align="center">表示</td>
<td>意味</td>
</tr>
<tr>
<td rowspan="2" align="center" valign="top"><math>\beta\, </math></td>
<td align="center"><math>prec\, </math></td>
<td align="left">先行制約</td>
</tr>
<tr>
<td align="center"><math>r_j\, </math></td>
<td align="left">準備時間制約</td>
</tr>
<tr>
<td rowspan="4" valign="top" align="center"><math>\gamma\, </math></td>
<td align="center"><math>C_{max}\, </math></td>
<td align="left">最大完了時間</td>
</tr>
<tr>
<td align="center"><math>\Sigma c_j\, </math></td>
<td align="left">滞留時間和</td>
</tr>
<tr>
<td align="center"><math>T_{max}\, </math></td>
<td align="left">最大納期遅れ</td>
</tr>
<tr>
<td align="center"><math>\Sigma T_j\, </math></td>
<td align="left">納期遅れ和</td>
</tr>
</table>
</td>
</tr>
</table>
<p></p>
</div>

　ジョブショップ問題の理論的研究の起源は1954年のジョンソン (S.M.Johnson) の定理 [7] にまで遡る.

　'''ジョンソンの定理''': 2機械フローショップにおいて<math>A_j\, </math>, <math>B_j\, </math>をそれぞれ第1機械及び第2機械におけるジョブ<math>j(=1,2,\cdots,n)\, </math>の処理時間とする. このとき, 最大完了時間最小化問題(<math>F2 || C_{max}\, </math>)の最適順序はつぎの[[順序付け規則]]で与えられる. すなわち,

<center>
<math>\max (A_j,B_{j+1}) < \max (A_{j+1},B_j)\, </math>
</center>

　ならば, ジョブ<math>j\, </math>をジョブ(<math>j+1\, </math>)より先に処理する. 等号の場合は, どちらが先でもよい.

　これ以後この様な最適な順序づけ規則の研究が進められたが, 1970年代初期のNP完全理論の誕生と共に, 多くのスケジューリング問題が（問題規模の多項式オーダーの計算量で解くことが保障されない）[[NP困難]]になることが証明された [2]. 例えば, <math>1 || \Sigma c_j\, </math>, <math>1 || T_{max}\, \, </math>, <math>P || \Sigma c_j, J2 || c_{max}\, </math> (J2は2機械ジョブショップを表す)などは最適順序づけ規則が存在するが, <math>1 | r_j | T_{max}\, </math>, <math>1 | prec | \Sigma c_j\, </math>, <math>p1 || c_{max}, F2 || \Sigma c_j\, </math>はNP困難となる.

　しかし, NP困難問題だからといって, 必ずしも手に負えないという訳ではない. 工夫された[[分枝限定法]]などを用いることによって (希な最悪例を除いて) かなり大きな問題例まで解くことが可能である (例えば, [3] 参照). ただし, 実際上のスケジューリング問題に対しては効率的な近似解放が必要である（中項目「スケジューリングアルゴリズム参照）.

----
'''参考文献'''

[1] J. Blazewicz, W. Cellary, K. Slowinski, J. Weglarz, ''Scheduling under Resource Constraints : Deterministic Model,'' J. C. Balzer, Basel, 1986.

[2] P. Brucker, ''Scheduling Algorithms,'' Springer, 1995.

[3] J. Cheng, H. Kise, G.Steiner and P. Stephenson, ''Branch-and-bound algorithm using fuzzy heuristics ofr solbing large-scale flow-shop scheduling problems, '' Fuzzy Set Based Heuristics for Optimization (J-L. Verdega Ed.),Springer (2003), 21-47.

[[4] R. W. Conway, W. L. Maxwell, and L. W. Miller, ''Theory of Scheduling,'' Addison-Weseley Reading, 1967. 関根智明監訳, 『スケジューリングの理論』, 日刊工業新聞社, 1971.

[5] M. Dawande, M.N, Geismar, S.P. Sethi and C. Sriskandarajah, "Sequencing and Scheduling in Robotic Cells：Recent Developments" Journal of Scheduling. 8(2005), 1099-1423.

[6] 人見勝人, 中島勝, 吉田照彦, 小島敏彦,『GTによる生産管理システム』, 日刊工業新聞社, 1981.

[7] S. M. Johnson, "Optimal Two and Three Stage Production Schedules with Setup Times Included," ''Naual Research Logistics Quartry,'' '''1''' (1954), 61-68.

[8] 木瀬洋,「生産スケジューリングの現状と動向」,『システム/制御/情報』, '''41''' (1997), 92-99.

[9] 木瀬洋,「道しるべ：ジョブショップスケジューリング問題」,『情報処理』, 39 (1998), 1150-1153.

[10] N. Raman, K. Stecke and E. Rachamadugu, "Forcused Review of FMS Scheduling Research," 『計測と制御』, '''33''' (1994), 680-689.

[11] M.L. Pinedo, Planning and Scheduling in Manufacturing and Services, Springer, 2000.

[[Category:スケジューリング|すけじゅーりんぐもんだい]]

《スケジューリングアルゴリズム》

2007-08-09T21:31:00Z

H.Yamaguchi:

【すけじゅーりんぐあるごりずむ (scheduling algorithm) 】

　[[スケジューリングアルゴリズム]] (scheduling algorithm) はスケジューリング問題 (中項目スケジューリング問題参照) を解く, すなわちスケジュールを作成するための方法・手続きであり, 問題の特性により様々なものが提案されている [1]-[6]. アルゴリズムは所与の評価値に対して最適なスケジュールを求める最適化法と最適とは限らないができる
だけ良いスケジュールを求める方法に大別できる.

　最適解を求める解析的方法には簡単な一機械総滞留時間最小化問題における処理時間順 (SPT) 規則の適用や, 2機械フローショップ問題に対するジョンソン (J.H.Johnson) の方法, その拡張である2機械ジョブショップ問題に対するジャクソン(J.R.Jackson)の方法などがある [1, 4]. より複雑な問題に対しては[[整数計画アプローチ (スケジューリング問題の)|整数計画アプローチ]] (integer programming approach) [2], [[分枝限定法]] (branch and bound method) [1, 6, 7] などがあるが, 問題の規模が大きくなると最適解を求めることが困難になり, 良い解で満足せざるを得なくなることが多い. 分枝限定法は分枝操作における分枝先の探索法や, 限定操作等のために利用する上 (下) 界値の推定値の精度によって求解効率は大きく影響される. このため問題に応じた探索方法, 推定法の考案など個別的対応が必要である. 早い時点で得られた暫定解の最適性の証明に (長い) 計算時間のほとんどを費やすことが多く, 許容可能な時間で探索を打ち切り, その時点での暫定解を実行解とすることも考えられる.

　様々な[[ディスパッチング規則]] (dispatching rule) [4, 8] を単独あるいは組み合わせて適用する方法はスケジューリングに広く用いられている. さらに, 直感的経験的なディスパッチング規則に加えて, 部分的に最適化を図るなどして, できるだけ最適解に近いスケジュールを探索する方法がいろいろ提案されている．例えば, ラグランジュ分解調整法 [17], [[リストスケジューリング]] (list scheduling) [3, 5], [[分割アルゴリズム (スケジューリングの)|分割アルゴリズム]] (decomposition algorithm) [9], ジョブショップスケジューリング問題に対する[[シフティングボトルネック法]]　(shifting bottleneck procedure) [10] 等がある. これらは発見的方法あるいはヒューリスティクス(heuristics)と呼ばれている [5].

　また, 熟練したスケジューリング担当者の専門的な知識を利用する人工知能 (artificial intelligence) を用いたスケジューリング・エキスパートシステム (expert system) の開発も活発に行われ, 実用に供されている [4, 11]. スケジューリング知識の獲得や更新の難しさもあり, その効率化を目指した知識獲得法や事例ベースの構築に関する研究などが進められている [11, 16]. 最近は計算機性能の向上とともにメタヒューリスティクス (meta-heuristics) と呼ばれる方法の研究が活発である [12]. これはスケジューリングに限らず幅広い組合せ最適化問題の解法として発展したものであり, シミュレーテッドアニーリング(simulated annealing), タブー探索 (tabusearch), 遺伝アルゴリズム (genetic algorithm), ニューラルネットワーク (neural network) などがある.

　[[近似アルゴリズム (スケジューリングの)|近似アルゴリズム]] (approximation algorithm) とは広義には, 上述のような必ずしも最適解を与えるとは限らないアルゴリズム全般を指すが、アルゴリズムの理論的研究においては、解の精度が解析的に求められているものだけを特に指すことがある [3].
　実務面ではこれらのアルゴリズムを組み込んだ生産[[スケジューリングソフトウェア]] (scheduling software) が多数開発されており, 実用に供されている [4, 14, 15]. また, スケジュール作成作業や修正を支援する対話型スケジューリングソフトウェアも実務的な効率化の一つの方向である. シミュレーション (simulation) はスケジュールの評価だけでなくスケジュールの作成にも広く用いられており, バックワード／フォワード・ハイブリッドシミュレーション法など様々な方法が提案されている [4, 13, 15].

----
'''参考文献'''

[1] コーンウエイ他著, 関根智明訳,『スケジューリングの理論』, 日刊工業新聞社, 1971.

[2] 鍋島一郎,『スケジューリング理論』, 森北出版, 1974.

[3] P.Chretienne, E.G.Coffman, Jr., J.K.Lenstra and Z.Liu, Eds.,''Scheduling Theory and its Applications'', John Wiley and Sons, 1995.

[4] 田中克己, 石井信明,『スケジューリングとシミュレーション』, 計測自動制御学会, 1995.

[5] J.Blazewicz, K.Ecker, E.Pesch, G.Schmidt and J.Weglarz, ''Scheduling in Computer and Manufacturing Processes'', Springer, 1996.

[6] P. Brucker, ''Scheduling Algorithms'', Second revised and Enlarged Edition, Springer, 1998.

[7] 茨木俊秀,『組み合わせ最適化 : 分枝限定法を中心として』, 産業図書、1983.

[8] T.E. Morton and D.W. Pentico, ''Heuristic Scheduling Systems'', John Wiley & Sons, Inc., 1993.

[9] C.N.Potts and L.N. van Wassenhove, "Dynamic Programming and Decomposition Approaches for the Single Machine Total Tardiness Problem," ''European Journal of Operational Research'', '''32''' (1987), 405-414.

[10] J.Adams, E. Balas and D. Zawack, "The Shifting Bottlerneck Procedure for Job Shop Scheduling," ''Management Science'', '''34''' (1988), 391-401.

[11] 特集：生産スケジューリング, 『計測と制御』, '''33''' (1994), 531-599.

[12] ミニ特集：組合せ最適化とスケジューリング問題への新接近, 『計測と制御』, '''34''' (1995), 339-375.

[13] 冬木正彦, 井上一郎, 「バックワード/フォワード・ハイブリッドシミュレーション法に基づく個別受注生産における納期重視型生産スケジューリング」,『日本経営工学会誌』, '''46''' (1995), 144-151.

[14] 安田一彦, 「生産スケジューリングソフトウェアの現状」, 『生産スケジューリング・シンポジウム'95講演論文集』, 31-36, 1995.

[15] 中野一夫,「スケジューリングにおけるシミュレーション技術とソフトウェア」,『システム/制御/情報』, '''41''' (1997), 106-111.

[16] 諏訪晴彦, 森田浩, 藤井進,「帰納的学習法によるスケジューリング・ルールの自動獲得とルールに基づく近傍探索スケジューリング-ジョブショップ総所要時間最小化問題への適用-」,『システム制御情報学会論文誌』, '''12''' (1999), 152-160.

[17] 特集　スケジューリングの革新的アルゴリズム‐ラグランジュ分解調整法‐, 『オペレーションズ・リサーチ』, 45, (2000), 256-286.

[[Category:スケジューリング|すけじゅーりんぐあるごりずむ]]

ソフトウェア特許

2007-08-09T21:23:11Z

H.Yamaguchi:

'''【そふとうぇあとっきょ (software patent)】'''

わが国では1986年以来, 著作権法によってソフトウェアを保護することになってきた. しかし著作権法は, 工業製品であるソフトウェアの保護には馴染まない性格をもつものであったため, 産業界にはソフトウェアに含まれる``アイディア``の特許法による保護を求める声が根強く存在した. このような要望に応えて, 特許庁は80年代後半以降, なし崩し的にソフトウェア特許を成立させてきたが, 96年以来より積極的にこれを認める方向に動き出している.

《アルゴリズム特許》

2007-08-09T21:15:04Z

H.Yamaguchi:

'''【あるごりずむとっきょ (algorithm patent) 】'''

　ソフトウェアとアルゴリズムの権利保護については, 古くから米国を中心に様々な議論が行われてきた.

　まずソフトウェア産業の黎明期にあたる1960年代には, IBMなどのコンピュータ・メーカーは, [[特許]] (patent)によるソフトウェアの保護を主張した. しかし, 二進化十進数を二進数に変換するプログラムに関して争われた, 「ゴッチューク対ベンソン判決」(1971年), ある種の化学プロセスの終了を判定するソフトウェアに関して争われた, 「パーカー対フルック判決」(1978年)において, 最高裁がソフトウェアの特許による保護を繰り返し拒絶したため, 米国政府は, 1980年に著作権法を改正し, [[著作権]] (copyright)によってソフトウェアを保護することを決定した.

　著作権法は, 本来文芸作品などに対して適用される法律で, 作品の表現は保護するが, その中に含まれるアイディア自体は保護しないのが特徴である. このため, リバース・エンジニアリングによってプログラムを解読し, それと本質的に同一のプログラムを作成・販売しても, 著作権の侵害となならない. ソフトウェア産業界が, アイディアの保護を求めるため, 特許法による権利保護を主張した原因はここにある.

　このように, 矛盾を抱えながらも著作権法による保護を決めた米国であったが, 著作権改訂の翌年に当たる1981年, 最高裁は「ダイヤモンド対ディーア判決」で, [[ソフトウェア特許]](software patent)への道を開いた. 最高裁はこの判決の中で, 数学公式もしくはアルゴリズムを自然法則のようなものと規定し, それ自体は特許対象とはしないが, それと同時に申請が単なる数学公式ではなく, 全体として産業プロセスの保護を求めている場合は状況は異なるとし, 当該申請は特許付与することを支持したのである.

　この判決以後, 米国ではソフトウェア特許が次々と成立した. その審査に当たっては, ソフトウェアの中に数学的アルゴリズムが含まれなければ特許適格, 数学的アルゴリズムが含まれているときは, 全体を見て判断するという「二段階審査」が用いられることになった.

　しかし, 数学的アルゴリズムと非数学的アリゴリズムの線引きをめぐって事態は紛糾し, 以後10年以上にわたる混乱を招くこととなった. この過程で成立したのが, AT&T-カーマーカーの線形計画法特許である. ここでAT&Tは, カーマーカーが発明した2つのアルゴリズム, すなわち射影変換法とアフィン変換法を特許申請し, 1988年に極めて適用範囲の広い[[アルゴリズム特許]]が成立することとなったのである.

　一方わが国では, 1970年代以来, ソフトウェアは著作権と特許法の中間に位置するプログラム権法を作成し, これによって権利保護を行うべきであるという議論が主流を占めていた. それは, ソフトウェアが特許法に規定する「発明」, すなわち「自然法則を利用した技術思想」とは考えにくいこと, またその一方で, 現行の著作権法は保護期間が長すぎる(60年間)ことなど, 工業製品であるソフトウェアの保護には適さないと考えられたためである. ところが, プログラム権法構想は, 米国の反対の下で潰え去り, わが国も著作権法を改定してソフトウェア保護を行うことが決まった. 1986年のことである.

　しかし, このころ既に米国は, ソフトウェアの特許による保護を推進していた. こうして, ソフトウェアは表現部分を著作権法で, アイディア部分(アルゴリズムを含む)を特許法で保護するという, ややこしい状況が生まれたのである.

　この結果, わが国にも米国と同じ混乱が持ち込まれることになった. 即ちソフトウェアは自然法則を利用した技術思想といえるか, 数学的アルゴリズムと非数学アリゴリズムの線引きはどのように行うか, などがそれである.

　この過程でわが国でも, 1991年には一旦 "単なる数学アルゴリズム" として拒絶されたカーマーカー特許が, 1993年に逆転公告され, 異議申立てを経て1995年に成立することとなった. これに対して1996年に無効審判請求が行われたが, 1998年12月にこれが却下され, アフィン変換法特許が最終的に成立した. これを受けて今野らは, 1999年3月東京高等裁判所に対して特許取り消し請求を行った.（この訴えは2002年3月に却下された）

　その争点は, (1)発明の新規性(ディキン法との類似性), (2)技術の開示の不十分性(超大型連立一次方程式の解法など), (3)適用範囲が広範すぎること, (4)数学アルゴリズムへの特許付与の是非などであるが, 詳細は文献 [1, 2]を参照して頂きたい.

　このように, わが国でも1980年代後半以来ソフトウェア特許は混乱の中にあったが, 1996年に特許庁が審査規準を大幅に改定したことによって, 混乱は納まりつつある. この改訂で特許庁は, 自然法則の利用については, ソフトウェアがコンピュータ利用を前提としており, コンピュータが自然法則の下で動いているという事実によって, ソフトウェアも自然法則を利用しているものと判断し, 長年の論争に決着を付けた. また数学的アルゴリズムも, それ自体は特許とはしないものの, それをインプリメントとしたプログラムは特許対象とするという解釈を行い, 事実上, 数学的アルゴリズムも特許対象とする方針を打ち出したのである. しかし, これらはあくまでも行政府である特許庁の法律解釈に過ぎないものであり, 法理論的にみて妥当か否かについては見解は分かれるであろう.

　歴史を振返れば, ソフトウェア特許は, 著作権法による保護が十分でないため違法コピーが横行し, 開発資金を十分に回収できないことに苛立った産業界の要請を受けて成立したものである. これに, 1980年代のレーガン政権以来の, 強いアメリカを目指す[[知的財産権]](intellectual properties right)戦略が重なり, いまではソフトウェア特許, (数学)アルゴリズム特許は当たり前のこととして受け入れられるようになった, と(法律関係者は)言う.

　果たして, ソフトウェア特許は, ソフトウェア産業やソフトウェア技術の発展に役立つ制度なのか. また現在のような, (数学アルゴリズムを含めて)何でも特許という状況が学問の進歩にとって望ましいものかどうか. これらについて, アルゴリズム特許と最も密接に関係しているオペレーションズ・リサーチ学会や, 応用数理学会で詳しい検討を行うことが求められているが, 結論が出るまでにまだかなりの時間が掛かるであろう.

　以上の文章を書いてから６年後の2006年現在，ソフトウェア特許を巡る状況は大きな転換点を迎えている．ソフトウェア関係者の間で，無数のソフトウェア特許が作り出す特許の藪がイノベーションを阻害しているという認識が高まる一方で，オープン・ソフト陣営が勢力を拡大する中，2004年に米国産業競争委員会が発表した「バルミサーノ・レポート」が，イノベーションを実現するためには，権利の囲い込みよりコラボレーションが重要であることを強調したからである．

　この結果わが国政府は，2005年以降ソフトウェア特許の審査を厳しくする一方で，権利の乱用に関する監視体制を強める方向に動き出している．また産業界でも特許の無料公開やプール制度などが広がりを見せており，ソフトウェア特許には逆風が強まっている．

----

'''参考文献'''

[1] 今野浩, 『特許ビジネスはどこへゆくのか』, 岩波書店, 2002.

[2] 今野浩, 中川淳司編著, 『ソフトウェア／アルゴリズムの権利保護』, 朝倉書店, 1996.

[[category:システム分析・意思決定支援・特許|あるごりずむとっきょ]]

《効用関数》

2007-08-09T20:53:03Z

H.Yamaguchi:

'''【こうようかんすう (utility function)】'''

　自然科学の領域で「価値」が陽に議論されることは少ないが, 人間を主体にした方策を論じるオペレーションズ・リサーチの分野では「価値」の問題を避けて通ることはできない.

　効用関数とは, 一言でいえば人間の価値観を定量的に表現するための数学モデルである. 価値に関する科学的アプローチは経済学の分野で古くから扱われてきた. 人びとは財を消費したりサービス受けることによって一定の心理的満足感を得るが, この満足の度合いを効用という. この概念は消費者行動理論において基本的役割を担う [1].

　いま, 財Aを <math>x_1\, </math> 量, 財Bを <math>x_2\, </math> 量だけ消費するときに得られる効用(または価値)を <math>u(x_1,x_2)\, </math> で表し, これを[[効用関数]](または[[価値関数]])という. ここで予算 <math>b\, </math> が与えられたとして, 財A, Bの単位量あたりの価格をそれぞれ <math>p_1\, </math>, <math>p_2\, </math> とすれば, 消費者は

<center><math>\mbox{maximize.} \qquad \quad u(x_1,x_2)\, </math></center>

<center><math>\mbox{subject to.} \quad p_1 x_1 + p_2 x_2 \le b,\, </math></center>

を満たす解, すなわち予算制約のもとで最も大きい満足感が得られる財Aと財Bの量の組を購入するであろう. すなわち, 「消費者は自己の効用を最大にする行動をとる」と考えて消費者行動を説明することが試みられている.

　近代経済学の初期においては, 主観価値説として[[基数尺度]] (cardinal scale)に従う基数効用関数(cardinal utility function)の存在を仮定することによってさまざまな経済理論を展開した. それは限界効用(marginal utility)を中心にした議論で限界革命とも呼ばれている. しかし, その後, 効用の可測性はあまりにも強い要請であると批判され, 人びとの主観的価値を表現する効用関数として基数効用関数を排除し, 大きさの大小関係だけを表す[[順序尺度]] (ordinalscale)に従う序数効用関数(または順序効用関数)(ordinal utility function)のみの存在を仮定することによって経済分析を行う方向に移ってゆく [1]. これは, 経験的に与えられる無差別曲線(indifference curve)を使って消費者行動を説明しようとするパレートの提案によるものである.
無差別曲線から導かれる序数効用に対して限界効用(効用の微分値)の概念は使えない. そのかわりに無差別曲線の傾きを表す限界代替率(marginal rate of substitution)が使われる [2].

　消費者行動の均衡条件を導出するうえでは序数効用関数によってその目的を達成することができるが, 多目的意思決定(multiple criteria decision making)のための選好解を導出するには, 基数効用関数の存在を仮定することが必要になる. さらに, リスクを伴う意思決定問題では, 評価の対象となる結果がある確率分布のもとで発生するので, 選好順序を求めるうえで効用の期待値を評価する必要があり, そのためには基数効用関数が必要になる. リスク下の意思決定問題に対して期待効用最大化の仮説が意味をもつように，公理系をはじめて作ったのはフォン・ノイマンとモルゲンシュテルンである [3].

　結果の集合 <math>X\, </math> 上の基数効用関数 <math>u : X \rightarrow \mathbf{R}\, </math> の, <math>X\, </math> 上の確率についての期待値

<center><math>E(u,p)= \sum_{x\in X}u(x)p(x)\, </math></center>

を期待効用(expected utility)という. <math>X\, </math> 上の確率の集合を <math>P=\{p_1,p_2,...\}\, </math> とするとき, 期待効用の大小によって <math>p\, </math> 上の[[選好関係]]　<math>\mathop \succsim \, </math> を表現することを考える.

'''定理'''：　基数効用関数の存在と一意性　

　<math>P\, </math> を <math>X\, </math> 上の確率の全集合とし, <math>(P, \mathop \succsim)\, </math> を <math>P\, </math> 上の選好構造とするとき, 任意の <math>p,q \in P\, </math> に対して

<center><math>p \mathop \succsim q \Leftrightarrow E(u,p)\geq E(u,q)\, </math></center>

を満たす <math>X\, </math> 上の基数効用関数 <math>u : X \rightarrow \mathbf{ R}\, </math> が存在するための必要十分条件は次のように与えられる. 　

　'''NM1'''　<math>(P, \mathop \succsim)\, </math> は弱順序である. 　

　'''NM2'''　<math>p \succ q \Rightarrow \alpha p + (1 - \alpha )r \succ\alpha q + (1-\alpha )r, \; \forall r \in P, \; \alpha \in (0,1)\, </math>

　'''NM3'''　<math>p \succ q \succ r \Rightarrow \alpha p + (1 - \alpha)r\succ q \succ \beta p + (1- \beta )r\, </math>, for some <math>\alpha, \beta \in(0,1)\, </math>

　このような効用関数<math>u\, </math> は正線形変換(<math>u'=h+ku\, </math> を満たす定数 <math>h\, </math> と <math>k>0\, </math> が存在)の範囲で一意であり, 別名フォン・ノイマン=モルゲンシュテルン効用関数という. 　

　さらに, サヴェージは, 結果の集合上に客観確率を考える代りに, 自然の集合上に主観確率(subjective probability)を考え, 期待効用最大化の仮説が成り立つ基数効用関数と主観確率が存在するための必要十分条件を求めた. [4]

　期待効用仮説に基づく期待効用モデルは, 「決定がいかにあるべきか」を議論する規範的(normative)モデルとしては有用なモデルであるが, 「決定が実際にどのようになされているか」を議論する記述的(descriptive)モデル(あるいは行動科学的モデル)としては問題がある. すなわち, アレーの反例やエルスバーグの反例に見られるように期待効用モデルでは説明できない現象がいくつか存在する [5]. これらを適切に説明するモデルとして, ノーベル経済学賞に輝いたカーネマンとトゥヴァースキによるプロスペクト理論[5]や累積プロスペクト理論[6]が提唱されている．

　プロスペクト理論は，期待効用理論における確率を，確率に関する主観的重み付き関数で置き換えて一般化することにより，アレーの判例（確実性効果），希求水準の効果，遊離効果などの，経験的に知られている選好構造を適切に説明するために作られた記述的モデルである．そこで使われる価値関数は，参照点（希求水準）をはさんで利得領域か損失領域で異なり，利得領域における価値は上に凸で緩やかなカーブであるのに対して，損失領域における価値は下に凸で急カーブであり非対称になっている．すなわち，利得領域ではリスク回避型であるのに対して，損失領域ではリスク選好となる．利得と損失の曲線の傾きが異なることは，損失回避を表現している[5]．また，確率に関する主観的重み関数は，「人々は非常に小さい確率を，それ自身より大きく感じる」ことをモデル化している．

　累積プロスペクト理論も，プロスペクト理論と同様の価値関数を仮定するが，確率に関する重みがプロスペクト理論とは異なっている．すなわち，確率の値が０または１付近の値をとるとき，確率の変化に対する重みの変化が大きく，確率の値が０または１から離れるほど，確率の変化に対する重みの変化が小さくなるようにモデル化されている．これにより，限界感度逓減に関する人々の心理的特性を忠実に表現している．

　さらに，期待効用モデルやプロスペクト理論を一般化したリスク下の価値関数や不確実性下の価値関数が提案されていて, そこでは事象の生起確率(またはDempster-Shaferの確率理論 [7] でいう焦点要素の基本確率)も評価属性のひとつとして扱われる [8]. リスク下の価値関数によって，アレーの反例や希求水準の効果はもとより，低確率高損失事象を対象にした期待効用モデルの反例を適切に表現することができる．また，不確実性下の価値関数によって，エルスバーグの反例はもとより，地球環境問題のように不確実性が高くて個々の事象の生起確率を見積もることは困難であるが，事象の集合に対する基本確率を見積もれるような現象を対象にした意思決定支援問題に応用することができる．また，このモデルによって悲観的な選好と楽観的な選好の相違を適切にモデル化することができる．

結果 <math>x \in X\, </math> が <math>n\, </math> 個の属性 <math>X_1,X_2,\ldots ,X_n\, </math> によって特徴づけられているとき, 結果 <math>x\, </math> は

<center><math>x=(x_1,x_2,\ldots ,x_n), \; x_i \in X_i, \; i =1,2,\ldots ,n\, </math></center>

で表される. 起こりうるすべての結果の集合 <math>X\, </math> は, 直積集合 <math>X_1 \times X_2\times \ldots \times X_n\, </math> で表され, これを <math>n\, </math> 属性空間という. <math>n\, </math> 属性効用関数は, <math>X=X_1 \times X_2 \times \ldots \times X_n\, </math> 上に <math>u:X_1 \times X_2\times \ldots \times X_n \rightarrow [0,1]\, </math> として定義される. このような <math>n\, </math> 属性効用関数を直接求めるには, 複数の属性を同時に考慮して選好判断をしなければならず, 実際にはほとんど不可能である. そこで, 複数の属性間に種々の独立性を仮定して, 直接評価する効用関数の属性の次元を少なくする分解表現を得ることが重要になる. とくに, <math>n\, </math> 個の属性が相互に効用独立という性質を満たすときには, [[加法型効用関数]]

<center><math>u(x)=u(x_1,x_2,\ldots ,x_n)=\sum_{i=1}^{n} k_i u_i(x_i)\, </math>　　　　　<math>(1) \,</math></center>

または[[乗法型効用関数]]

<center><math>ku(x)+1=\prod_{i=1}^{n}(kk_iu_i(x_i)+1)\, </math>　　　　　<math>(2) \,</math></center>

を得ることができる．ただし, <math>u_i:X_i \rightarrow [0,1]\, </math> すなわち <math>u_i\, </math> は属性 <math>X_i\, </math> 上の効用関数を表す. 分解表現が(1)式のような加法型で表現されるのは, <math>n\, </math> 個の属性が相互効用独立性はもとより加法独立性という性質を満足するときである. 詳細については文献[9]を参照されたい．

　複数の属性間で効用独立性が満たされないときには属性間に凸依存性という性質を仮定することによりさらに広範囲の分解表現を得ることができる [8].

----

'''参考文献'''

[1] P.A. Samuelson, ''Foundations of Economic Analysis,'' Harvard Univ. Press, Cambridge, USA, 1947. 佐藤隆三訳, 『経済分析の基礎』, 勁草書房, 1967.

[2] 中山弘隆, 谷野哲三, 『多目的計画法の理論と応用』, 計測自動制御学会, 1994.

[3] J. von Neumann and O. Morgenstern, ''Theory of Games and Economic Behavior'' Princeton Univ. Press, Princeton, NJ, USA, 1944.

[4] 市川惇信, 『意思決定論』, 共立出版, 1983.

[5] 広田すみれ,　増田真也,　坂上貴之編著：『心理学が描くリスクの世界』,　慶応義塾大学出版会, 2002.

[6] 成川康男, 非線形効用理論・累積プロスペクト理論,　知能と情報（日本知能情報ファジィ学会誌）,　Vol.16, No.4, pp.296-302, 2004.

[7] G. Shafer, ''A Mathematical Theory of Evidence,'' Princeton University Press, Princeton, N. J. 1976.

[8] 田村坦之, 中村豊, 藤田眞一, 『効用分析の数理と応用』, 計測自動制御学会編, コロナ社, 1997.

[9] R.L. Keeney and H. Raiffa, ''Decisions with Multiple Objectives,'' Cambridge Univ. Press (First published by Wiley, New York in 1976), Cambridge, England, 1993.

[[category:システム分析・意思決定支援・特許|こうようかんすう]]

《モデリング》

2007-08-09T20:02:09Z

H.Yamaguchi:

'''【もでりんぐ (Modeling)】'''

　[[モデリング]](Modeling)とは，現実世界の事象を数学的世界などの抽象世界の事象に置き換える作業のことである．置き換わった抽象世界の像を，モデルという．したがってモデリングはORの範疇以外でも盛んに用いられる概念であり，科学的に現実問題を解決する際には，必ず発生する作業といえる．ここでは，経営の科学としてのORの範疇におけるモデリング[1][2][3]を意識して述べる．
はじめに，モデリングの主な事例をあげておこう．

1．生態系などのダイナミックスを微分方程式でモデリングし，その解の振る舞いを研究することで地球環境などを探求する．

2．建造物にかかる力の分布を物理的方程式でモデリングし，建物などの強度を解析する．

3．組織や組織行動を論理的な様式でモデリングし，企業の行動や情報伝播などの支配的原理を解析する．

4．情報システム構築に際して，業務を論理モデルで表現し，システムの構造や機能を設計する．

5．需要変動などある種の不確実性を含む現象を確率的な記述でモデリングし，現実の事象の構造を分析し予測を行う

6．物流などの現実の動きをソフトウェアに置き換えて，計算機上で再現を試みるシミュレーションによって現実世界を模擬する．

7．企業における生産計画などの意思決定事象を，何らかの効用を最適化する数学的モデリングをし，最適生産計画などの意思決定に供する．

　　1.は地球環境の変化などを予測したりするのに，盛んに用いられるモデリングであり，実はランチェスターモデルなどORの黎明期の主たるモデリングとしても知られている．多くの場合，現実現象は非線形微分方程式でモデリングされ，解の追跡にはシステムダイナミックス用シミュレータが用いられる．

　　2.は構造計算書の偽造事件で，２００６年に世間を騒がせたことで有名になった．構造物にかかる力の分布などは，微分方程式でモデリングされる．最近の特殊な構造物を除き，結局巨大な連立一次方程式を解くことに帰着することが出来，数値計算手法の進歩を十分に受け入れることが可能である．

　　3.は会社組織や，業務遂行構造を抽象的に記述する試みとして，経営情報の分野で盛んに研究されている．次に挙げる情報システムの構築などの際に，業務記述（BPM：Business Process Modeling）の段階で用いられることも多い．

　　4.は主として業務情報システムの開発に用いられる．業務記述が終わると，各業務要素の機能をシステムに射影するためのモデリング手法（UML: Unified Modeling Language）などを用いてシステム設計を進めることがよく行われている．

　　5.はマーケッティングなどで用いられ，膨大な需要記録を元に予測された需要予測に基づいて，販売戦略などの構造とパラメータを決定するモデリングである．統計処理やデータマイニング，などを用いることを前提として計画される．

　　6.はサプライチェーンマネジメントの問題である．物流のネットワーク構造と需要・発注の戦略をモデリングし，離散系シミュレータを用いることが多い．

　　7.は意思決定問題である．ＯＲは経営の科学といわれ，経営の意思決定に寄与するところが大であり，この種のモデリングがもっとも効果的に働くであろう．数理計画問題は，生産計画などに表れる典型的なモデルのひとつであり，ＯＲの主要な部分を占める研究テーマとなっている．[[数理計画法]](Mathematical Programming) は数理計画問題を数値的に解く手法であり，非常によく研究されている．一方，[[AHP]](Analytic Hierarchy Process)などの，感覚など定量化しにくい要素に挑戦する意思決定モデルも盛んに研究され，実際広く用いられている．

　さて，モデリングの本質であるが，たとえば，高層ビルの設計においてエレベータを設置する問題を考えてみると，ビルに収容する予定の人々に対して，よりスムーズに上下移動サービスを提供することが課題となる．この際，各階の収容能力はエレベータの設置台数が増えれば減少する．一方，エレベータの台数が減れば当然上下移動サービスの質は低下する．上下移動サービスを要求する人数は，上層階に行くにしたがって減るであろう．時間帯による変動や，外来の人数の影響，もちろんコストなどなど考慮すべき要素は無数にあって，それらは複雑に絡み合っている．

　一般に実世界の課題は，複雑で問題の焦点が多岐にわたっている．このような，実世界の課題へのアプローチとして有力な方法のひとつがモデリングである．モデリングを適切に行うことによって，複雑な問題を単純化して本質的な課題構造を明らかにすることが出来る．モデルは数学などの抽象的表現がされているので，モデル上で数学的道具などを用いてさまざまな分析が可能となることもモデリングの効用である．

　エレベータの例に沿ってモデリングを考えてみよう．各階の総面積はあらかじめ決まっていて，エレベータビットの占める面積も与えられているはずである．したがって，各階を通過するエレベータの数による使用可能面積は簡単に計算可能である．エレベータの設置パターンを定めると，上下移動の単位時間当たりの性能が定まり，コストも定まる．そうすると，これらの関係は数学的表現が可能ということになる．一方，人々の行動は非常に複雑で抽象的表現は到底不可能であろう．このような複雑で簡単な説明ができないような現象に対しては，対象の本質を捉えて，単純化やデフォルメを行う必要がある．モデリングの役割は，実世界の現象の本質的な要因を抽出して，単純で明確な形にあらわすことにある．実際，高層ビルのエレベータ設置計画は，数学的な大まかなモデリングによって設置の大枠を決定し，細かな性能や運用計画は，シミュレーションを用いることとなろう．

　一般に，モデリングについての総合的な研究はまれであり，上に挙げたようなさまざまな適用分野ごとに，別々の発展をしている．しかし，モデリングを用いる手段は同じである．それは，いわゆるPDCA(Plan,Do,Check,Act)である．Planは，現実世界の現象をモデリングする段階である．Doは，構築されたモデルを用いてモデルの最適解などを導出する段階である．Checkは，導出された解を現実世界の現象に適用し，有効性を評価する段階である．Actは，Checkで検出された不適合要素を検討し，モデルの改良を加える段階である．かくして，モデリングを用いた現実課題の解決手法は，PDCAサイクルを回しながらより現実的な解決策に迫ることを目指す．このとき，モデルと現実の差異は多くの場合「誤差」と呼ばれるが，必ずしも量的な誤差だけではない．構造的（あるいは定性的）な差異が含まれているからである．したがって，現実とモデルの差異をここでは「不適合」ということとする．

　モデリングにおける注意点は，この不適合の検出と改良にあるといえる．不適合は下記のように分類されるであろう．

　●現実現象を簡略化しすぎ，本質的な要件を落としてしまったことによる不適合．

　●現実現象の要素間の関係を単純化（非線形を安易に線形化するなど）しすぎたことによる不適合．

　●考慮すべき制約条件を落としてしまったことによる不適合．

　●あまりに複雑化しすぎて，かえって本質的な構造を見落としたことによる不適合．

　PDCAサイクルは，このような不適合を発見し，よりよいモデルを構築する大切な手段である．特に，陥りやすいのは，複雑に考えすぎて本質的な構造を見失うことである．モデリングは現実現象のデフォルメであり，単純化してその本質を見つけることがその目的であることを忘れてはならない．不適合ではないが，もうひとつの考慮すべき点は，モデルを用いてなにを求めるか，というモデルの世界での「目的」を最初に決定しておくことである．たとえば，生産計画の最適化であれば，モデルは数学的な最適化問題となるであろう．サプライチェーンの在庫量予測などでは，おそらくシミュレーションを実施するであろう．したがって，数学的問題ではなく，ものの流れのデフォルメと構造をモデリングすることとなる．

　モデリングは，ＯＲにおいては定石といってよい手段であり，参考文献に挙げたような，学会誌に掲載されたいろいろな事例を参考にされたい．

'''参考文献'''

[1]　日本オペレーションズ・リサーチ，Vol.50, No.4, 2005.

[2]　日本オペレーションズ・リサーチ，Vol.51, No.5, 2006.

[3]　日本オペレーションズ・リサーチ，Vol.51, No.6, 2006.

《モデリング》

2007-08-09T19:58:44Z

H.Yamaguchi:

'''【もでりんぐ (Modeling)】'''

　モデリング(Modeling)とは，現実世界の事象を数学的世界などの抽象世界の事象に置き換える作業のことである．置き換わった抽象世界の像を，モデルという．したがってモデリングはORの範疇以外でも盛んに用いられる概念であり，科学的に現実問題を解決する際には，必ず発生する作業といえる．ここでは，経営の科学としてのORの範疇におけるモデリング[1][2][3]を意識して述べる．
はじめに，モデリングの主な事例をあげておこう．

1．生態系などのダイナミックスを微分方程式でモデリングし，その解の振る舞いを研究することで地球環境などを探求する．

2．建造物にかかる力の分布を物理的方程式でモデリングし，建物などの強度を解析する．

3．組織や組織行動を論理的な様式でモデリングし，企業の行動や情報伝播などの支配的原理を解析する．

4．情報システム構築に際して，業務を論理モデルで表現し，システムの構造や機能を設計する．

5．需要変動などある種の不確実性を含む現象を確率的な記述でモデリングし，現実の事象の構造を分析し予測を行う

6．物流などの現実の動きをソフトウェアに置き換えて，計算機上で再現を試みるシミュレーションによって現実世界を模擬する．

7．企業における生産計画などの意思決定事象を，何らかの効用を最適化する数学的モデリングをし，最適生産計画などの意思決定に供する．

　　1.は地球環境の変化などを予測したりするのに，盛んに用いられるモデリングであり，実はランチェスターモデルなどORの黎明期の主たるモデリングとしても知られている．多くの場合，現実現象は非線形微分方程式でモデリングされ，解の追跡にはシステムダイナミックス用シミュレータが用いられる．

　　2.は構造計算書の偽造事件で，２００６年に世間を騒がせたことで有名になった．構造物にかかる力の分布などは，微分方程式でモデリングされる．最近の特殊な構造物を除き，結局巨大な連立一次方程式を解くことに帰着することが出来，数値計算手法の進歩を十分に受け入れることが可能である．

　　3.は会社組織や，業務遂行構造を抽象的に記述する試みとして，経営情報の分野で盛んに研究されている．次に挙げる情報システムの構築などの際に，業務記述（BPM：Business Process Modeling）の段階で用いられることも多い．

　　4.は主として業務情報システムの開発に用いられる．業務記述が終わると，各業務要素の機能をシステムに射影するためのモデリング手法（UML: Unified Modeling Language）などを用いてシステム設計を進めることがよく行われている．

　　5.はマーケッティングなどで用いられ，膨大な需要記録を元に予測された需要予測に基づいて，販売戦略などの構造とパラメータを決定するモデリングである．統計処理やデータマイニング，などを用いることを前提として計画される．

　　6.はサプライチェーンマネジメントの問題である．物流のネットワーク構造と需要・発注の戦略をモデリングし，離散系シミュレータを用いることが多い．

　　7.は意思決定問題である．ＯＲは経営の科学といわれ，経営の意思決定に寄与するところが大であり，この種のモデリングがもっとも効果的に働くであろう．数理計画問題は，生産計画などに表れる典型的なモデルのひとつであり，ＯＲの主要な部分を占める研究テーマとなっている．数理計画法(Mathematical Programming) は数理計画問題を数値的に解く手法であり，非常によく研究されている．一方，AHP(Analytic Hierarchy Process)などの，感覚など定量化しにくい要素に挑戦する意思決定モデルも盛んに研究され，実際広く用いられている．

　さて，モデリングの本質であるが，たとえば，高層ビルの設計においてエレベータを設置する問題を考えてみると，ビルに収容する予定の人々に対して，よりスムーズに上下移動サービスを提供することが課題となる．この際，各階の収容能力はエレベータの設置台数が増えれば減少する．一方，エレベータの台数が減れば当然上下移動サービスの質は低下する．上下移動サービスを要求する人数は，上層階に行くにしたがって減るであろう．時間帯による変動や，外来の人数の影響，もちろんコストなどなど考慮すべき要素は無数にあって，それらは複雑に絡み合っている．

　一般に実世界の課題は，複雑で問題の焦点が多岐にわたっている．このような，実世界の課題へのアプローチとして有力な方法のひとつがモデリングである．モデリングを適切に行うことによって，複雑な問題を単純化して本質的な課題構造を明らかにすることが出来る．モデルは数学などの抽象的表現がされているので，モデル上で数学的道具などを用いてさまざまな分析が可能となることもモデリングの効用である．

　エレベータの例に沿ってモデリングを考えてみよう．各階の総面積はあらかじめ決まっていて，エレベータビットの占める面積も与えられているはずである．したがって，各階を通過するエレベータの数による使用可能面積は簡単に計算可能である．エレベータの設置パターンを定めると，上下移動の単位時間当たりの性能が定まり，コストも定まる．そうすると，これらの関係は数学的表現が可能ということになる．一方，人々の行動は非常に複雑で抽象的表現は到底不可能であろう．このような複雑で簡単な説明ができないような現象に対しては，対象の本質を捉えて，単純化やデフォルメを行う必要がある．モデリングの役割は，実世界の現象の本質的な要因を抽出して，単純で明確な形にあらわすことにある．実際，高層ビルのエレベータ設置計画は，数学的な大まかなモデリングによって設置の大枠を決定し，細かな性能や運用計画は，シミュレーションを用いることとなろう．

　一般に，モデリングについての総合的な研究はまれであり，上に挙げたようなさまざまな適用分野ごとに，別々の発展をしている．しかし，モデリングを用いる手段は同じである．それは，いわゆるPDCA(Plan,Do,Check,Act)である．Planは，現実世界の現象をモデリングする段階である．Doは，構築されたモデルを用いてモデルの最適解などを導出する段階である．Checkは，導出された解を現実世界の現象に適用し，有効性を評価する段階である．Actは，Checkで検出された不適合要素を検討し，モデルの改良を加える段階である．かくして，モデリングを用いた現実課題の解決手法は，PDCAサイクルを回しながらより現実的な解決策に迫ることを目指す．このとき，モデルと現実の差異は多くの場合「誤差」と呼ばれるが，必ずしも量的な誤差だけではない．構造的（あるいは定性的）な差異が含まれているからである．したがって，現実とモデルの差異をここでは「不適合」ということとする．

　モデリングにおける注意点は，この不適合の検出と改良にあるといえる．不適合は下記のように分類されるであろう．

　●現実現象を簡略化しすぎ，本質的な要件を落としてしまったことによる不適合．

　●現実現象の要素間の関係を単純化（非線形を安易に線形化するなど）しすぎたことによる不適合．

　●考慮すべき制約条件を落としてしまったことによる不適合．

　●あまりに複雑化しすぎて，かえって本質的な構造を見落としたことによる不適合．

　PDCAサイクルは，このような不適合を発見し，よりよいモデルを構築する大切な手段である．特に，陥りやすいのは，複雑に考えすぎて本質的な構造を見失うことである．モデリングは現実現象のデフォルメであり，単純化してその本質を見つけることがその目的であることを忘れてはならない．不適合ではないが，もうひとつの考慮すべき点は，モデルを用いてなにを求めるか，というモデルの世界での「目的」を最初に決定しておくことである．たとえば，生産計画の最適化であれば，モデルは数学的な最適化問題となるであろう．サプライチェーンの在庫量予測などでは，おそらくシミュレーションを実施するであろう．したがって，数学的問題ではなく，ものの流れのデフォルメと構造をモデリングすることとなる．

　モデリングは，ＯＲにおいては定石といってよい手段であり，参考文献に挙げたような，学会誌に掲載されたいろいろな事例を参考にされたい．

参考文献
[1]　日本オペレーションズ・リサーチ，Vol.50, No.4, 2005.

[2]　日本オペレーションズ・リサーチ，Vol.51, No.5, 2006.

[3]　日本オペレーションズ・リサーチ，Vol.51, No.6, 2006.

《モデリング》

2007-08-09T19:52:50Z

H.Yamaguchi: 新しいページ: 'モデリングモデリング(Modeling)とは，現実世界の事象を数学的世界などの抽象世界の事象に置き換える作業のことである．置き換...'

モデリング

モデリング(Modeling)とは，現実世界の事象を数学的世界などの抽象世界の事象に置き換える作業のことである．置き換わった抽象世界の像を，モデルという．したがってモデリングはORの範疇以外でも盛んに用いられる概念であり，科学的に現実問題を解決する際には，必ず発生する作業といえる．ここでは，経営の科学としてのORの範疇におけるモデリング[1][2][3]を意識して述べる．
はじめに，モデリングの主な事例をあげておこう．

1．生態系などのダイナミックスを微分方程式でモデリングし，その解の振る舞いを研究することで地球環境などを探求する．

2．建造物にかかる力の分布を物理的方程式でモデリングし，建物などの強度を解析する．

3．組織や組織行動を論理的な様式でモデリングし，企業の行動や情報伝播などの支配的原理を解析する．

4．情報システム構築に際して，業務を論理モデルで表現し，システムの構造や機能を設計する．

5．需要変動などある種の不確実性を含む現象を確率的な記述でモデリングし，現実の事象の構造を分析し予測を行う

6．物流などの現実の動きをソフトウェアに置き換えて，計算機上で再現を試みるシミュレーションによって現実世界を模擬する．

7．企業における生産計画などの意思決定事象を，何らかの効用を最適化する数学的モデリングをし，最適生産計画などの意思決定に供する．

1.は地球環境の変化などを予測したりするのに，盛んに用いられるモデリングであり，実はランチェスターモデルなどORの黎明期の主たるモデリングとしても知られている．多くの場合，現実現象は非線形微分方程式でモデリングされ，解の追跡にはシステムダイナミックス用シミュレータが用いられる．
2.は構造計算書の偽造事件で，２００６年に世間を騒がせたことで有名になった．構造物にかかる力の分布などは，微分方程式でモデリングされる．最近の特殊な構造物を除き，結局巨大な連立一次方程式を解くことに帰着することが出来，数値計算手法の進歩を十分に受け入れることが可能である．
3.は会社組織や，業務遂行構造を抽象的に記述する試みとして，経営情報の分野で盛んに研究されている．次に挙げる情報システムの構築などの際に，業務記述（UML: Unified Modeling Language）などを用いてシステム設計を進めることがよく行われている．
5.はマーケッティングなどで用いられ，膨大な需要記録を元に予測された需要予測に基づいて，販売戦略などの構造とパラメータを決定するモデリングである．統計処理やデータマイニング，などを用いることを前提として計画される．
6.はサプライチェーンマネジメントの問題である．物流のネットワーク構造と需要・発注の戦略をモデリングし，離散系シミュレータを用いることが多い．
7.は意思決定問題である．ＯＲは経営の科学といわれ，経営の意思決定に寄与するところが大であり，この種のモデリングがもっとも効果的に働くであろう．数理計画問題は，生産計画などに表れる典型的なモデルのひとつであり，ＯＲの主要な部分を占める研究テーマとなっている．数理計画法(Mathematical Programming) は数理計画問題を数値的に解く手法であり，非常によく研究されている．一方，AHP(Analytic Hierarchy Process)などの，感覚など定量化しにくい要素に挑戦する意思決定モデルも盛んに研究され，実際広く用いられている．
　さて，モデリングの本質であるが，たとえば，高層ビルの設計においてエレベータを設置する問題を考えてみると，ビルに収容する予定の人々に対して，よりスムーズに上下移動サービスを提供することが課題となる．この際，各階の収容能力はエレベータの設置台数が増えれば減少する．一方，エレベータの台数が減れば当然上下移動サービスの質は低下する．上下移動サービスを要求する人数は，上層階に行くにしたがって減るであろう．時間帯による変動や，外来の人数の影響，もちろんコストなどなど考慮すべき要素は無数にあって，それらは複雑に絡み合っている．
　一般に実世界の課題は，複雑で問題の焦点が多岐にわたっている．このような，実世界の課題へのアプローチとして有力な方法のひとつがモデリングである．モデリングを適切に行うことによって，複雑な問題を単純化して本質的な課題構造を明らかにすることが出来る．モデルは数学などの抽象的表現がされているので，モデル上で数学的道具などを用いてさまざまな分析が可能となることもモデリングの効用である．
　エレベータの例に沿ってモデリングを考えてみよう．各階の総面積はあらかじめ決まっていて，エレベータビットの占める面積も与えられているはずである．したがって，各階を通過するエレベータの数による使用可能面積は簡単に計算可能である．エレベータの設置パターンを定めると，上下移動の単位時間当たりの性能が定まり，コストも定まる．そうすると，これらの関係は数学的表現が可能ということになる．一方，人々の行動は非常に複雑で抽象的表現は到底不可能であろう．このような複雑で簡単な説明ができないような現象に対しては，対象の本質を捉えて，単純化やデフォルメを行う必要がある．モデリングの役割は，実世界の現象の本質的な要因を抽出して，単純で明確な形にあらわすことにある．実際，高層ビルのエレベータ設置計画は，数学的な大まかなモデリングによって設置の大枠を決定し，細かな性能や運用計画は，シミュレーションを用いることとなろう．
　一般に，モデリングについての総合的な研究はまれであり，上に挙げたようなさまざまな適用分野ごとに，別々の発展をしている．しかし，モデリングを用いる手段は同じである．それは，いわゆるPDCA(Plan,Do,Check,Act)である．Planは，現実世界の現象をモデリングする段階である．Doは，構築されたモデルを用いてモデルの最適解などを導出する段階である．Checkは，導出された解を現実世界の現象に適用し，有効性を評価する段階である．Actは，Checkで検出された不適合要素を検討し，モデルの改良を加える段階である．かくして，モデリングを用いた現実課題の解決手法は，PDCAサイクルを回しながらより現実的な解決策に迫ることを目指す．このとき，モデルと現実の差異は多くの場合「誤差」と呼ばれるが，必ずしも量的な誤差だけではない．構造的（あるいは定性的）な差異が含まれているからである．したがって，現実とモデルの差異をここでは「不適合」ということとする．
　モデリングにおける注意点は，この不適合の検出と改良にあるといえる．不適合は下記のように分類されるであろう．

　●現実現象を簡略化しすぎ，本質的な要件を落としてしまったことによる不適合．
　●現実現象の要素間の関係を単純化（非線形を安易に線形化するなど）しすぎたことによる不適合．
　●考慮すべき制約条件を落としてしまったことによる不適合．
　●あまりに複雑化しすぎて，かえって本質的な構造を見落としたことによる不適合．

　PDCAサイクルは，このような不適合を発見し，よりよいモデルを構築する大切な手段である．特に，陥りやすいのは，複雑に考えすぎて本質的な構造を見失うことである．モデリングは現実現象のデフォルメであり，単純化してその本質を見つけることがその目的であることを忘れてはならない．不適合ではないが，もうひとつの考慮すべき点は，モデルを用いてなにを求めるか，というモデルの世界での「目的」を最初に決定しておくことである．たとえば，生産計画の最適化であれば，モデルは数学的な最適化問題となるであろう．サプライチェーンの在庫量予測などでは，おそらくシミュレーションを実施するであろう．したがって，数学的問題ではなく，ものの流れのデフォルメと構造をモデリングすることとなる．
　モデリングは，ＯＲにおいては定石といってよい手段であり，参考文献に挙げたような，学会誌に掲載されたいろいろな事例を参考にされたい．

参考文献
[1]　日本オペレーションズ・リサーチ，Vol.50, No.4, 2005.
[2]　日本オペレーションズ・リサーチ，Vol.51, No.5, 2006.
[3]　日本オペレーションズ・リサーチ，Vol.51, No.6, 2006.

《提携形ゲーム》

2007-08-09T04:13:05Z

H.Yamaguchi:

'''【ていけいけいげーむ (game in coalitional form) 】'''

　[[提携形ゲーム]] (game in coalitional form) は協力ゲームの表現形式の一つであり, プレイヤー集合<math>N\, </math>と, プレイヤーが[[提携]] (coalition) を形成し共同行動をとる際に実現可能な結果を表す[[特性関数 (ゲーム理論の)|特性関数]] (characteristic function) <math>v\, </math>の組<math>(N, v)\, </math>で表わされる. このために提携形ゲームは[[特性関数形ゲーム]] (game in characteristic function form) とよばれることもある. 特性関数の値は, 提携がそのメンバーだけで実現可能な利得の総和 (実数値) で表される場合 ([[譲渡可能効用]]を持つゲーム, game with transferable utility, TU-game) と, 提携の各メンバーの実現可能な利得ベクトルの集合で表される場合 (譲渡可能効用を持たないゲーム, game without transferable utility, NTU-game) がある. 譲渡可能効用を持つゲームでは, 共同行動の利害を調整するために貨幣などの媒介物による利得の[[別払い]] (sidepayment) が必要となる. 譲渡可能効用を持たないゲームの詳細については [13] を参照.

　提携形ゲーム<math>(N, v)\, </math>における基本的な問題は, プレイヤー間の協力の結果, (1) いかなる提携が形成され, (2) 提携のメンバーの間で利得がどのように分配されるか, である. 協力に関する交渉の結果, 各プレイヤー<math>i\, </math>に最終的に分配される利得<math>x_i\, </math>から成るベクトル<math>x=(x_1, x_2, \ldots, x_n)\, </math>を利得ベクトルとよび, さまざまな合理性の基準により, 結果として到達されると考えられる利得ベクトルの集合を提携形ゲームの解とよぶ.

　[[優加法性 (ゲーム理論における)|優加法性]] (superadditivity) をみたすゲームにおいてはプレイヤー全体による提携Nが形成されると考えられるので<math>v(N)\, </math>の値をどのようにプレイヤー間で分配すべきかが問題となる. このとき, ゲームの解の基本的な条件としては[[全体合理性]] (total group rationality) と[[個人合理性]] (individual rationality) の2つがあげられる. 前者は, 利得ベクトルが, プレイヤーが協力して実現できる実現可能集合において[[パレート最適]] (Pareto optimum) であることを要請し, 後者はゲームに参加して協力することの結果が, 単独で行動するよりも悪くならないことを要請している. 全体合理性をみたす利得ベクトルを[[準配分]] (preimputation) とよび, 全体合理性と個人合理性の両方をみたす利得ベクトルを[[配分]] (imputation)とよぶ.

　提携形ゲームの解で, 経済分析や費用分担問題などの応用も多く, よく知られているのは[[コア]] (core) である. コアは常に存在するとは限らないが, 存在のための必要十分条件がボンダレーヴァ (O. N. Bondareva) やシャープレイ (L. S. Shapley) によって研究されている. 特に, 市場経済をゲームとして定式化した[[市場ゲーム]]については多くの研究があり, [[競争均衡]]がコアに含まれることが知られている. また, 非分割財市場ゲームなどの種々の割当て市場ゲームや[[投票ゲーム]], [[費用分担ゲーム]]などにおいても, コアは分配案の安定性を示す重要な概念となっている.

　コアと同様に [[支配 (配分の)|支配]] (domination) 関係によって定義された解として知られているのはフォンノイマン (J. von Neumann) とモルゲンシュテルン (O. Morgenstern) によって提唱された[[安定集合]] (stable set) である [14]. 安定集合は[[フォンノイマン・モルゲンシュテルン解]] (von Neumann-Morgenstern solution) とよばれることもある. 安定集合は存在しない場合もあるし, 複数存在する場合もあるが, 存在すればコアを含む. また, コア自身が安定集合であれば, コア以外に安定集合は存在しない.

　一方, 提携構造を考慮に入れた特性関数を基に始まった一連の研究があり, それらのゲームの解としては[[交渉集合]] (bargaining set) , [[カーネル (ゲーム理論における)|カーネル]] (kernel), [[仁]] (nucleolus) がある. 交渉集合はオーマン (R. J. Aumann) とマシュラー (M. Maschler) によって異議と逆異議を用いて定義された解であり, 常に存在し, コア, カーネル, 仁を含んでいる [2]. カーネルと仁は提携のもつ利得ベクトルへの不満 (超過要求) に基づいて定義された解である. カーネルはデービス (M. Davis) とマシュラーにより導入され [4], 仁はシュマイドラー (D. Schmidler) により導入された [10]. カーネルと仁はともに常に存在し, 仁はカーネルと[[最小コア (ゲーム理論の)|最小コア]] (least core) の共通部分に含まれている. 仁は常にただ1つの配分から成り, その計算法についてもいろいろな研究がなされている. 破産問題においては, ユダヤ教の教典かつ律法書であるタルムード (Talmud) に1500年前に記述された分配方法とカーネルの与える分配が一致するという興味深い結果が知られている [3]. カーネルと仁は配分の集合を基に, 定義されているが, 準配分の集合において同等の定式化を行うと, 準カーネル, 準仁などの概念が導かれる. これらの解の性質については [1]の18章にまとめられている.

　提携形ゲームにおいて, プレイヤーがそのゲームに参加する場合のゲームの事前評価の値をゲームの値という. ゲームの値の概念の中で最もよく知られたものは[[シャープレイ値]] (Shapley value) である [11] . シャープレイ値は全体合理性, 対称性, 加法性, ナルプレイヤーのゼロ評価の４公理をみたす唯一の値 (ゲームの関数) として与えられる. シャープレイ値の応用の1つは[[投票ゲーム]]への適用である. シャープレイ・シュービック指数と呼ばれ, 各投票者の影響力を示す[[パワー指数]]の1つとして広く用いられている.

　提携形ゲームにはこのように多数の解概念が提唱されているが, それらの解概念の共通点や差異を調べるためにいろいろなゲームのクラスにおいて, 解の間の幾何学的関係が研究されている. [[凸ゲーム]] (convex game) のクラスにおいては, 交渉集合がコアおよび安定集合と一致し, シャープレイ値はコアの重心になる. また, カーネルは仁と一致することが知られている. 凸ゲームを含む広いゲームのクラスや他のゲームのクラスにおける解の関係については [5] を参照されたい.

　近年, 公理化のアプローチを多くの提携形ゲームの解概念に用い, 統一的な公理(整合性公理)で解の性質を解明しようとする研究が進んでいる. ある状況 (ゲーム) で解の与える利得分配と, プレイヤー数名が解の与える利得を持ってそのゲームから退出し, 残された状況 (縮小ゲーム) での解の与える利得分配を比較する. 整合性公理は, この両方の状況での解の与える利得分配が一致することを要請している. このとき, 残されたプレイヤーへの退出プレイヤーの協力の形態により縮小ゲームの構造が異なり, この縮小ゲームの差異を基に, コア, 準仁, 準カーネル, シャープレイ値などの整合性公理による公理化が研究されている. この分野に関しては例えば [6] を参照.

　なお, 提携形ゲーム全般の詳しい解説は [7], [8], [9], [12], [13] などを参照されたい. また, [1] のいくつかの章には, 提携形ゲームに関するトピックがテーマごとに詳細にまとめられており参考になる.

----
'''参考文献'''

[1] R. J. Aumann and S. Hart, eds., ''Handbook of Game Theory Volume I, Volume II'', North-Holland, 1992, 1994.

[2] R. J. Aumann and M. Maschler, "The Bargaining Set for Cooperative Games," in ''Advances in Game Theory'', M. Dresher, L. S. Shapley and A. W. Tucker, eds., Princeton University Press, 1964.

[3] R. J. Aumann and M. Maschler, "Game Theoretic Analysis of a Bankruptcy Problem," ''Journal of Economic Theory'', '''36''' (1985), 195-213.

[4] M. Davis and M. Maschler, "The Kernel of a Cooperative Game," ''Naval Research Logistics Quarterly'', '''12''' (1965), 223-259.

[5] T. S. H. Driessen, ''Cooperative Games, Solutions and Applications'', Kluwer Academic Publishers, 1988.

[6] T. S. H. Driessen, "A Survey of Consistency Properties in Cooperative Game Theory," ''SIAM Review'', '''33''' (1991), 43-59.

[7] 船木由喜彦, エコノミックゲームセオリー, サイエンス社, 2001.

[8] 武藤滋夫, ゲーム理論入門, 日本経済新聞社, 2001.

[9] 岡田章, 『ゲーム理論』, 有斐閣, 1996.

[10] D. Schmeidler, "The Nucleolus of a Characteristic Function Game," ''SIAM Journal of Applied Mathematics'', '''17''' (1969), 1163-1170.

[11] L. S. Shapley, "A Value for n-Person Games," in ''Contributions to the Theory of Games II'', H. Kuhn and A. W. Tucker, eds., Princeton University Press, 1953.

[12] 鈴木光男, 『新ゲーム理論』, 勁草書房, 1994.

[13] 鈴木光男, 武藤滋夫, 『協力ゲームの理論』, 東京大学出版会, 1985.

[14] J. von Neumann and O. Morgenstern, ''Theory of Games and Economic Behavior, 3rd ed.'', Princeton University Press, 1953.

[[category:ゲーム理論|ていけいけいげーむ]]

《交渉ゲーム》

2007-08-09T04:07:48Z

H.Yamaguchi:

'''【こうしょうげーむ (bargaining game) 】'''

　交渉は, 複数の当事者が協力の条件を協議する状況であり, 各自が相互依存関係の中で意思決定をするゲームの状況である. [[交渉ゲーム]] (bargaining game) の研究は, ナッシュ (J. F. Nash)による[[2人交渉問題]]の交渉解に始まり, 近年では, ルビンシュタイン (A. Rubinstein) の[[交互オファーゲーム]]による交渉過程の分析が代表的である.

'''1　 2人交渉問題と交渉解'''　交渉の結果は, 妥結して協力するか決裂するかであり, 交渉の妥結点は交渉決裂時の状態に依存する. 2人交渉問題は, 2人のプレイヤー間の交渉を, 協力実現可能集合 <math>S\, </math> と交渉の基準点 <math>d\in S\, </math> の組 <math>(S, d)\, </math> として記述する. <math>S\, </math>は２次元実数ベクトル空間の部分集合である. 以下では, ベクトル間の不等号は要素ごとの不等号を意味する.

　協力実現可能集合 <math>S\, </math> は2人が協力して実現可能な[[利得 (ゲームの)|利得]]ベクトル集合であり, 妥結点の候補を表す. 厳密には, 2人のプレイヤーの[[相関戦略]]により実現可能な[[フォンノイマン・モルゲンシュテルン効用関数|フォンノイマン・モルゲンシュテルン期待効用]]ベクトル <math>(u_{1}, u_{2})\, </math> の集合が <math>S\, </math> である. 交渉問題では, 交渉決裂時は, 各プレイヤーは予め想定された行動を独立に実行し, 交渉の基準点 <math>d=(d_{1}, d_{2})\, </math> の利得を得るとする. 集合 <math>I(S, d)=\{u \in S|u \ge d\}\, </math> を (個人合理的) 交渉領域と呼ぶ. 通常, (1) 集合 <math>S\, </math> がコンパクト凸であり, (2) <math>x>d\, </math> なる点 <math>x \in S\, </math> が存在する, という2条件を満たす交渉問題が考察対象とされ, その集合を <math>B_{0}\, </math> とする. また, (1), (2)に加えて, 「<math>x \in S\, </math> かつ <math>x\ge y\ge d\, </math> ならば, <math>y\in S\, </math>」であり, 「交渉領域の[[パレート最適|弱パレート最適]]な境界線が水平, 垂直部分を持たない」交渉問題の集合を <math>B_{E}\, </math> とする.

　交渉問題の集合 <math>B\, </math> に属す任意の交渉問題 <math>(S, d)\, </math> に, 妥結点 <math>a\in S\, </math> を与える関数 <math>f:B \to {\mathbf{ R}}^{2}\, </math> を, (<math>B\, </math> 上の)[[交渉解]] (bargaining solution) <math>f\, </math> という. 交渉解は妥結方法を示す概念である. ナッシュは合理的妥結方法が満たすべき4つの公理を挙げて, それらを満たす交渉解を分析した.

'''公理1'''　(正アフィン変換からの独立性). 交渉問題 <math>(S, d)\, </math> と <math>(S^{\prime}, d^{\prime})\, </math> が, ある正アフィン変換 <math>y=(c_{1}x_{1}+b_{1}, c_{2}x_{2}+b_{2}), c_{1}, c_{2}>0\, </math>, により一致するとき, 交渉解が両問題に与える妥結点もその変換の下で一致する.

'''公理2'''　(パレート最適性). 交渉解は[[パレート最適]]な妥結点を与える.

'''公理3'''　(対称性). 交渉問題 <math>(S, d)\, </math> が対称的で, <math>(x, y)\in S\Leftrightarrow(y, x)\in S\, </math>, かつ, <math>d_{1}=d_{2}\, </math> ならば, 交渉解の与える妥結点 <math>(a_{1}, a_{2})\, </math> も対称的で, <math>a_{1}=a_{2}\, </math>.

'''公理4'''　(無関連な代替案からの独立性). 基準点が等しい交渉問題 <math>(S, d)\, </math> と <math>(T, d)\, </math> について, <math>T\subseteq S\, </math> かつ <math>f(S, d)\in T\, </math> ならば, <math>f(T, d)=f(S, d)\, </math>.

　公理1は利得の高低やその変化分の大小をプレイヤー間で比較する「個人間効用比較」の排除を求める公理であり, フォンノイマン・モルゲンシュテルン効用が正アフィン変換の下で同値なことからも仮定される. 公理2は交渉結果の効率性を求め, 公理3は, 交渉状況が対称的ならば妥結点も対称的であることを求めている. 公理4は, 妥結点とならなかった代替案を除いて, 再び交渉し直しても妥結点は変わらないことを求める公理である. ナッシュは, 交渉問題の集合 <math>B_{0}\, </math> 上で, 公理1-4を満たす交渉解が一意に定まることを証明した. [[ナッシュ解]]と呼ばれるその交渉解 <math>f^{{\rm N}}\, </math> は, 交渉領域内で2人のプレイヤーの基準点からの利得増加分の積を最大化する点を妥結点とし, <math>f^{\rm N}(S, d)= {\rm argmax}_{u\in I(S, d)}(u_{1}-d_{1})(u_{2}-d_{2})\, </math> で与えられる [3].

<center><table><tr><td align=center>[[画像:0075-a-g-07f1-mof.png|center|図1：交渉問題の妥結点]]</td></tr>
<td align=center>図1：交渉問題の妥結点</td></table></center>

　ナッシュ解の妥結点は, 公理系では仮定されないが, 個人合理的である. 図1は, ナッシュ解の妥結点と各公理の関係を示している. まず, 対称的交渉問題では, 公理2, 3から, <math>f^{{\rm N}}(S^{0}, d)=C^{\prime}\, </math>, <math>f^{{\rm N}}(S^{1}, d)=A\, </math> となる. 次に, <math>f^{{\rm N}}(S^{0}, d)=C^{\prime}\, </math> ならば, 公理1から, <math>f^{{\rm N}}(S^{3}, d)=C\, </math> となる. そして公理4から, <math>f^{{\rm N}}(S^{2}, d)=f^{{\rm N}}(S^{3}, d)=C\, </math> となる. 問題 <math>(S^{2}, d)\, </math> は問題 <math>(S^{1}, d)\, </math> よりも交渉領域が広いが, プレイヤー2の妥結点利得は減少している. よって, ナッシュ解の妥結点は単調的には推移しない.

　個人間効用比較を排除する公理1の下で, 妥結点の単調性を求めた交渉解として, [[カライ・スモルディンスキー解]] (Kalai-Smorodinsky solution, 以下<math>{\rm KS}\, </math>解と略す) がある. <math>{\rm KS}\, </math>解では, 基準点に加え, 交渉の理想点 (各プレイヤー <math>i\, </math> が交渉領域で獲得できる最大利得 <math>m_{i}={\rm max}\{u_{i}|u\in I(S, d)\}\, </math> の組 <math>M=(m_{1}, m_{2})\, </math>) が考慮される. いま, 「基準点と理想点が共に等しい問題 <math>(S, d)\, </math> と <math>(T, d)\, </math> について, <math>T\subseteq S\, </math> ならば, <math>f(S, d) \ge f(T, d)\, </math>」という条件を限定単調性の公理と呼ぶと, 交渉問題の集合 <math>B_{0}\, </math> 上で, 公理1-3, かつ, 限定単調性を満たす交渉解が一意に定まる [2]. この解が<math>{\rm KS}\, </math>解であり, 基準点と理想点を結ぶ線分と交渉領域のパレート最適な境界線との交点を妥結点とする. 以下, <math>{\rm KS}\, </math>解を <math>f^{{\rm KS}}\, </math> で表す.

　ナッシュ解と <math>{\rm KS}\, </math> 解の一意性から, 公理4と限定単調性の公理は両立しない. これは, ナッシュ解と<math>{\rm KS}\, </math>解が, 異なる観点から各々合理的な妥結方法であることを示す. 先の問題 <math>(S^{2}, d)\, </math> の理想点は <math>{\rm M}^{1}\, </math> なので, <math>f^{{\rm KS}}(S^{2}, d)=B\, </math> となる. しかし交渉領域が <math>S^{3}\, </math> に広がると, <math>f^{{\rm KS}}(S^{3}, d)=C\, </math> となり, 再びプレイヤー2の妥結点利得は減少する. これは公理1のためで, <math>f^{{\rm KS}}(S^{0}, d)=C^{\prime}\, </math> 故に, <math>f^{{\rm KS}}(S^{3}, d)=C\, </math> となるのである.

<center>表１：各交渉解とその妥結点 (図１参照)
<table width="506">
<tr>
<td colspan="4" width="506">
<hr>
</td>
</tr>
<tr>
<td align="center" width="125">交渉問題</td>
<td align="center" width="125">ナッシュ解</td>
<td align="center" width="125"><math>{\rm KS}\, </math>解 </td>
<td align="center" width="125">均等解</td>
</tr>
<tr>
<td colspan="4" align="center" width="506">
<hr>
</td>
</tr>
<tr>
<td align="center" width="125"><math>(S^{1}, d)\, </math></td>
<td align="center" width="125"><math>{\rm A}\, </math></td>
<td align="center" width="125"><math>{\rm A}\, </math></td>
<td align="center" width="125"><math>{\rm A}\, </math></td>
</tr>
<tr>
<td colspan="4" align="center" width="506">
<hr>
</td>
</tr>
<tr>
<td align="center" width="125"><math>(S^{2}, d)\, </math></td>
<td align="center" width="125"><math>{\rm C}\, </math></td>
<td align="center" width="125"><math>{\rm B}\, </math></td>
<td align="center" width="125"><math>{\rm B}\, </math></td>
</tr>
<tr>
<td colspan="4" align="center" width="506">
<hr>
</td>
</tr>
<tr>
<td align="center" width="125"><math>(S^{3}, d)\, </math></td>
<td align="center" width="125"><math>{\rm C}\, </math></td>
<td align="center" width="125"><math>{\rm C}\, </math></td>
<td align="center" width="125"><math>{\rm B}\, </math></td>
</tr>
<tr>
<td colspan="4" align="center" width="506">
<hr>
</td>
</tr>
</table></center>

　個人間効用比較が可能な交渉状況を考え, 公理1を要件としなければ, より強い単調性を満たす[[均等解]] (egalitarian solution) が公理化される. 条件「基準点が等しい交渉問題 <math>(S, d)\, </math> と <math>(T, d)\, </math> について, <math>T\subseteq S\, </math> ならば, <math>f(T, d)\le f(S, d)\, </math>」を単調性の公理と呼ぶと, 交渉問題の集合 <math>B_{E}\, </math> 上で, 公理2, 3, かつ, 単調性を満たす交渉解が一意に定まる. その交渉解は交渉領域内で各プレイヤーの基準点からの利得増加分を等しく最大化する点であり, 均等解と呼ばれる [2]. ただし, 考察する集合を<math>B_0\, </math>とすると, 均等解は必ずしもパレート最適ではない. 以上3つの交渉解を図1の例によって整理すると, 表1のようになる.

'''2　交互オファーゲーム'''　[[交互オファーゲーム]]は, 2人のプレイヤーが所与の価値の分配, 例えば, 分割可能な財1単位の分配について, 相手が了承するまで, 繰り返し交互に分配案を提示しあっていくゲームである.

<center><table><tr><td align=center>[[画像:0075-a-g-07f2-mof.png|center|図２：財分配の実現可能集合]]</td></tr>
<td align=center>図２：財分配の実現可能集合</td></table></center>

　いま, 各プレイヤー <math>i\, </math> は, <math>x\, </math> 単位の財から利得 <math>U_{i}(x)\, </math> を得て, 利得関数 <math>U_{i}\, </math> は連続狭義単調増加で凹, かつ, <math>U_{i}(0)=0\, </math> とする. すると, 2人に実現可能な利得の集合は, <math>P=\{(U_{1}(x), U_{2}(1-x))|1\ge x\ge 0\}\, </math> となり, 図2の曲線 <math>AB\, </math> のようになる.

　ゲームは次のように進行する. まず第1期に, プレイヤー1が, 分配案として, 集合 <math>P\, </math> 上の1点 <math>(u_{1}, u_{2})\, </math> をプレイヤー2に提示する. プレイヤー2が了承すれば, 分配案が実現してゲームは終了し, 却下した場合には, 第2期に入る. 以下, 次の期に入る毎にプレイヤーの役割が交代されて, 第1期と同様な手番でゲームが進行する.

　2人は共通の割引率 <math>\delta\in(0, 1)\, </math> を持つとし, プレイヤー <math>i\, </math> が, 第 <math>t\, </math> 期に利得 <math>u_{i}\, </math> を得た場合の現在利得は, <math>\delta^{t-1}u_{i}\, </math> であるとする. そして, これを交互オファーゲームの利得とする. 2人が永久に分配案を了承しない場合のゲームの利得は0とする.

　ルビンシュタインは, この交互オファーゲームの[[部分ゲーム完全均衡]]利得<math>u^*=(u_1^*, u_2^*)\, </math>は一意に定まり, <math>\delta\rightarrow 1\, </math>のとき, <math>u^*\, </math>は<math>P\, </math>の上で<math>u_1u_2\, </math>を最大にする点に収束することを証明した [1].

　この結果から, 割引率が1に収束するとき, 均衡利得 <math>u^{*}\, </math> は, 集合 <math>P\, </math> をパレート最適集合に持つ協力実現可能集合と基準点が <math>d=0\, </math> である交渉問題の, ナッシュ解の妥結点となることが分かる. つまり, 合意遅延のコストが十分小さい場合, 交互オファーゲームは, ナッシュ解の具体的交渉過程モデルの1つとなる. [[ナッシュプログラム]]参照)

　ナッシュ解のみでなく, <math>{\rm KS}\, </math>解や均等解についても, その非協力ゲームモデルを与える研究が行われている. そして, <math>n\, </math> 人交渉問題の交渉解や情報不完備な非協力交渉ゲームの研究も進んでいる [1], [2].

----
'''参考文献'''

[1] M. Osborne and A. Rubinstein, ''Bargaining and Markets'', Academic Press, 1990.

[2] W. Thomson, "Cooperative Models of Bargaining," in ''Handbook of Game Theory with Economic Applications'' ed. by R. Aumann et al, 1992, vol. 2, 1238-1284.

[3] J. Nash, "The Bargaining Problem," ''Econometrica'', '''18''' (1950), 155-162.

[[category:ゲーム理論|こうしょうげーむ]]

《協力ゲーム理論》

2007-08-09T04:06:39Z

H.Yamaguchi:

'''【きょうりょくげーむりろん (cooperative game theory) 】'''

1　協力ゲーム理論

　[[プレイヤー]]間で話し合いが行われ, 話し合いの結果到達した合意に拘束力がある状況を協力ゲームといい, このような状況を扱う理論を[[協力ゲーム理論]] (cooperative game theory) という. 協力ゲームは, プレイヤーの数が2人か3人以上かによって大きく状況が異なり, それぞれ別々に理論が発展してきている.

2　2人協力ゲーム

　プレイヤーが2人の場合には, 2人のプレイヤーが話し合いの結果協力して行動するかどうか, また, 協力した場合には, その結果得られる利得をどのように分配するかの交渉が問題になる. 従って, 2人協力ゲームを[[2人交渉問題]] と呼ぶこともある.

　2人協力ゲームの主たる解は, ナッシュ (J. F. Nash) によって与えられたもので, [[ナッシュ解]] ないしはナッシュ交渉解と呼ばれている. ナッシュは, 公理論的なアプローチによりナッシュ解を導いた. まず, 2人のプレイヤーが協力して実現できる [[利得 (ゲームの)|利得]]の対の全体と, 交渉が決裂したときに2人のプレイヤーが得る利得を明らかにし, これによって2人のプレイヤーの交渉の場を定めた. 前者を実現可能集合, 後者を交渉の基準点という. ついで, 交渉の妥結点が満たすべき性質を4つあげ, その4つの性質をすべて満たす解は, 交渉の場の中の唯1つの利得の対に定まり, 交渉の基準点からの2人のプレイヤーの利得の増分の積を最大にする点で与えられることを示した. これがナッシュ解である.

　ナッシュは, 1つの交渉のプロセスとして, 2人のプレイヤーがそれぞれの獲得したい利得を同時に言い合う非協力ゲームを考え, そのナッシュ均衡によってナッシュ解を達成できないかと考えた. ナッシュのこの試みは, 協力ゲームの解を非協力ゲームの均衡点として分析しようとする[[ナッシュプログラム]] の始まりであった. 後に, ルビンシュタイン(A. Rubinstein) が, 2人のプレイヤーが交互に2人の取り分を提示しあい, 提示された方がそれに同意すればゲームは終了し, 同意しなければそのプレイヤーが新たな提示を行うという[[交互オファーゲーム]]を提案し, 将来の利得がそれほど割り引かれない場合には, その[[部分ゲーム完全均衡]] としてナッシュ解が達成されることを示した.

　ナッシュ解は, 労使の賃金交渉, 商品の売り手と買い手の交渉, 2国間の交渉など, 様々な交渉の分析に用いられている.

3　多人数協力ゲーム

　3人以上の協力ゲームになると, 単に全員が協力するかどうかだけではなく, 部分的な協力関係を考える必要が生じ, 状況は2人協力ゲームに比べ複雑になる. 3人以上の協力ゲームは, 一般に<math>n\, </math>人協力ゲームと呼ばれる. <math>n\, </math>人協力ゲームにおける関心は, プレイヤー間でどのような協力関係が結ばれ, その結果得られた利得をプレイヤー間でどのように分け合うか, ないしは分け合うべきかということである.

　フォンノイマン (J. von Neumann) とモルゲンシュテルン (O. Morgenstern) は, <math>n\, </math>人協力ゲームにおいて, 協力関係を結んだプレイヤーのグループを[[提携]] と呼び, 提携それぞれに対して, それが獲得できる利得を与える関数を [[特性関数 (ゲーム理論の)|特性関数]]と呼んだ[8]. 特性関数によって表現された<math>n\, </math>人協力ゲームを[[提携形ゲーム]]ないしは特性関数形ゲームという.

　提携形ゲームでは, 特性関数の[[優加法性 (ゲーム理論における)|優加法性]]からプレイヤー全員の提携が形成されることは前提とし, 全員が協力したときに得られる利得をどのように分配すればよいかということがこれまでの主たる研究のテーマであった.

　提携形ゲームにおける最初の解は, フォンノイマンとモルゲンシュテルンによるものであり, [[安定集合]]ないしはフォンノイマン・モルゲンシュテルン解と呼ばれている. 提携形ゲームにおいては, プレイヤー間の利得分配の基準をどのように与えるかによって, これ以外にも, [[コア]], [[交渉集合]], [[カーネル (ゲーム理論における)|カーネル]], [[仁]], [[シャープレイ値]]など様々な解が提案されてきている. 安定集合, コア, 交渉集合, カーネルは一般に集合として与えられる解であり, 仁, シャープレイ値は唯1点からなる解である.

　これらの解のうち, 適用例が多いのは, どの提携にも不満を持たせない利得の分配であって, その考え方が受け入れられやすいコア, および1点からなる解である仁, シャープレイ値である. コアは, 経済学において, 市場における取引の分析など様々な分野で用いられており, 経済学における1つの重要な解概念となっている.

　仁, シャープレイ値は費用分担, 便益分配などの計画問題の解決案としてよく用いられている. よく知られた例としては, 水資源共同開発における費用分担, 大学内の電話料金の分担, 飛行場の滑走路補修費用の機種別分担などがある. また, シャープレイ値はプレイヤーの力関係を反映する解であるため, 議会における政党の影響力を評価するパワー指数としても用いられている.

4　協力ゲームの最近の発展

　協力ゲームにおける最近の理論的発展の主たるものは, 提携形成の分析であろう. これまでの提携形ゲームの研究では, プレイヤーの交渉を通してどのような提携が形成されるかという問題はほとんど分析されてこなかったが, 最近になって, ようやく提携形成の研究が盛んに行われるようになってきている. 協力ゲームの様々な解を用いるもの, 非協力ゲームからのアプローチを試みるもの, など様々なアプローチがある.

　いま1つの研究の方向は, [[戦略形ゲーム]], [[展開形ゲーム]]を用いた協力行動の分析である. これまでの協力ゲームの分析は, 提携形ゲームを用いたものがほとんどであった. しかしながら, 戦略形ゲーム, 展開形ゲームにおいてプレイヤーが共同で戦略を選択することも考えられ, これによって, 協力行動を分析することもできる. このような分析はなにも新しいものではないが, 提携形では分析し得ないプレイヤー間の協力関係を分析する方法として重要なものとなるであろう.

　以上の2つの方向の研究を進める上ではもちろんのこと, 今後, 協力ゲーム理論と[[非協力ゲーム理論]]の融合をはかることは, ゲーム理論の発展の上で非常に重要であると思われる.

5　協力ゲーム理論の文献

　協力ゲーム理論を扱った日本語の文献としては [7], また, 最近のものとしては [2], [3], [4], [5], [6] がある. 協力ゲームの解についてのこれまでの研究のサーベイは, [1] に詳しい.

----
'''参考文献'''

[1] R. J. Aumann and S. Hart, eds., ''Handbook of Game Theory Volume I, Volume II'', North-Holland, 1992, 1994.

[2] 船木由喜彦, 『エコノミックゲームセオリー』, サイエンス社, 2001.

[3] 武藤滋夫, ゲーム理論入門, 日本経済新聞社, 2001.

[4] 中山幹夫, 『はじめてのゲーム理論』, 有斐閣, 1997.

[5] 岡田章, 『ゲーム理論』, 有斐閣, 1996.

[6] 鈴木光男, 『新ゲーム理論』, 勁草書房, 1994.

[7] 鈴木光男, 武藤滋夫, 『協力ゲームの理論』, 東京大学出版会, 1985.

[8] J. von Neumann and O. Morgenstern, ''Theory of Games and Economic Behavior, 3rd ed.'', Princeton University Press, 1953.

[[category:ゲーム理論|きょうりょくげーむりろん]]

《展開形ゲーム》

2007-08-09T03:58:33Z

H.Yamaguchi:

'''【てんかいけいげーむ (game in extensive form) 】'''

　[[展開形ゲーム]] (game in extensive form) はプレイヤーの手番の系列を[[ゲームの木]] (game tree) を用いて表現するモデルである. ゲームの木 <math>K\, </math> はグラフ理論でいう有向木で, 木の分岐点はプレイヤーが選択肢を選ぶ手番, 枝は[[プレイヤー]]の選択肢あるいは行動を表す. 木の始点から終点までの経路をゲームの1つのプレイという.

　プレイヤー分割 <math>P=[P_{0}, P_{1}. \cdots, P_{n}]\, </math> は, ゲームの木 <math>K\, </math> の分岐点の全体を <math>n+1\, </math> 個の部分集合に分割する. <math>P_{i}\ (i=1, 2, \cdots, n)\, </math> はプレイヤー <math>i\, </math> の手番の集合を表す. <math>P_{0}\, </math> に含まれる手番は偶然手番とよばれ, プレイヤーの意思とは無関係な偶然機構によって枝が選択される. 天候やトランプゲームでランダムにカードを配るなどは, 偶然手番の典型的な例である. 偶然手番に対しては枝の選択を行なう確率分布 <math>p\, </math> が付与される.

　ゲームの情報分割 <math>U=[U_{0}, U_{1}, \cdots, U_{n}]\, </math> は,プレイヤー分割<math>P\, </math> の細分割である.各 <math>i=1, 2, \cdots, n\, </math> に対して <math>U_{i}=[u_{i1}, u_{i2}, \cdots, u_{im_{i}}]\, </math>はプレイヤー <math>i\, </math> の手番の集合 <math>P_{i}\, </math> を <math>m_{i}\, </math> 個の非空な部分集合に分割する. <math>U_{i}\, </math> に属する部分集合 <math>u_{ij}\ (j=1, 2, \cdots, m_{i})\, </math> をプレイヤー <math>i\, </math> の[[情報集合]] (information set) という.プレイヤーは行動を選択するとき,自分の手番がどの情報集合に属するかは知っているが,情報集合の中のどの分岐点であるかは知らない.

　ゲームの[[利得関数]] <math>h\, </math> は,ゲームの木 <math>K\, </math> の各終点 <math>z\, </math> に対してプレイヤーの[[利得 (ゲームの)|利得]]ベクトル <math>h(z)=(h_{1}(z), h_{2}(z), \cdots, h_{n}(z))\, </math> を対応させる.

　形式的には, 展開形ゲーム <math>\Gamma\, </math> は以上の5つの要素の組 <math>(K, P, p, U, h)\, </math> によって定義される. これらの5つの構成要素をゲームのルールという.

<center><table><tr><td align=center>[[画像:0072-a-g-04f1-mof.png|center|図１：展開形ゲーム]]</td></tr>
<td align=center>図１：展開形ゲーム</td></table></center>

　展開形ゲームの例として図1を考える.プレイヤー1と2の情報分割はそれぞれ <math>U_{1}=[u_{1}], U_{2}=[u_{21}, u_{22}]\, </math> である.図1では最初にプレイヤー1がRとLの2つの行動のうち1つを選択する. 次に, プレイヤー2はプレイヤー1の選択を知った上で, RとLのうちから1つの行動を選択する.ゲームは4つの終点をもち, 終点に付与されている利得ベクトルは上の数字がプレイヤー1の利得, 下の数字がプレイヤー2の利得を表す.

　図1のゲームのように, プレイヤーのすべての情報集合がただ1つの分岐点から成るゲームを[[完全情報ゲーム]] (game with perfect information) といい, そうでないゲームを不完全情報ゲーム (game with imperfect information) という. 完全情報ゲームでは, すべての手番においてプレイヤーはゲームの過去のプレイの経過を完全に知った上で行動を選択できる. チェスや将棋は完全情報ゲームである.

　展開形ゲームの部分木でそれ自身が展開形ゲームの構造をもつものを部分ゲームという. 図1のゲームは, 情報集合 <math>u_{21}\, </math> と <math>u_{22}\, </math> から始まる2つの部分ゲームをもつ.

　プレイヤー <math>i\, </math> の各情報集合 <math>u\in U_{1}\, </math> に対して <math>u\, </math> における選択肢の集合上の1つの確率分布 <math>b_{i}(u)\, </math> を対応させる関数 <math>b_{i}\, </math> をプレイヤー <math>i\, </math> の[[行動戦略]] (behavior strategy) という. 特に, すべての情報集合に対して1つの選択肢を確定的に対応させる行動戦略を[[純戦略]]という.

　例えば, 図1のゲームにおいて, プレイヤー1の純戦略 <math>\pi_{1}\, </math> はRとLの2通りであり, プレイヤー2の純戦略 <math>\pi_{2}\, </math> は, RR, RL, LR, LLの4通りである. ただし, 前の文字は情報集合 <math>u_{21}\, </math> でとる行動, 後の文字は情報集合 <math>u_{22}\, </math> でとる行動を表す. 図1の展開形ゲームから, プレイヤーの純戦略と利得の関係によって図2のような[[戦略形ゲーム]]を作ることができる.

<center><table width="310" border="1" cellspacing="2" cellpadding="0">
<tr>
<td width="30"><br></td>
<td>
<table width="280">
<tr>
<td align="center" width="70">LL</td>
<td align="center" width="70">LR</td>
<td align="center" width="70">RL</td>
<td align="center" width="70">RR</td>
</tr>
</table>
</td>
</tr>
<tr>
<td align="center">R</td>
<td>
<table width="280">
<tr>
<td align="center" width="70">1, 1*</td>
<td align="center" width="70">1, 1*</td>
<td align="center" width="70">-2, 0</td>
<td align="center" width="70">-2, 0</td>
</tr>
</table>
</td>
</tr>
<tr>
<td align="center">L</td>
<td>
<table width="280">
<tr>
<td align="center" width="70">-1, 0</td>
<td align="center" width="70">0, 1</td>
<td align="center" width="70">-1, 0</td>
<td align="center" width="70">0, 1*</td>
</tr>
</table>
</td>
</tr>
</table><br>図2：図1の展開形ゲームから作られた戦略形ゲーム</center>

　プレイヤーの行動分析のための最も基本的なゲームの解の概念は, ナッシュ (J. F. Nash) によって定義された非協力均衡点である. 一般に[[ナッシュ均衡]]と呼ばれている. 展開形ゲームの行動戦略の組 <math>b^{*}=(b_{1}^{*}, b_{2}^{*}, \cdots, b_{n}^{*})\, </math> がナッシュ均衡であるとは,すべてのプレイヤー <math>i=1, 2, \cdots, n\, </math> のすべての行動戦略 <math>b_{i}\, </math> に対して,

<center>
<math>H_{i}(b^{*}) \ge H_{i}(b^{*}/b_{i})\, </math>
</center>
　

が成り立つことである. ただし, <math>b^{*}/b_{i}\, </math> は <math>b^{*}\, </math> からプレイヤー <math>i\, </math> だけが戦略を <math>b_{i}^{*}\, </math> から <math>b_{i}\, </math> に変更してできる行動戦略の組を表し, <math>H_{i}\, </math> はプレイヤー i の期待利得関数を表す.

　完全情報ゲームのナッシュ均衡は, 最初に, 終点に一番近い分岐点で, その手番のプレイヤーの利得を最大にする最適戦略を求め, 以下順次, ゲームの木を後向きに解くことによって計算できる. 例えば, 図1のゲームで情報集合 <math>u_{21}\, </math> と <math>u_{22}\, </math> におけるプレイヤー2の最適戦略はそれぞれLとRである. このとき, 情報集合 <math>u_{1}\, </math> におけるプレイヤー1の最適戦略はRであり, 純戦略の組 (R, LR) はゲームのナッシュ均衡である. このようなナッシュ均衡の計算方法を, ゲームの後向き帰納法という. キューン (H. Kuhn) は, <math>n\, </math> 人[[完全情報ゲーム]] は純戦略の範囲で少なくとも1つのナッシュ均衡をもつことを証明した [1].

　図1のゲームは (R, LR) の他に図2の利得行列で＊をつけたナッシュ均衡をもつ. しかし, これらのナッシュ均衡は均衡プレイ上にない分岐点ではプレイヤーの最適戦略を導かないという欠点をもつ. ゼルテン (R. Selten) はナッシュ均衡のこのような欠点を解消するために, より強い均衡概念として, すべての部分ゲーム上にナッシュ均衡を導く[[部分ゲーム完全均衡]] (subgame perfect equilibrium) を定義した [3].

　ゼルテンの研究以後, 展開形ゲームの理論は大きく進展し, 現在, ゲーム的状況におけるプレイヤーの戦略的行動を解明する基礎理論としてORや経済学を始め広範囲の分野に応用されている.

　展開形ゲームについて詳しくは, [2] を参照されたい.

----
'''参考文献'''

[1] H. W. Kuhn, "Extensive Games and the Problem of Information," in H. W. Kuhn and A. Tucker(eds.), ''Contributions to the Theory of Games'', Vol. II, Annals of Mathematics Studies 28, Princeton University Press, 1953, 193-216.

[2] 岡田章, 『ゲーム理論』, 有斐閣, 1996.

[3] R. Selten, "Reexamination of the Perfectness Concept for Equilibrium Points in Extensive Games," ''International Journal of Game Theory'', '''4''' (1975), 25-55.

[[category:ゲーム理論|てんかいけいげーむ]]

《戦略形ゲーム》

2007-08-09T03:57:08Z

H.Yamaguchi:

'''【せんりゃくけいげーむ (game in strategic form) 】'''

　ゲームに参加する[[プレイヤー]]の集合を<math>N\, </math>, 各プレイヤー<math>i\, </math>のとりうる[[戦略 (ゲーム理論における)|戦略]]の全体を<math>S_i\, </math>, および<math>S=S_1 \times \cdots \times S_n\, </math> 上で定義された各プレイヤー<math>i\, </math> の[[フォンノイマン・モルゲンシュテルン効用関数]] (von Neumann-Morgenstern utility function) を<math>u_i\, </math> とするとき,

<center>
<math>G=(N; S_1, \ldots , S_n; u_1, \ldots , u_n)\, </math>
</center>

を[[戦略形ゲーム]] (game in strategic form) または[[標準形ゲーム]] (game in normal form) という. <math>N\, </math> と<math>S_i\, </math> がすべて有限集合であるとき, <math>G\, </math> を有限ゲームという. 効用関数<math>u_i\, </math> は, また[[利得関数]] (payoff function) ともいい, その値を利得という.

　戦略形で書かれたゲームは, 特にことわらない限り[[非協力ゲーム]]である. 戦略の数が有限な2人ゲームは次のような[[利得双行列 (ゲームの)|利得双行列]] (payoff bimatrix) で表現することができるので, [[双行列ゲーム]] (bimatrix game) ということがある.

<center>

[[画像:sk-0071-a-g-03-1.png]]

[[スタイル検討#戦略形ゲーム (0071-a-g-03-1)|スタイル検討]]
</center>



　ここに, 縦の<math>1, \ldots, m\, </math>はプレイヤー1の戦略, 横の<math>1, \ldots, n\, </math>はプレイヤー2の戦略であり, <math>a_{ij}, b_{ij}\, </math> は, プレイヤー1, 2が各々戦略<math>i, \ j\, </math>をとったときの, プレイヤー1, 2の利得である. <math>a_{ij}\, </math>を成分とする行列を<math>A\, </math>, <math>b_{ij}\, </math>を成分とする行列を<math>B\, </math>と表し, 利得双行列を簡単に<math>(A, B)\, </math>と表す. すべての<math>i, \ j\, </math>について, <math>a_{ij} + b_{ij} = 0\, </math>となる場合が[[2人ゼロ和ゲーム]] (two-person zerosum game) の戦略形である. 行列<math>B\, </math>は<math>A\, </math>の符号を変えたものであり, 行列<math>A\, </math>だけでゲームを記述できるので2人ゼロ和ゲームを[[行列ゲーム]] (matrix game) ということもある.

　双行列ゲーム<math>(A, B)\, </math>において, 各プレイヤーの[[混合戦略]] (mixed strategy) を各々<math>p=(p_1, \ldots , p_m)\, </math>, <math>q=( q_1, \ldots , q_n)\, </math> とすると, 各プレイヤーの利得の期待値 (期待利得) は各々 <math>pAq^{\top}\, </math> および <math>pBq^{\top}\, </math> で与えられる. <math>q^{\top}\, </math>は<math>q\, </math>の転置ベクトルを表す. また, 混合戦略に対してもとの戦略を[[純戦略]] (pure strategy) という. [[ナッシュ均衡]] <math>(p^*, q^*)\, </math>は, [[非協力ゲーム理論]]の項で述べた定義によって,

<center>
<math>p^*Aq^{*\top} \ge pAq^{*\top}, \ p^*Bq^{*\top} \ge p^*Bq^{\top}, \ \mbox{ for all } p, \ q \, </math>
</center>

をみたす混合戦略の組である. とくに, ゼロ和ゲームでは, <math>B=-A\, </math>であるから

<center>
<math>pAq^{*\top} \le p^*Aq^{*\top} \le p^*Aq^{\top} , \ \ \mbox{ for all } p, \ q \, </math>
</center>

となり, これから[[ミニマックス定理 (ゲーム理論における)|ミニマックス定理]] (minimax theorem)　

<center>
<math>\mbox{max}_{p} \mbox{min}_{q} \ pAq^{\top} \ =\ \mbox{min}_{q}\mbox{max}_{p}\ \ pAq^{\top} \, </math>
</center>

が導かれ, さらにこの値は<math>p^*Aq^{*\top}\, </math>に等しい. 左辺の値をマックスミニ値 (maxmin value), 右辺の値をミニマックス値(minimax value), さらに, この共通の値を[[ゲームの値]] (value of a game) という. また, このときの戦略<math>p^*, \ q^*\, </math>を各々[[マックスミニ戦略]] (maxmin strategy), [[ミニマックス戦略]] (minimax strategy) という.
　次に示すのは, 左が囚人のジレンマ (prisoner's dilemma), 右が逢い引きのジレンマ (battle of the sexes) という名で知られる有名な双行列ゲームである.

<center>

[[画像:sk-0071-a-g-03-2.png]]

[[スタイル検討#戦略形ゲーム (0071-a-g-03-2)|スタイル検討]]
</center>



囚人のジレンマでは, 純戦略の組 <math>(d, \ d)\, </math>のみが, また, 逢い引きのジレンマでは, 純戦略の組 <math>(a, \ a)\, </math>および<math>(b, \ b)\, </math>と, 混合戦略の組 <math>((2/3, 1/3)\, </math>, <math>(1/3, 2/3))\, </math>がナッシュ均衡である. とくに, 囚人のジレンマのナッシュ均衡では, 戦略<math>d\, </math>は相手のすべての戦略に対する[[最適反応 (ゲーム理論における)|最適反応]] (best reply) となっている. このようなナッシュ均衡を, [[支配戦略]]均衡 (dominant strategy equilibrium) ということがある. 逢い引きのジレンマには支配戦略は存在しない. また, 逢い引きのジレンマでは, 混合戦略ナッシュ均衡における利得の組<math>(2/3, \ 2/3)\, </math>は, たとえば純粋戦略ナッシュ均衡<math>(a, \ a)\, </math>における利得の組<math>(2, \ 1)\, </math>に対して各プレイヤーについて劣っている. このとき, 利得の組<math>(2/3, \ 2/3)\, </math>は<math>(2, \ 1)\, </math>に[[パレート支配]] (Pareto dominate) されるという.

　戦略形ゲームにおいて, もし, 各プレイヤーが共通の偶然機構にもとづいて戦略を選ぶことが許されているならば, 各プレイヤーは互いに相関した行動をとることができる. このような戦略を[[相関戦略]] (correlated strategy) という. たとえば, 逢い引きのジレンマで, コインを投げて表が出たら戦略の組<math>(a, \ a)\, </math>, 裏が出たら<math>(b, \ b)\, </math>とすることに2人が合意したとしよう. つまり, 2人とも, 表が出たら<math>a\, </math>をとり, 裏が出たら<math>b\, </math>をとるという相関戦略をとるものとする. このような合意がナッシュ均衡になるとき, すなわち, 相関戦略の組がナッシュ均衡となっているとき, これを[[相関均衡]] (correlated equilibrium) という. 上に述べた相関戦略の組は相関均衡であり, 2人の期待利得はともに<math>3/2\, </math>となることが容易にわかる. また, 混合戦略均衡は互いに独立な相関戦略からなる相関均衡にほかならない. 相関均衡の正式な定義については, たとえば [3] など参照. 　

　以上のゲームでは, 戦略形<math>G\, </math>についての知識がすべてのプレイヤーの間で[[共有知識]] (common knowledge) であると仮定されており, これらは[[完備情報ゲーム]] (game with complete information) といわれている. 他方, 不完備情報ゲームはハルサーニ(J. C. Harsanyi) [2] の定式化によって分析できるようになった. たとえば, 利得関数<math>u_i\, </math>に関する情報が不完備な場合は, まず有限個のパラメター<math>t_{i1}, t_{i2}, \ldots, t_{ik} \in T_i\, </math>を導入し, プレイヤー<math>i\, </math>の利得関数は, そのタイプによって, 有限個の利得関数<math>u_i(\cdot|t_{i1}), u_i(\cdot| t_{i2}), \ldots, u_i(\cdot| t_{ik})\, </math> (以下, まとめて<math>u_{i}(\cdot|t_{i})\, </math>と表す. )のうちのどれか1つに定まる, と定式化し直すことにより, <math>u_{i}\, </math>に関する不完備情報を表現する. この<math>t_i \in T_i\, </math>をプレイヤー<math>i\, </math>のタイプという. 各プレイヤー<math>i\, </math>は自分はどのタイプであるかを知っているが, 他のプレイヤーのタイプは知らない. ただし, 他のすべてのプレイヤーのタイプ<math>t_{-i} = (t_1 , \ldots, t_{i-1}, t_{i+1}, \ldots , t_n )\, </math>について条件付き確率<math>p_i(t_{-i}|t_i)\, </math>によって<math>t_{-i}\, </math>を推測することができるとする. こうして, 新たな戦略形ゲーム

<center>
<math>G'= (N, S_1, \ldots , S_n;
p_1, \ldots , p_n; T_1, \ldots, T_n;
u_1(\cdot|t_1), \ldots , u_n(\cdot|t_n))\, </math>
</center>

がえられる. これを[[ベイジアンゲーム]] (Bayesian game) という. また, 関数<math>s_i : T_i \rightarrow S_i\, </math>をベイジアンゲームの戦略という. すなわち, プレイヤー<math>i\, </math>は, 自分のタイプを知ってはいるが, どのタイプであったとしてもそのもとでの行動を指定しておくことがこの場合の戦略である. するとナッシュ均衡は, すべてのプレイヤー<math>i\, </math>とタイプ<math>t_i\, </math>および<math>a_{i} \in S_{i}\, </math> について次の条件をみたす戦略の組<math>s^*=(s^*_1, \ldots , s^*_n)\, </math>である. この戦略の組を, [[ベイジアンナッシュ均衡]] (Bayesian Nash equilibrium) という.

<center>
<math>\sum_{t_{-i} \in T_{-i}} u_i(s^*(t)|t_i)p_i(t_{-i}|t_i)
\ \ge\ \sum_{t_{-i} \in T_{-i}} u_i(s^*_{-i}(t_{-i}), a_i
| t_i)p_i(t_{-i}|t_i)\, </math>
</center>

ただし, <math>s^*(t)=(s^*_{-i}(t_{-i}), s^*_i(t_i))=(s^*_1(t_1), \ldots, s^*_n(t_n))\, </math>である. ベイジアンゲームは, 80年代以降, 情報経済学や産業組織論などの新しい分野の発展に大きく貢献している. これについてはたとえば, [1] を参照.

----
'''参考文献'''

[1] R. Gibbons, ''Game Theory for Applied Economists'', Princeton University Press, 1992. /福岡正夫, 須田伸一, 『経済学のためのゲーム理論入門』, 創文社, 1995.

[2] J. C. Harsanyi, "Games with Incomplete Information Played by `Bayesian' Players, parts I, II and III", ''Management Science'', '''14''' (1967-8), 159-182, 320-334, 486-502.

[3] M. J. Osborne and A. Rubinstein, ''A Course in Game Theory'', MIT Press, 1994.

[[category:ゲーム理論|せんりゃくけいげーむ]]

《ゲーム理論》

2007-08-09T03:53:10Z

H.Yamaguchi:

'''【げーむりろん (game theory) 】'''

1　ゲーム理論とは

　[[ゲーム理論]] (game theory) は, 複数意思決定主体の存在する状況における決定理論であり, フォンノイマン (J. von Neumann) とモルゲンシュテルン (O. Morgenstern) による大著"Theory of Games and Economic Behavior"([17])をその出発点とする. 複数の主体が存在するから, 主体間で利害の対立がある場合もあるし, 利害を共にする場合もある. このような状況において, 各意思決定主体はどのような行動をとるか, ないしは, とるべきかを数理的に分析することがゲーム理論の目的である. ゲーム理論では, 意思決定主体を[[プレイヤー]] (player), 各プレイヤーが持つ行動の計画を[[戦略 (ゲーム理論における)|戦略]] (strategy), プレイヤーがそれぞれの戦略をとった時に, 各プレイヤーが得られるもの, ないしは, それに対する評価値を[[利得 (ゲームの)|利得]] (payoff) と呼ぶ.

　ゲーム理論は, 想定するプレイヤーの行動様式の違いによって, [[非協力ゲーム理論]], [[協力ゲーム理論]]の2つに分かれて発展してきている. 非協力ゲーム理論は, プレイヤー間の話し合いはなく各プレイヤーがそれぞれ独立に戦略を決定する状況か, ないしは, たとえ話し合いがあったとしてもその結果得られた合意に拘束力のない状況を扱う. それに対して, 協力ゲーム理論は, プレイヤー間に話し合いのあることを前提とし, 話し合いの結果得られた合意に拘束力がある状況を扱う. 非協力ゲーム理論の扱うゲームを非協力ゲーム, 協力ゲーム理論の扱うゲームを協力ゲームと呼ぶ.

2　非協力ゲーム理論

　非協力ゲームは, 各プレイヤーの戦略と利得を用いて表現する[[戦略形ゲーム]]と, プレイヤーの意思決定を時間の流れと共に[[ゲームの木]]を用いて詳しく表現する[[展開形ゲーム]]に分かれる.

　非協力ゲーム理論における主要な解は, ナッシュ (J. F. Nash) によって与えられた[[ナッシュ均衡]]である. ナッシュ均衡とは, 各プレイヤーの戦略が他のプレイヤーの戦略の組に対する[[最適反応 (ゲーム理論における)|最適反応]]戦略になっているような戦略の組である. 戦略形ゲームにおいて, もともとの戦略が有限個である場合には, それらを確率混合して用いる[[混合戦略]]まで考えれば, ナッシュ均衡は必ず少なくとも1つ存在することが知られている.

　展開形ゲームは, プレイヤーの意思決定の順序, プレイヤーが意思決定の際に持っている情報などを詳細に表現できるものである. また, 展開形ゲームを考えると, ナッシュ均衡のうちのいくつかはその合理性に問題のあることが明らかになる. そのため, [[部分ゲーム完全均衡]], [[逐次均衡]], [[完全均衡]]などのナッシュ均衡の精緻化が展開形ゲームにおいて提唱されてきている.

3　協力ゲーム理論

　協力ゲームは, プレイヤーが2人の場合と3人以上の場合では, 状況が大きく異なり, それぞれ別々に理論が発達してきている.

　2人の協力ゲームでは, プレイヤーが話し合いの結果, 協力して行動するかどうか, また, 協力した場合には, その結果得られる利得をどのように分配するかの交渉が, 問題になる. 従って, 2人の協力ゲームを[[2人交渉問題]]と呼ぶこともある. 2人協力ゲームの主たる解もナッシュによって与えられたもので, [[ナッシュ解]]ないしはナッシュ交渉解と呼ばれている.

　3人以上の協力ゲームになると, 単に全員が協力するかどうかだけでなく, 部分的な協力関係を考える必要が生じ, 分析が難しくなる. 3人以上の協力ゲームは, 一般に<math>n\, </math>人協力ゲームと呼ばれる. フォンノイマンとモルゲンシュテルンは, <math>n\, </math>人協力ゲームにおいて, 協力関係を結んだプレイヤーのグループを[[提携]]と呼び, 提携それぞれに対して, それが獲得できる利得を与える関数を[[特性関数 (ゲーム理論の)|特性関数]]と呼んだ. 特性関数による<math>n\, </math>人協力ゲームの表現を[[提携形ゲーム]]ないしは特性関数形ゲームという. 提携形ゲームにおいては, プレイヤー間の利得分配の基準をどのように与えるかによって, [[安定集合]], [[コア]], [[交渉集合]], [[カーネル (ゲーム理論における)|カーネル]], [[仁]], [[シャープレイ値]]など, 様々な解が提案されてきている.

4　ゲーム理論の応用

　ゲーム理論がこれまで最大の貢献をなした分野は経済学であろう. 最初は, 交換市場や生産市場の[[競争均衡]]のコアによる新たな特徴付けなど, 協力ゲームの応用が中心であった. ついで, 産業組織論などにおいて企業競争の非協力ゲーム理論による分析が進み, 1980年代に入って爆発的な勢いで情報経済学をはじめ, ミクロ経済学の様々な分野に非協力ゲーム理論が浸透していった. いまでは, 経済学だけでなく, 政治学, 社会学などにおいてもゲーム理論は大きな貢献をなすものとなっている. これらの貢献に基づき, 1994年にはナッシュ,ハルサーニ(J.C.Harsanyi), ゼルテン(R.Selten)の3名, 2005年にはオーマン(R.J.Aumann), シェリング(T.C.Schelling)の2名のゲーム理論研究者がノーベル経済学賞を授与されている.

　ＯＲにおいても, 第2次世界大戦の軍事研究に始まり, 企業など組織における意思決定, 社会的, 公共的意思決定など, 非協力ゲーム, 協力ゲームが用いられているところは多い. 最も多い適用例は, 費用分担, 便益分配などの計画問題に対するものであろう. また, 投票による意思決定システムの協力ゲーム, 非協力ゲームによる分析もよく行われている.

5　最近のゲーム理論の発展

　最近のゲーム理論の発展で最も重要なものは, プレイヤーの限定合理性をとりこんだ研究であろう. ナッシュ均衡と部分ゲーム完全均衡などその精緻化は, プレイヤーの合理性を追求した結果得られた解であったが, これらの解が, 必ずしもわれわれが現実に経験する結果を導かないことが, 様々なゲーム的状況の分析から明らかになってきた.

　そこで出てきたのが, プレイヤーは必ずしも完全には合理的ではないとする[[限定合理性]]の考え方である. 限定合理性に対する１つのアプローチが, 進化ゲーム理論と学習であり, これらの理論によって, 社会における慣習, 制度などの形成過程が明らかにされるのではないかと期待されている.

　いま1つの重要なアプローチが, 実際に人間を使った[[実験 (ゲーム理論における)|実験]]によるゲーム理論の再検証である. 様々なゲームにおける実験が行われており, われわれ人間は, ゲーム理論の解が導く行動を必ずしもとらない場合もありうることが明らかにされ, 実験結果を基に, 新たな理論の構築が模索されている.

6　ゲーム理論の文献

　ゲーム理論の最近の一般的なテキストとしては, 和書では, [3], [8], [10], [12], [15], [16], 洋書では, [2], [4], [9], [13], [14], また, ゲーム理論のさまざまな分野への応用をまとめたものとして [1], [5], [6], [7], [11]がある.

----
'''参考文献'''

[1] A. Dixit and B. Nalebuff, ''Thinking Strategically'', N.W.Norton, 1991. 菅野隆, 嶋津祐一, 『戦略的思考とは何か』, TBSブリタニカ, 1991.

[2] D. Fudenberg and J. Tirole, ''Game Theory'', MIT Press, 1991.

[3] 船木由喜彦, 『エコノミックゲームセオリー』, サイエンス社, 2001.

[4] R.Gibbons, ''Game Theory for Applied Economists'', Princeton University Press, 1992. 福岡正夫, 須田伸一, 『経済学のためのゲーム理論入門』, 創文社, 1995.

[5] 今井晴雄, 岡田章, 『ゲーム理論の新展開』, 勁草書房, 2002.

[6] 今井晴雄, 岡田章, 『ゲーム理論の応用』, 勁草書房, 2005.

[7] 梶井厚志, 松井彰彦, 『ミクロ経済学戦略的アプローチ』, 日本評論社, 2000.

[8] 武藤滋夫, 『ゲーム理論入門』, 日本経済新聞社, 2001.

[9] R.B.Myerson, ''Game Theory'', Harvard University Press, 1991.

[10] 中山幹夫, 『はじめてのゲーム理論』, 有斐閣, 1997.

[11] 中山幹夫, 武藤滋夫, 船木由喜彦, 『ゲーム理論で解く』, 有斐閣, 2000.

[12] 岡田章, 『ゲーム理論』, 有斐閣, 1996.

[13] M.J.Osborne and A.Rubinstein, ''A Course in Game Theory'', MIT Press, 1994.

[14] G.Owen, ''Game Theory, 3rd ed''., Academic Press, 1996.

[15] 佐々木宏夫, 『入門ゲーム理論』, 日本評論社, 2003.

[16] 鈴木光男, 『新ゲーム理論』, 勁草書房, 1994.

[17] J.vonNeumann and O.Morgenstern, ''Theory of Games and Economic Behavior, 3rd ed.'', Princeton University Press, 1953.

[[category:ゲーム理論|げーむりろん]]

《ゲーム理論》

2007-08-06T07:43:54Z

H.Yamaguchi:

'''【げーむりろん (game theory) 】'''

1　ゲーム理論とは

　[[ゲーム理論]] (game theory) は, 複数意思決定主体の存在する状況における決定理論であり, フォンノイマン (J. von Neumann) とモルゲンシュテルン (O. Morgenstern) による大著"Theory of Games and Economic Behavior"([17])をその出発点とする. 複数の主体が存在するから, 主体間で利害の対立がある場合もあるし, 利害を共にする場合もある. このような状況において, 各意思決定主体はどのような行動をとるか, ないしは, とるべきかを数理的に分析することがゲーム理論の目的である. ゲーム理論では, 意思決定主体を[[プレイヤー]] (player), 各プレイヤーが持つ行動の計画を[[戦略 (ゲーム理論における)|戦略]] (strategy), プレイヤーがそれぞれの戦略をとった時に, 各プレイヤーが得られるもの, ないしは, それに対する評価値を[[利得 (ゲームの)|利得]] (payoff) と呼ぶ.

　ゲーム理論は, 想定するプレイヤーの行動様式の違いによって, [[非協力ゲーム理論]], [[協力ゲーム理論]]の2つに分かれて発展してきている. 非協力ゲーム理論は, プレイヤー間の話し合いはなく各プレイヤーがそれぞれ独立に戦略を決定する状況か, ないしは, たとえ話し合いがあったとしてもその結果得られた合意に拘束力のない状況を扱う. それに対して, 協力ゲーム理論は, プレイヤー間に話し合いのあることを前提とし, 話し合いの結果得られた合意に拘束力がある状況を扱う. 非協力ゲーム理論の扱うゲームを非協力ゲーム, 協力ゲーム理論の扱うゲームを協力ゲームと呼ぶ.

2　非協力ゲーム理論

　非協力ゲームは, 各プレイヤーの戦略と利得を用いて表現する[[戦略形ゲーム]]と, プレイヤーの意思決定を時間の流れと共に[[ゲームの木]]を用いて詳しく表現する[[展開形ゲーム]]に分かれる.

　非協力ゲーム理論における主要な解は, ナッシュ (J. F. Nash) によって与えられた[[ナッシュ均衡]]である. ナッシュ均衡とは, 各プレイヤーの戦略が他のプレイヤーの戦略の組に対する[[最適反応 (ゲーム理論における)|最適反応]]戦略になっているような戦略の組である. 戦略形ゲームにおいて, もともとの戦略が有限個である場合には, それらを確率混合して用いる[[混合戦略]]まで考えれば, ナッシュ均衡は必ず少なくとも1つ存在することが知られている.

　展開形ゲームは, プレイヤーの意思決定の順序, プレイヤーが意思決定の際に持っている情報などを詳細に表現できるものである. また, 展開形ゲームを考えると, ナッシュ均衡のうちのいくつかはその合理性に問題のあることが明らかになる. そのため, [[部分ゲーム完全均衡]], [[逐次均衡]], [[完全均衡]]などのナッシュ均衡の精緻化が展開形ゲームにおいて提唱されてきている.

3　協力ゲーム理論

　協力ゲームは, プレイヤーが2人の場合と3人以上の場合では, 状況が大きく異なり, それぞれ別々に理論が発達してきている.

　2人の協力ゲームでは, プレイヤーが話し合いの結果, 協力して行動するかどうか, また, 協力した場合には, その結果得られる利得をどのように分配するかの交渉が, 問題になる. 従って, 2人の協力ゲームを[[2人交渉問題]]と呼ぶこともある. 2人協力ゲームの主たる解もナッシュによって与えられたもので, [[ナッシュ解]]ないしはナッシュ交渉解と呼ばれている.

　3人以上の協力ゲームになると, 単に全員が協力するかどうかだけでなく, 部分的な協力関係を考える必要が生じ, 分析が難しくなる. 3人以上の協力ゲームは, 一般に<math>n\, </math>人協力ゲームと呼ばれる. フォンノイマンとモルゲンシュテルンは, <math>n\, </math>人協力ゲームにおいて, 協力関係を結んだプレイヤーのグループを[[提携]]と呼び, 提携それぞれに対して, それが獲得できる利得を与える関数を[[特性関数 (ゲーム理論の)|特性関数]]と呼んだ. 特性関数による<math>n\, </math>人協力ゲームの表現を[[提携形ゲーム]]ないしは特性関数形ゲームという. 提携形ゲームにおいては, プレイヤー間の利得分配の基準をどのように与えるかによって, [[安定集合]], [[コア]], [[交渉集合]], [[カーネル (ゲーム理論における)|カーネル]], [[仁]], [[シャープレイ値]]など, 様々な解が提案されてきている.

4　ゲーム理論の応用

　ゲーム理論がこれまで最大の貢献をなした分野は経済学であろう. 最初は, 交換市場や生産市場の[[競争均衡]]のコアによる新たな特徴付けなど, 協力ゲームの応用が中心であった. ついで, 産業組織論などにおいて企業競争の非協力ゲーム理論による分析が進み, 1980年代に入って爆発的な勢いで情報経済学をはじめ, ミクロ経済学の様々な分野に非協力ゲーム理論が浸透していった. いまでは, 経済学だけでなく, 政治学, 社会学などにおいてもゲーム理論は大きな貢献をなすものとなっている. これらの貢献に基づき, 1994年にはナッシュ,ハルサーニ(J.C.Harsanyi), ゼルテン(R.Selten)の3名, 2005年にはオーマン(R.J.Aumann), シェリング(T.C.Schelling)の2名のゲーム理論研究者がノーベル経済学賞を授与されている.

　ＯＲにおいても, 第2次世界大戦の軍事研究に始まり, 企業など組織における意思決定, 社会的, 公共的意思決定など, 非協力ゲーム, 協力ゲームが用いられているところは多い. 最も多い適用例は, 費用分担, 便益分配などの計画問題に対するものであろう. また, 投票による意思決定システムの協力ゲーム, 非協力ゲームによる分析もよく行われている.

5　最近のゲーム理論の発展

　最近のゲーム理論の発展で最も重要なものは, プレイヤーの限定合理性をとりこんだ研究であろう. ナッシュ均衡と部分ゲーム完全均衡などその精緻化は, プレイヤーの合理性を追求した結果得られた解であったが, これらの解が, 必ずしもわれわれが現実に経験する結果を導かないことが, 様々なゲーム的状況の分析から明らかになってきた.

　そこで出てきたのが, プレイヤーは必ずしも完全には合理的ではないとする[[限定合理性]]の考え方である. 限定合理性に対する１つのアプローチが, 進化ゲーム理論と学習であり, これらの理論によって, 社会における慣習, 制度などの形成過程が明らかにされるのではないかと期待されている.

　いま1つの重要なアプローチが, 実際に人間を使った[[実験 (ゲーム理論における)|実験]]によるゲーム理論の再検証である. これも, 人間の合理性の限界を認識することからスタートしている. 様々なゲームにおける実験が行われており, われわれ人間は, ゲーム理論の解が導く行動を必ずしもとらない場合もありうることが明らかにされ, 実験結果を基に, 新たな理論の構築が模索されている.

6　ゲーム理論の文献

　ゲーム理論の最近の一般的なテキストとしては, 和書では, [3], [8], [10], [12], [15], [16], 洋書では, [2], [4], [9], [13], [14], また, ゲーム理論のさまざまな分野への応用をまとめたものとして [1], [5], [6], [7], [11]がある.

----
'''参考文献'''

[1] A. Dixit and B. Nalebuff, ''Thinking Strategically'', N.W.Norton, 1991. 菅野隆, 嶋津祐一, 『戦略的思考とは何か』, TBSブリタニカ, 1991.

[2] D. Fudenberg and J. Tirole, ''Game Theory'', MIT Press, 1991.

[3] 船木由喜彦, 『エコノミックゲームセオリー』, サイエンス社, 2001.

[4] R.Gibbons, ''Game Theory for Applied Economists'', Princeton University Press, 1992. 福岡正夫, 須田伸一, 『経済学のためのゲーム理論入門』, 創文社, 1995.

[5] 今井晴雄, 岡田章, 『ゲーム理論の新展開』, 勁草書房, 2002.

[6] 今井晴雄, 岡田章, 『ゲーム理論の応用』, 勁草書房, 2005.

[7] 梶井厚志, 松井彰彦, 『ミクロ経済学戦略的アプローチ』, 日本評論社, 2000.

[8] 武藤滋夫, 『ゲーム理論入門』, 日本経済新聞社, 2001.

[9] R.B.Myerson, ''Game Theory'', Harvard University Press, 1991.

[10] 中山幹夫, 『はじめてのゲーム理論』, 有斐閣, 1997.

[11] 中山幹夫, 武藤滋夫, 船木由喜彦, 『ゲーム理論で解く』, 有斐閣, 2000.

[12] 岡田章, 『ゲーム理論』, 有斐閣, 1996.

[13] M.J.Osborne and A.Rubinstein, ''A Course in Game Theory'', MIT Press, 1994.

[14] G.Owen, ''Game Theory, 3rd ed''., Academic Press, 1996.

[15] 佐々木宏夫, 『入門ゲーム理論』, 日本評論社, 2003.

[16] 鈴木光男, 『新ゲーム理論』, 勁草書房, 1994.

[17] J.vonNeumann and O.Morgenstern, ''Theory of Games and Economic Behavior, 3rd ed.'', Princeton University Press, 1953.

《ゲーム理論》

2007-08-06T07:41:06Z

H.Yamaguchi:

'''【げーむりろん (game theory) 】'''

1　ゲーム理論とは

　[[ゲーム理論]] (game theory) は, 複数意思決定主体の存在する状況における決定理論であり, フォンノイマン (J. von Neumann) とモルゲンシュテルン (O. Morgenstern) による大著"Theory of Games and Economic Behavior"([17])をその出発点とする. 複数の主体が存在するから, 主体間で利害の対立がある場合もあるし, 利害を共にする場合もある. このような状況において, 各意思決定主体はどのような行動をとるか, ないしは, とるべきかを数理的に分析することがゲーム理論の目的である. ゲーム理論では, 意思決定主体を[[プレイヤー]] (player), 各プレイヤーが持つ行動の計画を[[戦略 (ゲーム理論における)|戦略]] (strategy), プレイヤーがそれぞれの戦略をとった時に, 各プレイヤーが得られるもの, ないしは, それに対する評価値を[[利得 (ゲームの)|利得]] (payoff) と呼ぶ.

　ゲーム理論は, 想定するプレイヤーの行動様式の違いによって, [[非協力ゲーム理論]], [[協力ゲーム理論]]の2つに分かれて発展してきている. 非協力ゲーム理論は, プレイヤー間の話し合いはなく各プレイヤーがそれぞれ独立に戦略を決定する状況か, ないしは, たとえ話し合いがあったとしてもその結果得られた合意に拘束力のない状況を扱う. それに対して, 協力ゲーム理論は, プレイヤー間に話し合いのあることを前提とし, 話し合いの結果得られた合意に拘束力がある状況を扱う. 非協力ゲーム理論の扱うゲームを非協力ゲーム, 協力ゲーム理論の扱うゲームを協力ゲームと呼ぶ.

2　非協力ゲーム理論

　非協力ゲームは, 各プレイヤーの戦略と利得を用いて表現する[[戦略形ゲーム]]と, プレイヤーの意思決定を時間の流れと共に[[ゲームの木]]を用いて詳しく表現する[[展開形ゲーム]]に分かれる.

　非協力ゲーム理論における主要な解は, ナッシュ (J. F. Nash) によって与えられた[[ナッシュ均衡]]である. ナッシュ均衡とは, 各プレイヤーの戦略が他のプレイヤーの戦略の組に対する[[最適反応 (ゲーム理論における)|最適反応]]戦略になっているような戦略の組である. 戦略形ゲームにおいて, もともとの戦略が有限個である場合には, それらを確率混合して用いる[[混合戦略]]まで考えれば, ナッシュ均衡は必ず少なくとも1つ存在することが知られている.

　展開形ゲームは, プレイヤーの意思決定の順序, プレイヤーが意思決定の際に持っている情報などを詳細に表現できるものである. また, 展開形ゲームを考えると, ナッシュ均衡のうちのいくつかはその合理性に問題のあることが明らかになる. そのため, [[部分ゲーム完全均衡]], [[逐次均衡]], [[完全均衡]]などのナッシュ均衡の精緻化が展開形ゲームにおいて提唱されてきている.

3　協力ゲーム理論

　協力ゲームは, プレイヤーが2人の場合と3人以上の場合では, 状況が大きく異なり, それぞれ別々に理論が発達してきている.

　2人の協力ゲームでは, プレイヤーが話し合いの結果, 協力して行動するかどうか, また, 協力した場合には, その結果得られる利得をどのように分配するかの交渉が, 問題になる. 従って, 2人の協力ゲームを[[2人交渉問題]]と呼ぶこともある. 2人協力ゲームの主たる解もナッシュによって与えられたもので, [[ナッシュ解]]ないしはナッシュ交渉解と呼ばれている.

　3人以上の協力ゲームになると, 単に全員が協力するかどうかだけでなく, 部分的な協力関係を考える必要が生じ, 分析が難しくなる. 3人以上の協力ゲームは, 一般に<math>n\, </math>人協力ゲームと呼ばれる. フォンノイマンとモルゲンシュテルンは, <math>n\, </math>人協力ゲームにおいて, 協力関係を結んだプレイヤーのグループを[[提携]]と呼び, 提携それぞれに対して, それが獲得できる利得を与える関数を[[特性関数 (ゲーム理論の)|特性関数]]と呼んだ. 特性関数による<math>n\, </math>人協力ゲームの表現を[[提携形ゲーム]]ないしは特性関数形ゲームという. 提携形ゲームにおいては, プレイヤー間の利得分配の基準をどのように与えるかによって, [[安定集合]], [[コア]], [[交渉集合]], [[カーネル (ゲーム理論における)|カーネル]], [[仁]], [[シャープレイ値]]など, 様々な解が提案されてきている.

4　ゲーム理論の応用

　ゲーム理論がこれまで最大の貢献をなした分野は経済学であろう. 最初は, 交換市場や生産市場の[[競争均衡]]のコアによる新たな特徴付けなど, 協力ゲームの応用が中心であった. ついで, 産業組織論などにおいて企業競争の非協力ゲーム理論による分析が進み, 1980年代に入って爆発的な勢いで情報経済学をはじめ, ミクロ経済学の様々な分野に非協力ゲーム理論が浸透していった. いまでは, 経済学だけでなく, 政治学, 社会学などにおいてもゲーム理論は大きな貢献をなすものとなっている. これらの貢献に基づき,1994年にはナッシュ,ハルサーニ(J.C.Harsanyi),ゼルテン(R.Selten)の3名,2005年にはオーマン(R.J.Aumann),シェリング(T.C.Schelling)の2名のゲーム理論研究者がノーベル経済学賞を授与されている.

　ＯＲにおいても, 第2次世界大戦の軍事研究に始まり, 企業など組織における意思決定, 社会的, 公共的意思決定など, 非協力ゲーム, 協力ゲームが用いられているところは多い. 最も多い適用例は, 費用分担, 便益分配などの計画問題に対するものであろう. また, 投票による意思決定システムの協力ゲーム, 非協力ゲームによる分析もよく行われている.

5　最近のゲーム理論の発展

　最近のゲーム理論の発展で最も重要なものは, プレイヤーの限定合理性をとりこんだ研究であろう. ナッシュ均衡と部分ゲーム完全均衡などその精緻化は, プレイヤーの合理性を追求した結果得られた解であったが, これらの解が, 必ずしもわれわれが現実に経験する結果を導かないことが, 様々なゲーム的状況の分析から明らかになってきた.

　そこで出てきたのが, プレイヤーは必ずしも完全には合理的ではないとする[[限定合理性]]の考え方である. 限定合理性に対する１つのアプローチが, 進化ゲーム理論と学習であり, これらの理論によって, 社会における慣習, 制度などの形成過程が明らかにされるのではないかと期待されている.

　いま1つの重要なアプローチが, 実際に人間を使った[[実験 (ゲーム理論における)|実験]]によるゲーム理論の再検証である. これも, 人間の合理性の限界を認識することからスタートしている. 様々なゲームにおける実験が行われており, われわれ人間は, ゲーム理論の解が導く行動を必ずしもとらない場合もありうることが明らかにされ, 実験結果を基に, 新たな理論の構築が模索されている.

6　ゲーム理論の文献

　ゲーム理論の最近の一般的なテキストとしては, 和書では, [3], [8], [10], [12], [15], [16], 洋書では, [2], [4], [9], [13], [14],また,ゲーム理論のさまざまな分野への応用をまとめたものとして [1], [5], [6], [7], [11]がある.

----
'''参考文献'''

[1] A. Dixit and B. Nalebuff, ''Thinking Strategically'', N.W.Norton, 1991. 菅野隆, 嶋津祐一, 『戦略的思考とは何か』, TBSブリタニカ, 1991.

[2] D. Fudenberg and J. Tirole, ''Game Theory'', MIT Press, 1991.

[3] 船木由喜彦, 『エコノミックゲームセオリー』, サイエンス社, 2001.

[4] R.Gibbons, ''Game Theory for Applied Economists'', Princeton University Press, 1992. 福岡正夫, 須田伸一, 『経済学のためのゲーム理論入門』, 創文社, 1995.

[5] 今井晴雄, 岡田章, 『ゲーム理論の新展開』, 勁草書房, 2002.

[6] 今井晴雄, 岡田章, 『ゲーム理論の応用』, 勁草書房, 2005.

[7] 梶井厚志, 松井彰彦, 『ミクロ経済学戦略的アプローチ』, 日本評論社, 2000.

[8] 武藤滋夫, 『ゲーム理論入門』, 日本経済新聞社, 2001.

[9] R.B.Myerson, ''Game Theory'', Harvard University Press, 1991.

[10] 中山幹夫, 『はじめてのゲーム理論』, 有斐閣, 1997.

[11] 中山幹夫, 武藤滋夫, 船木由喜彦, 『ゲーム理論で解く』, 有斐閣, 2000.

[12] 岡田章, 『ゲーム理論』, 有斐閣, 1996.

[13] M.J.Osborne and A.Rubinstein, ''A Course in Game Theory'', MIT Press, 1994.

[14] G.Owen, ''Game Theory, 3rd ed''., Academic Press, 1996.

[15] 佐々木宏夫, 『入門ゲーム理論』, 日本評論社, 2003.

[16] 鈴木光男, 『新ゲーム理論』, 勁草書房, 1994.

[17] J.vonNeumann and O.Morgenstern, ''Theory of Games and Economic Behavior, 3rd ed.'', Princeton University Press, 1953.

《プロジェクト管理》

2007-08-06T07:21:55Z

H.Yamaguchi:

'''【ぷろじぇくとかんり (project management) 】'''

　大規模な建設や研究開発をプロジェクト(project)とよび, これらプロジェクトを計画・設計・日程立案・組織化し, その実行過程を統制することを[[プロジェクト管理]]という. しかし実際には, プロジェクト管理の意味するところは, その言葉を使う人によって異なる. ORの分野では伝統的に, PERT/CPMなど問題を解く技術的な側面に主な関心がもたれてきたが, ほかの分野では, プロジェクト組織といった, 人間が関係する側面により関心が払われてきた.

　PERT/CPMは, プロジェクト・スケジューリング(project scheduling)と総称される. [[PERT]]は作業(job, activity)の所要時間に関して確率的取扱いを含むのに対し, [[CPM]]は決定論的アプローチである. それでも, これら2つの方法はよく似た手法であり, PERT/CPM法とよばれる [1, 2].

(1)PERT: PERTは, それまで使われてきたガントチャート(バーチャートともいう)に替わって, 大規模な工事の計画・管理の手法として, 1958年に米海軍のポラリス・ミサイル開発プロジェクトのために生み出された.

　PERTでは, プロジェクトを構成する作業の先行関係を表現するのに, 矢線(arrow)と結合点(node, event)とからなる有向のネットワーク図を用い, これに基づいて日程を計画・管理する手法である. また, このネットワーク図を[[アローダイヤグラム]]や矢線図(arrow diagram)とよび, そのかき方に次の3つのルールがある.

(i)1つの作業は2つの結合点を結ぶ1つの矢線で図示し, 矢線の両端の結合点番号の対 <math>(i,j)\, </math> によって作業を表す(図1 (a)参照).

(ii)「作業Cは作業AとBがすむと取りかかることができる」という先行関係は, 図1(b)のように表現する. 作業の先行関係を正確に表現するためにダミー作業が使われる(図1 (c)参照).

(iii)付番を一意的とするため, 平行作業には図1 (d)のようにダミー作業を導入する.

<center><table><tr><td align=center>[[画像:0179-C-B-03-kiso-zu1.png|center|図1 作業と先行関係の表現法]]</td></tr>
<td align=center><br>図1 作業と先行関係の表現法</td></table></center>

アローダイヤグラムの例を図2に示す.

<center><table><tr><td align=center>[[画像:0179-C-B-03-kiso-zu2.png|center|図2 アローダイヤグラムと結合点時刻の例]]</td></tr>
<td align=center><br>図2 アローダイヤグラムと結合点時刻の例</td></table></center>

　作業 <math> (i,j)\, </math> の作業時間 <math>D_{ij}\, </math> が与えられたとき, 結合点 <math>j\, </math> に最も早く到達しうる時刻を最早結合点時刻(earliest node time) <math>t_j^E\, </math> とよび,

<center>
<math>
\left \{
\begin{array}{ll}
t_1^E=0 & \\
t_j^E= {\max}_{(i,j) \in P} (t_i^E + D_{ij}) & \ j=2,3,\ldots ,n
\end{array}
\right.
\, </math>
</center>

で計算する. ただし, <math>P\, </math> はプロジェクト全体の作業集合, <math>n\, </math> は終点を意味する. この計算は前進計算という. 上式により求めた <math>t_n^E\, </math> はプロジェクト全体の工期(総所要日数ともいう)を与える. つぎに, この工期から逆算して, 結合点 <math>j\, </math> に遅くとも到達していなければならない限界の時刻である最遅結合点時刻(latest node time) <math>t_j^L\, </math> を次式から求める.

<center>
<math>
\left \{
\begin{array}{ll}
t_n^L=t_n^E & \\
t_j^L=\min_{(j,k) \in P} (t_k^L - D_{jk}) & j=1,2,\ldots ,n-1
\end{array}
\right.
\, </math>
</center>

この計算を後進計算という. これらの結合点時刻から, 各作業の開始時刻と終了時刻の限界が次式より求められる.

<center>
<table>
<tr>
<td rowspan="4"><math>q_{ij}=
\left\{
\begin{array}{l}
\\
\\
\\
\\
\\
\\
\end{array} \right. </math></td>
<td>最早開始時刻　<math>ES_{ij} = t_i^E \, </math></td>
</tr>
<tr>
<td>最遅開始時刻　<math>LS_{ij} = t_j^L - D_{ij} \, </math></td>
</tr>
<tr>
<td>最早終了時刻　<math>EF_{ij} = t_i^E + D_{ij} \, </math></td>
</tr>
<tr>
<td>最遅終了時刻　<math>LF_{ij} = t_j^L \, </math></td>
</tr>
</table>
</center>

　最早時刻と最遅時刻とに差異がある場合には, その作業に日程上の余裕があることを意味し, この余裕を[[フロート]](float)とよぶ. 作業 <math>(i,j)\, </math> の全余裕時間(total float) <math>TF_{ij}\, </math> と自由余裕(freefloat) <math>FF_{ij}\, </math> は, 次式から求められる.

<center>
<math>
\begin{array}{l}
TF_{ij} = t_j^L - t_i^E - D_{ij} = LF_{ij} - EF_{ij} \\
FF_{ij} = t_j^E - t_i^E - D_{ij}
\end{array}
\, </math>
</center>

　アローダイヤグラムの矢線を順方向にたどって, 始点から終点に至る作業の列をパス(path)とよぶ. とくに <math>TF_{ij}=0\, </math> の作業の列で形成されるパスは[[クリティカルパス]](criticalpath)とよばれ, その長さはすべてのパスのうち最長となっている.

　PERT手法を基礎として種々な拡張が試みられている [3], [4]. 例えば, (i)作業に確率的選択の要素を入れたGERT(graphical evaluation and review technique)やVERT(ventureevaluation and review technique), (ii)PERTの時間的要素とともに費用に関するデータを考慮して, 日程と費用の両面から計画・管理を行うPERT/COST, (iii) [[資源制約]]を考慮して, その山積み・[[山崩し]]をアローダイヤグラムを基礎に実施しようとする資源制約付きプロジェクト・スケジューリング, (iv)単一プロジェクトから複数のプロジェクトの管理へ展開するRAMPS(resource allocationand multi-project scheduling), などがある.

　また, PERT計算で必要な各作業の所要時間は[[3点見積法]]で見積もられることが多い.

(2)CPM: CPMでは, アローダイヤグラムを構成する各作業 <math>(i,j)\, </math> の所要時間が投入費用によって可変であるとし, 両者の間に図3のような線形関係を仮定して日程計算を行う. 各作業を標準時間 <math>D_{ij}\, </math> で行うときの費用を <math>M_{ij}\, </math> , 特急時間 <math>d_{ij}\, </math> で処理するときの費用を <math>m_{ij}\, </math> とするとき, 所要時間 <math>y_{ij}\, </math> ( <math>d_{ij} \le y_{ij} \le D_{ij}\, </math> )に対する費用 <math>z_{ij}\, </math> は

<center>
<math>
z_{ij} = -c_{ij}y_{ij} + k_{ij}
\, </math>
</center>

で与えられる. ただし,

<center>
<math>
c_{ij} = (m_{ij} - M_{ij})/(D_{ij} - d_{ij})
\, </math>
</center>

は, 作業を単位時間短縮するのに要する増加費用で, 費用増加率とよばれる. <math>k_{ij}\, </math> は定数項である.

　CPMは, 以下のように定式化される. アローダイヤグラムの結合点 <math>i\, </math> ( <math> i=1,2,\ldots ,n \, </math> )の結合点時刻を <math>t_i \, </math> , 達成したいプロジェクト全体の工期を <math>\lambda\, </math> ( <math>=t_n\, </math> )とすると,

制約条件:

<center>
<math>
\left \{
\begin{array}{ll}
y_{ij} + t_i - t_j \le 0 & (i,j) \in P \\
t_1 = 0 \\
t_n = \lambda \\
d_{ij} \le y_{ij} \le D_{ij}
\end{array}
\right.
\, </math>
</center>

のもとで, プロジェクトの総費用

<center>
<math>
z(\lambda)=\sum_{(i,j)\in P} (-c_{ij} y_{ij} + k_{ij})
\, </math>
</center>

を最小化するような日程計画{ <math>t_i, y_{ij}\, </math> }を求める問題となる. ここで, <math>P\, </math> はプロジェクトの作業集合を意味する.

　CPMの解法にはいくつかの方法がある. 1つの方法は, CPM問題を工期 <math>\lambda\, </math> をパラメタとするパラメトリック線形計画法(parametric LP)と見なして解く解法で, プライマル・デュアル法(primal-dual algorithm)に基づく解法が提案されている. より広く使われている解法にラベリング法(labeling algorithm)がある. この方法は, 各作業の費用増加率 <math>c_{ij}\, </math> を矢線の容量制約とし, 始点から終点に最大フローを流す問題としてCPM問題を解く方法である. 多くの解法が提案されており, その計算量の比較も行われている [5].

<center><table><tr><td align=center>[[画像:0179-C-B-03-kiso-zu3.png|center|図3 費用関数]]</td></tr>
<td align=center><br>図3 費用関数</td></table></center>

　プロジェクト・スケジューリングの最近の研究が [6, 7]にまとめられている.

----

'''参考文献'''

[1] 関根智明,『PERT・CPM』,日科技連出版社, 1973.

[2] 刀根薫,『PERT入門』,東洋経済新報社, 1977.

[3] S. E. Elmaghraby, ''Activity Networks,'' John Wiley & Sons, 1977. 加瀬滋男『アクティビティネットワーク』,日刊工業新聞社, 1979.

[4] S. I. Gass and C. M. Harris, eds., ''Encyclopedia of Operations Research and Management Science,'' Kluwer Academic, 1996. 森村英典, 刀根薫, 伊理正夫監訳,『経営科学OR用語大辞典』,朝倉書店, 1999.

[5] R. K. Ahuja, T. L. Magnanti and J. B. Orlin, "Network Flows," in ''Optimization'', G. L. Nemhauser, A. H. G. Rinnooy Kan and M. J. Todd, eds., North-Holland, 1989.

[6] L. V. Tavares, ''Advanced Models for Project Management,'' Kluwer Academic, 1999.

[7] J. Weglarz, ed., ''it Project Scheduling: Recent Models, Algorithms and Applications'', Kluwer Academic Publishers, 1999.