连续时间马尔科夫链及其在排队论中的应用

Continuous Time Markov Chain and Its Applications in Queuing Theory

摘要: 马尔科夫链的无记忆性简化了复杂系统的分析，使之成为研究排队论的核心方法之一。本文首先介绍了连续时间马尔科夫链的基本知识。然后重点探讨了连续时间马尔科夫链在排队论中的实际应用，借助于生灭过程的平稳分布等概率方法，详细分析了在数学期望的意义下的最优库存管理问题，展现了该模型的重要实用价值，为数学在管理科学、机械工程中的融通发展提供了重要的理论支持，也对培养学生理论联系实际的能力具有重要的提升作用。

Abstract: The Markov chains has become one of the core models in studying queuing theory, due to the fact that its memoryless property helps to simplify the analysis of complex systems. In this article, some basic knowledge of continuous time Markov chains is recalled at first. Then, the practical application of continuous time Markov chains in queuing theory was discussed. By applying probability methods such as the stationary distribution of birth and death processes, the optimal inventory management problem is solved thoroughly in the sense of mathematical expectations. The obtained results show the significant practical value of the continuous time Markov chains model and provide important theoretical support for the integrated development between mathematics, management science and mechanical engineering. Moreover, it also plays an important role in enhancing students’ ability to integrate theory with practice.

1. 引言

马尔科夫链是1906年由俄国数学家A. Markov提出的一种能用数学分析方法研究自然过程的一般图式。众所周知，在自然科学、经济活动和日常生活中存在大量的随机过程，如某地发生台风的次数、股票的价格变化、银行办理业务时的排队人数等。很多随机过程因具有某种特殊性质而获得不同的名称，如高斯过程、平稳过程等，其中，马尔科夫链是一种具有无记忆性的随机过程，其核心特点是：下一状态的概率分布仅由当前状态决定，而与之前的状态无关。这一性质被称为马尔科夫性质。A. Markov进行深入研究后指出：对于一个系统，由一个状态转至另一个状态的转换过程中，存在着转移概率，并且这种转移概率可以依据其紧接的前一种状态推算出来，与该系统的原始状态和此次转移前的马尔科夫过程无关。特别是在相同的时间长度里，若系统的转移规律相同且不随时间起点而改变，则这种随机过程称为具有平稳转移概率的马尔科夫链[1]。

二十世纪初，数学家们逐渐开始研究马尔科夫链的理论基础，包括状态分类、极限行为等。例如N. Wiener和P. Lévy等学者将马尔科夫链应用于更广泛的随机过程研究。二十世纪三十年代至五十年代，随着概率论基本理论的成熟与完善，马尔科夫链的理论得到了进一步发展。J. Doob和W. Feller等学者对马尔科夫链的极限定理和遍历性进行了深入研究。二十世纪后半叶，计算机技术的发展使得马尔科夫链的模拟和计算变得更加可行。蒙特卡罗方法和基于马尔科夫链的蒙特卡罗算法(Markov Chain-Monte Carlo, MCMC)已在统计学和机器学习中得到广泛应用。D. Ravenzwaaij等人详细介绍了对马尔科夫链蒙特卡罗采样的基本原理，通过简单的示例描述了什么是MCMC，我们可以利用这一算法解决哪些问题。同时，重点介绍了MCMC抽样的优势和局限性，并给出了规避这些困扰科学家的局限性的不同方法[2]。如今，马尔科夫链的理论与方法已经被广泛应用于自然科学、工程技术等方向[3]-[5]。宋永港与刘宏宽为研究海平面上升对黄浦江高潮位的影响，以上海吴淞站为代表，采用马尔科夫链蒙特卡罗算法预测了500组吴淞站未来30年最高潮位，预测未来30年内，海平面上升将引起吴淞站6.6 m以上千年一遇高潮位出现的概率增加14% [6]。

排队论是运筹学的分支之一，主要研究系统中排队现象的科学，通过数学模型分析顾客到达、服务时间、队列长度等，以优化服务效率和资源利用。排队论的起源可以追溯到1909年，丹麦数学家A. Erlang发表了关于电话流量和排队问题的研究，奠定了排队论的基础。英国统计学家D. Kendal在1953年提出了Kendall记号法，用于描述排队模型的特征，使得排队论在运筹学和工业工程领域得到了进一步的发展。由于在排队系统中，顾客的到达和服务过程通常是随机的，在一些常用的排队模型中，都假设顾客到达和服务时间服从泊松过程或指数分布，这些随机分布所具有的无记忆性，同时假设未来的队列长度或等待时间只依赖于当前状态，而与过去的状态无关。马尔科夫链的“无记忆性”恰好符合这一特性。另一方面，马尔科夫链提供了一种简洁的数学框架来描述系统的状态转移，即将排队系统的状态(如队列中的顾客数量)用马尔科夫链的状态来表示，而状态之间的转移通过转移概率矩阵来描述。这种建模方式大大简化了复杂排队系统的分析难度。此外，在排队系统的稳态分析中，如平均排队长度、平均等待时间、系统利用率等性能指标非常关键。而这些指标也可以容易地通过马尔科夫链的稳态方程得到。基于以上原因，马尔科夫链成为分析排队系统的理想工具。

