运筹学上机试题5-图论.doc

四、图论1、求下图中从v1到v3最短路。 从节点 1到节点3的最短路* 起点 终点 距离 - - - 1 2 1 2 3 6 此问题的解为:72、最小生成树电信公司要在15个城市之间铺设光缆，这些城市的位置及相互之间的铺设光缆的费用如下图所示。试求出一个连接在15个城市的铺设方案，使得总费用最小。 此问题的最小生成树如下：* 起点 终点 距离 - - - 1 4 1 1 2 2 2 5 2 5 8 1 5 6 2 6 3 1 8 7 2 8 9 3 9 12 2 12 11 4 11 10 1 10 13 3 13 14 1 14 15 3 此问题的解为:283、最短路问题例. 求下图中从v1到各点的最短路，并指出有哪些点是不可达到的。 从节点 1到节点2的最短路* 起点 终点 距离 - - - 1 2 4 此问题的解为:41到3没有路1到4没有路 从节点 1到节点5的最短路* 起点 终点 距离 - - - 1 5 1 此问题的解为:1 从节点 1到节点6的最短路* 起点 终点 距离 - - - 1 5 1 5 6 6 此问题的解为:7 从节点 1到节点7的最短路* 起点 终点 距离 - - - 1 7 3 此问题的解为:3 从节点 1到节点8的最短路* 起点 终点 距离 - - - 1 5 1 5 6 6 6 8 3 此问题的解为:104、最短路问题有6个村庄，各村庄的距离如下图所示。现在要开办一所小学，问应该建在哪个村庄，才能使得各村的学生上学的总路程最短？村庄123456合计10348410292301517173410628214856042255412406176107826033最小为17，选择村庄2或者村庄5建立学校5、例（多发点多收点的最大流问题）某产品有两个产地s1、s2，三个销地t1、t2、t3。运输系统如下图所示，其中v1和v2是两个中转站，各弧旁的数字是最大运输能力。求从产地到销地的最大运输量。V1-V2流量为2C12727c2C3C4C5C6C7C8C91812222从节点 1到节点9的最大流* 起点 终点 距离 - - - 1 2 27 1 3 18 2 6 10 2 4 5 2 5 12 3 5 6 3 8 12 4 6 7 4 7 0 5 4 2 5 7 6 5 8 10 6 9 17 7 9 6 8 9 22 此问题的解为:456 例（顶点有容量约束的最大流问题）某油田s通过输油管道向一炼油厂t输送原油，中间经过三个泵站v1、v2和v3，管道的输送能力和各泵站的输送能力如下图。求这个系统的最大输送能力。C1C2C3C4C5C6C7C891410139128111211 从节点 1到节点8的最大流* 起点 终点 距离 - - - 1 2 9 1 3 13 2 4 9 3 5 13 4 8 8 5 8 11 4 6 1 5 6 2 6 7 3 7 8 3 此问题的解为:227. . 求下图所示网络的最小费用最大流，弧旁数字为表示 (单位成本，容量）8. 北京（Pe）、东京(T)、纽约(N)、墨西哥城(M)、伦敦(L)、巴黎(Pa)各城市之间的航线距离如下表：LMNPaPeTL5635215160M5621577870N3521366868Pa2157365161Pe5178685113T6070686113由上述交通网络的数据确定最小生成树。 此问题的最小生成树如下：* 起点 终点 距离 - - - 1 4 21 1 3 35 3 2 21 1 5 51 5 6 13 此问题的解为:1419. 某台机器可连续工作4年，也可于每年末卖掉，换一台新的。已知于各年初购置一台新机器的价格及不同役龄机器年末的的处理价如下表所示。又新机器第一年运行及维修费为0.3万元，使用1-3年后机器每年的运行及维修费用分别为0.8，1.5，2.0万元。试确定该机器的最优更新策略，使4年内用于更换、购买及运行维修的总费用为最省。第一年第二年第三年第四年年初购置价使用了年的机器处理价2.52.02.61.62.81.33.11.1 第一年第二年第三年第四年购买价格2.52.62.83.1运行成本（每年）0.30.81.52运行成本（合计）0.31.12.64.6报废价格21.61.31.1总成本=购买价格+运行成本-报废价格年份2002年2003年2004年2005年2001年0.823.862002年00.92.13.92003年001.12.32004年0001.4从节点 1到节点5的最短路* 起点 终点 距离 - - - 1 2 0.8 2 3 0.9 3 5 2.3 此问题的解为:4设备够买3次，分别于2001、2002、2003年购买10. 某产品从仓库运往市场销售。已知各仓库的可供量、各市场需求量及从仓库至市场的路径的运输能力如下表所示（表中数字0代表无路可通），试求从仓库可运往市场的最大流量，各市场需求能否满足？仓库 市场1234可供量300201001001040405052020100需求量20206020C5C6C7C8C1C2301004020C300105020C42010405100C920206020 软件输入数据答案11011. 某单位招收懂俄、英、日、德、法文的翻译各一人，有5人应聘。已知乙懂俄文，甲、乙、丙、丁懂英文，甲、丙、丁懂日文，乙、戊懂德文，戊懂法文，问这5个人是否都能得到聘书？最多几个得到聘书，招聘后每人从事哪一方面翻译工作？12. 下表给出某运输问题的产销平衡表与单位运价表。将此问题转化为最小费用最大流问题，画出网络图并求数值解。产量 销地123产量2030242252087销量45613. 一只狼、一头山羊和一箩卷心菜在河的同侧。一个摆渡人要将它们运过河去，但由于船小，他一次只能运三者之一过河。显然，不管是狼和山羊，还是山羊和卷心菜，都不能在无人监视的情况下留在一起。问摆渡人应怎样把它们运过河去？