资源描述：
《实验二图论、动态规划求解》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、西华大学上机实验报告课程名称：运筹学年级传业：实验成绩：指导教师：施浩然姓名：实验日期：2013年10月实验名称：图论、动态规划求解学号：实验学时：2一、实验目的掌握网络图的计算机输入，求解最小树、最短路、最大流问题二、实验内容或设计思想首先将欲求的网络用计算机语言表达，再用lin知计算软件求出模型问题的解。最小树应用破圈方法求解最人流算法用找流量可增链的方法求解网络最短路运用了动态规划，函数迭代、矩阵运算筹的基木原理求解三、实验环境与工具计算机,lingo软件四、实验过程或实验数据最小树问题给定5个点，各点之间的距离如下程序所示。试用
2、LINGO软件解最小树问题。link(city,city):distzx;endsetsdata:dist=337999999999999999999999999460459999996750;enddaN=@size(city);min=@sum(link:dist*x);@for(city(k)
3、k#gt#l:@sum(city(i)Ii#ne#k:x(iAk))=1;@for(city(j)Ij#gt#l#and#j#ne#k:U(j)〉=U(K)+x(k,j)-(n-2)*(l-x(kzj))+(n-3)*x(jzk)；)；);
4、@sum(city(j)
5、j#gt#l:x(1,j))>=1;or(link:@bin(x););@for(city(k)
6、k#gt#l:@bnd(lzU(k)『999999);U(k)<=n-l-(n-2)*x(lzk););End在LINGO使用SOLVE命令求解如下：Globaloptimalsolutionfound.Objectivevalue:19.00000Objectivebound:19.00000Infeasibilities:0.0000000■/Extendedsolversteps:Totalsolverite
7、rations:VariableValue5.0000000.0000001.0000001.0000002.0000002.000000ReducedCost0.0000000.0000000.0000000.0000000.0000000.000000NU(1)U(2)U(3)U(4)U(5)DIST(1,1)3.0000000.000000DIST(1,2)5.0000000.000000DIST(lz3)3.0000000.000000DIST(lz4)999999.00.000000DIST(1,5)999999.00.000
8、000DIST(2,1)3.0000000.000000DIST(2,2)7.0000000.000000DIST(2,3)5.0000000.000000DIST(2,4)4.0000000.000000DIST(2,5)999999.00.000000DIST(3,1)9.0000000.000000DIST(3,2)6.0000000.000000DIST(3,3)0.0000000.000000DIST(3,4)6.0000000.000000DIST(3,5)7.0000000.000000DIST(4,1)999999.00
9、.000000DIST(4,2)4.0000000.000000DIST(4,3)6.0000000.000000DIST(4,4)0.0000000.000000DIST(4,5)45.000000.000000DIST(5,1)999999.00.000000DIST(5,2)6.0000000.000000DIST(5,3)7.0000000.000000DIST(5,4)5.0000000.000000DIST(5,5)0.0000000.000000X(1,1)0.0000003.000000x(1,2)1.0000005.0
10、00000X(1,3)1.0000003.000000X(1a4)0.000000999999.0X(1<5)0.000000999999.0X(2,1)0.0000003.000000x(2,2)0.0000007.000000X(2,3)0.0000005.000000X(2,4)1.0000004.000000X(2<5)0.000000999999.0x(3,1)0.0000009.000000X(3,2)0.0000006.000000X(3,3)0.0000000.000000X(3,4)0.0000006.000000X(
11、3,5)1.0000007.000000X(4,1)0.000000999999.0x(4,2)0.0000004.000000x(4,3)0.0000006.000000X(4,4)0.0000000.0
