基礎オペレーションズリサーチ 第12回 ~待ち行列モデル~ 担当:蓮池隆. 待ち行列理論とは  不特定多数の人・モノが,容量が有限の特定の施 設を利用する時に生じる混雑現象を解析するため の理論 テキスト P.244~

Slides:



Advertisements
Similar presentations
生物統計学・第 5 回 比べる準備をする 標準偏差、標準誤差、標準化 2013 年 11 月 7 日 生命環境科学域 応用生命科学 類 尾形 善之.
Advertisements

『わかりやすいパターン認 識』 第 5 章 特徴の評価とベイズ誤り確率 5.4 ベイズ誤り確率と最近傍決定則 発表日: 5 月 23 日(金) 発表者:時田 陽一.
Lesson 9. 頻度と分布 §D. 正規分布. 正規分布 Normal Distribution 最もよく使われる連続確率分布 釣り鐘形の曲線 -∽から+ ∽までの値を取る 平均 mean =中央値 median =最頻値 mode 曲線より下の面積は1に等しい.
土木計画学 第3回:10月19日 調査データの統計処理と分析2 担当:榊原 弘之. 標本調査において,母集団の平均や分散などを直接知ることは できない. 母集団の平均値(母平均) 母集団の分散(母分散) 母集団中のある値の比率(母比率) p Sample 標本平均 標本分散(不偏分散) 標本中の比率.
統計学 第3回 西山. 第2回のまとめ 確率分布=決まっている分布の 形 期待値とは平均計算 平均=合計 ÷ 個数から卒業! 平均=割合 × 値の合計 同じ平均値でも 同じ分散や標準偏差でも.
放射線の計算や測定における統計誤 差 「平均の誤差」とその応用( 1H) 2 項分布、ポアソン分布、ガウス分布 ( 1H ) 最小二乗法( 1H )
シミュレーション論Ⅰ 第 7 回 待ち行列のシミュレーション(2). 第 6 回のレポート(解答例) 乱数表より乱数を記入し、到着間隔・サービス時間にした がってグラフを作成する 例) 最大待ち人数:2人 最大待ち時間:5分 平均待ち時間:3分.
エクセルと SPSS による データ分析の方法 社会調査法・実習 資料. 仮説の分析に使う代表的なモデ ル 1 クロス表 2 t検定(平均値の差の検定) 3 相関係数.
サプライ・チェイン最適化 ー収益管理を中心としてー 東京海洋大学 久保 幹雄
●母集団と標本 母集団 標本 母数 母平均、母分散 無作為抽出 標本データの分析(記述統計学) 母集団における状態の推測(推測統計学)
数理統計学  第9回 西山.
数理統計学(第ニ回) 期待値と分散 浜田知久馬 数理統計学第2回.
第1回 確率変数、確率分布 確率・統計Ⅰ ここです! 確率変数と確率分布 確率変数の同時分布、独立性 確率変数の平均 確率変数の分散
データ分析入門(12) 第12章 単回帰分析 廣野元久.
疫学概論 ポアソン分布 Lesson 9.頻度と分布 §C. ポアソン分布 S.Harano,MD,PhD,MPH.
点対応の外れ値除去の最適化によるカメラの動的校正手法の精度向上
シミュレーション論Ⅰ 第6回 待ち行列のシミュレーション.
多変量解析 -重回帰分析- 発表者:時田 陽一 発表日:11月20日.
© Yukiko Abe 2014 All rights reserved
初級ミクロ経済学 -生産者行動理論- 2014年10月20日 古川徹也 2014年10月20日 初級ミクロ経済学.
ISDASインターネット分散観測: ワームの平均寿命はいくらか?
シミュレーション論Ⅰ 第9回 様々なシミュレーション:販売と在庫管理.
統計解析 第9回 第9章 正規分布、第11章 理論分布.
Bassモデルにおける 最尤法を用いたパラメータ推定
アルゴリズムイントロダクション第5章( ) 確率論的解析
最適生産量の決定.
大数の法則 平均 m の母集団から n 個のデータ xi をサンプリングする n 個のデータの平均 <x>
シミュレーション論Ⅰ 第4回 基礎的なシミュレーション手法.
シミュレーション論Ⅰ 第3回 シミュレーションと経済・社会システム.
電気基礎実験 <<グラフ処理>>
シミュレーション物理7 乱数.
統計学 第3回 10/11 担当:鈴木智也.
統計解析 第10回 12章 標本抽出、13章 標本分布.
統計解析 第1章 データの表現.
新幹線を用いたモーダルシフトの 可能性に関する研究
ネットワーク性能評価.
? ? ? ? ? ? ? ? 多変量解析とは? 問題となっている現象 ●問題の発生原因がわからない(因果関係)
ガウス過程による回帰 Gaussian Process Regression GPR
シミュレーション論 Ⅱ 第15回 まとめ.
市場規模の予測.
アーランの即時式モデル.
独立成分分析 1.問題は何か:例:解法:全体の見通し 2007/10/17 名雪 勲.
正規分布確率密度関数.
混合ガウスモデルによる回帰分析および 逆解析 Gaussian Mixture Regression GMR
確率論の基礎 「ロジスティクス工学」 第3章 鞭効果 第4章 確率的在庫モデル 補助資料
ミクロ経済学第9回 企業と費用2:費用最小化.
独立成分分析 5 アルゴリズムの安定性と効率 2007/10/24   名雪 勲.
Basic Tools B4  八田 直樹.
主成分分析 Principal Component Analysis PCA
市場規模の予測.
多変量解析 ~主成分分析~ 1.主成分解析とは 2.適用例と解析の目的 3.解析の流れ 4.変数が2個の場合の主成分分析
2009年12月4日 ○ 前田康成(北見工業大学) 吉田秀樹(北見工業大学) 鈴木正清(北見工業大学) 松嶋敏泰(早稲田大学)
経営システム工学入門実験A ビールゲーム 総評
ウィルスって どの位感染しているのかな? 菊池研究室  小堀智弘.
「データ学習アルゴリズム」 第3章 複雑な学習モデル 報告者 佐々木 稔 2003年6月25日 3.1 関数近似モデル
情報経済システム論:第13回 担当教員 黒田敏史 2019/5/7 情報経済システム論.
シミュレーション論 Ⅱ 第1回.
シミュレーション論Ⅰ 第7回 シミュレーションの構築と実施.
最尤推定・最尤法 明治大学 理工学部 応用化学科 データ化学工学研究室 金子 弘昌.
統計学  第9回 西 山.
疫学概論 ポアソン分布 Lesson 9.頻度と分布 §C. ポアソン分布 S.Harano,MD,PhD,MPH.
数理統計学 西 山.
独占はなぜいけないか.
公共経済学 (第2講 生産者の行動1) 今日の講義の目的 (1)費用関数、限界費用、平均費用という概念を理解する
待ち行列シミュレーション.
or-6. 待ち行列シミュレーション (オペレーションズリサーチを Excel で実習するシリーズ)
回帰分析入門 経済データ解析 2011年度.
Cプログラミング演習 ニュートン法による方程式の求解.
(昨年度のオープンコースウェア) 10/17 組み合わせと確率 10/24 確率変数と確率分布 10/31 代表的な確率分布
各種荷重を受ける 中空押出形成材の構造最適化
Presentation transcript:

基礎オペレーションズリサーチ 第12回 ~待ち行列モデル~ 担当:蓮池隆

待ち行列理論とは  不特定多数の人・モノが,容量が有限の特定の施 設を利用する時に生じる混雑現象を解析するため の理論 テキスト P.244~

給料日の銀行は大混雑  ATMは長蛇の列,窓口はガラガラ  振込の窓口はまあまあ  定期預金の窓口はガラガラ  ATMだけ長蛇の列って, 何とかしてください!

車で朝夕通勤すると…  とにかく“混む”!  道路をもっと広くしてor増やして,車を多く通る ようにすればよい? →そうすると,昼間はガラガラ&道路を拡張or増 設するコストは誰が払うの?

携帯電話の設備設計  携帯電話を“いつでも”つながるようにするために, 膨大な設備投資を行っている

携帯電話の設備設計  導入初期はトラブル続きだった? 利用頻度の見積りをせずに見切り発車すると,当 然つながらないことが多々  設計基準QoS(Quality of Service):「50回に1 回くらいはつながらなくてもしょうがない」と思 うなら,基地局はいくつくらい必要か?  数理モデル(確率モデル)による見積りが必要

生産システムへの適用  多品種少量生産では,工程の処理時間がばらつく  時々システムダウン  前工程からスムーズに流れてこない  後工程が引き取ってくれない  仕掛在庫の適正管理  ジャストインタイム生産方式において,最適なカ ンバン枚数は何枚か?