库存管理起源于二十世纪初的经济批量订货(EOQ)公式，基于确定性需求模型安排订货策略。该模型自提出后，学者们从动态定价、多产品批量优化等方向进行了拓展[7] [8]。然而，需求和供应往往具有不确定的波动性，往往需要结合概率分布(如泊松分布、指数分布等)设计库存策略。在这类随机模型中，人们更为关注于优化安全库存[9]。近年来，随着计算机技术的飞速发展，MCMC算法的引入使得以排队论模型为代表的随机模型在零售业、库存管理等领域中有了更加深入的应用。田志勇等人应用马尔科夫链理论，提出基于车辆库存的站点服务损失成本的计算方法，并根据溢出效应设计需求泊松参数调整方程组，构建最优车辆库存模型[10]。蒋莱建立了汽车零部件生命周期特点的预测模型，通过马尔科夫链的优化，克服了灰色模型与三次指数平滑法拟合精度不理想的缺陷[11]。

2. 连续时间马尔科夫链的基本概念

相较于离散时间马尔科夫链，连续时间的马尔科夫链有着更为广泛的应用，由于其时间的连续性，相应的理论和方法也有所不同。

• 连续时间马尔科夫链[12]：设随机过程$\left\{X\left(t\right),t\ge 0\right\}$ 的状态空间S，其中S可以是有限集或无限集。若对于任意一组时间取值$0\le t_1<t_2<\cdots <t_n<u<t$ ，X(t)的条件概率满足：

$P\left\{X\left(t\right)=j|X\left(t_1\right)=i_1,X\left(t_2\right)=i_2,\cdots ,X\left(t_n\right)=i_n,X\left(u\right)=i\right\}=P\left\{X\left(t\right)=j|X\left(u\right)=i\right\},$

即已知$X\left(u\right)=i$ 时，X(t)的条件概率与在u时刻之前的系统状态无关，仅与u时刻所处的状态有关，则称该随机过程X(t)是一个连续时间的马尔科夫链。

特别地，若条件概率$P\left\{X\left(t\right)=j|X\left(u\right)=i\right\}$ 只与时间区间$\left(u,t\right]$ 的长度有关、与其时间起点u无关，记作$p_{ij}\left(t-u\right)=P\left\{X\left(t\right)=j|X\left(u\right)=i\right\}$ ，则称该马尔科夫链是齐次的或具有平稳转移概率的，并称$p_{ij}\left(t-u\right)$ 为该区间上的转移概率。

• 转移矩阵：在上述转移概率$p_{ij}\left(t-u\right)$ 中，取$u=0$ ，则称矩阵

$P\left(t\right)=\left[\begin{array}{ccccc}{p}_{00}\left(t\right)& p_{01}\left(t\right)& \cdots & p_{0i}\left(t\right)& \cdots \\ p_{10}\left(t\right)& p_{11}\left(t\right)& \cdots & p_{1i}\left(t\right)& \cdots \\ ⋮& ⋮& \cdots & ⋮& \cdots \\ p_{i0}\left(t\right)& p_{i1}\left(t\right)& \cdots & p_{ii}\left(t\right)& \cdots \\ \cdots & \cdots & \cdots & \cdots & \cdots \end{array}\right]$

为齐次马尔科夫链的转移矩阵，且满足${\displaystyle \sum _j{p}_{ij}\left(t\right)}=1$ 。

• 生灭过程：对于齐次的连续时间马尔科夫链，如果系统从状态i出发，在极短时间内只能转移到左右相邻的状态，则称从状态i转移到状态i + 1为生、从状态i转移到状态i + 1为灭，这一转移过程称为生灭过程，其转移矩阵为

$P=\left[\begin{array}{ccccc}{p}_{00}& p_{01}& 0& 0& \cdots \\ p_{10}& p_{11}& p_{12}& 0& \cdots \\ 0& p_{21}& p_{22}& p_{23}& \cdots \\ 0& 0& \ddots & \ddots & \ddots \\ \cdots & \cdots & \cdots & \ddots & \ddots \end{array}\right].$

生灭过程这一随机模型有着广泛的实用背景。如某一地区人口数量的自然增加或减少(不考虑迁移)、细菌的繁殖与死亡等都可以用生灭过程描述。

3. 连续时间马尔科夫链在库存管理中的应用

