运筹学实验报告

1、精选优质文档-倾情为你奉上西华大学上机实验报告课程名称：运筹学年级/专业：09水利1班实验成绩：指导教师：姓名：实验日期：2011年11月实验名称：图论、动态规划求解学号：实验学时： 3一、实验目的 掌握网络图的计算机输入，求解最小树、最短路、最大流问题二、实验内容或设计思想首先将欲求的网络用计算机语言表达，再用lingo计算软件求出模型问题的解最小树应用破圈方法求解最大流算法用找流量可增链的方法求解网络最短路运用了动态规划，函数迭代、矩阵运算等的基本原理求解三、实验环境与工具 计算机，lingo软件，运筹学软件四、实验过程或实验数据1.最小树问题model:sets:city/1. 5/:U

2、;link(city,city):dist,x;endsetsdata:dist=0 3 4 10 3 0 4 6 5 4 4 0 6 10 6 6 0 4 5 4 0;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)

3、| j#gt#1: x(1,j)>=1;for (link: bin (x););for (city (k) | k#gt#1:bnd (1,U(k),);U(k)<=n-1-(n-2)*x(1,k););end分析过程 Global optimal solution found. Objective value: 16.00000 Extended solver steps: 0 Total solver iterations: 7 Variable Value Reduced Cost N 5. 0. U( 1) 0. 0. U( 2) 1. 0. U( 3) 1. 0. U(

4、 4) 3. 0. U( 5) 2. 0. DIST( 1, 1) 0. 0. DIST( 1, 2) 3. 0. DIST( 1, 3) 4. 0. DIST( 1, 4) 10.00000 0. DIST( 1, 5) .0 0. DIST( 2, 1) 3. 0. DIST( 2, 2) 0. 0. DIST( 2, 3) 4. 0. DIST( 2, 4) 6. 0. DIST( 2, 5) 5. 0. DIST( 3, 1) 4. 0. DIST( 3, 2) 4. 0. DIST( 3, 3) 0. 0. DIST( 3, 4) 6. 0. DIST( 3, 5) .0 0. DI

5、ST( 4, 1) 10.00000 0. DIST( 4, 2) 6. 0. DIST( 4, 3) 6. 0. DIST( 4, 4) 0. 0. DIST( 4, 5) 4. 0. DIST( 5, 1) .0 0. DIST( 5, 2) 5. 0. DIST( 5, 3) .0 0. DIST( 5, 4) 4. 0. DIST( 5, 5) 0. 0. X( 1, 1) 0. 0. X( 1, 2) 1. 3. X( 1, 3) 1. 4. X( 1, 4) 0. 10.00000 X( 1, 5) 0. .0 X( 2, 1) 0. 3. X( 2, 2) 0. 0. X( 2,

6、 3) 0. 4. X( 2, 4) 0. 6. X( 2, 5) 1. 5. X( 3, 1) 0. 4. X( 3, 2) 0. 4. X( 3, 3) 0. 0. X( 3, 4) 0. 6. X( 3, 5) 0. .0 X( 4, 1) 0. 10.00000 X( 4, 2) 0. 6. X( 4, 3) 0. 6. X( 4, 4) 0. 0. X( 4, 5) 0. 4. X( 5, 1) 0. .0 X( 5, 2) 0. 5. X( 5, 3) 0. .0 X( 5, 4) 1. 4. X( 5, 5) 0. 0. Row Slack or Surplus Dual Pri

7、ce 1 0. 0. 2 16.00000 -1. 3 0. 0. 4 3. 0. 5 5. 0. 6 0. 0. 7 0. 0. 8 3. 0. 9 5. 0. 10 4. 0. 11 0. 0. 12 1. 0. 13 1. 0. 14 0. 0. 15 0. 0. 16 0. 0. 17 2. 0. 18 0. 0. 19 1. 0. 20 0. 0. 21 0. 0. 22 1. 0. 23 2. 0. 最小支撑树由边（v1，v2），（v1，v3），（v2,v5），（v5,v4）组成，最小支撑树的树长为16.2 .最短路问题model:data: n=5;enddatasets: ci

