《2022年数学模型数学建次作业图论组合优化实验》由会员分享，可在线阅读，更多相关《2022年数学模型数学建次作业图论组合优化实验（42页珍藏版）》请在金锄头文库上搜索。
1、数学模型第六次作业图论（组合优化）实验6.1 实验目的与要求学会用图论（组合优化）的方法或思想建模学会用 LINGO 软件求解组合优化问题简历相应的数学模型，并对计算结果进行分析和讨论。6.2 基本实验1.设备更新问题某公司需要对一台已经使用了2年的机器确定今后 4年(n=4)的最优更新策略 .公司要求，用了 6年的机器必须更新，购买一台新机器的价格是100万元，表 6.1给出了该问题的数据，请给出设备的更新策略。解：根据题意可以设 A, B, C, D为判断年度，用数字表示机器已经使用的时间，则有第1年：机器使用的情况可以表示为A2；第2年：若第 1年机器不更新则情况表示成B3，若第一年机器
2、更新则精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 1 页，共 42 页第二年应表示成 B1；使用Lingo软件进行计算并取最优解，编程如下：model : sets: nodes/A2, B3, B1, C4, C2, C1, D5, D3, D2, D1,E6, E4, E3, E2, E1, F/; 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,E1 D5,E6 D3,E4 D3,E1 D2,E3
3、D2,E1 D1,E2 D1,E1 E6,F E4,F E3,F E2,F E1,F /: c, x; endsetsdata: 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 5 30 50 60 80; enddatan = size (nodes); max = sum(arcs: c * x); sum(arcs(i,j)| i #eq# 1 : x(i,j) = 1; for (nodes(i)| i #ne#
4、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); End 得到结果如下：Global optimal solution found. Objective value: 139.0000 Objective bound: 139.0000 Infeasibilities: 0.000000 Extended solver steps: 0 Total solver iterations: 0 精
5、选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 2 页，共 42 页 Variable Value Reduced Cost N 16.00000 0.000000 C( A2, B3) 17.30000 0.000000 C( A2, B1) -20.20000 0.000000 C( B3, C4) 15.70000 0.000000 C( B3, C1) -30.20000 0.000000 C( B1, C2) 18.40000 0.000000 C( B1, C1) -0.2000000 0.000000 C( C4, D5) 13.800
6、00 0.000000 C( C4, D1) -50.20000 0.000000 C( C2, D3) 17.30000 0.000000 C( C2, D1) -20.20000 0.000000 C( C1, D2) 18.40000 0.000000 C( C1, D1) -0.2000000 0.000000 C( D5, E1) 12.20000 0.000000 C( D5, E6) -70.20000 0.000000 C( D3, E4) 15.70000 0.000000 C( D3, E1) -30.20000 0.000000 C( D2, E3) 17.30000 0
7、.000000 C( D2, E1) -20.20000 0.000000 C( D1, E2) 18.40000 0.000000 C( D1, E1) -0.2000000 0.000000 C( E6, F) 5.000000 0.000000 C( E4, F) 30.00000 0.000000 C( E3, F) 50.00000 0.000000 C( E2, F) 60.00000 0.000000 C( E1, F) 80.00000 0.000000 X( A2, B3) 1.000000 -17.30000 X( A2, B1) 0.000000 20.20000 X(
8、B3, C4) 1.000000 -15.70000 X( B3, C1) 0.000000 30.20000 X( B1, C2) 0.000000 -18.40000 X( B1, C1) 0.000000 0.2000000 X( C4, D5) 1.000000 -13.80000 X( C4, D1) 0.000000 50.20000 X( C2, D3) 0.000000 -17.30000 X( C2, D1) 0.000000 20.20000 X( C1, D2) 0.000000 -18.40000 X( C1, D1) 0.000000 0.2000000 X( D5,
9、 E1) 1.000000 -12.20000 X( D5, E6) 0.000000 70.20000 X( D3, E4) 0.000000 -15.70000 X( D3, E1) 0.000000 30.20000 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 3 页，共 42 页 X( D2, E3) 0.000000 -17.30000 X( D2, E1) 0.000000 20.20000 X( D1, E2) 0.000000 -18.40000 X( D1, E1) 0.000000 0.2000000 X( E6, F) 0
10、.000000 -5.000000 X( E4, F) 0.000000 -30.00000 X( E3, F) 0.000000 -50.00000 X( E2, F) 0.000000 -60.00000 X( E1, F) 1.000000 -80.00000 Row Slack or Surplus Dual Price 1 0.000000 0.000000 2 139.0000 1.000000 3 0.000000 0.000000 4 0.000000 0.000000 5 0.000000 0.000000 6 0.000000 0.000000 7 0.000000 0.0
11、00000 8 0.000000 0.000000 9 0.000000 0.000000 10 0.000000 0.000000 11 0.000000 0.000000 12 0.000000 0.000000 13 0.000000 0.000000 14 0.000000 0.000000 15 0.000000 0.000000 16 0.000000 0.000000 17 0.000000 0.000000 18 0.000000 0.000000 分析结果容易得出最佳的路径为A2-B3-C4-D5-E1-F ，因此得出结论，设备的最优更新策略应该是使用5年。2. 运输问题有甲
12、、乙和丙三个城市，每年分别需要煤炭320万吨、250万吨和350精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 4 页，共 42 页万吨， 由A, B两个煤矿负责供应 .已知煤矿年产量 A为400万吨， B为450万吨，从两煤矿至各城市煤炭运价如表6.2所示.由于需求大于供应，经协商平衡，甲城市在必要时可少供应0-30万吨，乙城市需求量须全部满足，丙城市需求量不少于270万吨。试求将甲、乙两矿煤炭全部分配出去，满足上述条件又使总运费最低的调运方案。解：根据题意认为该问题是一个运输线性规划的典型问题。设甲、乙、丙三个城市的的煤炭获取量（Custome
13、r）1, 2, 3；A、B两个煤矿的煤炭贮存（ Warehouse ）表达为 A, B；煤矿与各城市之间的煤炭运价为P，用x表示决策点。使用 Lingo软件进行计算并取最优解，编程如下：Model : !2 Warehouse, 3 Customer Transportation Problem; sets: Warehouse / A, B/: Supply; Customer / 1, 2, 3/: Gain; Routes(Warehouse, Customer): c, x; Endsets! The objective;OBJ min = sum(Routes: c * x); !
14、The supply constraints;for (Warehouse(i): SUP sum(Customer(j): x(i,j) 290; sum(warehouse(i): x(i,1) 270; sum(warehouse(i): x(i,3) 350; ! Here are the parameters;精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 5 页，共 42 页data: Supply = 400, 450 ; Gain = 320, 250, 380 ; c = 15, 18, 22, 21, 25, 16; Endda
15、taend得到如下结果：Global optimal solution found. Objective value: 14650.00 Infeasibilities: 0.000000 Total solver iterations: 4 Variable Value Reduced Cost SUPPLY( A) 400.0000 0.000000 SUPPLY( B) 450.0000 0.000000 GAIN( 1) 250.0000 0.000000 GAIN( 2) 290.0000 0.000000 GAIN( 3) 310.0000 0.000000 C( A, 1) 15
16、.00000 0.000000 C( A, 2) 18.00000 0.000000 C( A, 3) 22.00000 0.000000 C( B, 1) 21.00000 0.000000 C( B, 2) 25.00000 0.000000 C( B, 3) 16.00000 0.000000 X( A, 1) 150.0000 0.000000 X( A, 2) 250.0000 0.000000 X( A, 3) 0.000000 12.00000 X( B, 1) 140.0000 0.000000 X( B, 2) 0.000000 1.000000 X( B, 3) 310.0
17、000 0.000000 因此得到结论：由A 矿向甲乙丙三座城市的送矿量（万吨）为150、250、0；由 B 矿向甲乙丙三座城市的送矿量 （万吨）为 140、0、310，此时总运输费最小，为14650万元。3、生产计划与库存管理(1)某公司生产一种除臭剂，它在1 至 4 季度的生产成本、生产量及精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 6 页，共 42 页订货量表 6.3所示.如果除臭剂在生产当季没有交货， 保管在仓库里除臭剂每盒每季度还需1 元钱的储存费用。如果某个季度的货物供应量不足，则允许延期交货，延期交货的罚金是每盒每季度3 元。请公
18、司希望制定一个成本最低(包括储存费用和罚金)的除臭剂的生产计划，问各季度应生产多少 ? (2)如果产品不允许延期交货，则公司考虑工人加班，已知加班生产出产品的成本要比原成本高出20%，且每季度加班最多生产2 万盒.问:在这种情况下，将如何安排生产，使总成本最少? 解：（1）根据题意，将此问题转化为运输问题，将每季度的生产量看作是供方，将每季度的订货量看作是需求方，将不属于本季度供货的量视为其他季度运输过来的，那么具体思路作图如下：红色字样为第一季度运输每件费用，5+13 5+12 5+1 5 季度 1 生产量季度 1 订货量精选学习资料 - - - - - - - - - 名师归纳总结 - -
19、 - - - - -第 7 页，共 42 页红色字样为季度 1 生产向 4 个季度的运送量；绿色字样为季度 2 生产向 4 个季度的运送量；蓝色字样为季度 2 生产向 4 个季度的运送量；黑色字样为季度 2 生产向 4 个季度的运送量。列出配送供需表格：季度 1 需求季度 2 需求季度 3 需求季度 4 需求6+1 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 8 页，共 42 页设 cij 为从季度生产 Ai 到季度需求 Bj 的配送单价， xij 为从季度生产Ai 到季度需求 Bj 的运输量，因此总的费用为：11mnijijijc x第 i
20、个季度的运出量应该小于或等于该季度的生产量：1mijijxa第 j 个季度的运入量应该等于该季度的需求量：1mijjixb根据此模型写出 Lingo 程序并求出最优解：Model : !4 Warehouse, 4 Customer Transportation Problem;sets: 季度 1 配送单价（万元/万盒）5 6 6 6 季度 2 配送单价（万元/万盒）8 5 6 7 季度 3 配送单价（万元/万盒）12 9 6 7 季度 4 配送单价（万元/万盒）15 12 9 6 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 9 页，共 42
21、 页 Warehouse /1.4/: a; Customer /1.4/: b; Routes(Warehouse, Customer): c, x; Endsets! Here are the parameters;data: a= 13, 15, 15, 13 ; b= 10, 14, 20, 8 ; c = 5, 6, 7, 8, 8, 5, 6, 7, 12, 9, 6, 7, 15, 12, 9, 6; Enddata! The objective;OBJ min = sum(Routes: c * x); ! The supply constraints;for (Warehou
22、se(i): SUP sum(Customer(j): x(i,j)= a(i); ! The demand constraints;for (Customer(j): DEM sum(Warehouse(i): x(i,j)= b(j); end得到如下结果：Global optimal solution found. Objective value: 294.0000 Infeasibilities: 0.000000 Total solver iterations: 7 Variable Value Reduced Cost A( 1) 13.00000 0.000000 A( 2) 1
23、5.00000 0.000000 A( 3) 15.00000 0.000000 A( 4) 13.00000 0.000000 B( 1) 10.00000 0.000000 B( 2) 14.00000 0.000000 B( 3) 20.00000 0.000000 B( 4) 8.000000 0.000000 C( 1, 1) 5.000000 0.000000 C( 1, 2) 6.000000 0.000000 C( 1, 3) 7.000000 0.000000 C( 1, 4) 8.000000 0.000000 精选学习资料 - - - - - - - - - 名师归纳总结
24、 - - - - - - -第 10 页，共 42 页 C( 2, 1) 8.000000 0.000000 C( 2, 2) 5.000000 0.000000 C( 2, 3) 6.000000 0.000000 C( 2, 4) 7.000000 0.000000 C( 3, 1) 12.00000 0.000000 C( 3, 2) 9.000000 0.000000 C( 3, 3) 6.000000 0.000000 C( 3, 4) 7.000000 0.000000 C( 4, 1) 15.00000 0.000000 C( 4, 2) 12.00000 0.000000 C(
25、 4, 3) 9.000000 0.000000 C( 4, 4) 6.000000 0.000000 X( 1, 1) 10.00000 0.000000 X( 1, 2) 3.000000 0.000000 X( 1, 3) 0.000000 0.000000 X( 1, 4) 0.000000 4.000000 X( 2, 1) 0.000000 4.000000 X( 2, 2) 11.00000 0.000000 X( 2, 3) 4.000000 0.000000 X( 2, 4) 0.000000 4.000000 X( 3, 1) 0.000000 8.000000 X( 3,
26、 2) 0.000000 4.000000 X( 3, 3) 15.00000 0.000000 X( 3, 4) 0.000000 4.000000 X( 4, 1) 0.000000 8.000000 X( 4, 2) 0.000000 4.000000 X( 4, 3) 1.000000 0.000000 X( 4, 4) 8.000000 0.000000 Row Slack or Surplus Dual Price OBJ 294.0000 -1.000000 SUP( 1) 0.000000 2.000000 SUP( 2) 0.000000 3.000000 SUP( 3) 0
27、.000000 3.000000 SUP( 4) 4.000000 0.000000 DEM( 1) 0.000000 -7.000000 DEM( 2) 0.000000 -8.000000 DEM( 3) 0.000000 -9.000000 DEM( 4) 0.000000 -6.000000 分析结果易知，最佳的方案为：第一季度生产14 万盒，给出 10 万盒满足第一季度要求，库存3 万盒，不拖欠；第二季度生产15 万盒，给出 11万盒，连同第一季度库存3 万盒加起来为 14 万盒满足第二季精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 1
28、1 页，共 42 页度要求，库存 4 万盒，不拖欠；第三季度生产15 万盒，全部给出，连同第二季度库存4 万盒加起来 19 万盒，拖欠 1 万盒；第四季度生产 9万盒， 还清第三季度拖欠1 万盒， 剩下 8 万盒满足第四季度需求。此方案下总成本最小，为294万元。（2）分析题目，可以将工人加班的费用视为除本季生产外为接下来其他季度供应货物的费用。参考如下配送供需表格：对于 Lingo 程序的改变，只需将每季度生产量扩充为+2 万盒即可，对于表格中午单价的位置，使用极大数105来表示无穷大，根据此模型写出 Lingo 程序并求出最优解：Model : 季度 1 需求季度 2 需求季度 3 需求季
29、度 4 需求季度 1 配送单价（万元/万盒）5 6 6 6 季度 2 配送单价（万元/万盒）- 5 6 6 季度 3 配送单价（万元/万盒）- - 6 7.2 季度 4 配送单价（万元/万盒）- - - 6 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 12 页，共 42 页!4 Warehouse, 4 Customer Transportation Problem;sets: Warehouse /1.4/: a; Customer /1.4/: b; Routes(Warehouse, Customer): c, x; Endsets! H
30、ere are the parameters;data: a= 15, 17, 17, 15 ; b= 10, 14, 20, 8 ; c = 5, 6, 6, 6, 100000, 5, 6, 6, 1000000, 1000000, 6, 7.2, 1000000, 1000000, 1000000, 6; Enddata! The objective;OBJ min = sum(Routes: c * x); ! The supply constraints;for (Warehouse(i): SUP sum(Customer(j): x(i,j)= a(i); ! The deman
31、d constraints;for (Customer(j): DEM sum(Warehouse(i): x(i,j)= b(j); end得到如下结果： Global optimal solution found. Objective value: 288.0000 Infeasibilities: 0.000000 Total solver iterations: 8 Variable Value Reduced Cost A( 1) 15.00000 0.000000 A( 2) 17.00000 0.000000 A( 3) 17.00000 0.000000 A( 4) 15.00
32、000 0.000000 B( 1) 10.00000 0.000000 B( 2) 14.00000 0.000000 B( 3) 20.00000 0.000000 B( 4) 8.000000 0.000000 C( 1, 1) 5.000000 0.000000 C( 1, 2) 6.000000 0.000000 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 13 页，共 42 页 C( 1, 3) 6.000000 0.000000 C( 1, 4) 6.000000 0.000000 C( 2, 1) 100000.0 0.0000
33、00 C( 2, 2) 5.000000 0.000000 C( 2, 3) 6.000000 0.000000 C( 2, 4) 6.000000 0.000000 C( 3, 1) 1000000. 0.000000 C( 3, 2) 1000000. 0.000000 C( 3, 3) 6.000000 0.000000 C( 3, 4) 7.200000 0.000000 C( 4, 1) 1000000. 0.000000 C( 4, 2) 1000000. 0.000000 C( 4, 3) 1000000. 0.000000 C( 4, 4) 6.000000 0.000000
34、X( 1, 1) 10.00000 0.000000 X( 1, 2) 0.000000 1.000000 X( 1, 3) 0.000000 0.000000 X( 1, 4) 5.000000 0.000000 X( 2, 1) 0.000000 99995.00 X( 2, 2) 14.00000 0.000000 X( 2, 3) 3.000000 0.000000 X( 2, 4) 0.000000 0.000000 X( 3, 1) 0.000000 999995.0 X( 3, 2) 0.000000 999995.0 X( 3, 3) 17.00000 0.000000 X(
35、3, 4) 0.000000 1.200000 X( 4, 1) 0.000000 999995.0 X( 4, 2) 0.000000 999995.0 X( 4, 3) 0.000000 999994.0 X( 4, 4) 3.000000 0.000000 Row Slack or Surplus Dual Price OBJ 288.0000 -1.000000 SUP( 1) 0.000000 0.000000 SUP( 2) 0.000000 0.000000 SUP( 3) 0.000000 0.000000 SUP( 4) 12.00000 0.000000 DEM( 1) 0
36、.000000 -5.000000 DEM( 2) 0.000000 -5.000000 DEM( 3) 0.000000 -6.000000 DEM( 4) 0.000000 -6.000000 分析结果，得到最优生产方案：精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 14 页，共 42 页第一季度生产 15 万盒（2 万盒为加班产出），10 万盒给出，满足第一季度需求，剩下5 万盒库存至第四季度；第二季度生产17 万盒（ 2万盒为加班产出），14 万盒给出，满足第二季度需求，剩下3 万盒库存至第三季度；第三季度生产17 万盒（2 万盒为加班产
37、出），连同第二季度库存共计20 万盒给出，满足第三季度需求；第四季度生产3万， 盒连同第一季度库存5万盒共计 8万盒给出，满足第四季度要求。此时可以将成本控制到最少288 万元。4. 指派问题某公司需要把 4 项工作派给 4 名工人，每名工人完成每项工作的费用如表 6.4所示， 其中工人甲不能完成工作C， 工人丙不能完成工作D。(1)确定每名工人完成工作的最优方案；精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 15 页，共 42 页(2)假设有另外一名工人（戊）能完成这4 项工作，完成每项工作相应费用分别为60、45、30 和 80 元。是否用这
38、名新工人（戊）替换原来的某位工人？(3)假设公司有了第5 项工作(E)，4 名工人（甲、乙、丙、丁）完成工作 E 的费用分别为 20、10、20 和 80 元。这项新工作E 比原有的四项工作 (A, B, C, D)的某一项优先吗？解：（1）根据题意，此题属于最优指派问题，引入如下变量：设变量为 xij,表示第 i 个人做第 j 项工作时，xij=1， 否则 xij=0。 因此，相应的线性规划问题为：i 11minnnijijjc x限制条件为：11nijjx，i=1, 2, , n, （每个人做一项工作）11nijix，j=1,2, n （每项工作有一个人去做）精选学习资料 - - - -
39、- - - - - 名师归纳总结 - - - - - - -第 16 页，共 42 页01ijx或，i, j=1, 2, , n 对于不能工作的情况取一个极大数代替之即可。根据此模型写出 Lingo 程序并求出最优解：model : !4 个工人， 4个工作的分配问题;sets: workers/w1.w4/; jobs/j1.j4/; links(workers,jobs): cost,volume; endsets! 目标函数 ;min =sum(links: cost*volume); ! 每个工人只能有一份工作;for (workers(I): sum(jobs(J): volume(
40、I,J)=1; ); ! 每份工作只能有一个工人;for (jobs(J): sum(workers(I): volume(I,J)=1; ); data: cost= 50 50 100000 20 70 40 20 30 90 30 50 100000 70 20 60 70; enddataend得到如下结果：Objective value: 140.0000 Infeasibilities: 0.000000 Total solver iterations: 8 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 17 页，共 42 页 Var
41、iable Value Reduced Cost COST( W1, J1) 50.00000 0.000000 COST( W1, J2) 50.00000 0.000000 COST( W1, J3) 100000.0 0.000000 COST( W1, J4) 20.00000 0.000000 COST( W2, J1) 70.00000 0.000000 COST( W2, J2) 40.00000 0.000000 COST( W2, J3) 20.00000 0.000000 COST( W2, J4) 30.00000 0.000000 COST( W3, J1) 90.00
42、000 0.000000 COST( W3, J2) 30.00000 0.000000 COST( W3, J3) 50.00000 0.000000 COST( W3, J4) 100000.0 0.000000 COST( W4, J1) 70.00000 0.000000 COST( W4, J2) 20.00000 0.000000 COST( W4, J3) 60.00000 0.000000 COST( W4, J4) 70.00000 0.000000 VOLUME( W1, J1) 0.000000 0.000000 VOLUME( W1, J2) 0.000000 50.0
43、0000 VOLUME( W1, J3) 0.000000 99990.00 VOLUME( W1, J4) 1.000000 0.000000 VOLUME( W2, J1) 0.000000 10.00000 VOLUME( W2, J2) 0.000000 30.00000 VOLUME( W2, J3) 1.000000 0.000000 VOLUME( W2, J4) 0.000000 0.000000 VOLUME( W3, J1) 0.000000 10.00000 VOLUME( W3, J2) 1.000000 0.000000 VOLUME( W3, J3) 0.00000
44、0 10.00000 VOLUME( W3, J4) 0.000000 99950.00 VOLUME( W4, J1) 1.000000 0.000000 VOLUME( W4, J2) 0.000000 0.000000 VOLUME( W4, J3) 0.000000 30.00000 VOLUME( W4, J4) 0.000000 30.00000 由此得到最佳的工作方案： 应该由甲来完成工作D， 乙来完成工作 C，丙来完成工作 B， 丁来完成工作 A。 此时总工作成本最小， 为 140 元。（2）根据题意加入一人戊后该工作变为5 人 4 项工作问题，安照该思路，使用 Lingo 写
45、出程序并求出最优解：model : !5 个工人， 4个工作的分配问题;sets: 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 18 页，共 42 页 workers/w1.w5/; jobs/j1.j4/; links(workers,jobs): cost,volume; endsets! 目标函数 ;min =sum(links: cost*volume); ! 每个工人只能有一份工作;for (workers(I): sum(jobs(J): volume(I,J)=1; ); ! 每份工作只能有一个工人;for (jobs(J): s
46、um(workers(I): volume(I,J)=1; ); data: cost= 50 50 100000 20 70 40 20 30 90 30 50 100000 70 20 60 70 60 45 30 80; enddataend得到如下结果：Global optimal solution found. Objective value: 120.0000 Infeasibilities: 0.000000 Total solver iterations: 6 Variable Value Reduced Cost COST( W1, J1) 50.00000 0.000000
47、 COST( W1, J2) 50.00000 0.000000 COST( W1, J3) 100000.0 0.000000 COST( W1, J4) 20.00000 0.000000 COST( W2, J1) 70.00000 0.000000 COST( W2, J2) 40.00000 0.000000 COST( W2, J3) 20.00000 0.000000 COST( W2, J4) 30.00000 0.000000 COST( W3, J1) 90.00000 0.000000 COST( W3, J2) 30.00000 0.000000 COST( W3, J
48、3) 50.00000 0.000000 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 19 页，共 42 页 COST( W3, J4) 100000.0 0.000000 COST( W4, J1) 70.00000 0.000000 COST( W4, J2) 20.00000 0.000000 COST( W4, J3) 60.00000 0.000000 COST( W4, J4) 70.00000 0.000000 COST( W5, J1) 60.00000 0.000000 COST( W5, J2) 45.00000 0.000
49、000 COST( W5, J3) 30.00000 0.000000 COST( W5, J4) 80.00000 0.000000 VOLUME( W1, J1) 0.000000 0.000000 VOLUME( W1, J2) 0.000000 40.00000 VOLUME( W1, J3) 0.000000 99990.00 VOLUME( W1, J4) 1.000000 0.000000 VOLUME( W2, J1) 0.000000 10.00000 VOLUME( W2, J2) 0.000000 20.00000 VOLUME( W2, J3) 1.000000 0.0
50、00000 VOLUME( W2, J4) 0.000000 0.000000 VOLUME( W3, J1) 0.000000 30.00000 VOLUME( W3, J2) 0.000000 10.00000 VOLUME( W3, J3) 0.000000 30.00000 VOLUME( W3, J4) 0.000000 99970.00 VOLUME( W4, J1) 0.000000 10.00000 VOLUME( W4, J2) 1.000000 0.000000 VOLUME( W4, J3) 0.000000 40.00000 VOLUME( W4, J4) 0.0000
51、00 40.00000 VOLUME( W5, J1) 1.000000 0.000000 VOLUME( W5, J2) 0.000000 25.00000 VOLUME( W5, J3) 0.000000 10.00000 VOLUME( W5, J4) 0.000000 50.00000 由此可以得出结论，此时最佳的工作方案为，由甲做工作D，乙来做工作 C，丁来做工作 B，戊来做工作 A。因此，戊要替换掉丙。此时成本最小，为 120 元。（3）根据题意加入工作E 后原题目变为 4 人 5 项工作问题，安照该思路，使用 Lingo 写出程序并求出最优解：model : !4 个工人， 5个
52、工作的分配问题;精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 20 页，共 42 页sets: workers/w1.w4/; jobs/j1.j5/; links(workers,jobs): cost,volume; endsets! 目标函数 ;min =sum(links: cost*volume); ! 每个工人只能有一份工作;for (workers(I): sum(jobs(J): volume(I,J)=1; ); ! 每份工作只能有一个工人;for (jobs(J): sum(workers(I): volume(I,J)=1;
53、 ); data: cost= 50 50 100000 20 20 70 40 20 30 10 90 30 50 100000 20 70 20 60 70 80; enddataend 得到如下结果：Global optimal solution found. Objective value: 80.00000 Infeasibilities: 0.000000 Total solver iterations: 5 Variable Value Reduced Cost COST( W1, J1) 50.00000 0.000000 COST( W1, J2) 50.00000 0.00
54、0000 COST( W1, J3) 100000.0 0.000000 COST( W1, J4) 20.00000 0.000000 COST( W1, J5) 20.00000 0.000000 COST( W2, J1) 70.00000 0.000000 COST( W2, J2) 40.00000 0.000000 COST( W2, J3) 20.00000 0.000000 COST( W2, J4) 30.00000 0.000000 COST( W2, J5) 10.00000 0.000000 COST( W3, J1) 90.00000 0.000000 精选学习资料
55、- - - - - - - - - 名师归纳总结 - - - - - - -第 21 页，共 42 页 COST( W3, J2) 30.00000 0.000000 COST( W3, J3) 50.00000 0.000000 COST( W3, J4) 100000.0 0.000000 COST( W3, J5) 20.00000 0.000000 COST( W4, J1) 70.00000 0.000000 COST( W4, J2) 20.00000 0.000000 COST( W4, J3) 60.00000 0.000000 COST( W4, J4) 70.00000 0
56、.000000 COST( W4, J5) 80.00000 0.000000 VOLUME( W1, J1) 0.000000 30.00000 VOLUME( W1, J2) 0.000000 30.00000 VOLUME( W1, J3) 0.000000 99980.00 VOLUME( W1, J4) 1.000000 0.000000 VOLUME( W1, J5) 0.000000 10.00000 VOLUME( W2, J1) 0.000000 50.00000 VOLUME( W2, J2) 0.000000 20.00000 VOLUME( W2, J3) 1.0000
57、00 0.000000 VOLUME( W2, J4) 0.000000 10.00000 VOLUME( W2, J5) 0.000000 0.000000 VOLUME( W3, J1) 0.000000 60.00000 VOLUME( W3, J2) 0.000000 0.000000 VOLUME( W3, J3) 0.000000 20.00000 VOLUME( W3, J4) 0.000000 99970.00 VOLUME( W3, J5) 1.000000 0.000000 VOLUME( W4, J1) 0.000000 50.00000 VOLUME( W4, J2)
58、1.000000 0.000000 VOLUME( W4, J3) 0.000000 40.00000 VOLUME( W4, J4) 0.000000 50.00000 VOLUME( W4, J5) 0.000000 70.00000 分析结果易知，此时的工作方案为甲完成工作D，乙完成工作 C，丙完成工作 E，丁完成工作 B，因此，新工作 E 的优先程度要比原工作A 要高。5. 旅行商问题张三住在 A 市，他在 A, B, C, D, E 和 F 市都有保险代理业务。由于业务关系，他每个月都需要访问这些城市作一次。表6.5给出了每个精选学习资料 - - - - - - - - - 名师归纳
59、总结 - - - - - - -第 22 页，共 42 页城市之间的距离， 试分析他按照什么的顺序访问这些城市使得总旅行的距离最短？ (1)用启发式算法求解； (2)用 LINGO 软件求解解：（1） 依题意，需选用一种启发式算法来求解此题目，由 A 出发再回到 A，选用利用 Hamilton 圈的方法。 根据数据表提供的数据绘出网络图：构造初始 Hamilton 圈 C1:A-B-C-D-E-F-A ：A B CD E F 588 129 483 1288 440 542 334 1096 825 448 1675 1410 1346 1638 B C 精选学习资料 - - - - - -
60、- - - 名师归纳总结 - - - - - - -第 23 页，共 42 页修改圈：w(AC)+w(BD)=448+542=990 w(AB)+w(CD)=588+483=1041 所以，修改圈 C1 为 C2。得到修改后的顺序为A-C-B-D-E-F-A ：此时全长为 w(AC)+w(CB)+w(BD)+w(ED)+w(EF)+w(FA) =448+129+542+1288+440+825=3672 （公里）对于 C2， 已经无法继续改进，因此， 该圈为此题目的最优Hamilton圈。由此得出旅行商的最佳路径为：A-C-B-D-E-F-A 。(2)假设旅行商问题由城市1, 2, ,n 组成
61、，wij表示城市 i 到城市 j 之A F D E 448 483 542 588 A C B F D E 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 24 页，共 42 页间的距离，决策变量定义为：xij=1 表示选择从城市i 到城市 j；xij=0表示不选择。则线性（整数）规划模型为：i 11minnnijijjw x限制条件为：11nijix，j=1,2, n 11nijjx，i=1, 2, , n, 1, ,2,3,., ,0,1,2,., .ijijjuunxnij i jnujn01ijx或，i, j=1, 2, , n 按照此模型
62、写出相应的Lingo 程序：model : sets: city/A B C D E F/: u; link(city, city): w, x; endsetsdata: !to: A B C D E F; w = 0 588 542 334 1096 825 !from A; 588 0 129 448 1675 1410!from B; 542 129 0 483 1638 1346!from C; 334 448 483 0 1288 1100!from D; 1096 1675 1638 1288 0 440!from E; 825 1410 1346 1100 440 0;!fro
63、m F;enddatan= size (city); min = sum(link: w * x); for (city(k): 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 25 页，共 42 页sum(city(i)| i #ne# k: x(i,k)=1; sum(city(j)| j #ne# k: x(k,j)=1; ); for (link(i,j)|i #gt# 1 #and# j #gt# 1 #and# i #ne# j: u(i)-u(j)+n*x(i,j)= 1; for (city(j)|j #gt# 1: sum( ci
64、ty(i)| i #ne# j: x(i, j) = 1; ); n= size (city); for (link(i,j)|i #ne# j: u(i)-u(j)+ n*x(i,j)= n-1); for (link: bin (x); end得到如下结果：Global optimal solution found. Objective value: 2176.000 Objective bound: 2176.000 Infeasibilities: 0.000000 Extended solver steps: 2 Total solver iterations: 110 Variab
65、le Value Reduced Cost N 6.000000 0.000000 U( A) 0.000000 0.000000 U( B) 2.000000 0.000000 U( C) 3.000000 0.000000 U( D) 1.000000 0.000000 U( E) 5.000000 0.000000 U( F) 1.000000 0.000000 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 30 页，共 42 页 W( A, A) 0.000000 0.000000 W( A, B) 588.0000 0.000000 W
66、( A, C) 542.0000 0.000000 W( A, D) 334.0000 0.000000 W( A, E) 1096.000 0.000000 W( A, F) 825.0000 0.000000 W( B, A) 588.0000 0.000000 W( B, B) 0.000000 0.000000 W( B, C) 129.0000 0.000000 W( B, D) 448.0000 0.000000 W( B, E) 1675.000 0.000000 W( B, F) 1410.000 0.000000 W( C, A) 542.0000 0.000000 W( C
67、, B) 129.0000 0.000000 W( C, C) 0.000000 0.000000 W( C, D) 483.0000 0.000000 W( C, E) 1638.000 0.000000 W( C, F) 1346.000 0.000000 W( D, A) 334.0000 0.000000 W( D, B) 448.0000 0.000000 W( D, C) 483.0000 0.000000 W( D, D) 0.000000 0.000000 W( D, E) 1288.000 0.000000 W( D, F) 1100.000 0.000000 W( E, A
68、) 1096.000 0.000000 W( E, B) 1675.000 0.000000 W( E, C) 1638.000 0.000000 W( E, D) 1288.000 0.000000 W( E, E) 0.000000 0.000000 W( E, F) 440.0000 0.000000 W( F, A) 825.0000 0.000000 W( F, B) 1410.000 0.000000 W( F, C) 1346.000 0.000000 W( F, D) 1100.000 0.000000 W( F, E) 440.0000 0.000000 W( F, F) 0
69、.000000 0.000000 X( A, A) 0.000000 0.000000 X( A, B) 0.000000 588.0000 X( A, C) 0.000000 542.0000 X( A, D) 1.000000 334.0000 X( A, E) 0.000000 1096.000 X( A, F) 1.000000 825.0000 X( B, A) 0.000000 588.0000 X( B, B) 0.000000 0.000000 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 31 页，共 42 页 X( B, C)
70、 1.000000 129.0000 X( B, D) 0.000000 448.0000 X( B, E) 0.000000 1675.000 X( B, F) 0.000000 1410.000 X( C, A) 0.000000 542.0000 X( C, B) 0.000000 129.0000 X( C, C) 0.000000 0.000000 X( C, D) 0.000000 483.0000 X( C, E) 0.000000 1638.000 X( C, F) 0.000000 1346.000 X( D, A) 0.000000 334.0000 X( D, B) 1.
71、000000 448.0000 X( D, C) 0.000000 483.0000 X( D, D) 0.000000 0.000000 X( D, E) 0.000000 1288.000 X( D, F) 0.000000 1100.000 X( E, A) 0.000000 1096.000 X( E, B) 0.000000 1675.000 X( E, C) 0.000000 1638.000 X( E, D) 0.000000 1288.000 X( E, E) 0.000000 0.000000 X( E, F) 0.000000 440.0000 X( F, A) 0.000
72、000 825.0000 X( F, B) 0.000000 1410.000 X( F, C) 0.000000 1346.000 X( F, D) 0.000000 1100.000 X( F, E) 1.000000 440.0000 X( F, F) 0.000000 0.000000 其计算结果表明，连接这6 个城市的最优连线为：A-D、A-F、B-C、D-B、F-E，连线最优总长度为2176公里。7.最大流问题三个炼油厂通过管道网络为两个分散的终端运送汽油。这个管道网络中精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 32 页，共 42
73、 页有三个泵站， 如图 6.1 所示.汽油的流向如图中箭头所示，图中标出了每一段管道的运送容量，单位是百万桶/天。求解下面的问题：(1)要满足这个网络的最大流量，每一个炼油厂每天的产量应该是多少；(2)要满足这个网络的最大流量，每一个终端每天的需求量应该是多少；(3)要满足这个网络的最大流量，每个泵站每天的容量应该是多少；(4)如果进一步假定在图6.1所示的网络中泵站 6 每天的最大容量限制为50 百万桶，求出相应的网络的最大容量。解：根据题意，该题目为多源多汇的最大流问题，于是想到将此多源多汇问题转换为单源单汇问题，作图如下：根据此模型写出 Lingo程序并求出最优解：model : 1 2
74、 3 4 5 6 7 8 s t 20 10 50 20 15 20 10 10 30 30 20 50 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 33 页，共 42 页sets: nodes/s,1,2,3,4,5,6,7,8,t/; arcs(nodes,nodes)/s 1,s 2,s 3,1 4,2 4,2 5,2 6,3 5,4 5,4 6,4 7,5 6,5 8,6 7,6 8,7 t,8 t/:c,f; endsetsdata: c=100000 100000 100000 20 10 20 50 15 20 10 10 30
75、30 50 20 100000 100000; enddatan= size (nodes); ! 顶点的个数 ;max=flow; for (nodes(i)|i #ne#1 #and# i #ne# n: sum(arcs(i,j):f(i,j)=sum(arcs(j,i):f(j,i); sum(arcs(i,j)|i #eq# 1:f(i,j)=flow; sum(arcs(i,j)|j #eq# n:f(i,j)=flow; for (arcs:bnd(0,f,c); end得到结果如下：Global optimal solution found. Objective value:
76、110.0000 Infeasibilities: 0.000000 Total solver iterations: 3 Variable Value Reduced Cost N 10.00000 0.000000 FLOW 110.0000 0.000000 C( S, 1) 100000.0 0.000000 C( S, 2) 100000.0 0.000000 C( S, 3) 100000.0 0.000000 C( 1, 4) 20.00000 0.000000 C( 2, 4) 10.00000 0.000000 C( 2, 5) 20.00000 0.000000 C( 2,
77、 6) 50.00000 0.000000 C( 3, 5) 15.00000 0.000000 C( 4, 5) 20.00000 0.000000 C( 4, 6) 10.00000 0.000000 C( 4, 7) 10.00000 0.000000 C( 5, 6) 30.00000 0.000000 C( 5, 8) 30.00000 0.000000 C( 6, 7) 50.00000 0.000000 C( 6, 8) 20.00000 0.000000 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 34 页，共 42 页 C(
78、7, T) 100000.0 0.000000 C( 8, T) 100000.0 0.000000 F( S, 1) 20.00000 0.000000 F( S, 2) 75.00000 0.000000 F( S, 3) 15.00000 0.000000 F( 1, 4) 20.00000 0.000000 F( 2, 4) 10.00000 0.000000 F( 2, 5) 15.00000 0.000000 F( 2, 6) 50.00000 0.000000 F( 3, 5) 15.00000 0.000000 F( 4, 5) 10.00000 0.000000 F( 4,
79、6) 10.00000 0.000000 F( 4, 7) 10.00000 -1.000000 F( 5, 6) 10.00000 0.000000 F( 5, 8) 30.00000 -1.000000 F( 6, 7) 50.00000 -1.000000 F( 6, 8) 20.00000 -1.000000 F( 7, T) 60.00000 0.000000 F( 8, T) 50.00000 0.000000 该系统的最大流量为 110百万桶 /天，由上面得到的运算结果回答以下问题：（1）炼油厂为1、2、3，要满足这个网络的最大流量，每个炼油厂每天的产量应为 S向炼油厂 1、2、
80、3的输送量，即炼油厂 1、2、3的产量应为 20、75、15百万桶/天。（2）终端为7、8，要满足这个网络的最大流量，每一个终端每天的需求量应为 7、8向T的输送量，即终端 7、8的需求量应为 60、50百万桶/天。（3）泵站为4、5、6，分别计算其每天的汇入总量即可，要满足这个网络的最大流量，泵站 4、5、6的容量应为 30、40、70百万桶 /天。(4)根据题意，只需在源程序中加入泵站6的限制条件最大容量限制为50百万桶即可，在（ 3）的程序中，采用了稀疏集的编写方法。下面精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 35 页，共 42 页的
81、程序编写方法是利用赋权邻接矩阵，这样可以不使用稀疏集的编写方法，写出 Lingo程序并求出最优解：model : sets: nodes/s,1,2,3,4,5,6,7,8,t/; arcs(nodes,nodes):c,f; endsetsdata: c=0; text(fdata.txt)=f; Enddatacalc: c(1,2)=100000; c(1,3)=100000; c(1,4)=100000; c(2,5)=20; c(3,5)=10; c(3,6)=20; c(3,7)=50; c(4,6)=15; c(5,6)=20; c(5,7)=10; c(5,8)=10; c(6
82、,7)=30; c(6,9)=30; c(7,8)=50; c(7,9)=20; c(8,10)=10000; c(9,10)=10000; endcalcn= size (nodes); ! 顶点的个数 ;max=flow;f(3,7)+f(5,7)+f(6,7)=50;for (nodes(i)|i #ne#1 #and# i #ne# n: sum(nodes(j):f(i,j)=sum(nodes(j):f(j,i); sum(nodes(i):f(1,i)=flow; sum(nodes(i):f(i,n)=flow; for (arcs:bnd(0,f,c); end得到如下结果：
83、Global optimal solution found. 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 36 页，共 42 页 Objective value: 90.00000 Infeasibilities: 0.000000 Total solver iterations: 5 Variable Value Reduced Cost N 10.00000 0.000000 FLOW 90.00000 0.000000 F( S, 1) 20.00000 0.000000 F( S, 2) 70.00000 0.000000 F( 1,
84、4) 20.00000 0.000000 F( 2, 4) 10.00000 0.000000 F( 2, 5) 20.00000 0.000000 F( 2, 6) 40.00000 0.000000 F( 4, 5) 10.00000 0.000000 F( 4, 6) 10.00000 0.000000 F( 4, 7) 10.00000 -1.000000 F( 5, 8) 30.00000 -1.000000 F( 6, 7) 50.00000 0.000000 F( 7, T) 60.00000 0.000000 F( 8, T) 30.00000 0.000000 因此，如果泵站
85、 6每天的最大容量限制为 50百万桶，相应的网络的最大容量为每天 90万桶。6.3 加分实验（所得税交纳点选址）所得税管理部门计划对某个地区中的所得税交纳点网络进行重新设精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 37 页，共 42 页计。图 6.2是对此地区内的城市和主要道路的示意图，城市旁边的黑体数字表示城市的居民数目， 单位为千人。 在连接城市之间的弧上标出来它们之间的距离，单位为千米（斜体字）。为覆盖各个城市，所得税管理部门决定在三个城市中设置纳税点。应在哪三个城市中设置纳税点才能够使居民与最近的纳税点之间的平均距离最小？解：精选学习资
86、料 - - - - - - - - - 名师归纳总结 - - - - - - -第 38 页，共 42 页根据题意，假设城市所有居民都会去选择距离城市最近的缴费点进行缴费，仅考虑所设置的缴费点满足居民与最近的缴费点之间的距离和最小.即可看成是有多个起点的最小生成树的求解问题，以所有居民到缴费点的最小距离之和为目标函数， 运用 Lingo 软件进行线性规划，求得最优解。以所有居民到缴费点的最短距离之和为目标函数，以选取的缴费点个数为 3，每个人去最近一个缴费点为约束条件进行线性规划，建立如下的线性规划模型：目标函数：i 11minnnijiijjSP C（1）限制条件为：1211,1,2,312
87、jCijiL（2）1213i1,2,3.,12iix，（3）; ,1,2,.,12. 401, 5016ijjiijCXi jxC（ ）或 （ ）或 （ ）式（1）表示满足所有居民到缴费点的距离之和最小，式中Sij表示从i 地区到 j 地区的距离，Pi表示第 i 个地区的人数， Cij表示是否为选取的缴费路径。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 39 页，共 42 页式（2）表示每个地区选取的缴费路径唯一. 式（3）表示所选取的缴费点数目为4，Xi表示第 i 个地区式（4）表示若未选择 Xj为缴费点则必然不选取Cij路径由下式可知Cij
88、必为 0 式（5）式（6）表示 Xj，Cij只能取 0 或 1，即选取与不选取两种状态首先列出各城市的居民人数： ：城市标号1 2 3 4 5 6 7 8 9 10 11 12 icR（千人）15 10 12 18 5 24 11 16 13 22 19 20 各城市之间的距离如下表所示：城市之间的距离 （Km）1 2 3 4 5 6 7 8 9 10 11 12 1 0 15 37 55 24 60 18 33 48 40 58 67 2 15 0 22 40 38 52 33 48 42 55 61 61 3 37 22 0 18 16 30 43 28 20 58 39 39 4 55
89、40 18 0 34 12 61 46 24 62 43 34 5 24 38 16 34 0 36 27 12 24 49 37 43 6 60 52 30 12 36 0 57 42 12 50 31 22 7 18 33 43 61 27 57 0 15 45 22 40 61 8 33 48 28 46 12 42 15 0 30 37 25 46 9 48 42 20 24 24 12 45 30 0 38 19 19 10 40 55 58 62 49 50 22 37 38 0 19 40 11 58 61 39 43 37 31 40 25 19 19 0 21 12 67 6
90、1 39 34 43 22 61 46 19 40 21 0 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 40 页，共 42 页将上述线性规划模型通过Lingo 软件编程得出最优化解以及相关的数据：model : sets: point/1.12/:p,x; way(point,point):d,c; endsetsdata: d= 0 15 37 45 24 60 18 33 48 40 58 67 15 0 22 40 38 52 33 48 42 55 61 61 37 22 0 18 16 30 43 28 20 58 39 39 45
91、 40 18 0 34 12 61 46 24 62 43 34 24 38 16 34 0 36 27 12 24 49 43 43 60 52 30 12 36 0 57 42 12 50 31 22 18 33 43 61 27 57 0 15 45 22 40 61 33 48 28 46 12 42 15 0 30 37 25 46 48 42 20 24 24 12 45 30 0 38 19 19 40 55 58 62 49 50 22 37 38 0 19 40 58 61 39 43 43 31 40 25 19 19 0 21 67 61 39 34 43 22 61 4
92、6 19 40 21 0; p= 15 10 12 18 5 24 11 16 13 22 19 20; enddatamin =sum(way(i,j):d(i,j)*p(i)*c(i,j); for (point(i):sum(point(j):c(i,j)=1); sum(point:x)=3; for (way(i,j):c(i,j)=x(j); for (way:bin (c); for (point:bin (x); End 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 41 页，共 42 页运行后得到如下结果（只列出有关非零结果）：
93、Global optimal solution found. Objective value: 2438.000 Objective bound: 2438.000 Infeasibilities: 0.000000 Extended solver steps: 0 Total solver iterations: 234 C( 1, 1) 1.000000 0.000000 C( 2, 1) 1.000000 150.0000 C( 3, 6) 1.000000 360.0000 C( 4, 6) 1.000000 216.0000 C( 5, 1) 1.000000 120.0000 C(
94、 6, 6) 1.000000 0.000000 C( 7, 1) 1.000000 198.0000 C( 8, 11) 1.000000 400.0000 C( 9, 6) 1.000000 156.0000 C( 10, 11) 1.000000 418.0000 C( 11, 11) 1.000000 0.000000 C( 12, 11) 1.000000 420.0000 由此，得到了最佳的制定规划方案：即纳税点为城市 1、6、11；城市 1、5、7到1缴税，城市 3、4、6、9到6缴税，城市 8、10、11、12到11缴税；求得最小距离加权和为2438（千米）。此时，居民与最近的纳税点之间平均距离的最小值为：2438/sum(p) 13.1784(Km) 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 42 页，共 42 页
