4.图论(组合优化)实验解读.pdf

4.图论(组合优化)实验解读工程数学 4.图论(组合优化)实验Gxxxxxxxxxxxxxxx xxxxxx工程数学Gxxxxxxxxx xxxxxxE-mail:xxxxxxxxxxxxxxx Tel:xxxxxxxxxx4数学建模基础：4.1.实验目的与要求学会用图论（组合优化）的方法或思想建模学会 LINGO 软件求解组合优化问题成立相应的数学模型，并对计算结果进行剖析议论4.2.基本实验4.2.1.设施更新问题某企业需要对一台已经使用了2 年的机器确立此后4 年（n=4）的最优更新策略。企业要求，用了年的机器一定更新，购置一台新机器的价钱是100 万元，表4.1 给出了该问题的数据，请给出设施的更新策略。解：1/4564.图论(组合优化)实验解读工程数学4.图论(组合优化)实验Gxxxxxxxxxxxxxxxxxxxxx用图论知识来理解本题。设用A,B 表示决议年度，用数字表示机龄，所以，第1 年决议的节点就是 A2，第 2 年只有两种可能，就是 B3（第 1 年不更新）或 B1(第 1 年更新)，以此类推。则得出 Lingo 的程序：sets:nodes/A2,B3,B1,C4,C2,C1,D5,D3,D2,D1,E6,arcs(nodes,nodes)/A2,B3A2,B1B3,C4B3,C1B1,C2B1,C1C4,D5C4,D1C2,D3C2,D1C1,D2D5,E1D5,E6D3,E4D3,E1D2,E3E6,FE4,FE3,FE2,FE1,F/:c,x;endsetsdata:17.3 530506080;enddatan=size(nodes);2/45C1,D1D2,E1D1,E2 D1,E14.图论(组合优化)实验解读工程数学4.图论(组合优化)实验Gxxxxxxxxxxxxxxxxxxxxxmax =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)|i#eq#n:x(j,i)=1;for(arcs:bin(x);则得出程序运转结果：(取非零的 x 结果)sum(arcs(j,i):x(j,i)=0剖析结果：A2-B3-C4-D5-E1-F，得悉设施应当是使用5 年后再更新设施，为最优更新策略。4.2.2.运输问题有甲、乙和丙三个城市，每年分别需要煤炭供给。已知煤矿年产量320 万吨、250 万吨和 350 万吨，由A,B 两个煤矿负责4.2 所示。因为需A 为 400 万吨，B 为 450 万吨，从两煤矿至各城市煤炭运价如表求大于供给，经磋商均衡，甲城市在必需时可少供给0-30 万吨，乙城市需求量须所有知足，丙城市需求量3/454.图论(组合优化)实验解读工程数学4.图论(组合优化)实验Gxxxxxxxxxxxxxxxxxxxxx许多于 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):SUPsum (To(j):x(i,j)=Demand(!Here are the parameters;data:Capacity=400,450;Demand=320,250,380;D=15,18,22,21,25,16;4/45j);4.图论(组合优化)实验解读工程数学4.图论(组合优化)实验GxxxxxxxxxxxxxxxxxxxxxEnddata程序运转结果以下：（1）甲ABC运量1521M290甲1521030乙1925M250丙2216M270丙2216080销量40045070（2）5/454.图论(组合优化)实验解读工程数学4.图论(组合优化)实验Gxxxxxxxxxxxxxxxxxxxxx甲甲乙丙丙销量ABC产量1521M290211521030211825M250242216M2701622160801640045070-60-16（3）甲ABC运量1521M290甲1521030乙1925M250丙2216M270丙2216080销量40045070（4）甲甲乙丙丙销量ABC产量1521M2902115213030161825M250242216M2701622160801640045070-60-16结论：调整后最优方案的最低花费：150*15+250*18+140*21+270*16+40*16+30*0+40*0=14650万元6/454.图论(组合优化)实验解读工程数学4.图论(组合优化)实验Gxxxxxxxxxxxxxxxxxxxxx4.2.3.生产计划与库存管理(1)某企业生产一种除臭剂，它在1 至 4 季度的生产成本、生产量及订货量表4.3 所示。假如除臭剂在生产当季没有交货，保存在库房里除臭剂每盒每季度还需不足，则同意缓期交货，缓期交货的罚金是每盒每季度1 元钱的储藏花费。假如某个季度的货物供给量3 元。请企业希望拟订一个成本最低(包含储藏花费和罚金)的除臭剂的生产计划，问各季度应生产多少?(2)假如产品不同意缓期交货，则企业考虑工人加班，已知加班生产出产品的成本要比原成本超出且每季度加班最多生产20%，2 万盒。问：在这类状况下，将怎样安排生产，使总成本最少?解：(1)设第一季度、第二季度、第三季度、第四时度生产量分别为a、b、c、d，a1 为第一季度后节余量，b1 为第二季度后节余量，c1 为第三季度后节余量，d1 为第四时度后的节余量。每季度的生产的除臭剂应当小于等于最大产量，大于等于订货量，第一个季度认为的季度中实质货物量应当等于上月的节余量加该月的产量，以此类推，能够得出；LINGO的程序：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程序运转结果以下：Gxxxxxxxxxxxxxxxxxxxxx8/454.图论(组合优化)实验解读工程数学4.图论(组合优化)实验Gxxxxxxxxxxxxxxxxxxxxx第一个季度应生产14 万盒，第二季度应当生产15 万盒，第三季度应当生产15 万盒，第四时度应当生产8 万盒除臭剂。最低花费为288 万元。（2）第 1 季度加班生产的产品为y1 盒，y2 盒，y3 盒，y3 盒，第 2 季度加班生产的产品为第 3 季度加班生产的产品为第 4 季度加班生产的产品为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+y3+d+y4=52;9/454.图论(组合优化)实验解读工程数学4.图论(组合优化)实验Gxxxxxxxxxxxxxxxxxxxxxa=10;b=24;c=44;d=13;EndLingo程序运转结果：Lingo运转结果可得：安排生产：第一季度正常生产13 万盒，不加班生产；第二季度正常生产15 万，加班生产1 万10/454.图论(组合优化)实验解读工程数学4.图论(组合优化)实验15 万，不加班生产；第四时度生产Gxxxxxxxxxxxxxxxxxxxxx盒；第三季度正常生产8 万盒，不加班生产。总成本最少为292 万元。4.2.4.指派问题某企业需要把4 项工作派给4 名工人，每名工人达成每项工作的花费如表工作 C，丙不可以达成工作D。4.4 所示，此中甲不可以达成（1）确立每名工人达成工作的最优方案；（2）假定有此外一名工人（戊）能达成这4 项工作，达成每项工作相应花费分别为60、45、30 和 80 元。能否用这名新工人（戊）替代本来的某位工人？（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;endsets11/454.图论(组合优化)实验解读工程数学4.图论(组合优化)实验Gxxxxxxxxxxxxxxxxxxxxxdata:c=5050999207040203090305099970206070enddatamin =sum(Assign:c*x);for(Flight(i):sum(Flight(j):x(i,j)=1;sum(Flight(j):x(j,i)=1;);Lingo 程序运转得：;12/454.图论(组合优化)实验解读工程数学4.图论(组合优化)实验Gxxxxxxxxxxxxxxxxxxxxx最优方案：甲达成工作D，乙达成 C，丙达成B，丁达成A。总花费为 140 元B 任务）。（2）依据题意增添一个工人（戊），设替代丙方案（且丁达成Lingo的程序：sets:13/454.图论(组合优化)实验解读工程数学4.图论(组合优化)实验Flight/1.5/;Assign(Flight,Flight):c,x;endsetsdata:c=505099920 99970402030 999903050999 9997020607099960453080999;enddatamin =sum(Assign:c*x);for(Flight(i):sum(Flight(j):x(i,j)=1;sum(Flight(j):x(j,i)=1;);Lingo 程序运转得：Gxxxxxxxxxxxxxxxxxxxxx14/454.图论(组合优化)实验解读工程数学4.图论(组合优化)实验Gxxxxxxxxxxxxxxxxxxxxx15/454.图论(组合优化)实验解读工程数学4.图论(组合优化)实验结论：1119-999=120,花费减少B，戊达成A。（3）Lingo 的程序：sets:Flight/1.5/;Assign(Flight,Flight):c,x;endsetsdata:c=5050999 20207040203010903050999207020607080999 999 999 999999enddataGxxxxxxxxxxxxxxxxxxxxx120元。甲达成 D，乙达成 C，丙达成5（去掉），丁达成16/45;4.图论(组合优化)实验解读工程数学4.图论(组合优化)实验Gxxxxxxxxxxxxxxxxxxxxxmin =sum(Assign:c*x);for(Flight(i):sum(Flight(j):x(i,j)=1;sum(Flight(j):x(j,i)=1;);Lingo 程序运转得：17/454.图论(组合优化)实验解读工程数学4.图论(组合优化)实验Gxxxxxxxxxxxxxxxxxxxxx结论：1079-999=80，甲达成D，乙达成C，丙达成E，丁达成 B，即 E 比 A 优先4.2.5.旅游商问题张三住在 A 市，他在 A,B,C,D,E 和 F 市都有保险代理业务市作一次。表.因为业务关系，他每个月都需要接见这些城4.5 给出了每个城市之间的距离，试剖析他依据什么的次序接见这些城市使得总旅游的距离最短?（1）用启迪式算法求解；（2）用 LINGO软件求解。解：（1）用启迪式算法求解18/454.图论(组合优化)实验解读工程数学4.图论(组合优化)实验由题意得悉，以下几条最为便利的路径：A-B-C-D-E-F-A行程=588+129+483+1288+440+825=3753A-B-C-D-F-E-A行程=588+129+483+1100+440+1096=3836A-B-C-E-F-D-A行程=588+129+1638+440+1100+334=4229A-B-C-E-D-F-A行程=588+129+1638+1288+1100+825=5568A-B-D-C-E-F-A行程=588+448+483+1638+440+825=4422A-B-D-C-F-E-A行程=588+448+483+1346+440+1096=4401A-B-D-E-C-F-A行程=588+448+1288+1638+1364+825=6151A-B-D-E-F-C-A行程=588+448+1288+440+1364+542=4670A-B-D-F-C-E-A行程=588+448+1100+1346+1638+1096=6234A-B-D-F-E-C-A行程=588+448+1100+440+1638+542=4756A-C-B-D-E-F-A19/45Gxxxxxxxxxxxxxxxxxxxxx公里；公里；公里；公里；公里；公里；公里；公里；公里；公里；4.图论(组合优化)实验解读工程数学4.图论(组合优化)实验行程=542+129+448+1288+440+825=3672A-C-B-D-F-E-A行程=542+129+448+1100+440+1096=3755A-C-B-E-D-F-A行程=542+129+1675+1288+1100+825=5559A-C-B-E-F-D-A行程=542+129+1675+440+1100+825=4711A-C-B-F-D-E-A行程=542+129+1410+1100+1288+1096=5565A-C-B-F-E-D-A行程=542+129+1410+440+1288+334=4143A-C-D-B-E-F-A行程=542+483+448+1675+440+825=4413A-C-D-B-F-E-A行程=542+483+448+1410+440+1096=4419A-C-D-E-B-F-A行程=542+483+1288+1675+1410+825=6223（2）用 LINGO 软件求解LINGO的程序：sets:city/A,B,C,D,E,F/:u;link(city,city):w,x;20/45Gxxxxxxxxxxxxxxxxxxxxx公里；公里；公里；公里；公里；公里；公里；公里；公里；4.图论(组合优化)实验解读工程数学4.图论(组合优化)实验endsetsdata:w=0,588,542,334,1096,825588,0,129,448,1675,1410542,129,0,483,1638,1346334,448,483,0,1288,11001096,1675,1638,1288,0,440825,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(link(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);程序运转结果以下：Gxxxxxxxxxxxxxxxxxxxxx21/454.图论(组合优化)实验解读工程数学4.图论(组合优化)实验Gxxxxxxxxxxxxxxxxxxxxx22/454.图论(组合优化)实验解读工程数学4.图论(组合优化)实验Gxxxxxxxxxxxxxxxxxxxxx23/454.图论(组合优化)实验解读工程数学4.图论(组合优化)实验Gxxxxxxxxxxxxxxxxxxxxx从答案可知：最短距离为A C B D E F A 最短距离3672。4.2.6.最优连线问题求 5 题中 6 个城市（A,B,C,D,E，F）的最优连线，城市之间的距离如表4.5 所示。解：sets:city/ABCD EF/:u;link(city,city):w,x;endsetsdata:!to:Aw=0B588C5421290483DEF;33444848301096825!from A;16751410!from B;16381346!from C;12881100!from D;588054212933444824/454.图论(组合优化)实验解读工程数学4.图论(组合优化)实验1096 1675825 1410163813461288 01100 440440 !from E;0;!from F;Gxxxxxxxxxxxxxxxxxxxxxenddatan=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(link(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);程序运转结果以下：25/454.图论(组合优化)实验解读工程数学4.图论(组合优化)实验Gxxxxxxxxxxxxxxxxxxxxx26/454.图论(组合优化)实验解读工程数学4.图论(组合优化)实验Gxxxxxxxxxxxxxxxxxxxxx27/454.图论(组合优化)实验解读工程数学4.图论(组合优化)实验Gxxxxxxxxxxxxxxxxxxxxx最优连线ACBDEFA4.2.7.最大流问题三个炼油厂经过管道网络为两个分别的终端运送汽油。这个管道网络中有三个泵站，如图所示。:汽油的流向如图中箭头所示，图中标出了每一段管道的运送容量，单位是百万桶(1)要知足这个网络的最大流量，每一个炼油厂每日的产量应当是多少；(2)要知足这个网络的最大流量，每一个终端每日的需求量应当是多少；(3)要知足这个网络的最大流量，每个泵站每日的容量应当是多少；/天。求解下边的问题28/454.图论(组合优化)实验解读工程数学4.图论(组合优化)实验Gxxxxxxxxxxxxxxxxxxxxx(4)假如进一步假定在图4.1 所示的网络中泵站6 每日的最大容量限制为50 百万桶，求出相应的网络解：由题已知条件令为从 i 到 j 的流量LINGO 的程序：Model:max=x47+x67+x68+x58;x14=20;x24=10;x26=50;x25=20;x35=15;x47=10;x46=10;29/45的最大容量。4.图论(组合优化)实验解读工程数学4.图论(组合优化)实验x45=20;x56=30;x58=30;x67=50;x68=x45+x46+x47;x35+x25x+x45=x58+x56;x26+x46+x56=x67+x68;end程序运转结果以下：Gxxxxxxxxxxxxxxxxxxxxx30/454.图论(组合优化)实验解读工程数学4.图论(组合优化)实验Gxxxxxxxxxxxxxxxxxxxxx（1）x14=20，炼油 1 产量为 20百万桶/天；x24=10，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，泵站，X56=10，泵站6 容量为70 百万桶/天。5 容量为 40 百万桶/天；X26=50，X46=10（4）LINGO 的程序：Model:max=x47+x67+x68+x58;31/454.图论(组合优化)实验解读工程数学4.图论(组合优化)实验x14=20;x24=10;x26=50;x25=20;x35=15;x47=10;x46=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程序运转结果以下：Gxxxxxxxxxxxxxxxxxxxxx32/454.图论(组合优化)实验解读工程数学4.图论(组合优化)实验Gxxxxxxxxxxxxxxxxxxxxx结论：X47=20，X24=10，泵站4 的容量为30 百万桶/天；X25=20，X35=15，X45=0，泵站 5的容量为35 百万桶/天；X26=40，X46=10，X56=0，泵站6 的容量为50 百万桶/天。33/454.图论(组合优化)实验解读工程数学4.图论(组合优化)实验Gxxxxxxxxxxxxxxxxxxxxx4.3.加分实验所得税管理部门计划对某个地域中的所得税缴纳点网络进行从头设计。图4.2 是对此地域内的城市和主要道路的表示图，城市旁边的黑体数字表示城市的居民数量，单位为千人。在连结城市之间的弧上标出了它们之间的距离，单位为千米(斜体字)。为覆盖各个城市，所得税管理部门决定在三个城市中设置纳税点。应在哪三个城市中设置纳税点才能够使居民与近来的纳税点之间均匀距离最小？解：LINGO 的程序：MODEL:sets:point/1.12/:p,x;way(point,point):d,c;endsetsdata:d=0 15 37 55 24 60 18 33 48 40 58 6734/454.图论(组合优化)实验解读工程数学4.图论(组合优化)实验4055586249502237380194067 61 39 34 43 22 61 46 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程序运转结果以下：Gxxxxxxxxxxxxxxxxxxxxx35/454.图论(组合优化)实验解读工程数学4.图论(组合优化)实验Gxxxxxxxxxxxxxxxxxxxxx36/454.图论(组合优化)实验解读工程数学4.图论(组合优化)实验Gxxxxxxxxxxxxxxxxxxxxx37/454.图论(组合优化)实验解读工程数学4.图论(组合优化)实验Gxxxxxxxxxxxxxxxxxxxxx38/454.图论(组合优化)实验解读工程数学4.图论(组合优化)实验Gxxxxxxxxxxxxxxxxxxxxx39/454.图论(组合优化)实验解读工程数学4.图论(组合优化)实验Gxxxxxxxxxxxxxxxxxxxxx40/454.图论(组合优化)实验解读工程数学4.图论(组合优化)实验Gxxxxxxxxxxxxxxxxxxxxx41/454.图论(组合优化)实验解读工程数学4.图论(组合优化)实验Gxxxxxxxxxxxxxxxxxxxxx42/454.图论(组合优化)实验解读工程数学4.图论(组合优化)实验Gxxxxxxxxxxxxxxxxxxxxx43/454.图论(组合优化)实验解读工程数学4.图论(组合优化)实验Gxxxxxxxxxxxxxxxxxxxxx结论：人数、距离之和为2438，那么在，6，11 设置纳税点最正确，此时：城市1，2，5，7 去44/4514.图论(组合优化)实验解读工程数学4.图论(组合优化)实验Gxxxxxxxxxxxxxxxxxxxxx城市 1；城市 3，4，6，9 去城市 6；城市 8，10，11，12 去城市 11。45/45