运筹学通论(下)课程笔记

Overview

KeyNotes

  1. 遍历$\Leftrightarrow$不可约+正常返;

预备知识

符号表

符号 意义
$N(t)$ 时间$(0,t]$内到达的顾客数
$\tau_n$ 更新时间间隔
$S_i$ 更新时刻
$M(t)$ 时间$(0,t]$内平均更新次数
$p_j^{(n)}$ $P\{X_n=j\}$
$\mathbf{p}^{(n)}$ $(p_0^{(n)},p_1^{(n)},\cdots)$, 马氏链在时刻$n$的瞬时分布
$\{p_j,j\in E\}$ 平稳分布:$\lim\limits_{n\to \infty}p_j^{(n)}=p_j$
$f_{ij}$ 有限步从 $i$ 到 $j$ 的首达概率
$\mu_i$ 状态 $i$ 的平均返回时间
$\lambda_i$ 生灭过程的出生速率
$\mu_i$ 生灭过程的死亡速率
  1. 定长分布(单点分布)
  2. 负指数分布
  3. $k$阶埃尔朗Erlang分布
  4. 超指数分布
  5. 泊松Poisson分布

Poisson 过程

定义:考虑当个到达的输入过程,令 $N(t)$ 表示在时间 $(0,t]$ 内到达的顾客数,如果 $N(t)$ 满足:

  1. $N(0)=0$;
  2. {$N(t), t\ge 0$}有独立、平稳增量;

则称$\{N(t),t\ge 0\}$是泊松过程、泊松流或简单流。

更新过程

几个概念:

  1. 更新间隔 $\tau_n$
  2. 更新时刻 $S_n$
  3. 更新次数 $N(t)$
  4. 更新函数 $M(t)$:表示平均更新次数

马尔可夫链

马尔可夫链的状态数是有限的或者无限的。经过一段时间,系统从一个状态转移到另外一个状态,只依赖于当前出发的状态,而于以前的历史状态无关。

  • 齐次的马尔可夫满足:$P\{X_{n+1}=j|X_0=i_0,X_1=i_1,\cdots,X_n=i\}=P\{X_{n+1}=j|X_n=j\}$
  • 马尔可夫性/无后效性:$P\{X_{n+1}=j|X_n=j\}=P\{X_1=j|X_0=i\},\quad \forall n \ge 0$

几个概念:

  1. 随机矩阵:非负矩阵$A=(a_{ij})$为随机矩阵,如果有$A$的任意一行元素之和为1。马尔可夫链$\{X_n|n\ge 0\}$的$n$步转移概率矩阵$P^{(n)}$是随机矩阵。
  2. Kolmogorov-Chapman(C-K)方程:

    分量形式:

  3. 首达时刻

  4. 首达概率
    • $f_{ij}^{(n)}$ 表示 $n$ 步首达 $j$ 的概率
    • $f_{ij}=\sum\limits_{n=1}^\infty f_{ij}^{(n)}$ 表示 有限步首达 $j$ 的概率
  5. 常返状态/非常返状态: $f_{ii}=1 $称状态 $i$ 是常返的;如果 $f_{ii} \lt 1$,称状态 $i$ 是非常返的。
  6. 常返状态的平均返回时间 $\mu_i=\sum\limits_{n=1}^\infty nf_{ii}^{(n)}$
  7. 正常返状态/零常返状态
    • 如果 $\mu_i \lt +\infty$,称状态 $i$ 是正常返的;
    • 如果 $\mu_i = +\infty$,称状态 $i$ 是零常返的;
  8. 周期状态/非周期状态:对于常返状态 $i$ 的周期$d$
    • 如果 $d>1$,称该状态是周期的;
    • 如果 $d=1$,称该状态是非周期的;

      周期 $d$ 的定义:对于常返状态 $i$,如果返回时间可以表示称 $d,2d,3d,\cdots$ (这里 $d$ 表示满足要求的最大正整数),则称 $d$ 是该状态的周期。

  9. 两个状态可达/互通
    • 可达:存在$n\ge 1$, 使得 $p_{ij}^{(n)} > 0$,则状态 $i$ 可达状态 $j$;
    • 互通:状态$i$可达状态 $j$、状态 $j$ 也可达状态 $i$
  10. 不可约:如果状态空间 $E$ 的任意两个状态都是互通的,称状态空间是不可约的,对应的马氏链也不可约。
  11. 遍历:如果马氏链不可约,每个状态又是正常返的,则该马氏链是遍历的。
  12. 不可约的齐次马氏链的状态要么全部都是正常返的、或全部都是零常返的、或者全部都是非常返的。如果有周期,则全部状态有相同的周期怎么证明???
  13. 平稳分布
    • 如果全部状态非常返、或者全部状态是零常返,则不存在平稳分布;
    • 如果全部状态是正常返,则而且,$\{p_j, j\in E\}$满足等式因此,$\{p_j, j\in E\}$是唯一的平稳分布
  14. 可数状态的马尔可夫过程
  15. 齐次的马尔可夫过程:其转移概率是齐次的,即 $p_{ij}(s, t)$ 只依赖于时间差 $t-s$,$p_{ij}(t)=p_{ij}(s+t),\, \forall s, t\ge 0$.
  16. 瞬时分布 $\mathbf{p}(t)$:$\mathbf{p}(t)=\{p_j(t),\, \forall j\in E\}$
  17. 标准的状态转移矩阵

    则称转移概率矩阵 $\mathbf{P}(t)$ 是标准的。

    设 $\mathbf{P}(t)$ 是标准的,则:

  18. 转移速率矩阵 $\mathbf{Q}$:$\mathbf{Q} = (q_{ij})\triangleq \mathbf{P}^\prime(0^+)=(p_{ij}^\prime(0^+))$,即矩阵 $Q$ 由转移概率函数 $p_{ij}(t)$ 在 $t=0$ 点的右导数组成。
    • 记 $q_i=-q_{ii}$,故 $0\le q_i\le +\infty$;
  19. 保守的转移速率矩阵 $Q$ 满足 $\sum\limits_{j\neq i} q_{ij}=q_i,\, \forall i\in E$。
  20. Kolmogorov 向后/向前方程
    Kolmogorov BF EquationsKolmogorov BF Equations
    Kolmogorov BF Equations-1Kolmogorov BF Equations-1
  21. 齐次不可约马氏过程存在平稳分布 $\pi=(\pi_0,\pi_1,\cdots)$,且满足方程$\pi \mathbf{Q}=\mathbf 0$。结合归一化条件可以求得马氏过程的平稳分布。