不動産の供給問題  「部屋を借りたい!」  空いている部屋を選び,契約する  借りている部屋を退去する  次に借りたい人が来るまで,その部屋は遊び状態  サービス時間=契約時間

エレベータの待ち時間  「エレベータの待ち時間が長すぎる!」という切 実な苦情  どのような対策をすればよいか?  エレベータ前に姿身を置く(自分の姿を見て,心を 紛らわせる)  今何階にいるかの表示を見えなくする(見えるから イライラ感がつのる?)  …  そもそも待ち時間を減少させる最適なエレベータ 台数やエレベータ管理の方法は?

ここからの講義内容  待ち行列理論  平均値解析  ラッシュアワーの問題 ~累積グラフと流体近似~  平均値とばらつき  携帯電話の呼損率  待ち時間のシミュレーション分析

待ち行列理論の目的  混雑の度合いを数量化して,設計基準を与える  サービスレベルと“待ち”に対するコストのトレー ドオフ分析  混雑の要因分析,感度分析により,状況の変化に 備える  混雑を軽減する施策の評価 テキスト P.245~

混雑現象のモデル分析  客がサービス施設に到着して  窓口のサービスを受け  退去する

「客」「窓口」「サービス」  銀行のATM  利用者+ATM+預入・出金・振込など  携帯電話  通話要求+回線+通話・通信  生産システム  仕掛在庫+加工機械+加工処理  駐車場  車+駐車スペース+駐車

「客」の在庫管理  「到着>退去」なら,在庫あふれ  平均的に『処理量(速度)κ>サービス要求量λ』  そうでないと…  未処理の要求はどんどん累積し,  いずれはシステムが破たんする κ λ 処理量(速度)κ<サービス要求量λの場合の図→

グラフを使った分析 待ち行列の長さの時間変化表示法  在庫グラフ(システム内(系内)の客を在庫と見て)  累積グラフ  到着客・退去客を累積したものを同じ座標軸上に 表示 時刻 系内 客数 テキスト P.246~

累積グラフを使った分析 待ち行列の長さの時間変化表示法  累積グラフ 細かく見れば 累積到着客数 :I(t) 累積退去客数 :O(t)

ここからの講義内容  待ち行列理論  平均値解析  ラッシュアワーの問題 ~累積グラフと流体近似~  平均値とばらつき  携帯電話の呼損率  待ち時間のシミュレーション分析

平均滞在時間の測り方  例:空中写真を撮って数える(マスコミでよくあ る『〇〇調べ』をこの類)  滞在者数=累積入場者数-累積退場者数 累積入場者数 :I(t) 累積退場者数 :O(t) 時間 人数 テキスト P.246~

平均滞在時間の測り方  例:調査カード(入場時に手渡し,退去時に回収)  滞在時間=n番目の入場時刻-n番目の退場時刻 (ただし,入ってきた人から順番に出るとする: FIFO(First In, First Out)) 累積入場者数 :I(t) 累積退場者数 :O(t) 時間 人数

滞在客数と滞在時間の関係性  累積到着数と累積退場数のグラフに囲まれた面積 を計算

面積計算の考え方:Case1  各人の滞在時間を全部足したもの(横に見る) → 平均滞在時間Wを入場客数N倍したもの

面積計算の考え方:Case2  単位時間毎の滞在客数の合計(縦に見る) → 滞在客数の時間平均Lを営業時間T倍したもの

重要:リトルの公式  平均滞在客数=到着率×平均滞在時間 :到着率

平均値による分析:不変式  累積到着数と累積退去数に挟まれたものは? 累積到着数 累積退去数 滞在客数 =滞在時間中の 到着客数 滞在時間 到着率

例:駐車スペースは何台必要?  郊外にアウトレットパークを作ろうとするとき, 駐車スペースは何台分用意すればよいか?  お客さんがどのくらい来るのか?  どのくらい滞在するのか? テキスト P.248

