运筹学基础 课件 第4章.pptx

第4章网络最优化;

4.1最小支撑树问题;?;

定义4-3连通图G=(V,E)的最小支撑树T(G)就是图的权重之和最小的支撑树。

其中,cij是边(i,j)的权重。;

;

例4-1某公司中标为“一带一路”上某国家的六个居民点提供宽带建设服务,图4-1给出了铺设通信线路的可能情况及相应距离。请确定最经济的通信线路铺设方案,使六个居民点可以连接起来。;

;

记六个居民点及相应的可能连接方式组成的图为G=(V,E),设xij为决策变量,xij=1代表点i与点j之间铺设的通信线路,否则不铺设。此问题可以表示为以下线性规划模型;

本问题可以使用线性规划求解,但是对于点的数量较多的问题,使用线性规划求解的话就不可行了。例如,对于有60个点的图,要用线性规划模型求解最小支撑树,需要的约束条件数量比地球上的原子数量还多。

支撑树使用了最少数量的边连通了图的所有点,从数量方面是网络连通优化设计问题的最优方案,而最小支撑树是边的总长度之和最小的支撑树,因此,从数量和质量方面都是最优的网络连通设计方案。;

4.1.2两个属性

1.Cut属性

在最小支撑树的线性规划模型中,式(4-2)代表连通性约束,不等式左侧的表达式表示图的截集中至少有一条边要保留。

定义4-4-图G=(V,E)中,对于?S?V,所有的一端在S中、一端不在S中的边构成的集合称为图的截集。;

例4-2图4-1的截集数量为6!/2,其中两个如图4-2所示。;

最小支撑树的Cut属性:连通图G任意截集的最小边必属于最小支撑树。;

2.Cycle属性

最小支撑树的另外一个属性是无圈的,因此,任意圈上肯定有一条边不属于最小支撑树,依据“贪婪法”的启发式规则,我们猜测圈上的最大边不属于最小支撑树。

最小支撑树的Cycle属性:图中圈上若只有单一最大边,则此最大边一定不属于最小支撑树;若有多条最大边,则去掉任意一条最大边,不影响得到最小支撑树。总之,去掉圈上一条最大边,仍然可以得到最小支撑树。;

;?;

算法的步骤如下:;

例4-3利用Prim算法求解图4-1的最小支撑树。

步骤1:首先令S={6},则Cut(S)={(6,3),(6,4)},E(T)=?,得到最小边为emin=(6,4),如图4-3所示。

步骤2:(6,4)是最小支撑树上的边,令E(T)=E(T)∪emin={(6,4)},S=S∪V(emin)={6,4},则

Cut(S)={(6,3),(4,1),(4,2),(4,3),(4,5)}

得到最小边emin=(4,2),如图4-4所示。;

;

;

步骤3:(4,2)是最小支撑树上的边,令E(T)=E(T)∪emin={(6,4),(4,2)},S=S∪V(emin)={6,4,2},则

Cut(S)={(6,3),(4,1),(4,3),(4,5),(2,1),(2,3),(2,5)}

得到最小边emin=(1,2),如图4-5所示。;

;

步骤4:(1,2)是最小支撑树上的边,令E(T)=E(T)∪emin={(6,4),(4,2),(1,2)},S=S∪V(emin)={6,4,2,1},则

Cut(S)={(6,3),(4,3),(4,5),(2,3),(2,5),(1,3),(1,5)}

得到最小边有三条,emin=(2,3)、(2,5)、(4,3),如图4-6所示。

;

;

步骤5:可以任选一条最小边加入E(T),如(2,3)。令E(T)=E(T)∪emin={(6,4),(4,2),(1,2),(2,3)},S=S∪V(emin)={6,4,2,1,3},则

Cut(S)={(4,5),(2,5),(1,5)}

得到最小边emin=(2,5),如图4-7所示。;

;

步骤6:(2,5)是最小支撑树上的边。令E(T)=E(T)∪emin={(6,4),(4,2),(1,2),(2,3),(2,5)},S=S∪V(emin)={6,4,2,1,3,5},算法结束,如图4-8所示。;

2.Kruskal算法

从构造的角度考虑,在选择一部分边时,只要避免将圈上的最大边选上就可以了。

Kruskal从构造的角度提出了寻找最小支撑树的方法。

Kruskal法将所有的边