图论(组合优化)实验

1、工程数学 4.图论(组合优化)实验 Gxxxxxxxxxxxxxxx xxxxxx工程数学Gxxxxxxxxx xxxxxxE-mail: xxxxxxxxxxxxxxx Tel: xxxxxxxxxx4 数学建模基础：1.2.3.4.4.1. 实验目的与要求l 学会用图论（组合优化）的方法或思想建模l 学会LINGO软件求解组合优化问题l 建立相应的数学模型，并对计算结果进行分析讨论4.2. 基本实验4.2.1. 设备更新问题某公司需要对一台已经使用了2年的机器确定今后4年（n=4）的最优更新策略。公司要求，用了6年的机器必须更新，购买一台新机器的价格是100万元，表4.1给出了该问题的数据

2、，请给出设备的更新策略。解：用图论知识来理解此题。设用A,B表示决策年度，用数字表示机龄，因此，第1年决策的节点就是A2，第2年只有两种可能，就是B3（第1年不更新）或B1(第1年更新)，以此类推。则得出Lingo的程序：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,E

3、1 D2,E3 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);则得出程序运行结果：(取非零的x结果)分析结果：A2-B3-C4-D5-E1-F，得知设备应该是使用5年后再更新设备，为最优更新策略。4.2.2. 运输问题有甲、乙和丙三个城市，每年分别需要煤炭320万吨、250万吨和350万吨，由A, B两个煤矿负责供应。已知煤矿年产量A为400万吨，B为450万吨，从两煤矿至各城市煤炭运价如表4.2所示。由于需求大于

