《ch网络模型》ppt课件

《《ch网络模型》ppt课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、运筹学Operations ResearchChapter6网络模型NetworkModeling6.1最小(支撑)树问题Minimal(Spanning)TreeProblem6.2最短路问题ShortestPathProblem6.3最大流问题MaximalFlowProblem6.4旅行售货员与中国邮路问题TravelingSalesmanandChinaCarrierProblem9/10/20215v1v2v3v4v5v6843752618图6－1运筹学中研究的图具有下列特征：（1）用点表示研究对象，用边（有方向或无方向）表示对象之间某种关系。（2）

2、强调点与点之间的关联关系，不讲究图的比例大小与形状。（3）每条边上都赋有一个权，其图称为赋权图。实际中权可以代表两点之间的距离、费用、利润、时间、容量等不同的含义。（4）建立一个网络模型，求最大值或最小值。9/10/2021边用[vi,vj]表示或简记为[i，j]，集合记为如图6－1所示，点集合记为边上的数字称为权，记为w[vi,vj]、w[i，j]或wij，集合记为连通的赋权图称为网络图，记为G＝｛V，E，W｝5v1v2v3v4v5v6843752618图6－19/10/20216.1最小(支撑)树问题Minimal(Spanning)TreeProblem

3、9/10/20216.1.1树的概念一个无圈并且连通的无向图称为树图或简称树(Tree)。组织机构、家谱、学科分支、因特网络、通讯网络及高压线路网络等都能表达成一个树图。可以证明：（1）一棵树的边数等于点数减1；（2）在树中任意两个点之间添加一条边就形成圈；（3）在树中去掉任意一条边图就变为不连通。在一个连通图G中，取部分边连接G的所有点组成的树称为G的部分树或支撑树(SpanningTree)。图6－2是图6－1的部分树。v1v2v3v4v5v64321图6－276.1最小树问题Minimaltreeproblem9/10/20216.1.2最小部分树将网络

4、图G边上的权看作两点间的长度（距离、费用、时间），定义G的部分树T的长度等于T中每条边的长度之和，记为C(T)。G的所有部分树中长度最小的部分树称为最小部分树，或简称为最小树。最小部分树可以直接用作图的方法求解，常用的有破圈法和加边法。破圈法：任取一圈，去掉圈中最长边，直到无圈。6.1最小树问题Minimaltreeproblem9/10/20215v1v2v3v4v5v6843752618图6－1【例6-1】用破圈法求图6－1的最小树。图6－4图6－4就是图6－1的最小部分树，最小树长为C(T)=4+3+5+2+1=15。当一个圈中有多个相同的最长边时，不能

5、同时都去掉，只能去掉其中任意一条边。最小部分树有可能不唯一，但最小树的长度相同6.1最小树问题Minimaltreeproblem9/10/2021加边法：取图G的n个孤立点｛v1，v2，…，vn}作为一个支撑图，从最短边开始往支撑图中添加，见圈回避，直到连通（有n－1条边）v1v2v3v4v5v643521图6－5在图6－5中，如果添加边[v1,v2]就形成圈｛v1,v2,v4｝，这时就应避开添加边[v1,v2]，添加下一条最短边[v3,v6]。破圈法和加边法得到树的形状可能不一样，但最小树的长度相等5v1v3v515v2v4v684375268×MinC(

6、T)=156.1最小树问题Minimaltreeproblem【例6-2】用加边法求图6－1的最小树图6－19/10/2021下一节：最短路问题1.树、支撑树、最小支撑树的概念2.掌握求最小树的方法：（1）破圈法（2）加边法作业：教材习题6.1，6.4，6.56.1最小树问题Minimaltreeproblem9/10/20216.2最短路问题ShortestPathProblem9/10/2021最短路问题在实际中具有广泛的应用，如管道铺设、线路选择等问题，还有些如设备更新、投资等问题也可以归结为求最短路问题求最短路有两种算法：一是求从某一点至其它各点之间最

7、短离的狄克斯屈拉(Dijkstra)算法另一种是求网络图上任意两点之间最短路的Floyd(弗洛伊德)矩阵算法。最短路问题，就是从给定的网络图中找出一点到各点或任意两点之间距离最短的一条路6.2.1最短路问题的网络模型6.2最短路问题ShortestPathProblem9/10/2021①②③④⑤⑥⑦610123214675811165图6－69【例6-3】图6－6中的权cij表示vi到vj的距离（费用、时间），从v1修一条公路或架设一条高压线到v7，如何选择一条路线使距离最短，建立该问题的网络数学模型。6.2最短路问题ShortestPathProblem9

8、/10/2021【解】设xij为选择弧