数学建模之图与网络模型

一、最短路问题

1.两个指定顶点之间的最短路径

Dijkstra算法: $(u_0,v_0)$ 按照距离$u_0$从近到远的顺序，依次求得$u_0$到G的个顶点的最短路径和距离，直至$v_0$或者G的所有顶点。

MATLAB代码如下（需要改图）：

tulun1.m
weight=    [0     2     8     1   Inf   Inf   Inf   Inf   Inf   Inf   Inf;
            2     0     6   Inf     1   Inf   Inf   Inf   Inf   Inf   Inf;
            8     6     0     7     5     1     2   Inf   Inf   Inf   Inf;
            1   Inf     7     0   Inf   Inf     9   Inf   Inf   Inf   Inf;
          Inf     1     5   Inf     0     3   Inf     2     9   Inf   Inf;
          Inf   Inf     1   Inf     3     0     4   Inf     6   Inf   Inf;
          Inf   Inf     2     9   Inf     4     0   Inf     3     1   Inf;
          Inf   Inf   Inf   Inf     2   Inf   Inf     0     7   Inf     9;
          Inf   Inf   Inf   Inf     9     6     3     7     0     1     2;
          Inf   Inf   Inf   Inf   Inf   Inf     1   Inf     1     0     4;
          Inf   Inf   Inf   Inf   Inf   Inf   Inf     9     2     4     0;];
[dis, path]=dijkstra(weight,1, 11)


dijkstra.m
function [min,path]=dijkstra(w,start,terminal)
n=size(w,1); label(start)=0; f(start)=start;
for i=1:n
   if i~=start
       label(i)=inf;
end, end
s(1)=start; u=start;
while length(s)<n
   for i=1:n
      ins=0;
      for j=1:length(s)
         if i==s(j)
            ins=1;
         end,  
      end
      if ins==0
         v=i;
         if label(v)>(label(u)+w(u,v))
            label(v)=(label(u)+w(u,v)); 
         f(v)=u;
         end, 
      end, 
   end   
v1=0;
   k=inf;
   for i=1:n
         ins=0;
         for j=1:length(s)
            if i==s(j)
               ins=1;
            end, 
         end
         if ins==0
            v=i;
            if k>label(v)
               k=label(v);  v1=v;
            end,  
         end,  
   end
   s(length(s)+1)=v1;  
   u=v1;
end
min=label(terminal); path(1)=terminal;
i=1; 
while path(i)~=start
      path(i+1)=f(path(i));
      i=i+1 ;
end
path(i)=start;
L=length(path);
path=path(L:-1:1);

2.每对顶点之间的最短路径

Flord算法：递推产生矩阵序列$A_1,…,A_k,…,A_n$,其中$A_k$的第$i$ 行第 $j$列元素$A_k(i,j)$表示从顶点$v_i$到顶点$v_j$的路径上所经过的顶点序号不大于$k$的最短路径长度。

MATLAB代码如下：

a= [ 0,50,inf,40,25,10;
     50,0,15,20,inf,25;
     inf,15,0,10,20,inf;
     40,20,10,0,10,25;
     25,inf,20,10,0,55;
     10,25,inf,25,55,0];
[D, path]=floyd(a)

floyd.m
function [D,path,min1,path1]=floyd(a,start,terminal)
D=a;n=size(D,1);path=zeros(n,n);
for i=1:n
   for j=1:n
      if D(i,j)~=inf
         path(i,j)=j;
      end, 
   end,
end
for k=1:n
   for i=1:n
      for j=1:n
         if D(i,k)+D(k,j)<D(i,j)
            D(i,j)=D(i,k)+D(k,j);
            path(i,j)=path(i,k);
         end, 
      end, 
   end,
end
if nargin==3
   min1=D(start,terminal);
   m(1)=start;
   i=1;
   path1=[ ];   
   while   path(m(i),terminal)~=terminal
      k=i+1;                                
      m(k)=path(m(i),terminal);
      i=i+1;
   end
   m(i+1)=terminal;
   path1=m;
end

二、网络最大流问题（图+线性规划）

1.定义

有向图$D=(V,A)$，$A$为弧集，发点$v_s$，收点$v_t$,其余为中间点，$c_{ij}$为弧的容量，$f_{ij}$为弧的流量

2.最大流问题模型

3.寻求最大流的标号法（Ford-Fulkerson）

标号过程：

1. 给$v_s$标上$(0,\infty)$
2. 找以$v_s$为起点的不饱和弧，标记$(v_s,l(v_j)$,$l(v_j)=min[(c_{ij}-f_ij),l(v_s)]$
3. 找以$v_s$为终点的非零弧，标记$(-v_s,l(v_j))=min[f_{ij},l(v_i)]$
4. 重复上述步骤直到不能继续标号或者给所有的点进行标号
5. 逆向寻找增广链，要求该链的每个顶点的$l(v_j)$都要大于最后一点的$l(v_t)$，可能方向不同
6. 把该链所有弧±上$l(v_t)$
7. 检查

最小费用最大流问题

三、Matlab工具箱

• 要求是下三角矩阵
• 求最大流的命令，只能解决权重都为正值，且两个顶点之见不能有两条弧，若有两条弧可以加一个点，用相同的权重

四、计划评审方法和关键路线法

作业：消耗时间或资源的行为

事件：作业的开始或结束

1.时间参数

1.1事件时间参数

1. 事件的最早时间：表示以事件$v_j$为始点的各工作最早可能开始的时间
2. 事件的最迟时间：不影响任务总工期条件下，以事件$v_j$为始点的各工作最迟必须开始的时间

1.2工作的时间参数

1. 工作的最早可能开工时间 和 工作的最早可能完工时间：

   $t_{ES}：$：最早可能开工时间

   $t_{EF}$:最早可能完工时间

   

2. 工作最迟必须开工时间 和 工作最迟必须完工时间

   $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