8、ties/1.n/: F; roads(cities,cities)/ 1,2 1,3 1,5 2,5 3,2 3,5 4,3 5,4 /: D, P;endsetsdata: D= 1 10 4 4 3 2 2 1;enddata F(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 分析过程 Feasible solution found. Total solver iterations

9、: 0 Variable Value N 5. F( 1) 4. F( 2) 4. F( 3) 2. F( 4) 4. F( 5) 0. D( 1, 2) 1. D( 1, 3) 10.00000 D( 1, 5) 4. D( 2, 5) 4. D( 3, 2) 3. D( 3, 5) 2. D( 4, 3) 2. D( 5, 4) 1. P( 1, 2) 0. P( 1, 3) 0. P( 1, 5) 1. P( 2, 5) 1. P( 3, 2) 0. P( 3, 5) 1. P( 4, 3) 1. P( 5, 4) 0. Row Slack or Surplus 1 0. 2 0. 3

10、0. 4 0. 5 0. 6 0. 7 0. 8 0. 9 0. 10 0. 11 0. 12 0. 13 0. V1到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,2 1,3 2,3 2,4 2,5 3,5 4,6 5,4 5,6 6,1/:cap,flow;endsetsmax=flow(6,1);for(arcs(i,j):flow(i,j)<cap

11、(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;enddataend分析过程 Global optimal solution found. Objective value: 8. Total solver iterations: 0 Variable Value Reduced Cost CAP( 1, 2) 4. 0. CAP( 1, 3) 8. 0. CAP( 2, 3) 2. 0. CAP( 2, 4) 2. 0. CAP( 2, 5) 1

12、. 0. CAP( 3, 5) 5. 0. CAP( 4, 6) 6. 0. CAP( 5, 4) 3. 0. CAP( 5, 6) 7. 0. CAP( 6, 1) 1000.000 0. FLOW( 1, 2) 3. 0. FLOW( 1, 3) 5. 0. FLOW( 2, 3) 0. 0. FLOW( 2, 4) 2. 0. FLOW( 2, 5) 1. 0. FLOW( 3, 5) 5. 0. FLOW( 4, 6) 2. 0. FLOW( 5, 4) 0. 0. FLOW( 5, 6) 6. 0. FLOW( 6, 1) 8. 0.Row Slack or Surplus Dual

13、 Price 1 8. 1. 2 1. 0. 3 3. 0. 4 2. 0. 5 0. 1. 6 0. 1. 7 0. 1. 8 4. 0. 9 3. 0. 10 1. 0. 11 992.0000 0. 12 0. 1. 13 0. 1. 14 0. 1. 15 0. 0. 16 0. 0. 17 0. 0. 最大流为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

14、,b1,b2,b3,c1,c2,c3,d1,d2,e/:d;arcs(nodes,nodes)/a,b1 a,b2 a,b3 b1,c1 b1,c2 b1,c3 b2,c1 b2,c2 b2,c3 b3,c1 b3,c2 b3,c3 C1,d1 c1,d2 c2,d1 c2,d2 c3,d1 c3,d2 d1,e d2,e/:w,p;endsetsN=size(nodes);d(n)=0;for(nodes(i)|i#LT#n: d(i)=min(arcs(i,j): w(i,j)+d(j);for(arcs(i,j):p(i,j)=if(d(i)#eq#w(i,j)+d(j),1,0);da

15、ta:W = 2 5 3 7 5 6 3 2 4 5 1 5 1 4 6 3 7 5 3 4;enddataend过程分析 Feasible solution found. Total solver iterations: 0 Variable Value N 10.00000 D( A) 11.00000 D( B1) 11.00000 D( B2) 7. D( B3) 8. D( C1) 4. D( C2) 7. D( C3) 9. D( D1) 3. D( D2) 4. D( E) 0. W( A, B1) 2. W( A, B2) 5. W( A, B3) 3. W( B1, C1)

16、7. W( B1, C2) 5. W( B1, C3) 6. W( B2, C1) 3. W( B2, C2) 2. W( B2, C3) 4. W( B3, C1) 5. W( B3, C2) 1. W( B3, C3) 5. W( C1, D1) 1. W( C1, D2) 4. W( C2, D1) 6. W( C2, D2) 3. W( C3, D1) 7. W( C3, D2) 5. W( D1, E) 3. W( D2, E) 4. P( A, B1) 0. P( A, B2) 0. P( A, B3) 1. P( B1, C1) 1. P( B1, C2) 0. P( B1, C3) 0. P( B2, C1) 1. P( B2, C2) 0. P( B2, C3) 0. P( B3, C1) 0. P( B3, C2) 1. P( B3, C3) 0. P( C1, D1) 1. P( C1, D2) 0. P( C2, D1) 0. P( C2, D2) 1. P( C3, D1) 0. P( C3, D2) 1. P( D1, E) 1. P( D2, E) 1.Row Slack or Surplus 1 0. 2 0. 3