《第6章网络模型.》由会员分享,可在线阅读,更多相关《第6章网络模型.(12页珍藏版)》请在金锄头文库上搜索。
1、第6章 网络模型图6426.1如图642所示,建立求最小部分树的01整数规划数学模型。【解】边i,j的长度记为cij,设数学模型为:图6436.2如图643所示,建立求v1到v6的最短路问题的01整数规划数学模型。【解】弧(i,j)的长度记为cij,设数学模型为:6.3如图643所示,建立求v1到v6的最大流问题的线性规划数学模型。【解】 设xij为弧(i,j)的流量,数学模型为6.4求图641的最小部分树。图6-41(a)用破圈法,图6-41(b)用加边法。图644【解】图6-44(a),该题有4个解,最小树长为22,其中一个解如下图所示。图6-44(b),最小树长为20。最小树如下图所示。
2、6.5 某乡政府计划未来3年内,对所管辖的10个村要达到村与村之间都有水泥公路相通的目标。根据勘测,10个村之间修建公路的费用如表6-20所示。乡镇府如何选择修建公路的路线使总成本最低。表6-20两村庄之间修建公路的费用(万元)123456789101234567891012.810.59.68.57.713.812.713.112.611.413.911.28.67.58.314.815.78.59.68.98.013.212.410.59.38.812.714.812.713.615.89.88.211.713.69.78.910.513.414.69.110.512.68.98.8【解】
3、属于最小树问题。用加边法,得到下图所示的方案。最低总成本74.3万元。6.6在图645中,求A到H、I的最短路及最短路长,并对图(a)和(b)的结果进行比较。 图645【解】图645(a):A到H的最短路PAH=A,B,F,H,A,C,F,H最短路长22;A到I的最短路PAI=A,B,F,I,A,C,F,I最短路长21。对于图645(b):A到H的最短路PAH=A,C,G,F,H,最短路长21;A到I的最短路PAI=A,C,G,F,I,最短路长20;结果显示有向图与无向图的结果可能不一样。6.7已知某设备可继续使用5年,也可以在每年年末卖掉重新购置新设备。已知5年年初购置新设备的价格分别为3.
4、5、3.8、4.0、4.2和4.5万元。使用时间在15年内的维护费用分别为0.4、0.9、1.4、2.3和3万元。试确定一个设备更新策略,使5年的设备购置和维护总费用最小。【解】设点vj为第j年年初购置新设备的状态,(i,j)为第i年年初购置新设备使用到第j年年初,弧的权为对应的费用(购置费维护费),绘制网络图并计算,结果见下图所示。总费用最小的设备更新方案为:第一种方案,第1年购置一台设备使用到第5年年末;第二种方案,第1年购置一台设备使用到第2年年末,第3年年初更新后使用到第5年年末。总费用为11.5万元。图6466.8图646是世界某6大城市之间的航线,边上的数字为票价(百美元),用Fl
5、oyd算法设计任意两城市之间票价最便宜的路线表。【解】教师可利用模板求解:datachpt6ch6.xlsL1v1v2v3v4v5v6v108.895.686v28.801051004v3910034.814v45.653012100v581004.81209v6641410090L2v1v2v3v4v5v6v108.88.65.686v28.8085134v38.68034.814v45.65307.89v58134.87.809v66414990L3v1v2v3v4v5v6v108.88.65.686v28.8085134v38.68034.812v45.65307.89v58134.87
6、.809v66412990最优票价表:v1v2v3v4v5v6v108.88.65.686v2085134v3034.812v407.89v509v60v1、v2、v6到各点的最优路线图分别为: 6.9 设图646是某汽车公司的6个零配件加工厂,边上的数字为两点间的距离(km)。现要在6个工厂中选一个建装配车间。(1)应选那个工厂使零配件的运输最方便。(2)装配一辆汽车6个零配件加工厂所提供零件重量分别是0.5、0.6、0.8、1.3、1.6和1.7吨,运价为2元/吨公里。应选那个工厂使总运费最小。【解】(1)利用习题6.8表L3的结果v1v2v3v4v5v6Maxv108.88.65.686
7、8.8v28.808513412.8v38.68034.81212v45.65307.899v58134.87.80912.8v6641299012选第1个工厂最好。(2)计算单件产品的运价,见下表最后一行。计算单件产品的运费,见下表最后一列。v1v2v3v4v5v6单件产品运费v108.88.65.68684.88v28.808513489.16v38.68034.81282.16v45.65307.8971.96v58134.87.80981.92v6641299082.2运价11.21.62.63.23.4选第4个工厂最好。图6476.10 如图647,(1)求v1到v10的最大流及最大
8、流量;(2)求最小割集和最小割量。【解】给出初始流如下第一轮标号:得到一条增广链,调整量等于5,如下图所示调整流量。第二轮标号:得到一条增广链,调整量等于2,如下图所示调整流量。第三轮标号:得到一条增广链,调整量等于3,如下图所示调整流量。第四轮标号:不存在增广链,最大流量等于45,如下图所示取 ,最小截集(3,7),(4,7),(6,9),(8,10),最小截量等于45。6.11 将3个天然气田A1、A2、A3的天然气输送到2个地区C1、C2,中途有2个加压站B1、B2,天然气管线如图648所示。输气管道单位时间的最大通过量cij及单位流量的费用dij标在弧上(cij, dij)。求(1)流
9、量为22的最小费用流;(2)最小费用最大流。图648【解】虚拟一个发点和一个收点T6.111得到流量v22的最小费用流,最小费用为271。求解过程参看习题部分答案PPT文档。T6.1113最小费用最大流如下图,最大流量等于27,总费用等于351。6.12如图646所示,(1)求解旅行售货员问题;(2)求解中国邮路问题。图6-46【解】(1)旅行售货员问题。距离表C12345618.895.68628.81054391034.81445.65312584.8129664149在C中行列分别减除对应行列中的最小数,得到距离表C1。距离表C112345613.23.400.60.422.861034
10、7001140.6207.251.207.29600103.2由距离表C1,v1到v4, H1= v1, v4 ,v3 ,v5 ,v6 ,v2 ,v1, C(H1)=5.6+3+4.8+9+4+8.8=35.2去掉第1行第四列,d41=,得到距离表C2。得到距离表C21235622.8603470114207.251.209600103.2距离表C2的每行每列都有零,H2= H1= v1, v4 ,v3 ,v5 ,v6 ,v2 ,v1就是总距离最小的Hamilton回路,C(H1) =35.2。(2)中国邮路问题。虚拟一条边取回路H1v1,v3,v4,C(H1)=9+5+3=17,C(v1,v3)=9 C(H1)/2,调整回路。所有回路满足最短回路的准则,上图是最短的欧拉回路,其中边(v1, v4)和(v4, v3)各重复一次。6.13 思考与简答题(1)运筹学研究的图有哪些特征。(2)什么是树形图。(3)简述求有向图最短路的Dijkstra算法的基本步骤。(4)Dijkstra算法在求有向图与无向图最短路时有什么不同。(5)什么是网络最大流问题?最大流与最大流量有何区别。(6)简述最大流问题Ford-Fulkerson标号算法的基本思路。(7)求最小树有哪几种方法,分别简述各种方法的求解思路。(8)简述增广链的含义。(9)什么是最小割集,最小割集的经济含义是什么。返回顶部