5、供应，经协商平衡，甲城市在必要时可少供应0-30万吨，乙城市需求量须全部满足，丙城市需求量不少于270万吨。试求将甲、乙两矿煤炭全部分配出去，满足上述条件又使总运费最低的调运方案。解：sets: From / A, B/: Capacity; To / C1, C2, C3/: Demand; Routes( From, To): D, x;endsets! The objective;OBJ min = sum(Routes: D * x);! The supply constraints;for (From(i): SUP sum (To(j): x(i,j) = Demand(j);!

6、Here are the parameters;data: Capacity = 400, 450 ; Demand = 320, 250, 380 ; D = 15, 18, 22, 21, 25, 16;Enddata程序运行结果如下：（1）甲甲乙丙丙销量A1515192222400B2121251616450CM0MM070运量2903025027080（2）甲甲乙丙丙销量VjA1515182222400-6B21212516164500CM0MM070-16产量2903025027080Ui2121241616（3）甲甲乙丙丙销量A1515192222400B2121251616450

7、CM0MM070运量2903025027080（4）甲甲乙丙丙销量VjA1515182222400-6B21212516164500CM30MM070-16产量2903025027080Ui2116241616结论：调整后最优方案的最低费用：150*15+250*18+140*21+270*16+40*16+30*0+40*0=14650万元4.2.3. 生产计划与库存管理(1)某公司生产一种除臭剂，它在1至4季度的生产成本、生产量及订货量表4.3所示。如果除臭剂在生产当季没有交货，保管在仓库里除臭剂每盒每季度还需1元钱的储存费用。如果某个季度的货物供应量不足，则允许延期交货，延期交货的罚金是

8、每盒每季度3元。请公司希望制定一个成本最低(包括储存费用和罚金)的除臭剂的生产计划，问各季度应生产多少?(2)如果产品不允许延期交货，则公司考虑工人加班，已知加班生产出产品的成本要比原成本高出20%，且每季度加班最多生产2万盒。问：在这种情况下，将如何安排生产，使总成本最少?解：(1) 设第一季度、第二季度、第三季度、第四季度生产量分别为a、b、c、d，a1为第一季度后剩余量，b1为第二季度后剩余量，c1为第三季度后剩余量，d1为第四季度后的剩余量。每季度的生产的除臭剂应该小于等于最大产量，大于等于订货量，第一个季度以为的季度中实际货物量应该等于上月的剩余量加该月的产量，以此类推，可以得出；L

9、INGO的程序：model:min=5*a+5*b+6*c+6*d+ya1+b1+c1+d1;a=10;a=14;b=20;c=8;d=13;d1=d+c1-8;end程序运行结果如下：第一个季度应生产14万盒，第二季度应该生产15万盒，第三季度应该生产15万盒，第四季度应该生产8万盒除臭剂。最低费用为288万元。（2）第1季度加班生产的产品为y1盒，第2季度加班生产的产品为y2盒，第3季度加班生产的产品为y3盒，第4季度加班生产的产品为y3盒，LINGO的程序：Model:min=8*a+9*y1+7*b+8*y2+7*c+8.2*y3+6*d+7.2*y4-78;a+y1+b+y2+c+y

10、3+d+y4=52;a=10;b=24;c=44;d=13;End Lingo程序运行结果：Lingo运行结果可得：安排生产：第一季度正常生产13万盒，不加班生产；第二季度正常生产15万，加班生产1万盒；第三季度正常生产15万，不加班生产；第四季度生产8万盒，不加班生产。总成本最少为292万元。4.2.4. 指派问题某公司需要把4项工作派给4名工人，每名工人完成每项工作的费用如表4.4所示，其中甲不能完成工作C，丙不能完成工作D。（1）确定每名工人完成工作的最优方案；（2）假设有另外一名工人（戊）能完成这4项工作，完成每项工作相应费用分别为60、45、30和80元。是否用这名新工人（戊）替换原

11、来的某位工人？（3）假设公司有了第5项工作（E），4名工人（甲、乙、丙、丁）完成工作E的费用分别为20、10、20和80元。这项新工作E比原有的四项工作（A，B，C，D）的某一项优先吗？解：根据题意分析方案。利用lingo的程序(不可能任务设成999，求min)sets: Flight/1.4/; Assign(Flight, Flight): c, x;endsetsdata: c = 50 50 999 20 70 40 20 30 90 30 50 999 70 20 60 70 ;enddatamin = sum(Assign: c*x);for(Flight(i): sum(Flig

12、ht(j): x(i,j) = 1; sum(Flight(j): x(j,i) = 1;);Lingo程序运行得： 最优方案：甲完成工作D， 乙完成C，丙完成B，丁完成A。总费用为140元（2） 根据题意增加一个工人（戊），设替换丙方案（且丁完成B任务）。Lingo的程序：sets: Flight/1.5/; Assign(Flight, Flight): c, x;endsetsdata: c = 50 50 999 20 999 70 40 20 30 999 90 30 50 999 999 70 20 60 70 999 60 45 30 80 999;enddatamin = su

13、m(Assign: c*x);for(Flight(i): sum(Flight(j): x(i,j) = 1; sum(Flight(j): x(j,i) = 1;); Lingo程序运行得： 结论：1119-999=120, 费用减少120元。甲完成D，乙完成C，丙完成5（去掉），丁完成B，戊完成A。（3）Lingo的程序：sets: Flight/1.5/; Assign(Flight, Flight): c, x;endsetsdata: c = 50 50 999 20 20 70 40 20 30 10 90 30 50 999 20 70 20 60 70 80 999 999

14、999 999 999 ;enddatamin = sum(Assign: c*x);for(Flight(i): sum(Flight(j): x(i,j) = 1; sum(Flight(j): x(j,i) = 1;);Lingo程序运行得： 结论：1079-999=80，甲完成D，乙完成C，丙完成E，丁完成B， 即E比A优先4.2.5. 旅行商问题张三住在A市，他在A, B, C,D,E和F市都有保险代理业务.由于业务关系，他每个月都需要访问这些城市作一次。表4.5给出了每个城市之间的距离，试分析他按照什么的顺序访问这些城市使得总旅行的距离最短?（1）用启发式算法求解； （2）用LIN

15、GO软件求解。解：（1）用启发式算法求解由题意得知，以下几条最为便捷的路径：A- B- C- D- E- F- A路程s1=588+129+483+1288+440+825=3753公里；A- B- C- D- F- E- A路程s2=588+129+483+1100+440+1096=3836公里；A- B- C- E- F- D- A路程s3=588+129+1638+440+1100+334=4229公里；A- B- C- E- D- F- A路程s4=588+129+1638+1288+1100+825=5568公里；A- B- D- C- E- F- A路程s5=588+448+48

16、3+1638+440+825=4422公里；A- B- D- C- F- E- A路程s6=588+448+483+1346+440+1096=4401公里；A- B- D- E- C- F- A路程s7=588+448+1288+1638+1364+825=6151公里；A- B- D- E- F- C- A路程s8=588+448+1288+440+1364+542=4670公里；A- B- D- F- C- E- A路程s9=588+448+1100+1346+1638+1096=6234公里；A- B- D- F- E- C- A路程s10=588+448+1100+440+1638+

17、542=4756公里；A- C- B- D- E- F- A路程s11=542+129+448+1288+440+825=3672公里；A- C- B- D- F- E- A路程s12=542+129+448+1100+440+1096=3755公里；A- C- B- E- D- F- A路程s13=542+129+1675+1288+1100+825=5559公里；A- C- B- E- F- D- A路程s14=542+129+1675+440+1100+825=4711公里；A- C- B- F- D- E- A路程s15=542+129+1410+1100+1288+1096=5565

18、公里；A- C- B- F- E- D- A路程s16=542+129+1410+440+1288+334=4143公里；A- C- D- B- E- F- A路程s17=542+483+448+1675+440+825=4413公里；A- C- D- B- F- E- A路程s18=542+483+448+1410+440+1096=4419公里；A- C- D- E- B- F- A路程s19=542+483+1288+1675+1410+825=6223公里；（2）用LINGO软件求解LINGO的程序：sets: city/A,B,C,D,E,F/: u; link(city, city

19、): w, x;endsetsdata: w =0,588,542,334,1096,825 588,0,129,448,1675,1410 542,129,0,483,1638,1346 334,448,483,0,1288,1100 1096,1675,1638,1288,0,440 825,1410,1346,1100,440,0; enddatan=size(city);min = sum(link: w * x);for(city(k): sum(city(i)| i #ne# k: x(i,k)=1; sum(city(j)| j #ne# k: x(k,j)=1;);for(li

20、nk(i,j)| i #gt# 1 #and# j #gt# 1 #and# i #ne# j: u(i)-u(j)+n*x(i,j)=n-1;);for(link: bin(x);程序运行结果如下：从答案可知：最短距离为ACBDEFA最短距离3672。4.2.6. 最优连线问题求5题中6个城市（A, B, C,D,E，F）的最优连线，城市之间的距离如表4.5所示。解：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

21、 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;!from F;enddatan=size(city);min = sum(link: w * x);for(city(k): sum(city(i)| i #ne# k: x(i,k)=1; sum(city(j)| j #ne# k: x(k,j)=1; );for(l

22、ink(i,j)|i #gt# 1 #and# j #gt# 1 #and# i #ne# j: u(i)-u(j)+n*x(i,j)=n-1;);for(link: bin(x);程序运行结果如下：最优连线ACBDEFA4.2.7. 最大流问题 三个炼油厂通过管道网络为两个分散的终端运送汽油。这个管道网络中有三个泵站，如图4.1所示。汽油的流向如图中箭头所示，图中标出了每一段管道的运送容量，单位是百万桶/天。求解下面的问题: (1)要满足这个网络的最大流量，每一个炼油厂每天的产量应该是多少； (2)要满足这个网络的最大流量，每一个终端每天的需求量应该是多少； (3)要满足这个网络的最大流量，

23、每个泵站每天的容量应该是多少；(4)如果进一步假定在图4.1所示的网络中泵站6每天的最大容量限制为50百万桶，求出相应的网络的最大容量。解：由题已知条件令xij为从i到j的流量LINGO的程序：Model:max=x47+x67+x68+x58;x14=20;x24=10;x26=50;x25=20;x35=15;x47=10;x46=10;x45=20;x56=30;x58=30;x67=50;x68=x45+x46+x47;x35+x25x+x45=x58+x56;x26+x46+x56=x67+x68;end程序运行结果如下：（1）x14=20，炼油1产量为20百万桶/天；x24=10，

24、x25=20， x26=50，炼油厂2的产量为80百万桶/天；X35=15，炼油厂3的产量为1百万桶/天。（2）X47=10，X67=50，终端7需求量为60百万桶/天；X58=30，X68=20，终端8需求量为50百万桶/天。（3）X47=20，X24=10时，泵站4容量为30百万桶/天；X25=20，X35=15， X45=5，泵站5容量为40百万桶/天；X26=50， X46=10， X56=10，泵站6容量为70百万桶/天。（4）LINGO的程序：Model:max=x47+x67+x68+x58;x14=20;x24=10;x26=50;x25=20;x35=15;x47=10;x4

25、6=10;x45=20;x56=30;x58=30;x67=50;x68=x45+x46x+x47;x35+x25x45=x58+x56;x26+x46x+x56=x67+x68;x26+x46+x56=50;end程序运行结果如下：结论：X47=20，X24=10，泵站4的容量为30百万桶/天；X25=20， X35=15， X45=0，泵站5的容量为35百万桶/天；X26=40，X46=10，X56=0，泵站6的容量为50百万桶/天。4.3. 加分实验 所得税管理部门计划对某个地区中的所得税交纳点网络进行重新设计。图4.2是对此地区内的城市和主要道路的示意图，城市旁边的黑体数字表示城市的居民数目，单位为千人。在连接城市之间的弧上标出了它们之间的距离，单位为千米(斜体字)。为