生灭过程

没看懂,先跳过

一些概念:

  1. 出生速率 $\lambda_i$、死亡速率 $\mu_i$;

在$\{p_j, j\in E\}$存在的条件下,有下面的平衡方程:

  1. 有限状态的生灭过程 $E=\{0,1,\cdots,K\}$,有: 然后结合$\sum_{j=0}^{K}p_k=1$,可得:其中,
  2. 无限状态的生灭过程 $E=\{0,1,2,\cdots\}$,有: 然后结合$\sum_{j=0}^{\infty}p_k=1$,可得:其中,

排队论

符号表

符号 意义
$T_i$ 第 $i$ 个顾客达到的时间
$X_i$ $X_i=T_i-T_{i-1}$,顾客相继到达间隔
$p_n(t)$ $p_n(t)=P\{N(t)=n\},\, n, t\ge 0$
$p_n$ 系统中有 $n$ 个顾客的稳态概率,$\lim\limits_{t\to\infty}p_n(t)=p_n, n\ge 0$
$\{p_n, n\ge 0\}$ 稳态队长分布
$a_n$ $P\{稳态下到达的顾客发现已经有 n 个顾客在系统中\}$
$\pi_n$ $P\{稳态下顾客离开时发现身后恰有 n 个顾客在系统中\}$
$N$ 稳态下的队长 $N=P\{N=n\}, n\ge 0$
$L$ 稳态下的平均对长 $L=E[N]=\sum\limits_{n=0}^\infty np_n$
$L_q$ 系统中等待的顾客平均数
$T_q(t)$ 时刻 $t$ 到达的顾客的等待时间分布函数
$T_q$ 稳态下顾客的等待时间
$S$ 顾客的服务时间
$T$ 顾客的逗留时间 $T=T_q+S$
$W_q$ 稳态下顾客的平均等待时间 $W_q=E[T_q]$
$W$ 稳态下顾客的平均逗留时间 $W=E[T]$
忙期 服务台从开始工作到所有服务台空间之间的间隔
闲期 服务台空闲的时间长度
$A(t)$ $(0,t)$ 中到达的顾客数分布函数
$B(t)$ $(0,t)$ 中到达的顾客在系统中逗留时间之和
$\lambda(t)$ $(0,t)$ 中顾客平均到达速率 $=\frac{A(t)}{t}$
$\mu$ 服务时间的负指数分布参数
$W(t)$ $(0,t)$ 中到达顾客的平均逗留时间分布函数 $=\frac{B(t)}{A(t)}$
$\rho$ 排队系统的交通强度 $\rho=\frac{\lambda}{\mu}$
$T_n^+$ 第 $n$ 个顾客服务完毕离去的时刻