駐車スペースの見積り  ピーク時の利用客:10分あたり20台  ピーク時の滞在時間は約2時間  リトルの公式による滞在車数の見積り:  到着率:λ=N/T=20/(1/6)=120  平均滞在時間:W=2  平均滞在車数:L=λW=120×2=240  平均でも240台分は必要.ばらつきを考えると もっと必要になるかも?? 時間を(時)に合わ せて計算(もちろん (分)でもOK)

コールセンターの設計  コールセンター:電話による顧客サービス用施設  ピーク時の電話は1時間当たり600本かかってくる  ピーク時の客への対応時間は5分  リトルの公式によるオペレータ数の見積り  到着率:λ=N/T=600/60=10  平均滞在時間:W=5  平均オペレータ対応数:L=λW=50  平均で考えても,50人のオペレータが必要!

ここからの講義内容  待ち行列理論  平均値解析  ラッシュアワーの問題 ~累積グラフと流体近似~  平均値とばらつき  携帯電話の呼損率  待ち時間のシミュレーション分析

ラッシュアワーの問題  ラッシュアワーっていつまで?  時差出勤(平準化)は効果があるの?  座席レス車両による効果は?  … テキスト P.249~

ラッシュアワーの問題  輸送可能量を超えたら,増え続けるだけ  1人1人のランダム行動の影響は小さい → マスとしての分析が必要 輸送可能量 利用客数の 時間推移

ラッシュアワー(累積グラフによる分析)  積み残しは累積する! 累積積み残し

 交通量のピーク≠渋滞量のピーク ラッシュアワー(累積グラフによる分析) 累積グラフに おける接線の 傾き最大

 ピークに合わせても遅い ラッシュアワー(累積グラフによる分析) 渋滞の解消時刻 渋滞の ピーク 輸送力の 増強

 到着のピークを見越して対策をうつべし! ラッシュアワー(累積グラフによる分析) 渋滞の解消時刻 混雑度 も減少 輸送力の 増強

ここからの講義内容  待ち行列理論  平均値解析  ラッシュアワーの問題 ~累積グラフと流体近似~  平均値とばらつき  携帯電話の呼損率  待ち時間のシミュレーション分析

平均値による分析:定常条件  累積到着数<累積退去数なら,混雑は解消方向 時間 テキスト P.252~

平均値による分析:定常条件  累積到着数>累積退去数なら,混雑は解消しない 時間

待ち行列理論の主たる対象  単位時間当たりの処理可能量(速度):κ  単位時間当たりのサービス要求量:λ  定常条件:(平均処理可能量)>(平均要求量)  トラフィック密度: テキスト P.252~

現実を考えると…  サービス要求量(到着する客数)は,時々刻々変化  例:通勤ラッシュ,お昼時のレストラン,…  分析の主眼:ピーク時の処理能力は十分か?  サービス要求量の極端な変動はないと仮定

ばらつきの影響  リトルの公式で設計すると苦情が殺到するかも…  平均値より多い日もあるし,少ない日もある  来場パターンは時間的に一様ではない  ピーク時でも波がある  ばらつきがあるから,良くないことも起こる!  確率モデルによる分析が必要!

バスの待ち時間  スケジュール通り一定間隔に到着すれば…  10分間隔でこれば,平均待ち時間は5分  渋滞で到着が不規則になると…  平均待ち時間は増えるのか?減るのか?  例:間隔が5分と15分を繰り返す場合  間隔5分の時は,平均待ち時間は2.5分  間隔15分の時は,平均待ち時間は7.5分  結局平均すると5分?? テキスト P.254~

バスの待ち人数(累積グラフ)  停留所の待ち人数=累積到着数-累積退去数 累積退去客数

バスの待ち時間のグラフ  グラフの平均的な高さ=客の平均待ち時間 傾き45度の直線 待ち 時間

バスの平均待ち時間  ランダムな到着ならば  グラフの面積を計算して,平均の高さを計算すれ ばわかる! 平均待ち時間

バスの平均待ち時間  面積の計算方法  1つ1つの三角形は直角三角形  1辺の長さは到着間隔  T時間の間にN台到着

