一、最短路问题
1.两个指定顶点之间的最短路径
Dijkstra算法: $(u_0,v_0)$ 按照距离$u_0$从近到远的顺序,依次求得$u_0$到G的个顶点的最短路径和距离,直至$v_0$或者G的所有顶点。
MATLAB代码如下(需要改图):
1 | tulun1.m |
2.每对顶点之间的最短路径
Flord算法:递推产生矩阵序列$A_1,…,A_k,…,A_n$,其中$A_k$的第$i$ 行第 $j$列元素$A_k(i,j)$表示从顶点$v_i$到顶点$v_j$的路径上所经过的顶点序号不大于$k$的最短路径长度。
MATLAB代码如下:
1 | a= [ 0,50,inf,40,25,10; |
二、网络最大流问题(图+线性规划)
1.定义
有向图$D=(V,A)$,$A$为弧集,发点$v_s$,收点$v_t$,其余为中间点,$c_{ij}$为弧的容量,$f_{ij}$为弧的流量
2.最大流问题模型
3.寻求最大流的标号法(Ford-Fulkerson)
标号过程:
- 给$v_s$标上$(0,\infty)$
- 找以$v_s$为起点的不饱和弧,标记$(v_s,l(v_j)$,$l(v_j)=min[(c_{ij}-f_ij),l(v_s)]$
- 找以$v_s$为终点的非零弧,标记$(-v_s,l(v_j))=min[f_{ij},l(v_i)]$
- 重复上述步骤直到不能继续标号或者给所有的点进行标号
- 逆向寻找增广链,要求该链的每个顶点的$l(v_j)$都要大于最后一点的$l(v_t)$,可能方向不同
- 把该链所有弧±上$l(v_t)$
- 检查
最小费用最大流问题
三、Matlab工具箱
- 要求是下三角矩阵
- 求最大流的命令,只能解决权重都为正值,且两个顶点之见不能有两条弧,若有两条弧可以加一个点,用相同的权重
四、计划评审方法和关键路线法
作业:消耗时间或资源的行为
事件:作业的开始或结束
1.时间参数
1.1事件时间参数
- 事件的最早时间:表示以事件$v_j$为始点的各工作最早可能开始的时间
- 事件的最迟时间:不影响任务总工期条件下,以事件$v_j$为始点的各工作最迟必须开始的时间
1.2工作的时间参数
工作的最早可能开工时间 和 工作的最早可能完工时间:
$t_{ES}:$:最早可能开工时间
$t_{EF}$:最早可能完工时间
工作最迟必须开工时间 和 工作最迟必须完工时间
$t_{LS}:$最迟必须开工时间
$t_{LF}$:最迟必须完工时间
2.完成作业期望和实现事件的概率
$t_{ij}$是完成作业$(i,j)$的实际时间,则数学期望和方差如下:
$$
E(t_{ij})=\frac{a_{ij}+4m_{ij}+b_{ij}}{6}\
Var(t_{ij})=\frac{(b_{ij}-a_{ij})^2}{36}
$$
$T=\sum_{(i,j)\in关键线路}t_{ij}$
假设T服从正态分布,规定工期为d,则
$$
P{T\leq d}=\Phi(\frac{d-\overline T}{S})
$$
五、油管订购和运输
直接看书QAQ