一般性结论

  1. 当输入过程为Poisson过程时,有 $\forall\, t\ge 0, p_n(t)=a_n(t),\, n\ge 0$

Little 公式

  1. 设平均到达率 $\lambda$,平均逗留时间 $W$ 存在,即: 则平均队长 $L$ 也存在,且满足:
  2. 考虑系统中的平均等待顾客数 $L_q(t)$:有 $L_q=\lambda W_q$

M/M/型模型

$M/M/1/\infty$

顾客到达服从参数为 $\lambda (\, >0)$ 的Poisson过程,服务时间服负服指数分布参数为 $\mu (\, >0)$。

  1. 定义状态和状态空间

    • 状态:系统顾客数 $N(t)$
    • 状态空间:$E=\{0,1,2,\cdots\}$
  2. 确定状态转移率

  3. 画出状态转移图并得到 $Q$ 矩阵

    • 状态转移图
      M/M/1/infty StatusM/M/1/infty Status
    • $Q$ 矩阵
  4. 微分差分方程组
    由Kolmogorov向前方程$\mathbf p^\prime(t)=\mathbf p(t)\mathbf{Q}$, 得到:

    令$p_j=\lim\limits_{t\to\infty}p_j(t), j=0,1,2,\cdots$,

    • 当 $\rho \ge 1$, $p_j=0$ 不构成概率分布;
    • 当 $\rho < 1$, 也称此时是统计平衡,$\{p_j\}$ 存在,且与初始分布无关,且构成几何概率分布:
  5. 稳态下的数字特征

    • 平均顾客数 $L=E[N]$;
    • 顾客数方差 $D[N]$;
    • 等待的平均顾客数 $L_q=E[N_q]$;
    • 等待顾客数方差 $D[N]$;
    • 非空排队的指标
  6. 等待时间/逗留时间

    • 等待时间分布函数 $W_q(t)$;
    • 平均等待时间 $\bar{W}_q(t)=E[W_q]$;
    • 等待时间方差 $D[W_q]$
    • 逗留时间分布函数 $W(t)$;
    • 平均逗留时间 $\bar{W}(t)=E[W]$;
    • 逗留时间方差 $D[W]$
  7. 忙期

    • 忙期的分布密度函数 $B(t)$;
    • 平均忙期长度 $\bar{b}$;
    • 一个忙期所服务的平均顾客数 $\mu \bar{b}$

      结论:忙期内相继输出的间隔时间是独立的,同参数 $\mu$ 的随机变量,即参数为 $\mu$ 的Poisson流。

  8. 输出过程

    • 顾客离去的时间间隔 $T^+_{n+1}-T^+_{n}, n\ge 1$

具有可变输入的 M/M/1/$\infty$

- 顾客达到不一定都进入系统,而与该顾客到达时看到的队长 $k$ 有关,他此时进去系统的概率为 $a_k$,且 $1=a_0>a_1>a_2>\cdots>a_k\to 0,\ (k\to \infty)$。
- 到达的参数依旧是参数为 $\lambda(\lambda > 0)$的Poisson过程,服务服从参数为 $\mu$ 的负指数分布。

$M/M/\infty$ 模型

在忙的服务台数=系统中顾客数,即服务台数无穷,系统无等待时间,逗留时间就是服务时间。
状态转移概率为:

$M/M/c/\infty$ 模型

离去过程是参数为 $\lambda$ 的简单流。
状态转移概率为:

$M/M/c/K$ 模型

系统中总共有 $K$ 个位置,$c$ 个服务台独立工作,$c\le K$。当 $K$ 个位置全部被占用,新到的顾客就自动离开。到达当顾客依然是参数为 $\lambda$ 的泊松流,服务时间为参数为 $\mu$ 的负指数分布。
状态转移概率为:

有限源的简单排队系统

$M/M/c/M/M$ 系统

$M/M/c/c/M$ 系统

其他类似系统

  • M/M/c/m + K/m 系统
  • 两阶段循环排队系统

可化成 M/M 型排队系统

$M/E_k/1/\infty$ 系统

到达时间是Poisson流,服务时间是 $k$ 级Erlang分布。把顾客的服务时间看成 $k$ 个相位(独立,同指数分布),每个相位的平均服务时间为 $\frac{1}{k\mu}$,依次降次排列。
此时的状态 $N(t)$ 是一个二元组 $(n,i)$,$n$ 表示系统的顾客数,$i$ 表示正在接受服务的顾客所处的位相。状态空间 $E=\{(n,i)|i=1,2,\cdots,k; n=1,2,\cdots\}\cup \{0\}$
状态转移图为:
状态转移图状态转移图

