图论与网络流

§1引言图论是应用十分广泛的运筹学分支，它已广泛地应用在物理学、化学、控制论、信息论、科学管理、电子计算机等各个领域。在实际生活、生产和科学研究中，有许多问题都可以用图论的理论和方法来解决。例如，完成工程任务的时间最少；运输距离最短；工程所用费用最少……等等。B题灾情巡视路线下图为某县的乡（镇）、村公路网示意图，公路边的数字为该路段的公里数。今年夏天该县遭受水灾。为考察灾情、组织自救，县领导决定，带领有关部门负责人到全县各乡（镇）、村巡视。灾情巡视路线指从县政府所在地出发，走遍各乡（镇）、村，又回到县政府所在地的路线。若分三组（路）巡视，试设计总路程最短且各组尽可能均衡的灾情巡视路线。1998年全国大学生数学建模竞赛题目假定巡视人员在各乡（镇）停留时间T=2小时，在各村停留时间t=1小时，汽车行驶速度V=35公里/小时。要24小时内完成巡视，至少应分几组；给出这种分组下你认为最佳的灾情巡视路线。在上述关于T,t和V的假定下，如果巡视人员足够多，完成巡视的最短时间是多少；给出在这种最短时间完成巡视的要求下，你认为最佳的灾情巡视路线。若巡视组数已定(如三组），要求尽快完成巡视，讨论T，t和V改变对最佳灾情巡视路线的影响。2001建模竞赛题目（大专组）C题基金使用计划某校基金会有一笔数额为M元的基金，打算将其存入银行或购买国库券。当前银行存款及各期国库券的利率见下表。假设国库券每年至少发行一次，发行时间不定。取款政策参考银行的现行政策。校基金会计划在n年内每年用部分本息奖励优秀师生，要求每年的奖金额大致相同，且在n年末仍保留原基金数额。校基金会希望获得最佳的基金使用计划，以提高每年的奖金额。请你帮助校基金会在如下情况下设计基金使用方案，并对M=5000万元，n=10年给出具体结果：1.只存款不购国库券；2.可存款也可购国库券；3.学校在基金到位后的第3年要举行百年校庆，基金会希望这一年的奖金比其它年度多20%。银行存款税后年利率（%）国库券年利率（%）活期0.792半年期1.664一年期1.800二年期1.9442.55三年期2.1602.89五年期2.3043.142000“网易杯”全国大学生数学建模竞赛试题B题钢管订购和运输要铺设一条的输送天然气的主管道,如图一所示(见下页)。经筛选后可以生产这种主管道钢管的钢厂有。图中粗线表示铁路，单细线表示公路，双细线表示要铺设的管道(假设沿管道或者原来有公路，或者建有施工公路)，圆圈表示火车站，每段铁路、公路和管道旁的阿拉伯数字表示里程(单位km)。为方便计，1km主管道钢管称为1单位钢管。一个钢厂如果承担制造这种钢管，至少需要生产500个单位。钢厂在指定期限内能生产该钢管的最大数量为个单位，钢管出厂销价1单位钢管为万元，如下表：1单位钢管的铁路运价如下表：•1000km以上每增加1至100km运价增加5•公路运输费用为1单位钢管每公里0.1万元（不足整公里部分按整公里计算）。•钢管可由铁路、公路运往铺设地点（不只是运到点，而是管道全线）。•（1）请制定一个主管道钢管的订购和运输计划，使总费用最小（给出总费用)。•（2）请就（1）的模型分析：哪个钢厂钢管的销价的变化对购运计划和总费用影响最大，哪个钢厂钢管的产量的上限的变化对购运计划和总费用的影响最大，并给出相应的数字结果。•（3）如果要铺设的管道不是一条线，而是一个树形图，铁路、公路和管道构成网络，请就这种更一般的情形给出一种解决办法，并对图二按（1）的要求给出模型和结果。2008年北京奥运会的建设工作已经进入全面设计和实施阶段。奥运会期间，在比赛主场馆的周边地区需要建设由小型商亭构建的临时商业网点，称为迷你超市（MiniSupermarket,以下记做MS）网，以满足观众、游客、工作人员等在奥运会期间的购物需求，主要经营食品、奥运纪念品、旅游用品、文体用品和小日用品等。在比赛主场馆周边地区设置的这种MS，在地点、大小类型和总量方面有三个基本要求：满足奥运会期间的购物需求、分布基本均衡和商业上赢利。2004年A题奥运会临时超市网点设计鸟巢国家体育馆水立方请你按以下步骤对图2的20个商区设计MS网点：1）根据附录中给出的问卷调查数据，找出观众在出行、用餐和购物等方面所反映的规律。2）假定奥运会期间（指某一天）每位观众平均出行两次，一次为进出场馆，一次为餐饮，并且出行均采取最短路径。依据1的结果，测算图2中20个商区的人流量分布（用百分比表示）。3）如果有两种大小不同规模的MS类型供选择，给出图220个商区内MS网点的设计方案（即每个商区内不同类型MS的个数），以满足上述三个基本要求。4）阐明你的方法的科学性，并说明你的结果是贴近实际的。例1最短路问题（SPP－shortestpathproblem）一名货柜车司机奉命在最短的时间内将一车货物从甲地运往乙地。从甲地到乙地的公路网纵横交错，因此有多种行车路线，这名司机应选择哪条线路呢？例2公路连接问题某一地区有若干个主要城市，现准备修建高速公路把这些城市连接起来，使得从其中任何一个城市都可以经高速公路直接或间接到达另一个城市。假定已经知道了任意两个城市之间修建高速公路的成本，那么应如何决定在哪些城市间修建高速公路，使得总成本最小？假设货柜车的运行速度是恒定的，那么这一问题相当于需要找到一条从甲地到乙地的最短路。例3指派问题（assignmentproblem）一家公司经理准备安排n名员工去完成n项任务，每人一项。由于各员工的特点不同，不同的员工去完成同一项任务时所获得的回报是不同的。如何分配工作方案可以使总回报最大？例4中国邮递员问题（CPP－chinesepostmanproblem）一名邮递员负责投递某个街区的邮件。如何为他设计一条最短的投递路线（从邮局出发，经过投递区内每条街道至少一次，最后返回邮局）？由于这一问题是我国管梅谷教授1960年首先提出的，所以国际上称之为中国邮递员问题。（匹配问题）例5旅行商问题（TSP－travelingsalesmanproblem）一名推销员准备前往若干城市推销产品。如何为他（她）设计一条最短的旅行路线（从驻地出发，经过每个城市恰好一次，最后返回驻地）？这一问题的研究历史十分悠久，通常称之为旅行商(推销员）问题。例6运输问题（transportationproblem）某种原材料有M个产地，现在需要将原材料从产地运往N个使用这些原材料的工厂。假定M个产地的产量和N家工厂的需求量已知，单位产品从任一产地到任一工厂的运费已知，那么如何安排运输方案可以使总运输成本最低？上述问题有两个共同的特点：一，其目的都是从若干可能的安排或方案中寻求某种意义下的最优安排或方案，数学上把这种问题称为最优化或优化（optimization）问题；二，都易于用图形的形式直观地描述和表达，数学上把这种与图相关的结构称为网络（network）。与图和网络相关的最优化问题就是网络最优化或称网络优化（networkoptimization）问题。由于多数网络优化问题是以网络上的流（flow）为研究的对象，因此网络优化又常常被称为网络流（networkflows）或网络流规划等。故事的背景是十八世纪的东普鲁士，美丽的Pregel河穿过哥尼斯堡；人们在河的两岸及河中两个小岛间建立了七座桥，将它们连结成一个风景优美的公园。有一天，有人突发奇想：如何才能走遍七座桥，而每座桥都只能经过一次，最后又回到原先的出发点？例1七桥问题18世纪东普鲁士哥尼斯堡被普列格尔河分为四块，它们通过七座桥相互连接起来，问能否从某块陆地出发，经每座桥一次而且仅一次，回到出发点？ACBDABCD任何一个点作为出发点都必须先“出”后“回”，才能行遍与该点相连的桥。行遍性问题对此问题，欧拉给出了一个通用判定规则：从图的某一个顶点出发，经过每条线正好一次，最后回到原来的顶点，当且仅当这个图连成一片且每个顶点都有偶数条线和它连接。思考：能否将图的每一条线走遍，但只走一次。（不必回到原顶点）从图的某一个顶点出发，经过每条线正好一次，当且仅当这个图连成一片且最多只有两个顶点是奇次的，且必须从某奇次点出发，到另一奇次点结束。ABCD以下网络中哪一个是可以遍历的(即一笔而不重复地画成)？一笔画问题欧拉注意到：一个奇顶点在这种遍历式的旅行中，要么是起点，要么是终点．由于一个遍历的网络只能有一个起点和一个终点，因而这种网络的奇点数不能多于两个．例2人、狼、羊、菜渡河问题一个摆渡人F希望用一条小船把一只狼W、一头羊G和一篮白菜C从一条河的左岸渡到右岸去，而船小只能容纳F、W、G、C中的两个，决不能在无人看守情况下，留下狼和羊在一起，羊和白菜在一起，问应怎样渡河才能将狼、羊、白菜都运过去？用小圆圈（顶点）表示河岸左边的各个状态，两点连线当且仅当两状态可在规定允许下转移。FWGCFWGFWCFGCFGWCWGC00FWGCWCFWCCWFGCFWGGFG一个人带三只狼和三只羊过河，一条船可容两只动物，没人在时，如果狼的数量不少于羊的数量就会吃掉羊，如何安全渡河?•有一天，一家人（爸爸、妈妈、2个女儿、2个儿子）和警察、小偷，想过河，船上只能装两个人，爸爸、妈妈、警察三人会划船，在过河的时候，爸爸不在的时候，妈妈会打儿子，妈妈不在的时候，爸爸会打女儿。警察不在的时候，小偷会打一家人。怎样才能使他们安全的过河？？？例3化学药品存放问题某公司生产几种化学药品a,b,c,d,e,f,g，其中某些化学药品不相容，为安全，公司要把相容的药品放在不同格中，问至少应将仓库划分为多少格？我们可以用顶点表示各个化学药品，两顶点连线当且仅当两药品不相容，便可得一个图G:adcbefg图G的点色数便是所求的最少格数为每个顶点赋一色，使凡有连线的两顶点异色，点色数即是使图得到正常点上色的最少色数。→图的正常点上色地图着色问题（四色问题）：任何一张地图只用四种颜色就能使具有共同边界的国家着上不同的颜色。111223344用数学语言表示，即“将平面任意地细分为不相重迭的区域，每一个区域总可以用1，2，3，4这四个数字之一来标记，而不会使相邻的两个区域得到相同的数字。”世界近代三大数学难题：1.费尔马大定理（1637年）在阅读丢番图《算术》拉丁文译本时，曾在第11卷第8命题旁写道：将一个立方数分成两个立方数之和，或一个四次幂分成两个四次幂之和，或者一般地将一个高于二次的幂分成两个同次幂之和，这是不可能的。)2(nzyxnnn关于此，我确信已发现了一种美妙的证法，可惜这里空白的地方太小，写不下。经过三个半世纪的努力，这个世纪数论难题才由普林斯顿大学英国数学家安德鲁•怀尔斯和他的学生理查•泰勒于1995年成功证明。3.哥德巴赫猜想（1742年6月7日，德国数学家在写给著名数学家欧拉的一封信中提出）：2.四色问题1）任何不小于6的偶数，都是两个奇质数之和；2）任何不小于9的奇数，都是三个奇质数之和。世界近代三大数学难题：任何一张地图只用四种颜色就能使具有共同边界的国家着上不同的颜色。路线着色问题一个人来到他从未造访过的小镇上，驾着车到处寻找他朋友的家，即使连路名都没有。朋友说，别担心，他会指示他如何到达，先向左，再向右，接着向左……”这个难题的假设是，在出发点（圆点）及道路（直线）的数量都固定的情况下，应该有办法以不同颜色标示道路，让人不管从哪一个点出发，都能到达固定的点。这在真实生活中的情况就像是，不管朋友住在哪里，只要知道你家的位置，绕再远都有办法到你家。以图为范本，如果按照蓝—红—红,蓝—红—红,蓝—红—红...的方式行走，不管从哪个点出发都能到黄色的点；如果是蓝—蓝—红,蓝—蓝—红,蓝—蓝—红...则一定能到绿点…（万能地图）图：是指某类具体事物和这些事物之间的联系如果我们用点表示这些具体事物，用连接两点的线段（直的或曲的）表示两个事物的特定的联系，就得到了描述这个“图”的几何形象。图与网络是运筹学（OperationsResearch）中的一个经典和重要的分支，所研究的问题涉及经济管理、工业工程、交通运输、计算机科学与信息技术、通讯与网络技术等诸多领