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

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分布
    $$\begin{align*}
    f(t)=\begin{cases}
    \frac{\lambda(\lambda t){k-1}}{(k-1)!}e{-\lambda t}, & t\ge 0;\
    0,& t<0.
    \end{cases}
    \end{align*}$$
  4. 超指数分布
  5. 泊松Poisson分布
    $$\begin{align*}
    p_i=P{X=i}=\frac{\lambdai}{i!}e{-\lambda},\quad i=0,1,2,\cdots
    \end{align*}$$

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)方程:
    $$P{(n+m)}=P{(n)}P{(m)}=P{(m)}P^{(n)},\quad \forall n, m\ge 0$$
    分量形式:
    $$p_{ij}^{(n+m)}=\sum_{k\in E}p_{ik}{(n)}p_{kj}{(m)}, \forall i,j\in E$$

  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$ 是零常返的;
      $$\begin{align*}
      状态的属性 \begin{cases}
      常返状态\begin{cases}
      正常返状态\
      零常返状态\
      \end{cases}\
      非常返状态
      \end{cases}\
      常返状态,才具有平均返回时间、周期。
      \end{align*}$$
  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. 平稳分布

    • 如果全部状态非常返、或者全部状态是零常返,则不存在平稳分布;
    • 如果全部状态是正常返,则
      $$\begin{align*}
      p_j=\frac{1}{\mu_i} \gt 0,\quad \forall\ j\in E
      \end{align*}$$
      而且,${p_j, j\in E}$满足等式
      $$\begin{align*}
      \sum_{j\in E}p_j=1,, p_j=\sum_{i\in E}p_ip_{ij},\quad \forall\ j\in E
      \end{align*}$$
      因此,${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. 标准的状态转移矩阵


    $$\lim_{t\to 0^+}p_{ij}(t)=\delta_{ij}=\begin{cases}
    0, & i\neq j\
    1, & i=j
    \end{cases}\quad \forall, i,j \in E
    $$
    则称转移概率矩阵 $\mathbf{P}(t)$ 是标准的。

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

    • $$-\infty \le \lim_{t\to 0^+}\frac{p_{ii}(t)-1}{t}\triangleq q_{ii}\le 0, \forall\ i\in E$$
    • $$0 \le \lim_{t\to 0^+}\frac{p_{ij}(t)}{t}\triangleq q_{ij}\le +\infty, \forall\ i\neq j$$
  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$。结合归一化条件
    $$\begin{align*}
    0\le \pi\le 1\
    \sum_{i\in E}\pi_i=1
    \end{align*}$$
    可以求得马氏过程的平稳分布。

生灭过程

没看懂,先跳过

一些概念:

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

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

  1. 有限状态的生灭过程 $E={0,1,\cdots,K}$,有:
    $$\begin{align*}
    \begin{cases}
    \lambda_0 p_0=\mu_1 p_1,\
    (\lambda_j+\mu_j)p_j=\lambda_{j-1}p_{j-1}+\mu_{j+1}p_{j+1},\quad j=1,2,\cdots,K-1\
    \lambda_{K-1}p_{K-1}=\mu_Kp_k
    \end{cases}
    \end{align*}$$
    然后结合$\sum_{j=0}^{K}p_k=1$,可得:
    $$
    p_j=\left(\frac{\lambda_0\lambda_1\cdots\lambda_{j-1}}{\mu_1\mu_2\cdots\mu_{j}}\right)p_0,\quad j=1,2,\cdots,K
    $$
    其中,
    $$
    p_0=\frac{1}{1+\sum_{j=1}^K\frac{\lambda_0\lambda_1\cdots\lambda_{j-1}}{\mu_1\mu_2\cdots\mu_j}}
    $$
  2. 无限状态的生灭过程 $E={0,1,2,\cdots}$,有:
    $$\begin{align*}
    \begin{cases}
    \lambda_0 p_0=\mu_1 p_1,\
    (\lambda_j+\mu_j)p_j=\lambda_{j-1}p_{j-1}+\mu_{j+1}p_{j+1},\quad j=1,2,\cdots\
    \end{cases}
    \end{align*}$$
    然后结合$\sum_{j=0}^{\infty}p_k=1$,可得:
    $$
    p_j=\left(\frac{\lambda_0\lambda_1\cdots\lambda_{j-1}}{\mu_1\mu_2\cdots\mu_{j}}\right)p_0,\quad j=1,2,\cdots
    $$
    其中,
    $$
    p_0=\frac{1}{1+\sum_{j=1}^\infty\frac{\lambda_0\lambda_1\cdots\lambda_{j-1}}{\mu_1\mu_2\cdots\mu_j}}
    $$

排队论

符号表

符号 意义
$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 公式

$$\begin{align*}
L(t)=\frac{1}{t}\int_0^tN(x)\mathrm{d}x=\frac{B(t)}{t}=\frac{A(t)}{t}\frac{B(t)}{A(t)}=\lambda(t)W(t)
\end{align*}$$

  1. 设平均到达率 $\lambda$,平均逗留时间 $W$ 存在,即:
    $$\begin{align*}
    \lim_{t\to \infty}\lambda(t)=\lambda,\
    \lim_{t\to \infty}W(t)= W
    \end{align*}$$
    则平均队长 $L$ 也存在,且满足:
    $$\begin{align*}
    L=\lim_{t\to \infty}L(t)=\lambda W
    \end{align*}$$
  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. 确定状态转移率
    $$\begin{align*}
    p_{ij}(\Delta t)=\begin{cases}
    \lambda\Delta t+\mathcal{o}(\Delta t), &j=i+1, i\ge 0\
    \mu\Delta t+\mathcal{o}(\Delta t), &j=i-1, i\ge 0\
    \mathcal{o}(\Delta t), &|i-j|\ge 2
    \end{cases}
    \end{align*}$$

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

    • 状态转移图
      M/M/1/infty StatusM/M/1/infty Status
    • $Q$ 矩阵
      $$\mathbf{Q}=\left(\begin{array}{ccccccccc}
      -\lambda & \lambda & 0 & 0 & \cdots & 0 & 0 & 0 & \cdots\
      \mu & -(\lambda+\mu) & \lambda & 0 & \cdots & 0 & 0 & 0 & \cdots\
      0 & \mu & -(\lambda+\mu) & \lambda & \cdots & 0 & 0 & 0 & \cdots\
      \vdots & \vdots & \vdots & \vdots & \ddots & \vdots & \vdots & \vdots & \vdots\
      0 & 0 & 0 & 0 & \cdots & -(\lambda+\mu) & -\lambda & 0 & \cdots\
      0 & 0 & 0 & 0 & \cdots & \mu & -(\lambda+\mu) & -\lambda & \cdots\
      0 & 0 & 0 & 0 & \cdots & 0 & \mu & -(\lambda+\mu) & \cdots\
      \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \ddots\
      \end{array}\right)$$
  4. 微分差分方程组
    由Kolmogorov向前方程$\mathbf p^\prime(t)=\mathbf p(t)\mathbf{Q}$, 得到:
    $$\begin{align*}
    \begin{cases}
    p^\prime_0(t)=-\lambda p_0(t)+\mu p_1(t),\
    p^\prime_j(t)=-(\lambda+\mu) p_j(t)+\lambda p_{j-1}(t)+\mu p_{j+1}(t)
    \end{cases}
    \end{align*}$$

    令$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}$ 存在,且与初始分布无关,且构成几何概率分布:
      $$p_j=(1-\rho)\rho^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$ 模型