$E_k/M/1/\infty$ 排队系统

顾客相继到达的时间间隔是 $k$ 阶Erlang分布。将顾客的到达划分为 $k$ 个位相处理。
此时的状态 $N(t)$ 是一个二元组 $(i,n)$,$n$ 表示系统的顾客数,$i$ 表示到达的顾客所处的位相。状态空间 $E=\{(i,n)|i=1,2,\cdots,k; n=0,1,\cdots\}$
状态转移图为:
状态转移图状态转移图

$E_k/E_l/1/\infty$ 排队系统

$M/PH/1/\infty$ 排队系统

服务时间是 $PH$ 分布。

Phase-type ($PH$) 分布:对于一个连续时间、具有 $m+1$ 个状态的 $(m\ge 1)$ 的马氏过程,其中 $1,2,\cdots,m$ 是瞬态状态,$m+1$ 是吸收状态。假设一个过程的初始分布向量是 $(\alpha, \alpha_m)$,那么,连续时间的 $PH$ 分布就是上面过程出发到吸收状态的时间分布。
参考链接:Wikipedia: Phase-type_distribution

$PH/M/1/\infty$ 排队系统

$PH/PH/1/\infty$ 排队系统

一般排队系统

马氏决策-绪论

序列决策模型

关键(已知量):

  1. 所有的决策时刻点集;
  2. 系统的所有可能的状态集合;
  3. 可以采用的全体行动集合;
  4. 与状态和行动有关连的即得报酬或费用集合;
  5. 与状态和行动有关连的状态转移概率的集合;

马氏决策过程

$\{T, S, A(i), p(\cdot|i,a), r(i,a)\}$ 称为一个马氏决策过程。转移概率只依赖于当前的状态和决策者选取的行动,而不依赖于过去的历史。

有限阶段($N$ 阶段)准则

$T=\{0,1,\cdots,N-1\}, 0 \lt N\lt \infty$, $r(i,a)$ 是有界报酬函数。在选择一个策略并实施之后,决策者在 $0,1,\cdots, N$ 时依一定的概率收到一串报酬,将其累加就是该模型的效用函数
对 $N\ge 0$,策略 $\pi \in \Pi$ 下的 $N$ 阶段期望总报酬效用函数定义为:

无限阶段折扣模型

离散决策时刻、无限阶段的折扣马氏决策问题。$T=\{0,1,\cdots\}$,决策者在阶段 $0,1,\cdots$ 时可以依一定概率获得一串报酬,报酬折现以后累加就是该模型的具体效用函数,折现率称为折扣因子
对策略 $\pi\in\Pi$ 和固定的折扣因子 $\beta, (0\lt \beta\lt 1)$,折扣模型的报酬效用函数定义为:

平均准则

离散决策时刻,无限阶段,采用平均期望报酬来代替折扣模型的马氏决策问题。

为状态 $i$ 出发并使用策略 $\pi$ 的平均收益。

主要结论

主要结论主要结论

马氏决策-有限阶段模型

有限阶段的值迭代算法

有限阶段的值迭代算法有限阶段的值迭代算法
$u_t^\pi(i)$ 表示的是从决策时刻 $k$ 开始以后到决策时刻终止的报酬和。

有限阶段向后递归迭代算法

有限阶段向后递归迭代算法有限阶段向后递归迭代算法

单调向后递归算法

单调向后递归算法单调向后递归算法
步骤5 没有太懂

马氏决策-折扣模型

Banach 不动点定理

设 $P$ 是一个 $N\times N$ 的实矩阵,如果当 $n\to\infty$ 时 $P^n\to \mathbf 0$。那么,$I-P$的逆矩阵存在,且有:

策略迭代算法

策略迭代算法策略迭代算法

值迭代算法

值迭代算法值迭代算法

改进的策略迭代算法

马氏决策-平均模型

References

  1. Ke Liu. 运筹学通论课件.

Appendix

Appendix A. 常见级数

我好菜啊,常见的级数求和都不熟练了

Appendix B. 马尔可夫链收敛的充分条件

  • 离散时间
  • 有限状态
  • 非周期:马尔可夫链是非周期的
  • 不可约:任意两个状态互通

Tips: PageRank的转移矩阵就是一个Markov收敛的状态转移概率矩阵。

坚持原创技术分享,您的支持将鼓励我继续创作!