资源描述：
《北京工业大学-数学建模6-图论(组合优化)实验201311》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、图论（组合优化）实验作业一、基本实验1.设备更新问题某公司需要对一台已经使用了2年的机器确定今后4年（n=4）的最优更新策略。公司要求，用了6年的机器必须更新，购买一台新机器的价格是100万元，表6.1给出了该问题的数据，请给出设备的更新策略。表6.1每年设备运行收入、运行成本以及折旧现值（单位：万元）使用年数收入运行成本折旧现值020.00.2—119.00.680.0218.51.260.0317.21.550.0415.51.730.0514.01.810.0612.22.25.0解：设rk,ck和sk表示某台k龄机器的年收入，运行
2、费用和折旧现值（如图6.1），购买一台新机器的费用每年都是I，则每项决策所产生的价值是：图6.1设备更新问题网络表示图：编写Lingo程序，用图的方法求解设备更新问题，本质上就是求解图中从起始点到终点的最长路，因此模型的数学表达式与最短路模型的表达式基本相同，只需将求极小值改为求极大值，其他不变。Lingo程序为：sets:nodes/A2,B3,B1,C4,C2,C1,D5,D3,D2,D1,E6,E4,E3,E2,E1,F5,F4,F3,F2,F1,G/;arcs(nodes,nodes)/A2,B3A2,B1B3,C4B3,C1B1
3、,C2B1,C1C4,D5C4,D1C2,D3C2,D1C1,D2C1,D1D5,E6D5,E1D3,E4D3,E1D2,E3D2,E1D1,E2D1,E1E6,F1E4,F5E4,F1E3,F4E3,F1E2,F3E2,F1E1,F2E1,F1F5,GF4,GF3,GF2,GF1,G/:c,x;endsetsdata:c=17.3-20.215.7-30.218.4-0.213.8-50.217.3-20.218.4-0.212.2-70.215.7-30.217.3-20.218.4-0.2-75.213.8-50.215.7-30.
4、217.3-20.218.4-0.21030506080;enddatan=@size(nodes);max=@sum(arcs:c*x);@sum(arcs(i,j)丨i#eq#1:x(i,j)=1;@for(nodes(i))丨i#ne#1#and#i#ne#n:@sum(arcs(i,j):x(i,j))-@sum(arcs(j,i):x(j,i))=0);@sum(arcs(j,i)丨i#eq#n:x(j,i))=1;@for(arcs:@bin(x));运行结果见xueyunqiang-chapter6-1从运行结果xueyun
5、qiang-chapter6-1可知最优方案为:A2→B3→C1→D2→E3→F1→G,即为（K,R,K,K,R），使用-更新-使用-使用-更新，使用2年的机器在第1决策年继续使用，第2决策年开始更新，第3决策年继续使用，第4决策年继续使用，第5决策年更新。2.运输问题有甲、乙和丙三个城市，每年分别需要煤炭320万吨、250万吨和350万吨，由A、B两个煤矿负责供应。已知煤矿年产量A为400万吨，B为450万吨，从两煤矿至各城市煤炭运价如表6.2所示。由于需求大于供应，经协商平衡，甲城市在必要时可少供应0-30万吨，乙城市需求量必须全部满
6、足，丙城市需求量不少于270万吨。试求甲、乙两煤炭全部分配出去，满足上述条件又使总运费最低的调运方案。表6.2煤矿与各城市之间的煤炭运价表（单位：万元/万吨）甲乙丙A151822B212516解：设cij,i=1,2,j=1,2,3分别为煤矿A,B向甲乙丙运送煤炭的运价。xij,i=1,2,j=1,2,3分别为煤矿A,B向甲乙丙三个城市运送的煤炭量。所要解决的问题是总运费最低，即目标函数为：由于要求A,B煤炭全部分配出去，bj为甲乙丙城市的最低需求量：数学规划问题为：按照数学规划模型，编写Lingo程序如下：sets:from/A,B/:
7、Capacity;to/jia,yi,bing/:Demand;routes(from,to):c,x;endsets[obj]min=@sum(routes:c*x);@for(from(i):[SUP]@sum(to(j):x(i,j))=Capacity(i));@for(to(j):[DEM]@sum(from(i):x(i,j))>=Demand(j));data:Capacity=400,450;Demand=290,250,270;c=15,18,22,21,25,16;enddata从xueyunqiang-chapter
8、6-2运行结果可知，最优方案为：A向甲运送150万吨，向乙运送250万吨，不向丙运送；B向甲运送140万吨，向丙运送310万吨，不向乙运送；此时的最优方案的总费用为14650万元。其中甲得到的