在忙的服务台数=系统中顾客数,即服务台数无穷,系统无等待时间,逗留时间就是服务时间。
状态转移概率为:
$$\begin{align*}
p_{ij}(\Delta t)=\begin{cases}
\lambda\Delta t+\mathcal o(\Delta t), & j=i+1, i\ge 0;\
i\mu\Delta t+\mathcal o(\Delta t), & j=i-1, i\ge 1;\
\mathcal o(\Delta t), & |i-j|\ge 2.
\end{cases}
\end{align*}$$

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

离去过程是参数为 $\lambda$ 的简单流。
状态转移概率为:
$$\begin{align*}
p_{ij}(\Delta t)=\begin{cases}
\lambda\Delta t+\mathcal o(\Delta t), & j=i+1, i\ge 0;\
i\mu\Delta t+\mathcal o(\Delta t), & j=i-1, i=1,2,\cdots,c-1;\
c\mu\Delta t+\mathcal o(\Delta t), & j=i-1, i=c,c+1,\cdots;\
\mathcal o(\Delta t), & |i-j|\ge 2.
\end{cases}
\end{align*}$$

$M/M/c/K$ 模型

系统中总共有 $K$ 个位置,$c$ 个服务台独立工作,$c\le K$。当 $K$ 个位置全部被占用,新到的顾客就自动离开。到达当顾客依然是参数为 $\lambda$ 的泊松流,服务时间为参数为 $\mu$ 的负指数分布。
状态转移概率为:
$$\begin{align*}
p_{ij}(\Delta t)=\begin{cases}
\lambda\Delta t+\mathcal o(\Delta t), & j=i+1, i=0,1,\cdots,K-1;\
i\mu\Delta t+\mathcal o(\Delta t), & j=i-1, i=1,2,\cdots,c-1;\
c\mu\Delta t+\mathcal o(\Delta t), & j=i-1, i=c,c+1,\cdots,K;\
\mathcal o(\Delta t), & |i-j|\ge 2.
\end{cases}
\end{align*}$$

有限源的简单排队系统

$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$ 阶段期望总报酬效用函数定义为:
$$
V_N(i,\pi)\triangleq\sum_{t=0}{N-1}E_\pii[r(Y_t,\Delta_t)]+E_\pi^i[r(Y_N)], \quad i\in S
$$

无限阶段折扣模型

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

平均准则

离散决策时刻,无限阶段,采用平均期望报酬来代替折扣模型的马氏决策问题。
$$\begin{align*}
\bar V(i,\pi)&\triangleq\liminf_{N\to\infty}\frac{V_N(i,\pi)}{N+1}\
&=\liminf_{N\to\infty}\frac{1}{N+1}E_\pii\left{\sum_{t=0}{N}r(Y_t,\Delta_t)\right}
\end{align*}$$
为状态 $i$ 出发并使用策略 $\pi$ 的平均收益。

主要结论

主要结论主要结论

马氏决策-有限阶段模型

有限阶段的值迭代算法

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

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

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

单调向后递归算法

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

马氏决策-折扣模型

Banach 不动点定理

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

策略迭代算法

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

值迭代算法

值迭代算法值迭代算法

改进的策略迭代算法

马氏决策-平均模型

References

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

Appendix

Appendix A. 常见级数

我好菜啊,常见的级数求和都不熟练了
$$\begin{align*}
\frac{1}{x}&=\sum_{n=0}^\infty x^n, &x\in(-1,\ 1)\
ex&=\sum_{n=0}\infty \frac{x^n}{n!}, &x\in \mathbb R\
\cos x&=\sum_{n=0}^\infty (-1)n\frac{x{2n}}{(2n)!}, &x\in \mathbb R\
\sin x&=\sum_{n=0}^\infty (-1)n\frac{x{2n+1}}{(2n+1)!}, &x\in \mathbb R\
\ln (1+x)&=\sum_{n=0}^\infty (-1){n+1}\frac{x{n}}{n}, &x\in (-1,\ 1]
\end{align*}$$

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

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

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

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