アルゴリズム論 b (2014) [第6回] 待ち行列と動的計画法 窓口に並ぶ行列 客の到着 待ち行列の発生 窓口 サービス対応 サービス終了 退出 窓口１つ M/M/1 到着時間ランダム・サービス時間ランダム M/D/1 到着時間ランダム・サービス時間一定 窓口が複数 n 個 M/M/n 客の到着 → 直列方式 ○ ○ ○ → ○ ○ → ○ ○ ○ → ○ ○ ○ → ○ ○ 退去 客の到着 並列方式 退去 ※並んだ後から窓口変更はできない 客の到着 ○ ○ → ○ ○ ○ → ○ ○ ○ → ○ ○ → ○ ○ ○ → ○ ○ ○ → 窓口ランダム 選択 退去 客の到着 窓口最小人数 選択 退去 ※並んだ後から窓口変更はできない 平均到着率 平均サービス量 平均窓口利用率 待ち席無限大 λ 1分あたり到着する客数 μ 1分あたり処理できる客数 ρ＝ λ / nμ ρ<1 平均到着率 λ 1分あたり到着する客数 平均サービス量 μ 1分あたり処理できる客数 平均サービス時間 t s=1/ μ 1人あたりの処理時間 平均待ち行列長さ 平均システム内客数 Lq 平均滞在客数 （サービスを受けている客を除く） L 平均の行列人数 平均窓口利用率 平均の行列人数 L＝ ρ ρ＝ λ / μ Lq ＝ 1ー ρ ρ2 1ー ρ 平均待ち時間 リトルの法則 Wq ＝ ρ 1ー ρ ts = Lq λ 1. M/M/1 とM/D/1のシミュレーションを実行し、その違 いを分析せよ。サービス時間がランダムと一定の場合 では、待ち行列がどうなるか。 2. 窓口２つの直列・並列の場合のシミュレーションを実行し、 気が付いた点などを自由に論じること。 ※実際にいくつかの条件で実行してみた結果に基づき 記述すること。 大きな問題を分解 分割統治法 動的計画法 トップダウン ボトムアップおよびトップダウン 大問題 中問題 小問題 最短経路問題 ゴールへの道筋を手前までのルートを遡りながら 決定 ダイクストラ・アルゴリズム 1, 1, 2, 3, 5, 8, 13, 21,…… 1+1=2 X3=X2+X1 1+2=3 X4=X3+X2 2+3=5 X4=X3+X2 … Xn+1= Xn + Xn-1 手前の2項を加える 黄金比とは 黄金比 隣の２数の比 1/1 2/1 比の値 1 １＋√5 ２ 2 3/2 1.5 5/3 1.666 という値に近づく 8/5 1.6 13/8 21/13 1.625 1.615 黄金比 クレジットカード、名刺、本・・ 縦横比＝８：５ 約 1.6 F(n) を求めるのに、より小さい n の値から求める 状態遷移図 問題を小さい問題に分解 求める解は Fn または F∞ n 待ち行列 人 確率遷移 λ λ n+1人 n人 n-1人 μ μ n人の状態 (n-1)人状態からλの確率で流入 (n+1)人状態からμの確率で流入 (n-1)人の状態 n人状態からλの確率で流出 (n+1)人の状態 n人状態からμの確率で流出 n人の状態 (λ+μ)pn = λpn-1 + 流出量 = 流入量 μpn+1 (n=１，２, …) ※流入と流出が釣り合うと平均的に同じ行列人数になる pn が求まれば平均人数は求まる 窓口２つの場合のシミュレーション 直列の場合 並列の場合
© Copyright 2024 ExpyDoc
