数学模型课程笔记, 不完整.

课程大纲

  1. 优化
    1. 凸优化
      1. 线性优化(LP): 单纯形法
    2. 组合优化
      1. 整数优化(IP)
      2. 动态规划(DP): 序列比对问题, Viterbi解码算法, 最短路径算法
    3. 图论
      1. 最短路径问题: Dijkstra算法;
      2. 最小生成树问题: 破圈法; Kruskal算法;
      3. 关键路径分析(CPA)
      4. 赶工优化问题
      5. 最大流问题: Ford-Fulkerson算法;
  2. 动力系统
    1. 种群动力学
    2. 传染病模型
  3. 随机过程
    1. Markov模型
    2. 隐Markov模型
    3. 随机模拟
  4. 统计分类
    1. 人工神经网络模型
    2. 决策树
    3. 支持向量机
  5. 决策论
    1. 层次分析法(AHP)
  6. 数值线性代数
    1. 奇异值分解(SVD)

Simplex algorithm 单纯形法

线性规划的标准型: (有的地方要求最小值, 有的地方要求最大值, 不统一.)

将线性规划问题化为标准型:

  1. 变量替换;
  2. 引入松弛变量将不等式变成等式;
  3. 将无约束变量化为两非负变量之差;

单纯形法原理: 可行域是一个凸多面体, 有可能无界. 可行域的顶点与线性方程组 Ax=b 的基本解一一对应. 可行域上如果目标函数有最小值, 则一定在顶点处达到. 如果目标函数在一个顶点上不取到最小值, 则从这个顶点出发有一条边, 目标函数在这条边上单调下降. 如果这条边有限长, 则此边连接另一个顶点; 如果这条边无限长, 则此线性规划问题无最优解.

单纯形法基本步骤:

  1. 确定初始基本变量 B 和初始基本可行解 X
    • 常数项 b 应该非负;
    • 如果某一行常数项 $b_d$ 为负, 可以选取此行系数 A 为负的变量为换入基本变量 $X_e$, 通过转轴操作 pivot(d,e) 就有可能使常数项 b 为非负;
  2. 循环步骤 2-4, 除非以下判据之一成立:
    • 最优解判据: 目标函数中非基本变量 N 的检验数 λ 全部非正;
    • 无有限最优解判据: 存在一个换入基本变量 $X_e$ , 使得所有的 $A_{d,e}$ 非正;
  3. 确定换入基本变量 $X_e$ 和换出基本变量 $X_d$
    • $X_e$ 满足检验数 $λ_e$ 为正, 且为当前最大;
    • 对所有的 $A_{i,e}>0$ , 求取 $θ = b_i / A_{i,e}$ ;
    • $X_d$ 满足在所有 θ 中, $θ_d$ 最小;
  4. 转轴操作 pivot(d,e)
    • 重新填写基本变量列表, 将 $X_d$ 改为 $X_e$ ;
    • 对矩阵进行行变换, 使 $X_e$ 所在列变成单位向量, 操作目标函数值 Z 时, 记得改变符号;
  5. 所得 $Z_0$ 即为最优目标函数值, b 即为非基本变量取值

种群动力学与传染病模型

单物种模型:

  1. Malthus模型:
    • 人口增长率 = 生产率 - 死亡率, 是个常数.
    • dN/dt = rN
    • 结论: 人口指数增长
  2. Logistic模型:
    • 人口增长率 = 内禀增长率 - 竞争项
    • dN / dt = aN - bN^2
    • 结论: 若 N0 > a/b, N 单调减少; 若 N0 < a/b, N 单调增加; 最终都趋于 a/b.

两物种竞争模型:

  • 人口增长率 = 内禀增长率 - 种内竞争项 - 种间竞争项
  • $dN_1 / dt = r_1 N_1 (1 - (N_1 + b_{12} N_2) / K_1)$
  • $dN_2 / dt = r_2 N_2 (1 - (N_2 + b_{21} N_1) / K_2)$
  • 计算平衡点, 依据参数的不同取值, 分析相图的定性结构, 可以得到不同的竞争结果.

捕食被捕食模型:

  • 被捕食者增长率 = 内禀增长率 - 捕食导致死亡率
  • 捕食者增长率 = 捕食导致出生率 - “内禀死亡率”
  • $dN_1 / dt = aN_1 - bN_1 N_2$
  • $dN_2 / dt = dN_2 N_1 - cN_2$
  • 分析相图, 并对方程组做首次积分可知, 系统存在闭合轨道, 即有周期解.

