运筹学实验6桂电

桂林电子科技大学运筹学实验报告实验六动态规划辅导员意见：计算机科学与工程学院信息管理与信息系统专业12003401班第实验小组作者黄桂学号1200340119同作者辅导员实验日期2014年12月22日成绩：签名一、实验目的：(1)掌握动态规划原理和数学建模方法；(2)掌握用动态规划、整数规划等来求解最短路径问题、小规模的货郎担问题；(3)掌握用软件来实现动态规划应用求解方法。二、实验类型：综合设计型三、实验内容:用动态规划、整数规划方法来求解小规模的货郎担问题等NP难度问题。（1）最短路线问题。利用动态规划来求解多段图最短路径问题。对如下图所示的一个3段图，图上的数字代表该段路径的成本。现要求求出一条从起点1到汇点7的最短路径，并计算出最短路径成本。答：在LINGO输入以下代码：model:data:n=7;enddatasets:cities/1..n/:F;!7个城市;roads(cities,cities)/1,21,31,42,52,63,53,64,65,76,7/:D,P;endsetsdata:D=1467615821;enddataF(n)=0;@for(cities(i)|i#lt#n:F(i)=@min(roads(i,j):D(i,j)+F(j)););!显然，如果P(i,j)=1,则点i到点n的最短路径的第一步是i--j，否则就不是。由此，我们就可方便的确定出最短路径，P表示的就是路径，为1是被选择的;@for(roads(i,j):P(i,j)=@if(F(i)#eq#D(i,j)+F(j),1,0));End点击solve得到以下运行结果为：根据以上运行结果知，最短路径为：1,3,5,7（2）小规模货郎担问题（TSP）。提法一：有一个推销员，从城市1出发，要遍访城市2，3，…，n各一次，最后返回城市1。已知从城市i到j的旅费为Cij，问他应按怎样的次序访问这些城市，使得总旅费最少？提法二：有一个卖货郎，从城镇1出发，要遍访城镇2，3，…，n各一次，最后返回城镇1。已知从城镇i到j的距离为Dij，问他应按怎样的次序访问这些城镇，使得总路程最短？用动态规划求解以下货郎担问题。已知4个城市间距离如下表所示，求从V1出发，经其余城市一次且仅一次最后返回V1的最短路径与距离。距离城市城市V1V2V3V4V10679V28097V35808V46550答：在LINGO输入以下代码：!货郎担问题;model:sets:city/1..4/:u;link(city,city):dist,!距离矩阵;x;!最后求解的结果矩阵;endsetsn=@size(city);data:!距离矩阵，它并不需要是对称的;dist=0679809758086550;!要解决的问题的数据;enddata!目标函数;min=@sum(link:dist*x);@FOR(city(K):!进入城市K;@sum(city(I)|I#ne#K:x(I,K))=1;!离开城市K;@sum(city(J)|J#ne#K:x(K,J))=1;);!保证不出现子圈;@for(city(I)|I#gt#1:@for(city(J)|J#gt#1#and#I#ne#J:u(I)-u(J)+n*x(I,J)=n-1););!限制u的范围以加速模型的求解，保证所加限制并不排除掉TSP问题的最优解;@for(city(I)|I#gt#1:u(I)=n-2);!定义X为0\1变量;@for(link:@bin(x));end点击solve得到以下界面为：最短路径为1，2，4，3