运筹学上机试题5-图论

《运筹学上机试题5-图论》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、四、图论1、求下图中从v1到v3最短路。从节点1到节点3的最短路　　　*************************起点终点距离------------121236此问题的解为:72、最小生成树电信公司要在15个城市之间铺设光缆，这些城市的位置及相互之间的铺设光缆的费用如下图所示。试求出一个连接在15个城市的铺设方案，使得总费用最小。此问题的最小生成树如下：　　　*************************起点终点距离------------1411222525815626318728939122121141110110133131

2、4114153此问题的解为:283、最短路问题例.求下图中从v1到各点的最短路，并指出有哪些点是不可达到的。从节点1到节点2的最短路　　　*************************起点终点距离------------124此问题的解为:41到3没有路1到4没有路从节点1到节点5的最短路　　　*************************起点终点距离------------151此问题的解为:1从节点1到节点6的最短路　　　*************************起点终点距离------------151566此问题的解为

3、:7从节点1到节点7的最短路　　　*************************起点终点距离------------173此问题的解为:3从节点1到节点8的最短路　　　*************************起点终点距离------------151566683此问题的解为:104、最短路问题有6个村庄，各村庄的距离如下图所示。现在要开办一所小学，问应该建在哪个村庄，才能使得各村的学生上学的总路程最短？村庄123456合计103484102923015171734106282148560422554124061761078260

4、33最小为17，选择村庄2或者村庄5建立学校5、例（多发点多收点的最大流问题）某产品有两个产地s1、s2，三个销地t1、t2、t3。运输系统如下图所示，其中v1和v2是两个中转站，各弧旁的数字是最大运输能力。求从产地到销地的最大运输量。V1-V2流量为2C12727c2C3C4C5C6C7C8C91812222从节点1到节点9的最大流　　　*************************起点终点距离------------12271318261024525123563812467470542576581069177968922此问题的解为:

5、456例（顶点有容量约束的最大流问题）某油田s通过输油管道向一炼油厂t输送原油，中间经过三个泵站v1、v2和v3，管道的输送能力和各泵站的输送能力如下图。求这个系统的最大输送能力。C1C2C3C4C5C6C7C891410139128111211从节点1到节点8的最大流　　　*************************起点终点距离------------129131324935134885811461562673783此问题的解为:227..求下图所示网络的最小费用最大流，弧旁数字为表示(单位成本，容量）8.北京（Pe）、东京(T)、纽

6、约(N)、墨西哥城(M)、伦敦(L)、巴黎(Pa)各城市之间的航线距离如下表：LMNPaPeTL5635215160M5621577870N3521366868Pa2157365161Pe5178685113T6070686113由上述交通网络的数据确定最小生成树。此问题的最小生成树如下：　　　*************************起点终点距离------------14211335322115515613此问题的解为:1419.某台机器可连续工作4年，也可于每年末卖掉，换一台新的。已知于各年初购置一台新机器的价格及不同役龄机器年

7、末的的处理价如下表所示。又新机器第一年运行及维修费为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年2

8、005年2001年0.823.862002年00.92.13.92003年001.12.32004年0001.4从节点1到节点5的最短路　　　***********