带年龄结构的人口模型:

  • 将种群按年龄分为 n 个组, 每个组都有其相应的出生率和死亡率.
  • 列出相应微分方程组即可求解.

传染病模型:

  1. SI模型
    • 总人数不变, 为N; 病人和健康人的比例分别为i, s. 每个病人每天有效接触个人, 并且使接触到的健康人生病.
    • $N di/dt = \lambda sN_i$, 即 $di / dt = λ i(1-i)$
    • 可以求出i随时间的变化, 也可以求出传染病高潮到来时刻, 即i变化率最大的时刻.
    • 结论: i趋于1
  2. SIS模型
    • 基于SI模型, 假设病人每天治愈的比例为.
    • $di/dt = \lambda i(1-i) - \mu i$, 即 di/dt = -λ i[i-(1-1/σ)], 其中 σ=λ/μ为接触数, 指一个感染期内病人的有效接触人数.
    • 分析相空间定性结构可知: 当 σ>1 时, i 趋于 1-1/σ; 当 σ<=1 时, i趋于0.
  3. SIR模型
    • 基于SI模型, 假设痊愈者具有免疫力而不再被感染;
    • 假设各类型个体在人群中混合是均匀的;
    • 假设总人数足够大, 只考虑传染的平均效应;
      • ds/dt = -λis
      • di/dt = λsi-μi
      • dr/dt = αi, 其中r为痊愈者比例.
      • 由于 s+i+r=1, 可以只考虑前两个方程.
    • 结论:
      • 可以算得相轨线方程, 进一步可以算出 s 满足的超越方程, 忽略方程中的 i_0 可以估算接触数;
      • 当 s=1/σ 时, i取到最大值; 若 s_0>1/σ , i先增加后减少, 传染病蔓延; 若s0<1, i减少, 传染病不蔓延;
      • 为了预防传染病蔓延, 可以降低日接触率(提高卫生水平), 提高日治愈率(提高医疗水平), 提高 r_0 (群体免疫);
      • 记被传染人数比例 $x = s_0 - s_{\infty}$ , 可以在假设 $i_0 \approx 0, s_0 \approx 1, x \ll s_0, s_0 \delta \approx 1$ 下, 得到 $x \approx 2(s_0 - 1/\sigma)$, 于是可以通过提高阈值 1/σ, 降低被传染人数比例x.

图论和网络流问题

最短路径问题: Dijkstra's algorithm

  • (addWithPriority) 用一个向量 l 记录从起始顶点 s 到各个顶点的最短距离, 初始时 l(s)=0 , 其余值均为无穷大, 加入队列 Q;
  • 用一个树 r 记录从 s 点到各个顶点的最短路径(Shortest Path Tree), 初始值均为NA;
  • 记上一次新移出 Q 的点为 p, 初始值为NA, 迭代直到目标顶点 t not in Q (or Q empty):
    • (extractMin) 移出 Q 中 l 值最小的顶点 p, 表示我们已经找到从 s 到 p 的最短路径;
    • (decreasePriority) 对于所有能由 p 点直接抵达的仍在 Q 中的顶点 i, 如果 p 点到 s 点的最短距离 l(p) 与 p 点到 i 点的边长 w(p, i) 之和小于当前 l(i), 则用前者更新 l(i) 并记 r(i)=p;

最小生成树问题:

  1. 破圈法:
    1. 在图中寻找一个圈, 若已无圈则跳到第三步;
    2. 在圈中选取权最大的边, 从图中截去该边, 返回第一步;
    3. 如果边数比顶点数小一, 则已找到最短树.
  2. Kruskal算法:
    1. 初始时, 图中仅有 n 个顶点, 无边;
    2. 将原有边按递增排列;
    3. 选择连通两个连通分量的最短边, 直到加入 n-1 条边为止.

关键路径分析(CPA): 关键路径算法(CPM)

  • 时间用数组 ee 表示各事件可能的最早发生时间, 用数组 le 表示各事件允许的最迟发生时间;
  • ee(0)=0, 事件的最早发生时间不早于先决活动全部做完的时间, 由此计算出全部 ee;
  • le(n-1)=ee(n-1), 事件的最迟发生时间不迟于任一后续活动开始的时间, 由此计算出全部 le;
  • 如果事件的最早发生时间等于最迟发生时间, 则它属于关键路径.

