资源描述
会计学12022年7月16日星期六18世纪德国哥尼斯堡如图（a）七座桥，能否不重复一次走完并回到出发地？（a）七桥问题示意图（b）七桥问题简单图1736年，欧拉在圣彼得堡科学院作了一次学术报告。在报告中，他证明了鉴别任一图形能否一笔画出的准则，即欧拉定理。第1页/共35页2022年7月16日星期六“任何一张地图只用四种颜色就能使有共同边界的国家着上不同的颜色。”1852年，英国搞地图着色工作的格思里，首先提出了四色问题。1872年，英国数学家凯利正式向伦敦数学学会提出这个问题，于是四色猜想成了世界数学界关注的问题。美国数学教授哈肯和阿佩尔于1976年6月,使用伊利诺斯大学的电子计算机计算了1200个小时，作了100亿个判断，终于完成了四色定理的证明。不过不少数学家认为应该有一种简捷明快的书面证明方法。各省用点表示,有边界接壤的用连线表示,则:这张地图有几种颜色?能区分各省的边界吗?第2页/共35页2022年7月16日星期六运筹学中把一些研究对象用节点表示，对象之间的关系用连线边表示。用点、边的集合构成图。图论是研究有节点和边所组成图形的数学理论和方法。图是网络分析的基础，根据具体研究的网络对象（如：铁路网、电力网、通信网等），赋予图中各边某个具体的参数，如时间、流量、费用、距离等，规定图中各节点代表具体网络中任何一种流动的起点，中转点或终点，然后利用图论方法来研究各类网络结构和流量的优化分析。图论广泛地应用于物理学、化学、信息论、科学管理、电子计算机等各个领域。如在管理中网络合理架设、网络承载能力分析、服务设施布点、匹配问题等。第3页/共35页2022年7月16日星期六第4页/共35页2022年7月16日星期六【例7.1】有A、B、C、D、E5个球队，已比赛过，就在这两队相应的点之间连一条线.A B C E D【例7.2】8种化学药品，不能存放在同一个库房里的用连线表示。【例7.3】若在五支球队比赛中，甲胜乙表示为“甲乙”，则右图表明A三胜一负，B和E一胜一负，C和D一胜两负。第5页/共35页2022年7月16日星期六图7.5(a)v1v2v3v4e1e2e3e4e5a1a2a3v1v2v3v5e6图7.5(b)第6页/共35页2022年7月16日星期六图7.5(a)v1v2v3v4e1e2e3e4e5a1a2a3v1v2v3v5e6图7.5(b)第7页/共35页2022年7月16日星期六,VVEEGG及则称是图7.5(a)v1v2v3v4e1e2e3e4e5a1a2a3v1v2v3v5e6图7.5(b)完全图，子图，支撑图（部分图）一个简单图中若任意两点之间均有边相连，称这样的图为完全图，如图7.5(b)；图如果满足的子图；如果满足的一个支撑图（或称为部分图）。如图7.6(b)是图(a)的子图，并不是支撑图，图(c)是图(a)的支撑图。(,)(,)GV EGV E和,VVEEGG及则称是第8页/共35页2022年7月16日星期六承【例7-2】这是一个染色问题,其方法:找出次数最大的点,将其与不相邻的点组成新的点集;再从其余的子图中找出次数最大的点,将其与不相邻的点组成新的点集,直到子图的点集为空.v1v8v2v7v3v6v5v4,至少需要3个库房第9页/共35页2022年7月16日星期六第10页/共35页2022年7月16日星期六第11页/共35页2022年7月16日星期六任选vi,使viV,其余点在中VV从V与的连线中找一条最小边,使其包含在最小支撑树内所有点均在V中?结束是,iiVvV V vV否ABCDEF872594631【例7.4】求下图最小支撑树W(T*)=17第12页/共35页2022年7月16日星期六任取一个圈,从圈中去掉一条最大的边(如果有两条或两条以上的边都是权最大的边,则任意去掉其中一条).在余下的图中重复这个步骤,直到不含圈的图为止,此时的图便是最小树.ABDEF82594631C743取回路ABC，去掉最大边A,B；取回路BCE，去掉最大边B,E；取回路BCED，去掉最大边D,E；取回路BCEFD，去掉最大边B,DW(T*)=17第13页/共35页2022年7月16日星期六(1)(2)(3)(4)(5)(1)Gary(1)Gary(2)Fort Wayne(2)Fort Wayne(3)Evansvile(3)Evansvile(4)Terre Haute(4)Terre Haute(5)South Hend(5)South Hend13213221721716416458581321322902017921721729011330316416420111319658587979303196因政治原因不能建造连接(1)和(2)的公路以及连接(3)和(5)的公路.如何建造可使总施工长度最短?123452171645829020179196113W(T*)=414WinQSB演示Excel演示Lingo演示第14页/共35页2022年7月16日星期六2444633223322ABCTDEFS02356789结论：最短路径SADT，或SCFT；最短路长：9【例7.6】第15页/共35页2022年7月16日星期六【例7.7】用Dijkstra方法求点S到点T的最短路及路长。056813最短路线:SACT或:SAT最短路长:13(1)给S标号0(2)V=S,补集CV=A,B,C,T,minLSS+DSB,LSS+DSA=0+5,0+6=5给B标号5,S,B加粗(2)V=S,B,CV=A,C,T,minLSS+DSA,LSB+DBC=0+6,5+8=6给A标号6,S,A加粗(3)V=S,B,A,CV=C,T,minLSA+DAC,LSA+DAT,LSB+DBC=6+2,6+7,5+6=8给C标号8,A,C加粗(3)V=S,B,A,C,CV=T,minLSA+DAT,LSC+DCT=6+7,8+5=13给T标号13,A,C或A,T加粗WinQSB演示Excel演示Lingo演示第16页/共35页2022年7月16日星期六【例7.9】求各点间最短路矩阵(0)0232034630243204402364203243023220D解(1)构造邻接矩阵(1)(0)(0)(0)(0)(0)(0)(0)(0)(0)(0)(0)(0)(0)(0)(0)(0)min,SBSSSBSAABSBBBSCCBSDDBSEEBSFFBSTTBddddddddddddddddd0,23,0,32,4,3 (1)(0)(0)minijirrjddd(2)计算经过1个中间点的可达矩阵一般地(3)利用递推公式计算经过1个中间点的可达矩阵自编软件ExcelORM所见即所得.第17页/共35页2022年7月16日星期六案例7-2设备更新问题设备在各年年初的价格第1年第2年第3年第4年第5年1012131415使用不同时间（年）的设备所需要的维修费用使用年数0-11-22-33-44-5维修费用4691219v1v2v3v4v5v6202941602231432332241416171819求费用最小的设备更新计划.Dijkstra标号算法：先给v1标号“0”给v2标号“14”给v3标号“20”01 11 21 11 31 11 41 11 51 11 60 14020minmin 02914041060v vv vv vv vv vv vv vv vv vv vLdLdLdLdLd1 11 31 11 41 11 51 11 61 22 31 22 41 22 51 22 6020029041060minmin2014 16142214311443v vv vv vv vv vv vv vv vv vv vv vv vv vv vv vv vLdLdLdLdLdLdLdLd141 11 41 11 51 11 61 22 41 22 51 22 61 33 41 33 51 33 60290410601422minmin 1431144320 1720232032v vv vv vv vv vv vv vv vv vv vv vv vv vv vv vv vv vv vLdLdLdLdLdLdLdLdLd 29给v4标号“29”给v5标号“41”给v6标号“52”20291 11 51 11 61 22 51 22 61 33 51 43 61 44 51 44 604106014311443minmin412023203229 182924v vv vv vv vv vv vv vv vv vv vv vv vv vv vv vv vLdLdLdLdLdLdLdLd411 11 61 22 61 33 61 44 615 650601443minmin 203252292441 19v vv vv vv vv vv vv vv vv vv vLdLdLdLdLd最优路线：V1V3V6即第1年初购置，第3年初更新，第5年末结束。总费用：5252第18页/共35页2022年7月16日星期六 v3【例7.10】解(1)找出奇点(4个)(2)连接不超过回路长一半的边组成两对(虚线)(3)虚线重复一次,其余边只走一次(有多种走法)第19页/共35页2022年7月16日星期六解(1)找出奇点(6个)(2)连接不超过回路长一半的边组成两对(虚线)(3)虚线重复一次,其余边只走一次(有多种走法)第20页/共35页2022年7月16日星期六第21页/共35页2022年7月16日星期六第22页/共35页2022年7月16日星期六第23页/共35页2022年7月16日星期六第24页/共35页2022年7月16日星期六第25页/共35页2022年7月16日星期六第26页/共35页2022年7月16日星期六【例7.12】用标号法求网络的最大流。(0,)1(,4)v6(,4)v3(,4)v解 给v1标号（0，+）v1,v3非饱和弧，给v3标号，标号值min+,9-5=4，即v3标号（v1,4）v3,v6非饱和弧，给v6标号，标号值min4,5-0=4，即v6标号（v3,4）v6,v7非饱和弧，给v7标号，标号值min4,10-3=4，即v7标号（v6,4）逆向追踪找到增广链v1v3v6v7,最大可调整流量(t)=4增广链上所有的弧均为前向弧，流量+4。(0,)6(,4)v第27页/共35页2022年7月16日星期六3(0)2(0)1(0)3(0)2(0)洛杉矶JSDeDL朱诺 西雅图 丹佛 达拉斯解 先绘制容量网络图 再用Ford-Fulkerson标号算法(0,)(,3)J(,2)De(,3)S3(2)2(2)3(2)(J,1)(S,1)(L,1)1(1)2(1)3(3)最小割第28页/共35页2022年7月16日星期六第29页/共35页2022年7月16日星期六第30页/共35页2022年7月16日星期六承【例7.15】，用标号算法求从节点1到节点5的最小费用最大流。解 赋初始流0流,构造容量网络由费用构造加权网络(零流弧以bij加权,饱和弧构造反向弧以-bij反向加权,非饱和且非零流以bij和-bij双向加权).并求最短路即增广链.在增广链上调整流量第31页/共35页2022年7月16日星期六三个供应商运往每个仓库最大运输量为6;两个仓库运往每个工厂的最大运输量为6;单位费用=商品价格+单位运价;仓库到工厂的运输单价为已知数;700200500400v1v3v4v2v5v6v7供应商 仓库 工厂(6,)(6,)(6,)(6,)(6,)(6,)234402296023000232002315023200(6,)(6,)(6,)(6,)供应商供应商商品价格商品价格单位运价单位运价仓库仓库1仓库仓库2123225002270022300300+4运送路程运送路程200+5运送路程运送路程500+2运送路程运送路程300+4160=940200+550=450500+2200=900300+440=460200+560=500500+2100=700设fij表示从节点i到j的流量,则有:fij=6;目标总费用最小:min=bijfij;供应能力限制:f14+f15=10;f24+f25=10;f34+f35=10;工厂需求限制:f46+f56=10;f47+f57=6;中间点平衡:f14+f24+f34=f46+f47;f15+f25+f35=f56+f57;第32页/共35页2022年7月16日星期六有如下Lingo模型：min=23440*f14+22960*f15+23150*f24+23200*f25+23200*f34+23000*f35+200*f46+700*f47+400*f56+500*f57;!总费用最小;f14+f15=10;!产大于销，运出货物不超过各供货商供应能力;f24+f25=10;f34+f35=10;f46+f56=10;!运达货物等于工厂需求;f47+f57=6;f14+f24+f34=f46+f47;!中间点平衡;f15+f25+f35=f56+f57;f14=6;f15=6;f24=6;f25=6;f34=6;f35=6;f46=6;f47=6;f56=6;f57=6;!运量限制;Lingo模型运行结果Objective value:374460.0Total solver iterations:2 Variable Value Variable Value F15 6.000000 F46 6.000000 F24 6.000000 F56 4.000000 F35 4.000000 F57 6.000000 第33页/共35页2022年7月16日星期六第34页/共35页
展开阅读全文