图论（组合优化）实验1. 设备更新问题某公司需要对一台已经使用了2年的机器确定今后4年（n=4）的最优更新策略。公司要求，用了6年的机器必须更新，购买一台新机器的价值是100万元，表4.1给出了该问题的数据，请给出设备的更新策略。解答：设Wxy为从第二年开始算，使用x年到y年的购买设备的总消费W12=100-17.2+1.5-50=34.3 W13=100-15.5+1.7+1.5-30=57.7 W14=100-14+1.5+1.7+1.8-10=81 W15=100-12.2+1.5+1.7+1.8+2.2-5=90 W23=100-15.5+1.7-30=56.2 W24=100-14+1.7+1.8-10=79.5 W25=100-12.2+1.7+1.8+2.2-5=88.5 W34=100-14+1.8-10=77.8 W35=100-12.2+1.8+2.2-5=86.8 W45=100-12.2+2.2-5=85Lingo语句：sets: nodes/1.5/; arcs(nodes, nodes)|&1 #lt# &2: w, x; endsetsdata: w = 34.3 57.7 81 90 56.2 79.5 88.5 77.8 86.8 85; enddata n = size(nodes); min = sum(arcs: w * x); for(nodes(i)| i #ne# 1 #and# i #ne# n: sum(arcs(i,j): x(i,j) = sum(arcs(j,i): x(j,i); sum(arcs(i,j)| i #eq# 1 : x(i,j) = 1; 运行结果： Global optimal solution found.Objective value: 90.00000 Total solver iterations: 0 Variable Value Reduced Cost N 5.000000 0.000000 W( 1, 2) 34.30000 0.000000 W( 1, 3) 57.70000 0.000000 W( 1, 4) 81.00000 0.000000 W( 1, 5) 90.00000 0.000000 W( 2, 3) 56.20000 0.000000 W( 2, 4) 79.50000 0.000000 W( 2, 5) 88.50000 0.000000 W( 3, 4) 77.80000 0.000000 W( 3, 5) 86.80000 0.000000 W( 4, 5) 85.00000 0.000000 X( 1, 2) 0.000000 0.000000 X( 1, 3) 0.000000 54.50000 X( 1, 4) 0.000000 76.00000 X( 1, 5) 1.000000 0.000000 X( 2, 3) 0.000000 87.30000 X( 2, 4) 0.000000 108.8000 X( 2, 5) 0.000000 32.80000 X( 3, 4) 0.000000 76.00000 X( 3, 5) 0.000000 0.000000 X( 4, 5) 0.000000 0.000000 Row Slack or Surplus Dual Price 1 0.000000 0.000000 2 90.00000 -1.000000 3 0.000000 -90.00000 4 0.000000 -55.70000 5 0.000000 -86.80000 6 0.000000 -85.00000根据计算结果分析可知按着W15花费最少，即在第3年购买新设备第6年年底卖掉设备，最小花费为90万元。2. 运输问题有甲、乙和丙三个城市，每年分别需要煤炭320万吨、250万吨和350万吨，由A，B两个煤矿负责供应，一直煤矿年产量A为400万吨，B为450万吨，从两煤矿至各城市煤炭运价表如4.2所示。由于需求大于供应，经协商平衡，甲城市在必要时可少供应0-30万吨，乙城市需求量必须全部满足，丙城市需求量不少于270万吨。试求将甲、乙两煤矿全部分配出去，满足上述条件又使总运费最低的调运方案。解答：需求和产量表：甲乙丙产量A151822400B212516450需求320250350总需求：320+250+350=920；总产量：400+450=850增加一个虚拟产地C，产量为70需求和产量表：甲1甲2乙丙1丙2产量A1515182222400B2121251616450C0000070需求2903025027080数学模型：Min=i=1nj=1nCijxijs.t.j=1nxijai，i=1,2,3mi=1nxijbi，i=1,2,3nxij0LINGO语句：sets: From / A1, A2,A3/: Capacity; To / B1, B2, B3, B4, B5/: Demand;Routes( From, To): c, x;endsetsOBJ min = sum(Routes: c * x);for(From(i): SUPsum(To(j): x(i,j) = Demand(j);data: Capacity = 400, 450,70; Demand = 290, 30, 250, 270, 80; c = 15, 15, 18, 22, 22 21, 21, 25, 16, 16 ? , 0 , ? , ? , 0; enddata运行结果： Global optimal solution found. Objective value: 14650.00 Infeasibilities: 0.000000Total solver iterations: 7Variable Value Reduced CostX( A1, B1) 150.0000 0.000000X( A1, B2) 0.000000 5.000000X( A1, B3) 250.0000 0.000000X( A1, B4) 0.000000 12.00000X( A1, B5) 0.000000 12.00000X( A2, B1) 140.0000 0.000000X( A2, B2) 0.000000 5.000000X( A2, B3) 0.000000 1.000000X( A2, B4) 270.0000 0.000000X( A2, B5) 40.00000 0.000000X( A3, B1) 0.000000 95.00000X( A3, B2) 30.00000 0.000000X( A3, B3) 0.000000 92.00000X( A3, B4) 0.000000 100.0000X( A3, B5)