运筹学上机试题5图论_第1页
运筹学上机试题5图论_第2页
运筹学上机试题5图论_第3页
运筹学上机试题5图论_第4页
运筹学上机试题5图论_第5页
已阅读5页,还剩8页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

1、四、图论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到

2、各点的最短路,并指出有哪些点是不可达到的。从节点 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个村庄,各村庄的距离如下图所示

3、。现在要开办一所小学,问应该建在哪个村庄,才能使得各村的学生上学的总路程最短?村庄123456合计10348410292301517173410628214856042255412406176107826033最小为17,选择村庄2或者村庄5建立学校5、例(多发点多收点的最大流问题)某产品有两个产地s1、s2,三个销地t1、t2、t3。运输系统如下图所示,其中v1和v2是两个中转站,各弧旁的数字是最大运输能力。求从产地到销地的最大运输量。V1-V2流量为2C12727c2C3C4C5C6C7C8C91812222从节点 1到节点9的最大流* 起点 终点 距离 - - - 1 2 27 1 3

4、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

5、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年,也可

6、于每年末卖掉,换一台新的。已知于各年初购置一台新机器的价格及不同役龄机器年末的的处理价如下表所示。又新机器第一年运行及维修费为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年2

7、003年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产量2030

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论