图论第二次作业.doc

《图论第二次作业.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、图论第二次作业：1某乡政府计划未来3年内，对所管辖的10个村要达到村与村之间都有水泥公路相通的目标。根据勘测，10个村之间修建公路的费用如表所示。乡镇府如何选择修建公路的路线使总成本最低。两村庄之间修建公路的费用(万元)123456789101234567891012.810.59.68.57.713.812.713.112.611.413.911.28.67.58.314.815.78.59.68.98.013.212.410.59.38.812.714.812.713.615.89.88.211.713.69.78.910.513.414.69.110.512.68.98.82

2、在下图中，求A到H、I的最短路及最短路长，并对图(a)和(b)的结果进行比较。图3已知某设备可继续使用5年，也可以在每年年末卖掉重新购置新设备。已知5年年初购置新设备的价格分别为3.5、3.8、4.0、4.2和4.5万元。使用时间在1～5年内的维护费用分别为0.4、0.9、1.4、2.3和3万元。试确定一个设备更新策略，使5年的设备购置和维护总费用最小。3-1设备更新问题：企业使用一台设备，每年年初，企业领导就要确定是购置新的，还是继续使用旧的.若购置新设备，就要支付一定的购置费用；若继续使用，则需支付一定的维修费用.现要制定一个五年之内的设备更新计划，使得五年内总的支付费用最少.

3、已知该种设备在每年年初的价格为：第一年第二年第三年第四年第五年1111121213使用不同时间设备所需维修费为：使用年限0－11－22－33－44－5维修费56811183-2　购车问题。Anly大学毕业后刚取得汽车驾驶执照，对SKY05型汽车情有独钟，准备第1年年初买一辆使用了3年的SKY05型的二手车，价格为7.12万元。一年后可以继续使用该车，也可以卖掉该车后购买同一品牌的新车，不再购买二手车。通过市场调查和预测，得到有关资料如下：1）该车第一年年初的价格为10万元，以后逐年降价，第二年到第5年的降价幅度分别为4%，5%，7%，5%，第t年的价格记为Pt，t=1,2,3,…2

4、）购新车必须支付10%的各项税费，购置费用记为Ct，Ct=1.1Pt3）该车第t年的维护费用Mt是使用年限t的函数，4）汽车年折旧率为15%，汽车残值为无论第5年年末更新或不更新，将汽车残值从成本中减去，等价于将车卖掉。Anly应如何制定一个5年的购车方案，才能使5年的总成本最低（不计其它成本）？5设下图是某汽车公司的6个零配件加工厂，边上的数字为两点间的距离(km)。现要在6个工厂中选一个建装配车间。（1）应选那个工厂使零配件的运输最方便。（2）装配一辆汽车6个零配件加工厂所提供零件重量分别是0.5、0.6、0.8、1.3、1.6和1.7吨，运价为2元/吨公里。应选那个工厂使总运

5、费最小。