北京工业大学-数学建模6-图论组合优化实验201311.docx

图论（组合优化）实验作业 基本实验 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龄机器的年收入，运行费用和折旧现值（如图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,B3 A2,B1 B3,C4 B3,C1 B1,C2 B1,C1 C4,D5 C4,D1 C2,D3 C2,D1 C1,D2 C1,D1 D5,E6 D5,E1 D3,E4 D3,E1 D2,E3 D2,E1 D1,E2 D1,E1 E6,F1 E4,F5 E4,F1 E3,F4 E3,F1 E2,F3 E2,F1 E1,F2 E1,F1 F5,G F4,G F3,G F2,G F1,G /: c, x; endsets data: c=17.3 -20.2 15.7 -30.2 18.4 -0.2 13.8 -50.2 17.3 -20.2 18.4 -0.2 12.2 -70.2 15.7 -30.2 17.3 -20.2 18.4 -0.2 -75.2 13.8 -50.2 15.7 -30.2 17.3 -20.2 18.4 -0.2 10 30 50 60 80; enddata n = @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 从运行结果xueyunqiang-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万吨，乙城市需求量必须全部满足，丙城市需求量不少于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/: Capacity; to / jia, yi , bing/: Demand; routes(from, to): c,