最后编辑：1周前

[MD]

1. 运筹学

1.1 运输问题

伏格尔算法

谁用完，划掉谁

1. 计算行和列中的次小值和最小值的差(有两个最小值时， 差为0)，填入行差、列差
2. 在所有的行差、列差中找最大差值
3. 在最大差值所对应的行(列)中，定位最小值所在单元格
4. 在供应量和需求量里选较小的与上一步定位的单元格相乘
5. 分配完的行（列）划掉，不再参与计算
6. 重复步骤1~5，直至表格内的供求量均为0
7. 此时所有乘数为运输的数量方案，总价为剩余单元格的值之和

1.2 指派问题

匈牙利算法

• 以本单元格的数值–本行最小值代替本单元格数值
• 以本单元格的数值–本列最小值代替本单元格数值
• 减去的所有值之和为最短用时
• 0为可以安排的位置
• 划掉安排好的行或列

1.3 动态规划

1.3.1 最短路径

标号法

1. 将开始节点$S$标记为$0$
2. $节点k的标记=紧前节点的标记+MIN(紧前节点到节点k的所有路径)$
3. 直至标记到结束节点$E$
4. 此时如果$标记值-路径=紧前标记值$，则该路径在最短路径上
5. 连通$E$到$S$得到的路径为最短路径

1.3.2 最小生成树

扩圈法

• 找一个闭合路径
• 去掉一个最大边
• 重复步骤直至没有闭合路径

1.3.3 图与网络图

• 如果有表，表转图，不能同时进行的活动相连
• 数奇点个数：
  • 奇点个数为0：任意点到任意点
  • 奇点个数为2：一个奇点到另一个奇点
• 找出能一笔画的起点和终点
• 计算所有边之和
• 如果要求回到起点：
  • 奇点个数为0：无需操作
  • 奇点个数为2：再加上两个奇点之间的最短距离

1.3.4 最大流量

• 在起点至终点选一条通路
• 删除此通路最短的边，该边的权值为此路径的最大流量$a_i$
• 剩下的边权值$-a_i$
• 重复操作，直至起点到终点的权值为0
• $\sum_{i=1}^{n}(a_i)$

1.3.5 资源分配

• 计算单位收益
• 列方程组穷举计算最大值

1.4 线性规划

• 解方程组，问什么设什么，注意约束条件
• 般有两个未知数$X$,$Y$以及其它条件，写多个($2$~$N$)不等式，考虑$X = 0$或$Y = 0$的情况，求最值的第三个方程为: $Z = aX +bY+c$

2. 决策分析

2.1 不确定型决策

2.1.1 乐观决策法

每个方案$a_i$取结果状态最大值$MAX(\theta)$，在最后选择出最大值$MAX(MAX(\theta))$所在的方案当选

2.1.2 悲观决策法

每个方案$a_i$取结果状态最小值$MIN(\theta)$，在最后选择出最大值$MAX(MIN(\theta))$所在的方案当选

2.1.3 平均值决策法

每个方案$a_i$取结果状态平均数$\overline{\theta}$，在最后选择出最大值$MAX(\overline{\theta})$所在的方案当选

2.1.4 悔值决策法

1. 求出方案$a_1$的所有悔值：
   方案$a_1$的悔值$\theta_1=MAX(\theta_1)-$方案$a_1$的结果状态$\theta_1$
   方案$a_1$的悔值$\theta_2=MAX(\theta_2)-$方案$a_1$的结果状态$\theta_2$
   …
   方案$a_1$的悔值$\theta_j=MAX(\theta_j)-$方案$a_1$的结果状态$\theta_j$
2. 在方案$a_1$的悔值$\theta$中，选出最大值$MAX(方案a_1的悔值\theta)$
3. 继续求出方案$a_2$~$a_i$的所有悔值：
   方案$a_2$的悔值$\theta_1=MAX(\theta_1)-$方案$a_2$的结果状态$\theta_1$
   …
   方案$a_i$的悔值$\theta_j=MAX(\theta_j)-$方案$a_i$的结果状态$\theta_j$
4. 得出最大悔值：$MAX(方案a_1的悔值\theta)$，$MAX(方案a_2的悔值\theta)$，…，$MAX(方案a_i的悔值\theta)$
5. 选出最大悔值中的最小值$MIN(MAX(方案a_i的悔值\theta))$，该方案当选

2.2 风险型决策

2.2.1 期望值决策法

1. 求方案$a_i$的期望：
   $E(a_1)=\sum_{j=1}^{n}$(方案$a_1$的结果状态$\theta_j$的概率$×$方案$a_1$的结果状态$\theta_j$)
   …
   $E(a_i)=\sum_{j=1}^{n}$(方案$a_i$的结果状态$\theta_j$的概率$×$方案$a_i$的结果状态$\theta_j$)
