4. 離散系シミュレーション
現実のシステムは連続的に変化している。
しかし,
・対象システムの時間経過に伴う状態変化が,
連続的よりは,むしろ離散的と見なせる場合を
離散システム(系)と呼ぶ。
・対象システムを,離散的に状態変化が起こる
システムと見なして,模擬するものを離散系シ
ミュレーションと称す。
031119
031202
1
離散システムのモデル化
・活動の開始と終了の2つの事象だけでモデル化
・構成要素を「客」と「サービス施設」に分けてモデ
ル化
客の状態: 「サービスを受けている」 / 「待っている」
サービス施設の状態: 「サービスしている」 / 「手待ち
の状態にある」
要求の状態変化: 客の到着 / サービスの終了
031118
2
Queuing(待合せ)問題
キューイング発生の原因: 要求 > 処理能力
情報量不足が基本的原因
サービス施設の取り合い,行列
取り合い問題の解決法 (優先順序の問題)
(1) 予約: 情報を事前に与える
(2) 優先順位: 前後関係を与える
(3) 複雑なルールなどを設定
(4) Queuing(待ち行列,待合せ問題)
サービス施設が一定のキャパシティであれば,情報
不足と取り合いの両面から,合理的な,最適な,数
量的なポイントを見つけていくこと。
031120
3
Queuing問題のモデリング
定量的な数値の与え方
到着側(λ)とサービス側(μ)の定量的モデル
解析的方法 vs. シミュレーション
031125
4
到着率とサービス率
到着率 λ
到着時間間隔: 指数分布
ある時間内に発生する到着確率: ポアソン分布
事故や故障の場合: MTBF(平均故障間隔)
(Mean Time Between Failure)
サービス率 μ
サービス時間: アーラン分布
次数 k = 1 (指数分布)
031120
5
指数分布 Exponential distribution
031118
6
指数分布の分布関数や期待値
031118
7
ポアソン分布
031118
8
ポアソン分布と指数分布との関係
031118
9
Kendall’s notation
031118
10
定量的な数値の与え方
到着側(λ) と
の定量的モデル
サービス側(μ)
11
病院内の患者の流れ
031121
12
病院の定量的モデル
13
病院のシミュレーション
14
CVS(Computer-controlled Vehicle System)の例
15
解析的な方法
システムの状態とその時間的変化
窓口サービスで
の状態の変化
=使用中の窓
口数の変化
状態の時間的変化
031125
16
Erlangの状態方程式
到着側:
ポアソン分布(λ)
サービス側:
指数分布(μ)
17
シミュレーションによる方法
離散系シミュレーション言語
代表的特性
GPSS
SIMSCRIPT
SIMULA
18
離散系シミュレーション言語の特性1
1) モデル概念の提供
「対象」と「属性」(attribute)をどのような数値の配列
で表現し,変化させるか。 World-viewの統一。
言語固有のモデル概念
2) タイミングのコントロール
時間経過・・・同時並行現象→serialな(計算機)処理
タイミングコントロール: 汎用言語ではプログラマが実施
事象方式: 事象の起こる時点だけに注目
活動単位: 活動という単位で状態変化を記述
031118
19
離散系シミュレーション言語の特性2
3) 確率過程の表現
不確定モデル = stochastic model
各種分布の取扱い: 指数分布,ポアソン分布,正規
分布など,確率過程処理の簡単な表現
4) プログラムデバッグ機能
・シミュレーションプログラムのdebugは格段に難しい
・正解のわかった標準プログラムはない
・モデルの信憑(ぴょう)性の確証はどこにもない
031118
20
離散系シミュレーション言語
活動単位
事象方式
活動単位
031120
21
インタプリタとコンパイラの比較
011103
22
GPSS
General Purpose System Simulation
1961 IBM Gordonらにより開発。
世界で一番よく使われているシミュレーション
言語。
開発目的: 計算機システムの待ち行列分析
031119
23
GPSSの概念モデル
1) transaction 運動体 (動的要因)
時間の経過とともにシステムの
中を動いていくもの
2) equipment 施設 (静的要因)
a) storage 複数施設
同時に複数個のトランザクションが入り
うる,もしくは使用できる機器設備類
例) 駐車場,倉庫,コンピュータメモリ,教室
b) facility 単一施設
同時に単一のトランザクションだけが使用できる機器設備
類
例) 窓口,CPU
031129
24
GPSSの例題
劇場の切符売場とプログラム売子の問題
劇場で興行を開始する
支配人の関心: 切符売場とプログラム売子の稼
動状況は?
切符売場とプログラム売子の前での客の待ち行
列は?
不都合な結果がでたら,何か対策を打たねばなら
ない
031119
25
劇場シミュレーションの目的
目的
・切符売場(売子)やプログラム売子の稼動状況
・切符売場での客の待ち行列の状態
・どの位の客がやってくるか
データ収集
・客の人数
・客の到着状況は,客の劇場への到着間隔はどうか
・どのようなサービスが必要か
・それぞれの売場では何人の売子が必要か
・何人の客について何時間シミュレートするか
031120
26
Flow chart 流れ図
単純化した仮定
・切符売り場は1か所
・客は全員切符を買う
・プログラム売子は1人
・客は全員プログラムを買う
計算条件
行列番号 ○1
行列番号 ○2
施設番号 △1
施設番号 △2
031120
施設番号△1
行列番号○1
施設番号△2
行列番号○2
27
劇場シミュレーションのデータ
1. 客の劇場にやってくる間隔
平均的に 6秒間に 1人。ばらつきは 3秒間
2. 切符売場のサービス時間
1人平均 5秒。ばらつきは 3秒
3. 切符売場から劇場に入るのに要する時間
7秒
4. プログラム売子のサービス時間
1人平均 4秒。ばらつきは 1秒
5. シミュレーションをする客数
300人
031120
28
ブロック図とコーディング
031120
29
GPSSの特徴
1.
2.
3.
4.
5.
6.
離散型モデルでトランザクション中心
モデルをアセンブラ形式の命令で記述
命令語の概念がわかりやすい
デバッグが容易
多くの待ちを含むモデルに適当
IBM が(利用者として)長年かけて開発改良
031120
30
GPSSの限界
1. 数式の記述に限界がある
2. 複雑な計算は時間がかかる
3. 単純な要素が重なった大きなモデルは扱え
る。しかし,複雑なロジックの表現は困難
4. 待ち行列でないモデルは扱えない
5. モデル内容を時間で変化させることは困難
6. トランザクションを動かさないと何もできない
7. 小数点が扱えない(関数を除く)
031120
31
運動体や施設の実物との対応
031119
32
SIMSCRIPT(Simulation scriptor)
RAND社により 1961年 FORTRANを拡張して開
発された離散系シミュレーション言語。
システムの記述の基本概念として,総合的に事
象をとらえる物の見方(world-view)をとってい
る。GPSSはentity(物)オリエンテッドな見方だ。
SIMSCRIPTは,あるシステムを時間軸に直交す
る平面で切ったとき,そこに存在するシステム
状態と,その時刻で生起する事象を総合的に
とらえることのできるシミュレータである。・・・
金太郎飴のようだ。
031120
33
SIMSCRIPTでのシステム状態の記述
Entity ---Permanent Entity(Sim.中に存在しつづける対
象)
-Temporary Entity(出入,生滅する対象)
Attribute-Permanent Attribute(P Entityの大きさや個数)
Eの属性 -Temporary Attribute(自動車[TE]の速度など)
Set
(Entityの集まりの定義,一括処理の便宜を提供)
構成要素
SIMSCRIPT ⇔ GPSS
Permanent Entity ⇔ Facility, Storage
Temporary Entity ⇔ Transaction
031120
34
SIMSCRIPTでの時間管理:
Event方式
利用者は1つのイベントが起きると,システムの状
態がどのように変わるかをEvent routineで記述
する。
Event: 時間パターンに従って生起するシステム状態変化
Event ---Exogenous Event (外生事象)
(システム外から制御されるもの)
-Endogenous Event (内生事象)
(システム内部の変化に起因するもの)
031120
35
SIMSCRIPTの特徴
1.
2.
モデル化の概念としては,一般性,融通性に富む
のが利点。プログラム作成が多少難しい点が難点。
共通的なサブモデルがない。
GPSSはinterpretiveに実行される。SIMSCRIPTは
オブジェクトプログラムの実行である。→計算速度
が高い。モデル化機能の融通性のため,シミュレー
タ容量でも勝っている。
計算速度とメモリ容量に問題がない場合: GPSS
そうでない場合: SIMSCRIPT
031120
36
SIMULA(Simulation language)
ノルウェー計算センタで1965年開発。
SIMULA I: ALGOL60がホスト言語。モデルを活
動単位で記述。ALGOLの構造的明快さが生
かされ,整った言語体系。
SIMULA67: システムを同じような性質を持つ要
素型(プロセスクラス)に分けて考える。
プロセスクラス: 属性+行動規則(脚本)
モデルの実際の要素: 実体(object)。個々の実
体が4状態をとり,推移していく。
031129
37
SIMULAでのプロセスの実体の状態推移
031129
38
新機能言語の技術動向
39
新機能言語の歴史的展開
40
第4章 Key words
離散系 vs. 連続系
定量的な数値の与え方
到着側(λ)とサービス側(μ)の定量的モデル
指数分布,ポアソン分布,アーラン分布
解析的方法 容易ではない
シミュレーション
World-view。 事象方式,活動単位
GPSS, SIMSCRIPT, SIMULA(言語に寄与)
031202
41
ダウンロード

離散系シミュレーション