数模日记3
排队论模型
PS：此处的排队论，真的就是单纯的排队。
排队论研究随机服务系统的确定性规律。
等待时间、服务时间、到达时间具有随机性。
[TOC]
基本组成
输入
- 顾客总体的数量：有限/无限
- 顾客到来的方式：个体/批
- 到达的间隔时间：不确定（随机变量，遵从概率分布）
顾客的行为假定为：
- 在未服务之前不会离开（等待制）
- 当看到队列很长的时候离开（有损失）
- 从一个队列移到另一个队列（上两种结合）
排队规则
队列容量：有限/无限
----- 此处的队列是排队队列。
排队规则：FCFS、LCFS、RSS（random）、PS（priority）、GD（一般规则）
服务规则
- 服务机构（1 / 多）个
- 服务台：并行、串行、混合排列
- 服务方式：单个/批处理
数量指标
每天的排队人数是随机的，所以取长期的平均值。
\(L_s\)：(line system)平均队长。既在排队、又在接受服务的人。
\(L_q\)：(line query)平均队列长。只包括排队的人，不包括正在接受服务的人。
\(W_s\)：(wait system)平均逗留时间。顾客在这个系统中（排队+服务）停留的时间平均值。
\(W_q\)：(wait query)平均等待时间。顾客在排队的时间的平均值。
为求解以上4个指标，引入：
记号方案
Kendall 记号
X：顾客到达的时间分布，输入过程的特征。Y：服务时间分布。Z：服务台的个数。取值 1/c（\(c \gt 1\)，表示多个服务台）A：排队系统允许的最大顾客容量。取值有限/无限。B：顾客总体数量，指不在排队的、外部的顾客数量。（多分 ）取值有限/无限。C：排队队则，如FCFS。
常见：\(X/Y/Z/A/B/C = M/M/1/\infty/ \infty /FCFS\)
X/Y：
- M：表示泊松过程 or 负指数分布
- D：表示确定型分布
- \(E_k\)：表示 k 阶埃尔朗分布（综合到一起的分布）
- G：表示一般服务时间分布
- GI：表示一般相互独立的时间间隔分布
排队论模型
单服务台模型(FCFS)
\(M/M/1\)（标准型）
$ M/M/1// /FCFS$
求解要建立稳态概率方程： \[ \begin{cases} \lambda P_0=\mu P_1 \\ \lambda P_{n-1}+\mu P_{n+1}-(\lambda +\mu)P_n=0& ,n\ge 1 \\ \end{cases} \] 由递推公式得： \[ P_n = (\frac{\lambda}{\mu})^n P_0 \] 令\(\rho = \frac{\lambda}{\mu}\)： \[ \sum^{\infty}_{n=0}P_n=1\\ P_0\sum^{\infty}_{n=0}P_n= \frac{P_0}{1-\rho}=1 \] 故： \[ P_0=1-\rho\\ P_n=(1-\rho)\rho^n \] 这是系统状态为 \(n\) 的概率，然后接下来计算上述的4个指标。
平均队长\(L_s\)：(serve+queue) \[
L_s=\sum_{n=1}^\infty nP_n=\sum_{n=1}^\infty n (1-\rho)\rho^n =
\frac{\rho}{1-\rho}=\frac{\lambda}{\mu-\lambda}
\] 平均队列长\(L_q\)：(queue) \[
L_q=\sum_{n=1}^\infty(n-1)P_n=\frac{\rho\lambda}{\mu-\lambda}
\] 平均逗留时间\(W_s\)：(serve+queue) \[
W_S=\frac 1{\mu-\lambda}=\frac{\rho}{\lambda(1-\rho)}
\] 平均等待时间\(W_q\)：(queue) \[
W_q=W_s-\frac 1{\mu}=\frac{\rho}{\mu-\lambda}=\rho\times W_S
\]
$ M/M/1/N/ $
其稳态概率方程： \[ \left\{ \begin{aligned} \lambda P_1&=\mu P_1 \\ \lambda P_{n-1}+\mu P_{n+1}&=(\lambda +\mu)P_n& ,1\le n\le N-1 \\ \mu P_N&=\lambda P_{N-1} \end{aligned} \right. \]
它的计算结果已知，自己去Google。
$ M/M/1//m$
顾客的总体数量是有限的，该模型等价于\(M/M/1/m/m\)
假设每个顾客到达率相同且为 \(\lambda\)，在系统外的平均顾客数为 \(m-L_S\)。
系统的有效到达率\(\lambda _e=\lambda(m-L_s)\)
(有效到达率与顾客总容量以及当前剩余的容量有关)
其稳态方程： \[
\left\{
\begin{aligned}
m\lambda_e P_1&=\mu P_1 \\
(m-n+1)\lambda_e P_{n-1}+\mu P_{n+1}&=[(m-n)\lambda_e +\mu]P_n&
,1\le n\le m-1 \\
\mu P_m&=\lambda_e P_{m-1}
\end{aligned}
\right.
\]
多服务台模型（FCFS）
\(M/M/c\)（标准型）
顾客流为泊松流，平均到达率为 \(\lambda\)，各个服务台的平均服务率是 \(\mu\)，则：
整个服务机构的平均服务率是：\(n\mu\ (n \lt c)\) or \(c\mu\ (n\ge c)\)，令\(\rho = \frac{\lambda}{c\mu}\)(系统服务强度)
当 \(\rho >1\) 时，会出现排队现象。
稳态方程如下。 \[
\begin{cases}
\lambda P_0=\mu P_1 \\
\lambda P_{n-1}+(n-1)\mu P_{n+1}=(\lambda +n\mu)P_n& ,1\le n\le c \\
c\mu P_{n+1}+\lambda P_{n-1}=(\lambda+c\mu)P_n&,n\gt c
\end{cases}
\]
\(M/M/c/N/\infty\)（系统容量有限型）
\(M/M/c/\infty/m\)（顾客源有限型）
略，Google。