高项分析及公式(下)

最后编辑:2周前

[MD]

1. 运筹学

1.1 运输问题

伏格尔算法

谁用完,划掉谁

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

1.2 指派问题

匈牙利算法

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

1.3 动态规划

1.3.1 最短路径

标号法

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

1.3.2 最小生成树

扩圈法

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

1.3.3 图与网络图

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

1.3.4 最大流量

  1. 链接起点ss到终点tt的一条通路EE
  2. 找出通路EE的最小边MM的值ii
  3. 通路EE的其他边的值依次减去ii,得到新值kk,如果k=0k=0则删除该边
  4. 重复1~3步直至再也没有sstt的通路
  5. 所有步骤减去的ii之和为图GG的最大流量

1.3.5 资源分配

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

1.4 线性规划

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

2. 决策分析

2.1 不确定型决策

2.1.1 乐观决策法

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

2.1.2 悲观决策法

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

2.1.3 平均值决策法

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

2.1.4 悔值决策法

  1. 求出方案a1a_1的所有悔值:
    方案a1a_1的悔值θ1=MAX(θ1)\theta_1=MAX(\theta_1)-方案a1a_1的结果状态θ1\theta_1
    方案a1a_1的悔值θ2=MAX(θ2)\theta_2=MAX(\theta_2)-方案a1a_1的结果状态θ2\theta_2

    方案a1a_1的悔值θj=MAX(θj)\theta_j=MAX(\theta_j)-方案a1a_1的结果状态θj\theta_j
  2. 在方案a1a_1的悔值θ\theta中,选出最大值MAX(方案a1的悔值θ)MAX(方案a_1的悔值\theta)
  3. 继续求出方案a2a_2~aia_i的所有悔值:
    方案a2a_2的悔值θ1=MAX(θ1)\theta_1=MAX(\theta_1)-方案a2a_2的结果状态θ1\theta_1

    方案aia_i的悔值θj=MAX(θj)\theta_j=MAX(\theta_j)-方案aia_i的结果状态θj\theta_j
  4. 得出最大悔值:MAX(方案a1的悔值θ)MAX(方案a_1的悔值\theta)MAX(方案a2的悔值θ)MAX(方案a_2的悔值\theta),…,MAX(方案ai的悔值θ)MAX(方案a_i的悔值\theta)
  5. 选出最大悔值中的最小值MIN(MAX(方案ai的悔值θ))MIN(MAX(方案a_i的悔值\theta)),该方案当选

2.2 风险型决策

2.2.1 期望值决策法

  1. 求方案aia_i的期望:
    E(a1)=j=1nE(a_1)=\sum_{j=1}^{n}(方案a1a_1的结果状态θj\theta_j的概率××方案a1a_1的结果状态θj\theta_j)

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

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

  1. 求出方案aa的所有悔值:
    方案a1a_1的悔值θ1=MAX(θ1)\theta_1=MAX(\theta_1)-方案a1a_1的结果状态θ1\theta_1
    方案a1a_1的悔值θ2=MAX(θ2)\theta_2=MAX(\theta_2)-方案a1a_1的结果状态θ2\theta_2

    方案a1a_1的悔值θj=MAX(θj)\theta_j=MAX(\theta_j)-方案a1a_1的结果状态θj\theta_j
    方案a2a_2的悔值θ1=MAX(θ1)\theta_1=MAX(\theta_1)-方案a2a_2的结果状态θ1\theta_1

    方案aia_i的悔值θj=MAX(θj)\theta_j=MAX(\theta_j)-方案aia_i的结果状态θj\theta_j
  2. 求出方案aia_i的悔值期望ER(ai)ER(a_i)
    ER(a1)=j=1nER(a_1)=\sum_{j=1}^{n}(方案a1a_1的结果状态θj\theta_j的概率××方案a1a_1的结果状态θj的悔值\theta_j的悔值)

    ER(ai)=j=1nER(a_i)=\sum_{j=1}^{n}(方案aia_i的结果状态θj\theta_j的概率××方案aia_i的结果状态θj的悔值\theta_j的悔值)
  3. 取最小值MIN(ER(ai))MIN(ER(a_i))的方案当选

3. 进度类

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

  • 活动在方框内
  • 关系类型:SS、SF、FF、FS(常用)

关键路径法(六标时图)

ESES 工期 EFEF
活动名称
LSLS 总浮动时间(总时差) LFLF

假设活动11为第一个活动,活动nn为最后一个活动:

  • 总浮动时间(总时差)=LFEF=LSES总浮动时间(总时差)=LF-EF=LS-ES
  • 关键路径的总浮动时间为0
  • ES1=LS1=总浮动时1=0ES_1=LS_1=总浮动时间_1=0
  • 活动ii的最早开始时间为它的紧前活动们的最早完成时间的最大值:ESi=MAX(EFi)ES_i=MAX(EF_{\leftarrow i})
  • 活动ii的最迟完成时间为它的紧后活动们的最迟开始时间的最小值:LFi=MIN(LSi)LF_i=MIN(LS_{i \rightarrow})
  • LFn=EFnLF_n=EF_n
  • LS=ES+工期LS=ES+工期
  • 自由浮动时i=MIN(ESi)EFi自由浮动时间_i=MIN(ES_{i \rightarrow})-EF_i

3.2 双代号网络图(ADM、AOA、箭线图)

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

3.3 双代号时标网络图

波形线表示活动与紧后活动的自由浮动时间(自由时差),虚线表示虚活动

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

3.4. 进度的三点估算

3.4.1 三角分布

Te=(To+Tm+Tp)3T_e=\frac{(T_o+T_m+T_p)}{3}

3.4.2 β\beta分布

Te=(To+4Tm+Tp)6T_e=\frac{(T_o+4T_m+T_p)}{6}

3.4.3 进度三点估算的概率

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

P(xμ3σ)0.1%P(x\leq\mu-3\sigma)\approx0.1\%

P(μ3σxμ2σ)2.1%P(\mu-3\sigma\leq x \leq\mu-2\sigma)\approx2.1\%

P(μ2σxμσ)13.6%P(\mu-2\sigma\leq x \leq\mu-\sigma)\approx13.6\%

P(μσxμ)34.1%P(\mu-\sigma\leq x \leq\mu)\approx34.1\%

P(μxμ+σ)34.1%P(\mu \leq x \leq\mu+\sigma)\approx34.1\%

P(μ+σxμ+2σ)13.6%P(\mu+\sigma\leq x \leq\mu+2\sigma)\approx13.6\%

P(μ+2σxμ+3σ)2.1%P(\mu+2\sigma\leq x \leq\mu+3\sigma)\approx2.1\%

P(xμ+3σ)0.1%P(x\geq\mu+3\sigma)\approx0.1\%

3.5 进度压缩

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

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注

[smirking] [hentai] [wounded] [cracker] more »