运筹学实验报告

西华大学能源与环境学院学生上机实验报告西华大学上机实验报告课程名称：运筹学年级/专业：09水利1班实验成绩：指导教师：姓名：实验日期：2011年11月实验名称：图论、动态规划求解学号：实验学时：3一、实验目的掌握网络图的计算机输入，求解最小树、最短路、最大流问题二、实验内容或设计思想首先将欲求的网络用计算机语言表达，再用lingo计算软件求出模型问题的解最小树应用破圈方法求解最大流算法用找流量可增链的方法求解网络最短路运用了动态规划，函数迭代、矩阵运算等的基本原理求解三、实验环境与工具计算机，lingo软件，运筹学软件四、实验过程或实验数据1.最小树问题model:sets:city/1..5/:U;link(city,city):dist,x;endsetsdata:dist=03410999999304654406999999106604999999599999940;enddataN=@size(city);min=@sum(link:dist*x);@for(city(k)|k#gt#1:@sum(city(i)|i#ne#k:x(i,k))=1;@for(city(j)|j#gt#1#and#j#ne#k:U(j)=U(k)+x(k,j)-(n-2)*(1-X(k,j))+(n-3)*x(j,k);););@sum(city(j)|j#gt#1:x(1,j))=1;@for(link:@bin(x););@for(city(k)|k#gt#1:@bnd(1,U(k),999999);U(k)=n-1-(n-2)*x(1,k););end分析过程Globaloptimalsolutionfound.Objectivevalue:16.00000西华大学能源与环境学院学生上机实验报告Extendedsolversteps:0Totalsolveriterations:7VariableValueReducedCostN5.0000000.000000U(1)0.0000000.000000U(2)1.0000000.000000U(3)1.0000000.000000U(4)3.0000000.000000U(5)2.0000000.000000DIST(1,1)0.0000000.000000DIST(1,2)3.0000000.000000DIST(1,3)4.0000000.000000DIST(1,4)10.000000.000000DIST(1,5)999999.00.000000DIST(2,1)3.0000000.000000DIST(2,2)0.0000000.000000DIST(2,3)4.0000000.000000DIST(2,4)6.0000000.000000DIST(2,5)5.0000000.000000DIST(3,1)4.0000000.000000DIST(3,2)4.0000000.000000DIST(3,3)0.0000000.000000DIST(3,4)6.0000000.000000DIST(3,5)999999.00.000000DIST(4,1)10.000000.000000DIST(4,2)6.0000000.000000DIST(4,3)6.0000000.000000DIST(4,4)0.0000000.000000DIST(4,5)4.0000000.000000DIST(5,1)999999.00.000000DIST(5,2)5.0000000.000000DIST(5,3)999999.00.000000DIST(5,4)4.0000000.000000DIST(5,5)0.0000000.000000X(1,1)0.0000000.000000X(1,2)1.0000003.000000X(1,3)1.0000004.000000X(1,4)0.00000010.00000X(1,5)0.000000999999.0X(2,1)0.0000003.000000X(2,2)0.0000000.000000X(2,3)0.0000004.000000X(2,4)0.0000006.000000X(2,5)1.0000005.000000X(3,1)0.0000004.000000X(3,2)0.0000004.000000X(3,3)0.0000000.000000X(3,4)0.0000006.000000X(3,5)0.000000999999.0X(4,1)0.00000010.00000X(4,2)0.0000006.000000X(4,3)0.0000006.000000X(4,4)0.0000000.000000X(4,5)0.0000004.000000X(5,1)0.000000999999.0X(5,2)0.0000005.000000X(5,3)0.000000999999.0X(5,4)1.0000004.000000X(5,5)0.0000000.000000西华大学能源与环境学院学生上机实验报告RowSlackorSurplusDualPrice10.0000000.000000216.00000-1.00000030.0000000.00000043.0000000.00000055.0000000.00000060.0000000.00000070.0000000.00000083.0000000.00000095.0000000.000000104.0000000.000000110.0000000.000000121.0000000.000000131.0000000.000000140.0000000.000000150.0000000.000000160.0000000.000000172.0000000.000000180.0000000.000000191.0000000.000000200.0000000.000000210.0000000.000000221.0000000.000000232.0000000.000000最小支撑树由边（v1，v2），（v1，v3），（v2,v5），（v5,v4）组成，最小支撑树的树长为16.2.最短路问题model:data:n=5;enddatasets:cities/1..n/:F;roads(cities,cities)/1,21,31,52,53,23,54,35,4/:D,P;endsetsdata:D=110443221;enddataF(n)=0;@for(cities(i)|i#lt#n:F(i)=@min(roads(i,j):D(i,j)+F(j)););@for(roads(i,j):P(i,j)=@if(F(i)#eq#D(i,j)+F(j),1,0));西华大学能源与环境学院学生上机实验报告end分析过程Feasiblesolutionfound.Totalsolveriterations:0VariableValueN5.000000F(1)4.000000F(2)4.000000F(3)2.000000F(4)4.000000F(5)0.000000D(1,2)1.000000D(1,3)10.00000D(1,5)4.000000D(2,5)4.000000D(3,2)3.000000D(3,5)2.000000D(4,3)2.000000D(5,4)1.000000P(1,2)0.000000P(1,3)0.000000P(1,5)1.000000P(2,5)1.000000P(3,2)0.000000P(3,5)1.000000P(4,3)1.000000P(5,4)0.000000RowSlackorSurplus10.00000020.00000030.00000040.00000050.00000060.00000070.00000080.00000090.000000100.000000110.000000120.000000130.000000V1到V5的最短路长为4，最短路径为V1到V5V2到V5的最短路长为4，最短路径为V2到V5V3到V5的最短路长为4，最短路径为V3到V5V4到V5的最短路长为4，最短路径为V4到V3到V53.最大流问题model:sets:nodes/1..6/;arcs(nodes,nodes)/1,21,32,32,42,53,54,65,45,66,1/:cap,flow;endsetsmax=flow(6,1);@for(arcs(i,j):flow(i,j)cap(i,j));@for(nodes(i):@sum(arcs(j,i):flow(j,i))=@sum(arcs(i,j):flow(i,j)));data:cap=4,8,2,2,1,5,6,3,7,1000;enddata西华大学能源与环境学院学生上机实验报告end分析过程Globaloptimalsolutionfound.Objectivevalue:8.000000Totalsolveriterations:0VariableValueReducedCostCAP(1,2)4.0000000.000000CAP(1,3)8.0000000.000000CAP(2,3)2.0000000.000000CAP(2,4)2.0000000.000000CAP(2,5)1.0000000.000000CAP(3,5)5.0000000.000000CAP(4,6)6.0000000.000000CAP(5,4)3.0000000.000000CAP(5,6)7.0000000.000000CAP(6,1)1000.0000.000000FLOW(1,2)3.0000000.000000FLOW(1,3)5.0000000.000000FLOW(2,3)0.0000000.000000FLOW(2,4)2.0000000.000000FLOW(2,5)1.0000000.000000FLOW(3,5)5.0000000.000000FLOW(4,6)2.0000000.000000FLOW(5,4)0.0000000.000000FLOW(5,6)6.0000000.000000FLOW(6,1)8.0000000.000000RowSlackorSurplusDualPrice18.0000001.00000021.0000000.00000033.0000000.00000042.0000000.00000050.0000001.00000060.0000001.00000070.0000001.00000084.0000000.00000093.0000000.000000101.0000000.00000011992.00000.000000120.0000001.000000130.0000001.000000140.0000001.000000150.0000000.000000160.0000000.000000170.0000000.000000最大流为v1到v2为3，最大流为v1到v3为5，最大流为v2到v3为0，最大流为v2到v4为2，最大流为v2到v5为1，最大流为v3到v5为5，最大流为v4到v6为2，最大流为v5到v4为0，最大流为v5到v6为6，最大流为v6到v1为83.动态规划model:sets:nodes/a,b1,b2,b3,c1,c2,c3,d1,d2,e/:d;arcs(nodes,nodes)/a,b1a,b2a,b3b1,c1b1,c2b1,c3b2,c1b2,c2b2,c3b3,c1b3,c2b3,c3C1,d1c1,d2c2,d1c2,d2c3,d1c3,d2d1,ed2,e/:w,p;endsetsN=@size(nodes);西华大学能源与环境学院学生上机实