最大流问题:

  1. Ford-Fulkerson 算法;
    • 为图分配初始流, 可以是零流;
    • 根据伴随增量网络寻求增广链, 若不存在, 则已最优;
      • 伴随增量网络的顶点与原图相同;
      • 若原图某一条边流量不饱和, 则增加一条正向弧, 权为流量增加潜力;
      • 若原图某一条边流量不为零, 则增加一条逆向弧, 权为当前流量;
      • 流量增广链是伴随增量网络中从起点到终点的一条初等链, 可由正向弧和逆向弧构成;
    • 在增广链上调整流量, 产生新的可行流, 返回第二步.
      • 寻找增广链的最大流量 f;
      • 如果增广链上一条弧是正向弧, 则原图对应弧流量增加 f;
      • 如果增广链上一条弧是逆向弧, 则原图对应弧流量减少 f;
    • 注: 算法只对整数容量适用; 最大流的解不唯一.
  2. 最小切割
    • 将图切割为两份, P 图包含起点, Q 图包含终点.
    • 切割容量是切割的函数, 表示从 P 图到 Q 图的总流量(不是净流量).
    • 对任意可行流, 切割容量不小于流量.
    • 最小切割容量就是最大流.

赶工优化问题:

  • 对当前活动图计算关键路径和总工期 T, 并计算关键网络, 即由关键路径构成的图;
  • 由关键网络构建费用网络;
    • 如果活动当前耗时等于最少耗时, 则该活动无法赶工, 赶工成本为无穷大;
    • 如果活动当前耗时尚大于最少耗时, 则赶工成本由已知数据提供;
  • 计算费用网络的最大流对应的切割;
  • 令切割上的活动工期为 0, 计算总工期 T', 并计算跃变度 J=T-T';
  • 跃变度和各活动可赶工时间的最小值即为可缩短工期;
  • 将切割上的活动均减去可缩短工期, 计算赶工成本和新的总工期;
  • 重复上述步骤, 直至达到预期的总工期.

随机过程

  • Markov模型
    • 句子平均长度问题: 状态集合; 概率转移矩阵; 求不变分布.
  • 隐Markov模型
    • 解码问题: Viterbi 算法

动态规划

序列比对问题

  1. 全局比对
    • 用矩阵F记录最佳比对得分, 其中 F(i,j) 表示子序列 $X_i = (x_1, x_2,\dots, x_i)$ 和 $Y_j = (y_1, y_2, \dots, y_j)$ 的最佳比对得分;
    • 空序列和空序列的最佳比对得分为 F(0,0)=0 ;
    • 长度为 n 的序列和空序列的最佳比对得分为 F(n,0) = F(0,n) = -n ;
    • 递推计算 F(i,j) 的值, 并用反向箭头记录取得该最佳得分的匹配路径;
      • 将序列 $$1$ 和 $Y_j$ 的最佳比对结果后面分别加上 $x_i$ 和空格, 比对得分为 F(i-1,j)-1;
      • 将序列 $X_i$ 和 $Y_{j-1}$ 的最佳比对结果后面分别加上空格和 $y_j$ , 比对得分为 F(i,j-1)-1;
      • 将序列 $X_{i-1}$ 和 $Y_{j-1}$ 的最佳比对结果后面分别加上 $x_i$ 和 $y_j$ , 比对得分为 $F(i-1,j-1) + d_{ij}$ , $d_{ij}$ 为 $x_i$ 和 $y_j$ 的匹配结果;
      • 序列 $X_i$ 和 $Y_j$ 的比对方式可以分为上述三类, 最优比对得分 F(i,j) 就是上述三个值的最大值;
    • 重复上一步, 直至计算出 F(m,n);
    • 最佳比对得分即为 F(m,n), 沿着箭头回溯可以得到最优路径.
  2. 局部比对: Smith-Waterman算法
    • F(0,0) = F(n,0) = F(0,n) = 0;
    • $F(m,n) = \max{ F(i-1,j)-1 , F(i,j-1)-1 , F(i-1,j-1)+d_{ij} , 0 }$;
    • 在F中找到最大值, 回溯至0为止.

🏷 Category=Modeling