网络优化的数学模型—1详解.ppt

网络优化的数学模型(1); 最小生成树及算法 ;1．最小生成树及算法;定理2 设G是具有n个顶点的图，则下述命题等价：;2）图的生成树;;（II）找图中生成树的方法;A 避圈法 ;a) 深探法;13;3;3;B 破圈法;B 破圈法;3) 最小生成树与算法;A Kruskal算法（或避圈法）;例10用Kruskal算法求下图的最小树.;B破圈法;如图的交通网络，每条弧上的数字代表车辆在该路段行驶所需的时间，有向边表示单行道，无向边表示可双向行驶。若有一批货物要从1号顶点运往11号顶点，问运货车应沿哪条线路行驶，才能最快地到达目的地？ ; 某公司在六个城市C1,C2,C3,C4,C5,C6都有分公司，公司成员经常往来于它们之间，已知从Ci到Cj的直达航班票价由下述矩阵的第i行，第j列元素给出（?表示无直达航班），该公司想算出一张任意两个城市之间的最廉价路线航费表。 ;练习 求图中任意两点间的最短路及最小生成树.;5. 旅行售货员问题;旅行售货员问题或货郎担问题. ;一个可行的办法 :;定义 若对于某一对i和j，有;例对下图16的K6,用二边逐次修正法求较优H圈.; 分析: 找出的这个解的好坏可用最优H圈的权;6. 中国邮递员问题;欧拉于1736年研究并解决了此问题， 他用点表示岛和陆地，两点之间的连线表示连接它们的桥，将河流、小岛和桥简化为一个网络，把七桥问题化成判断连通网络能否一笔画的问题。之后他发表一篇论文，证明了上述走法是不可能的。并且给出了连通网络可一笔画的充要条件这一著名的结论。;一笔画问题;想一想：;一笔画问题;中国邮递员问题 ;解决这样的问题，可以采用奇偶点图上作业法：如果在配送范围内，街道中没有奇点，那么他就可以从配送中心出发，走过每条街道一次，且仅一次，最后回到配送中心，这样他所走的路程也就是最短的路程。;对于有奇点的街道图，该怎么办呢？ 这时就必须在每条街道上重复走一次或多次。 ;如果在某条路线中，边[vi,vj]上重复走几次，我们就在图中vi,vj之间增加几条边，令每条边的权和原来的权相等，并把所增加的边，称为重复边，于是这条路线就是相应的新图中的尤拉图。 原来的问题可以叙述为在一个有奇点的图中，要求增加一些重复边，使新图不含奇点???并且重复边的总权为最小。 我们把使新图不含奇点而增加的重复边简称为可行（重复边）方案，使总权最小的可行方案为最优方案。;现在的问题是第一个可行方案如何确定？ 在确定一个可行方案后，怎么判断这个方案是否为最优方案？ 若不是最优方案，如何调整这个方案？;车辆从某配送中心（v1）出发，给街道边上的超市（v2,v3,v4,v5,v6,v7,v8,v9）送货，如图4-8所示。;显然街区图上有奇点（4个），不满足“一笔画”的条件，则必然有一些街道要被重复走过（添加重复边）才能回到原出发点。此时得到的图就无奇点。 那么该怎样添加重复边，使得图中全为偶点呢？ 其实可以通过连接匹配的奇点得到！;第一步：确定初始可行方案;这样就得到初始方案.在这个图中，没有奇点，故称它为欧拉图。对应于这个可行方案，重复边总权为51。;想一想;第二步：调整可行方案 ;第二步：调整可行方案;;第二步：调整可行方案;第二步：调整可行方案;;检查图4中圈（v1,v2, v9, v6,v7, v8,v1）的总长度为24，但圈上重复边总权为13，大于该圈总长度的一半，因此可以做一次调整，使重复边总长度下降为15。见图5。;图5;检查图5，均满足条件（1）和（2），于是得到最优方案。图5中的任一欧拉圈都是汽车的最优配送路线。 如：v1-v2-v9-v8-v1-v8-v7-v6-v5-v4-v9-v6-v9-v4-v3-v2-v1是汽车的一条最优配送路线。;祝各位同学大展宏“图”！