バスの平均待ち時間  平均の高さ:

バスの平均待ち時間(まとめ)  バスの到着間隔:X(確率変数)  期待値:m=E(X)  分散:σ 2 =V(X)=E(X 2 )-m 2  バスの平均待ち時間  ばらつきとともに,待ち時間は限りなく増える c:変動係数

ここからの講義内容  待ち行列理論  平均値解析  ラッシュアワーの問題 ~累積グラフと流体近似~  平均値とばらつき  携帯電話の呼損率  待ち時間のシミュレーション分析

携帯電話のかかりにくさ  携帯電話での通話は,アンテナから先の回線(有 線)が必要  回線が全て埋まっていれば,通話要求は拒否される  通話要求が受け付けられない  サービスが悪すぎ!  他の会社に変えよう! とならないように  回線を増設したいが,どのくらい増やせばよい? → まずは現状分析を! テキスト P.258~

携帯電話の呼損率  呼損率:  全通話要求回数のうち,つながらなかった通話要求 の数  1日のうちで全ての回線が使用中である時間比率  回線使用状況は確率変動する → 全回線通話中の確率がわかればOK

使用回線数算出のための確率モデル  平衡状態ならば… 通話要求:λ通話終了:k/m k回線使用している 確率:p k (m:通話時間) k-1回線使用している 確率:p k-1

呼損率の公式(アーランの呼損式)  a=λm:通話時間中の到着数(単位:アーラン)  M:回線数

アーランの呼損式(呼損率)  呼損率をグラフで表現する

ここからの講義内容  待ち行列理論  平均値解析  ラッシュアワーの問題 ~累積グラフと流体近似~  平均値とばらつき  携帯電話の呼損率  待ち時間のシミュレーション分析

待ち時間と到着,サービスの関係  単一窓口の待ち行列モデル  待ち時間の漸化式 テキスト P.265~

リンドレーの公式  ある客の待ち時間は,サービス時間と到着間隔で 表現できる  待たされる場合:  待たされない場合:もちろん0 まとめると

リンドレーの公式を利用した分析  到着間隔,処理時間がわかれば待ち時間は計算で きる!

シミュレーション分析  客が到着したつもりで  待ったつもりで  サービスを受けたつもりで,分析  変化のあった時刻さえ分かれば,待ち行列の動き は「計算」できる!

数値実験  時刻0で,空のシステムに新たな客が到着  その客の待ち時間は0,つまりW 1 =0  その客のサービス時間S 1 と次の到着間隔A 2 を決定  次の客の待ち時間は ,  その客のサービス時間S 2 と次の到着間隔A 3 を決定  次の客の待ち時間は,  以下同様.

架空サービス時間,到着間隔の生成  過去のデータからランダムに選ぶ  4.5, 2.1, 5.3, 6.2, 4.1, 3.4, 3.8,…  経験分布関数から求める

理想的なランダムデータの生成方法  逆関数法:(累積)分布関数を求め,その逆関数を 利用したランダムデータの生成方法  正規分布の場合:=NORMINV(RAND(),m,s)  指数分布の場合:=-LN(RAND())*m

とあるシミュレーション結果  到着間隔は指数分布にしたがう(平均6分)  サービス時間は一定値(4分)

とあるシミュレーション結果  シミュレーションにより,たくさん結果は得られる が,結局はどれが正しいの?→バラツキのまとめ方 を参照!

シミュレーションは標本調査  シミュレーション実験は標本調査と同じ  実験結果はたまたま得られたものにすぎない,but,  実験を繰り返せば,だいだいの様子がわかる!  標本調査  標本平均:  分散: 誤差

(参考)平均待ち時間の公式  ポラツェックヒンチンの公式: テキスト P.268~ ただし,mは平均サービス 時間,cはサービス時間の 変動係数

やはりどうしても…  簡単な確率計算は必要  以下の確率に対して,計算方法くらいはパッとでき てほしいです…(来年のOR/Bに向けて)

今日のまとめ  待ち行列の有名公式・リトルの公式が導出さ れる過程,および公式そのものもマスターし よう!  待ち時間が変動する場合の待ち行列モデルを 理解しよう!  シミュレーション分析をすることで,待ち行 列モデルの理解を深めよう!