问题背景：某企业在采购产品时必须考虑，若进货量较大，则需要缴纳大量的存储费；反之，若进货量太小，则可能影响生产造成经济损失。解决这一问题最好的办法是能及时供应。考虑到生产、运输等多方面原因，这一方法较为理想化，在实际运营中难以做到。根据往年的销售经验该企业对产品的需求量服从参数为$\lambda$ 的泊松分布、生产时间服从参数为$\mu$ ，$\left(\lambda <\mu \right)$ 的指数分布。每件产品单位时间的存储费为c元，缺货损失费为h元。因此，企业希望寻求合适的库存量S，使得存储费与缺货损失费的总和最小。

问题求解：如果把企业的需求视为“顾客”、需求量视为“排队队长”、生产厂家视为“服务台”，那么这个问题对应着排队论中的M/M/1/∞模型。

设$N\left(t\right)$ 表示t时刻的企业需求量，$p_k\left(t\right):=P\left\{N\left(t\right)=k\right\}$ ，并取服务强度$\rho =\frac{\lambda }{\mu }$ 。由于产品需求量服从泊松分布、生产时间服从指数分布，故在销售、生产过程的任何时间内，状态的转移概率与时间起点无关、只与时间跨度有关。由此可知，这两个过程都是齐次的连续时间马尔科夫链。以下，我们证明$\left\{N\left(t\right),t\ge 0\right\}$ 是生灭过程。

在一个充分小的时间区间$\left[t,t+\Delta t\right]$ 内，由连续时间马尔科夫链的无记忆性，生产量的转移概率

$p_{i,i+1}\left(\Delta t\right)=P\left\{N\left(t+\Delta t\right)=i+1|N\left(t\right)=i\right\}=\lambda \Delta t{\text{e}}^{-\lambda \Delta t}=\lambda \Delta t+o\left(\Delta t\right),$ (1)

且当$j>i+1$ 时，

$p_{i,j}\left(\Delta t\right)=P\left\{N\left(t+\Delta t\right)=j|N\left(t\right)=i\right\}=o\left(\Delta t\right).$ (2)

同理可得，产品需求量的转移概率