2. 在所有方案的期望中选最大值$MAX(E(a_i))$

2.2.2 最小悔值与期望值决策法

1. 求出方案$a$的所有悔值：
   方案$a_1$的悔值$\theta_1=MAX(\theta_1)-$方案$a_1$的结果状态$\theta_1$
   方案$a_1$的悔值$\theta_2=MAX(\theta_2)-$方案$a_1$的结果状态$\theta_2$
   …
   方案$a_1$的悔值$\theta_j=MAX(\theta_j)-$方案$a_1$的结果状态$\theta_j$
   方案$a_2$的悔值$\theta_1=MAX(\theta_1)-$方案$a_2$的结果状态$\theta_1$
   …
   方案$a_i$的悔值$\theta_j=MAX(\theta_j)-$方案$a_i$的结果状态$\theta_j$
2. 求出方案$a_i$的悔值期望$ER(a_i)$：
   $ER(a_1)=\sum_{j=1}^{n}$(方案$a_1$的结果状态$\theta_j$的概率$×$方案$a_1$的结果状态$\theta_j的悔值$)
   …
   $ER(a_i)=\sum_{j=1}^{n}$(方案$a_i$的结果状态$\theta_j$的概率$×$方案$a_i$的结果状态$\theta_j的悔值$)
3. 取最小值$MIN(ER(a_i))$的方案当选

3. 进度类

3.1 单代号网络图（PDM、前导图、紧前关系绘图法）

• 活动在方框内
• 关系类型：SS、SF、FF、FS（常用）

关键路径法（六标时图）

$ES$	工期	$EF$
活动名称
$LS$	总浮动时间（总时差）	$LF$

假设活动$1$为第一个活动，活动$n$为最后一个活动：

• $总浮动时间（总时差）=LF-EF=LS-ES$
• 关键路径的总浮动时间为0
• $ES_1=LS_1=总浮动时间_1=0$
• 活动$i$的最早开始时间为它的紧前活动们的最早完成时间的最大值：$ES_i=MAX(EF_{\leftarrow i})$
• 活动$i$的最迟完成时间为它的紧后活动们的最迟开始时间的最小值：$LF_i=MIN(LS_{i \rightarrow})$
• $LF_n=EF_n$
• $LS=ES+工期$
• $自由浮动时间_i=MIN(ES_{i \rightarrow})-EF_i$

3.2 双代号网络图（ADM、AOA、箭线图）

• 活动在线上
• 节点为事件，用圆圈表示
• 虚活动不消耗时间和资源

3.3 双代号时标网络图

波形线表示活动与紧后活动的自由浮动时间（自由时差），虚线表示虚活动

• 总工期:终点与起点的时间差
• 关键路径︰自始至终无波形线的线路（1条及以上）。关键活动（关键工作）:关键路径上的活动
• 总时差: $MIN$(从本工作起经过的所有波形线之和)。自由时差:该工作上的波形线长度

3.4. 进度的三点估算

3.4.1 三角分布

$$T_e=\frac{(T_o+T_m+T_p)}{3}$$

3.4.2 $\beta$分布

$$T_e=\frac{(T_o+4T_m+T_p)}{6}$$

3.4.3 进度三点估算的概率

• 计算期望 $\mu =T_e$
• 计算标准差 $\sigma=\frac{T_p-T_o}{6}$
• 项目的期望($T$)、标准差($\sigma$)、方差($\sigma^2$)均为项目所有活动之和，即$T=\sum_{i=1}^{n}(t_i)$、$\sigma=\sum_{i=1}^{n}(\sigma_i)$、$\sigma^2=\sum_{i=1}^{n}(\sigma_i^2)$

$P(x\leq\mu-3\sigma)\approx0.1\%$

$P(\mu-3\sigma\leq x \leq\mu-2\sigma)\approx2.1\%$

$P(\mu-2\sigma\leq x \leq\mu-\sigma)\approx13.6\%$

$P(\mu-\sigma\leq x \leq\mu)\approx34.1\%$

$P(\mu \leq x \leq\mu+\sigma)\approx34.1\%$

$P(\mu+\sigma\leq x \leq\mu+2\sigma)\approx13.6\%$

$P(\mu+2\sigma\leq x \leq\mu+3\sigma)\approx2.1\%$

$P(x\geq\mu+3\sigma)\approx0.1\%$

3.5 进度压缩

• 并行
• 压缩关键路径上的活动。
• 考虑间接成本
• 关键路径可能不止一条
• 每压缩一次就要考虑关键路径是否变化。$时间=工作量/人数$
• 考虑人手或者资金不足导致的停工
• 压缩优先顺序∶①价格②关键路径上的共同活动