【管理运筹学】背诵手册（七）| 网络计划与排队论
七、网络计划
网络图中的第一个事项称为起始事项，它只表示整个任务的开始；而最后一个事项称为终止事项，它只表示整个任务的结束；介于起始事项和终止事项之间的所有事项都称为中间事项，它既表示前项工作的结束，又表示后项工作的开始。
所有各条线路的长度中，可以找到一条所需工时最长的路，这条最长的线路在网络图中称为关键线路。
每道工作的期望工时可估计为 t ( i , j ) = a + 4 m + b 6 t(i,j)=\frac{a+4m+b}{6} t(i,j)=6a+4m+b 其中， a a a 为最乐观时间， b b b 为最悲观时间， m m m 为最可能完成时间。
事项有三个参数：最早开始、最迟结束、时差。
工作的时间参数有：最早开始、最早结束、最迟开始、最迟结束、总时差和单时差。
总时差给出了可供利用的最多机动时间，为工作最晚结束时间减去最早结束时间。总时差为 0 的工作称为关键工作，连接所有关键工作的线路即为关键线路。
工作的单时差为紧前工作最晚结束，紧后工作最早开始时具有的机动时间。关键工作的单时差一定为 0 ，但单时差为 0 的工作不一定为关键工作。
工作的总时差等于它的箭尾事项和箭头事项的时差之和，加上本身的单时差。
八、排队论
3 个基本部分：输入过程、排队规则、服务机构。
最主要、影响最大的三个因素：1. 顾客相继到达的间隔时间的分布；2. 服务时间的分布；3. 服务台个数。
Kendall 记号： X / Y / Z / A / B / C X/Y/Z/A/B/C X/Y/Z/A/B/C ，前三个分别为最主要三个因素，后三个分别是系统容量限制 N N N ，顾客源数目 m m m 以及服务规则。
M / M / 1 / ∞ / ∞ M/M/1/\infty/\infty M/M/1/∞/∞ 的状态概率的方程： { λ P 0 = μ P 1 , λ P n − 1 + μ P n + 1 = ( λ + μ ) P n , n ≥ 1. \begin{cases} \lambda P_0=\mu P_1, \\ \lambda P_{n-1}+\mu P_{n+1}=(\lambda+\mu)P_n,n\geq1. \end{cases} {λP0=μP1,λPn−1+μPn+1=(λ+μ)Pn,n≥1. 要求服务强度 ρ < 1 \rho<1 ρ<1 ，可推得： P 0 = 1 − ρ , P n = ρ n P 0 P_0=1-\rho,P_n=\rho^nP_0 P0=1−ρ,Pn=ρnP0 。各指标公式为： L s = λ μ − λ , L q = L s − λ μ ; W s = L s λ , W q = W s − 1 μ . L_s=\frac{\lambda}{\mu-\lambda},L_q=L_s-\frac{\lambda}{\mu};W_s=\frac{L_s}{\lambda},W_q=W_s-\frac{1}{\mu}. Ls=μ−λλ,Lq=Ls−μλ;Ws=λLs,Wq=Ws−μ1.
在 M / M / 1 M/M/1 M/M/1 情况下，顾客在系统中逗留的时间服从参数为 μ − λ \mu-\lambda μ−λ 的指数分布，因此期望为 1 / ( μ − λ ) 1/(\mu-\lambda) 1/(μ−λ) 。
Little 公式有四个，为 L s = λ W s , L q = λ W q ; W s = W q + 1 μ , L s = L q + λ μ . L_s=\lambda W_s,L_q=\lambda W_q;W_s=W_q+\frac{1}{\mu},L_s=L_q+\frac{\lambda}{\mu}. Ls=λWs,Lq=λWq;Ws=Wq+μ1,Ls=Lq+μλ. 对于有容量限制的 M / M / 1 / N / ∞ M/M/1/N/\infty M/M/1/N/∞ ，其状态概率的稳态方程，比 M / M / 1 / ∞ / ∞ M/M/1/\infty/\infty M/M/1/∞/∞ 多一个在系统中有 N N N 个顾客时的方程。此时系统只会中不会再有顾客进入，于是在 n = N n=N n=N 处只有： λ P N − 1 = μ P N \lambda P_{N-1}=\mu P_N λPN−1=μPN ，即 { λ P 0 = μ P 1 , λ P n − 1 + μ P n + 1 = ( λ + μ ) P n , n ≤ N − 1 , λ P N − 1 = μ P N . \begin{cases} \lambda P_0=\mu P_1, \\ \lambda P_{n-1}+\mu P_{n+1}=(\lambda+\mu)P_n,n\leq N-1,\\ \lambda P_{N-1}=\mu P_N. \end{cases} ⎩ ⎨ ⎧λP0=μP1,λPn−1+μPn+1=(λ+μ)Pn,n≤N−1,λPN−1=μPN. 此时有 P 0 + P 1 + ⋯ + P N = 1 P_0+P_1+\cdots+P_N=1 P0+P1+⋯+PN=1 ，可以解得 P 0 = 1 − ρ 1 − ρ N + 1 P_0=\frac{1-\rho}{1-\rho^{N+1}} P0=1−ρN+11−ρ 各个状态之间仍然是满足 P n = ρ n P 0 P_n=\rho^nP_0 Pn=ρnP0 。队长指标为 L s = ρ 1 − ρ − ( N + 1 ) ρ N + 1 1 − ρ N + 1 , L q = L s − ( 1 − P 0 ) L_s=\frac{\rho}{1-\rho}-\frac{(N+1)\rho^{N+1}}{1-\rho^{N+1}},L_q=L_s-(1-P_0) Ls=1−ρρ−1−ρN+1(N+1)ρN+1,Lq=Ls−(1−P0) 当考虑等待时间，到达率应变为有效到达率 λ e \lambda_e λe ，其值为 ( 1 − P N ) λ (1-P_N)\lambda (1−PN)λ ，可推出其另一个表达式为 λ e = μ ( 1 − P 0 ) \lambda_e=\mu(1-P_0) λe=μ(1−P0) 。Little 公式仍然适用，即 W s = L s / λ e , W q = W s − 1 / μ W_s=L_s/\lambda_e,W_q=W_s-1/\mu Ws=Ls/λe,Wq=Ws−1/μ 。
对于顾客源为有限 ( M / M / 1 / ∞ / m ) (M/M/1/\infty/m) (M/M/1/∞/m)的情形，最常见的是机器因故障待修的问题。特别的是它每个顾客经过服务后仍回到原来总体，所以它每个状态的到达转移都不相同。状态 0 到状态 1 的转移率为 m λ m\lambda mλ ，状态 1 到状态 2 的转移率为 ( m − 1 ) λ (m-1)\lambda (m−1)λ ，状态 m − 1 m-1 m−1 到状态 m m m 的转移率为 λ \lambda λ 。而且，由于顾客总体为 m m m ，实际上容量最大也不会超过 m m m ，因此这和 ( M / M / 1 / m / m ) (M/M/1/m/m) (M/M/1/m/m) 的意义相同。
对于标准的多服务台 ( M / M / c / ∞ / ∞ ) (M/M/c/\infty/\infty) (M/M/c/∞/∞) ，整个系统的平均服务率（平均利用率）为 λ / ( c μ ) \lambda/(c\mu) λ/(cμ) ，需保证其小于 1 。由于其有多个服务台，因此每个状态的离去转移也不同，状态 1 到状态 0 的转移率为 μ \mu μ ，状态 2 到状态 1 的转移率为 2 μ 2\mu 2μ，状态 n ( n < c ) n(n<c) n(n<c) 到状态 n − 1 n-1 n−1 的转移率为 n μ n\mu nμ 。当 n ≥ c n\geq c n≥c 时，后面的状态转移率一直为 c μ c\mu cμ 。
对于一般服务时间 M / G / 1 M/G/1 M/G/1 模型，是指顾客到达间隔服从负指数分布，但服务时间服从任意分布的情形。下面的关系都是成立的： E ( 系统中顾客数 ) = E ( 队列中顾客数 ) + E ( 服务机构顾客数 ) E ( 系统中逗留时间 ) = E ( 排队时间 ) + E ( 服务时间 ) E(系统中顾客数)=E(队列中顾客数)+E(服务机构顾客数)\\ E(系统中逗留时间)=E(排队时间)+E(服务时间) E(系统中顾客数)=E(队列中顾客数)+E(服务机构顾客数)E(系统中逗留时间)=E(排队时间)+E(服务时间) 当服务时间服从负指数分布时， E ( 服务时间 ) = 1 / μ , E ( 服务机构顾客数 ) = λ E ( T ) = ρ E(服务时间)=1/\mu,E(服务机构顾客数)=\lambda E(T)=\rho E(服务时间)=1/μ,E(服务机构顾客数)=λE(T)=ρ 。
P-K 公式（ ρ = λ E ( T ) \rho=\lambda E(T) ρ=λE(T)）： L s = ρ + ρ 2 + λ 2 D ( T ) 2 ( 1 − ρ ) L_s=\rho+\frac{\rho^2+\lambda^2D(T)}{2(1-\rho)} Ls=ρ+2(1−ρ)ρ2+λ2D(T) 只要知道 λ , E ( T ) , D ( T ) \lambda,E(T),D(T) λ,E(T),D(T) ，不管什么分布，就可以求出 L s L_s Ls ，进而求出 L q = L s − λ E ( T ) , W s = L s / λ , W q = L q / λ L_q=L_s-\lambda E(T),W_s=L_s/\lambda,W_q=L_q/\lambda Lq=Ls−λE(T),Ws=Ls/λ,Wq=Lq/λ 。