$p_{i,j}\left(\Delta t\right)=\{\begin{array}{l}\lambda \Delta t+o\left(\Delta t\right),j=i-1,\hfill \\ o\left(\Delta t\right),j<i-1.\hfill \end{array}$ (3)

由于需求量与生产量是相互独立的，结合(1)~(3)可知$\left\{N\left(t\right),t\ge 0\right\}$ 是生灭过程，且其参数为

$\{\begin{array}{c}{\lambda }_k=\lambda ,k\ge 0,\\ {\mu }_k=\mu ,k\ge 1.\end{array}$

根据生灭过程的基本理论，当$\rho =\frac{\lambda }{\mu }<1$ 时，其平稳分布存在，且满足

$p_k=\underset{t\to \infty }{\lim }{p}_k\left(t\right)=\frac{{\lambda }_{k-1}{\lambda }_{k-2}\cdots {\lambda }_0}{{\mu }_k{\mu }_{k-1}\cdots {\mu }_1}\cdot \frac{1}{{\displaystyle \sum _{k=0}^{\infty }\frac{{\lambda }^k}{{\mu }^k}}}={\rho }^k\left(1-\rho \right),k\ge 1.$

基于以上讨论，我们在数学期望的意义下分别计算该企业的平均缺货数与平均库存数。其中，平均缺货数

$\begin{array}{c}{N}_{缺}={\displaystyle \sum _{n=S}^{\infty }\left(n-S\right)p_n}={\displaystyle \sum _{n=S}^{\infty }n\left(1-\rho \right){\rho }^n}-S{\displaystyle \sum _{n=S}^{\infty }\left(1-\rho \right){\rho }^n}\\ ={\displaystyle \sum _{n=S}^{\infty }n\left(1-\rho \right){\rho }^n}-S{\rho }^S.\end{array}$

平均库存数

$\begin{array}{c}{N}_{存}={\displaystyle \sum _{n=0}^{S-1}\left(S-n\right)p_n}=S{\displaystyle \sum _{n=0}^{S-1}\left(1-\rho \right){\rho }^n}-{\displaystyle \sum _{n=0}^{S-1}n\left(1-\rho \right){\rho }^n}\\ =S\left(1-{\rho }^S\right)-\frac{\rho }{1-\rho }+{\displaystyle \sum _{n=S}^{\infty }n\left(1-\rho \right){\rho }^n}.\end{array}$

因此，企业需支付的总费用为

$\begin{array}{c}F\left(S\right)=c{N}_{存}+h{N}_{缺}\\ =c\left[S\left(1-{\rho }^S\right)-\frac{\rho }{1-\rho }+{\displaystyle \sum _{n=S}^{\infty }n\left(1-\rho \right){\rho }^n}\right]+h\left[{\displaystyle \sum _{n=S}^{\infty }n\left(1-\rho \right){\rho }^n}-S{\rho }^S\right]\\ =c\left[S\left(1-{\rho }^S\right)-\frac{\rho }{1-\rho }\right]+\left(h+c\right){\displaystyle \sum _{n=S}^{\infty }n\left(1-\rho \right){\rho }^n}-hS{\rho }^S.\end{array}$ (4)

又因为

${\displaystyle \sum _{n=S}^{\infty }n\left(1-\rho \right){\rho }^n}={\rho }^S{\displaystyle \sum _{k=0}^{\infty }\left(k+S\right)\left(1-\rho \right){\rho }^k}={\rho }^S\left(\frac{\rho }{1-\rho }+S\right).$ (5)

将(5)代入(4)可得，

$\begin{array}{c}F\left(S\right)=c\left[S\left(1-{\rho }^S\right)-\frac{\rho }{1-\rho }\right]+\left(h+c\right)\frac{{\rho }^{S+1}}{1-\rho }+\left(h+c\right)S{\rho }^S-hS{\rho }^S\\ =cS-\frac{c\rho \left(1-{\rho }^S\right)}{1-\rho }+\frac{h{\rho }^{S+1}}{1-\rho }.\end{array}$

设$S^{\ast }$ 为$F\left(S\right)$ 的最小值点，则$S^{\ast }$ 满足

$F\left(S^{\ast }+1\right)\ge F\left(S^{\ast }\right),且F\left(S^{\ast }-1\right)\ge F\left(S^{\ast }\right).$

由$F\left(S^{\ast }+1\right)\ge F\left(S^{\ast }\right)$ 可得${\rho }^{S^{\ast }+1}\le \frac{c}{c+h}$ ，即

$S^{\ast }\ge \frac{\ln c-\ln \left(c+h\right)}{\ln \rho }-1.$

另一方面，由$F\left(S^{\ast }-1\right)\ge F\left(S^{\ast }\right)$ 可得${\rho }^{S^{\ast }}\ge \frac{c}{c+h}$ ，即

$S^{\ast }\le \frac{\ln c-\ln \left(c+h\right)}{\ln \rho }.$

综上，

$S^{\ast }\in \left[\frac{\ln c-\ln \left(c+h\right)}{\ln \rho }-1,\frac{\ln c-\ln \left(c+h\right)}{\ln \rho }\right]$

有唯一的整数取值，该值即为该企业在追求最小成本时所寻求的最优库存数。

注：在上述库存管理问题中，如果该企业有多条供货渠道(生产产家)，则可以利用M/M/m/∞系统或m个M/M/1/∞系统来求解最优库存问题模型，其中m为供货渠道的数量。根据排队论的基本原理，除空闲概率$p_0$ 外，M/M/m/∞系统的各项性能指标，如服务强度、等待时间、等待队长等均优于m个M/M/1/∞系统。

4. 总结与展望

近几十年来，排队论的应用几乎无处不在。凡是具有公共服务性质的行业、凡是可能出现拥挤的领域，都有排队论的用武之地。随着人们对科学管理的需求不断提升，排队论已成为优秀管理人员的必备知识，各高校都开设了排队论的相关课程。连续时间马尔科夫链作为数学建模中的一类基础模型，以微积分与初等概率论知识为基础，为研究排队论问题提供了一种重要的理论方法，但其抽象性使得部分学生在学习过程中难度较大。本文通过最优库存管理中的实际案例，将连续时间马尔科夫链的原理与专业课中的现实问题相结合，帮助学生更加形象、深入地理解数学理论。在教学实践中，这一理论与实践相结合的思想，对培养学生解决实际问题的能力、实现中国式现代化的人才建设目标具有重要意义。此外，基于连续时间马尔科夫链的排队论模型在处理运输管理、城市交通管理与流量控制、可靠性、军事运筹学方面都体现出其强大的能力，现已融入到数学建模课程与竞赛等方面[13] [14]，能够促进数学与管理科学、机械工程等学科的融合发展。

需要指出的是，连续时间马尔科夫链在应用于库存管理时也存在一定的局限性。例如，实际需求可能受到季节性影响或因供应链中断发生突变，此时模型可能出现偏差，转移概率也可能失效。另一方面，EOQ公式在库存管理中也有广泛应用，但该方法难以直接融入马尔科夫链模型。这些都将为连续时间马尔科夫链在库存管理中的应用带来新的机遇。

基金项目

本文受上海市扬帆计划(23YF1429100)，上海市高等教育学会2024~2026年度规划研究课题(2QYB24120)，和上海理工大学本科教学研究与改革项目(JGXM202310, JGXM202410)的资助。

NOTES

^*通讯作者。