《运筹学实验报告.doc》由会员分享，可在线阅读，更多相关《运筹学实验报告.doc（7页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、_西华大学上机实验报告课程名称：运筹学年级/专业：09水利1班实验成绩：指导教师：姓名：实验日期：2011年11月实验名称：图论、动态规划求解学号：实验学时： 3一、实验目的 掌握网络图的计算机输入，求解最小树、最短路、最大流问题二、实验内容或设计思想首先将欲求的网络用计算机语言表达，再用lingo计算软件求出模型问题的解最小树应用破圈方法求解最大流算法用找流量可增链的方法求解网络最短路运用了动态规划，函数迭代、矩阵运算等的基本原理求解三、实验环境与工具 计算机，lingo软件，运筹学软件四、实验过程或实验数据1.最小树问题model:sets:city/1. 5/:U;link(city,c
2、ity):dist,x;endsetsdata:dist=0 3 4 10 999999 3 0 4 6 5 4 4 0 6 999999 10 6 6 0 4 999999 5 999999 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);););s
3、um (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分析过程 Global optimal solution found. Objective value: 16.00000 Extended solver steps: 0 Total solver iterations: 7 Variable Value Reduced Cost N 5.000000 0.000000 U( 1) 0.000000 0
4、.000000 U( 2) 1.000000 0.000000 U( 3) 1.000000 0.000000 U( 4) 3.000000 0.000000 U( 5) 2.000000 0.000000 DIST( 1, 1) 0.000000 0.000000 DIST( 1, 2) 3.000000 0.000000 DIST( 1, 3) 4.000000 0.000000 DIST( 1, 4) 10.00000 0.000000 DIST( 1, 5) 999999.0 0.000000 DIST( 2, 1) 3.000000 0.000000 DIST( 2, 2) 0.00
5、0000 0.000000 DIST( 2, 3) 4.000000 0.000000 DIST( 2, 4) 6.000000 0.000000 DIST( 2, 5) 5.000000 0.000000 DIST( 3, 1) 4.000000 0.000000 DIST( 3, 2) 4.000000 0.000000 DIST( 3, 3) 0.000000 0.000000 DIST( 3, 4) 6.000000 0.000000 DIST( 3, 5) 999999.0 0.000000 DIST( 4, 1) 10.00000 0.000000 DIST( 4, 2) 6.00
6、0000 0.000000 DIST( 4, 3) 6.000000 0.000000 DIST( 4, 4) 0.000000 0.000000 DIST( 4, 5) 4.000000 0.000000 DIST( 5, 1) 999999.0 0.000000 DIST( 5, 2) 5.000000 0.000000 DIST( 5, 3) 999999.0 0.000000 DIST( 5, 4) 4.000000 0.000000 DIST( 5, 5) 0.000000 0.000000 X( 1, 1) 0.000000 0.000000 X( 1, 2) 1.000000 3
7、.000000 X( 1, 3) 1.000000 4.000000 X( 1, 4) 0.000000 10.00000 X( 1, 5) 0.000000 999999.0 X( 2, 1) 0.000000 3.000000 X( 2, 2) 0.000000 0.000000 X( 2, 3) 0.000000 4.000000 X( 2, 4) 0.000000 6.000000 X( 2, 5) 1.000000 5.000000 X( 3, 1) 0.000000 4.000000 X( 3, 2) 0.000000 4.000000 X( 3, 3) 0.000000 0.00
8、0000 X( 3, 4) 0.000000 6.000000 X( 3, 5) 0.000000 999999.0 X( 4, 1) 0.000000 10.00000 X( 4, 2) 0.000000 6.000000 X( 4, 3) 0.000000 6.000000 X( 4, 4) 0.000000 0.000000 X( 4, 5) 0.000000 4.000000 X( 5, 1) 0.000000 999999.0 X( 5, 2) 0.000000 5.000000 X( 5, 3) 0.000000 999999.0 X( 5, 4) 1.000000 4.00000
9、0 X( 5, 5) 0.000000 0.000000 Row Slack or Surplus Dual Price 1 0.000000 0.000000 2 16.00000 -1.000000 3 0.000000 0.000000 4 3.000000 0.000000 5 5.000000 0.000000 6 0.000000 0.000000 7 0.000000 0.000000 8 3.000000 0.000000 9 5.000000 0.000000 10 4.000000 0.000000 11 0.000000 0.000000 12 1.000000 0.00
10、0000 13 1.000000 0.000000 14 0.000000 0.000000 15 0.000000 0.000000 16 0.000000 0.000000 17 2.000000 0.000000 18 0.000000 0.000000 19 1.000000 0.000000 20 0.000000 0.000000 21 0.000000 0.000000 22 1.000000 0.000000 23 2.000000 0.000000 最小支撑树由边（v1，v2），（v1，v3），（v2,v5），（v5,v4）组成，最小支撑树的树长为16.2 .最短路问题mod
11、el:data: n=5;enddatasets: cities/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 fo
12、und. Total solver iterations: 0 Variable Value N 5.000000 F( 1) 4.000000 F( 2) 4.000000 F( 3) 2.000000 F( 4) 4.000000 F( 5) 0.000000 D( 1, 2) 1.000000 D( 1, 3) 10.00000 D( 1, 5) 4.000000 D( 2, 5) 4.000000 D( 3, 2) 3.000000 D( 3, 5) 2.000000 D( 4, 3) 2.000000 D( 5, 4) 1.000000 P( 1, 2) 0.000000 P( 1,
13、 3) 0.000000 P( 1, 5) 1.000000 P( 2, 5) 1.000000 P( 3, 2) 0.000000 P( 3, 5) 1.000000 P( 4, 3) 1.000000 P( 5, 4) 0.000000 Row Slack or Surplus 1 0.000000 2 0.000000 3 0.000000 4 0.000000 5 0.000000 6 0.000000 7 0.000000 8 0.000000 9 0.000000 10 0.000000 11 0.000000 12 0.000000 13 0.000000 V1到V5的最短路长为
14、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(i,j);for(nodes(i):sum(arcs(j,i):flow(j,i)=sum(arcs(i,j):flow(i,j);data:
15、cap=4,8,2,2,1,5,6,3,7,1000;enddataend分析过程 Global optimal solution found. Objective value: 8.000000 Total solver iterations: 0 Variable Value Reduced Cost CAP( 1, 2) 4.000000 0.000000 CAP( 1, 3) 8.000000 0.000000 CAP( 2, 3) 2.000000 0.000000 CAP( 2, 4) 2.000000 0.000000 CAP( 2, 5) 1.000000 0.000000 C
16、AP( 3, 5) 5.000000 0.000000 CAP( 4, 6) 6.000000 0.000000 CAP( 5, 4) 3.000000 0.000000 CAP( 5, 6) 7.000000 0.000000 CAP( 6, 1) 1000.000 0.000000 FLOW( 1, 2) 3.000000 0.000000 FLOW( 1, 3) 5.000000 0.000000 FLOW( 2, 3) 0.000000 0.000000 FLOW( 2, 4) 2.000000 0.000000 FLOW( 2, 5) 1.000000 0.000000 FLOW(
17、3, 5) 5.000000 0.000000 FLOW( 4, 6) 2.000000 0.000000 FLOW( 5, 4) 0.000000 0.000000 FLOW( 5, 6) 6.000000 0.000000 FLOW( 6, 1) 8.000000 0.000000Row Slack or Surplus Dual Price 1 8.000000 1.000000 2 1.000000 0.000000 3 3.000000 0.000000 4 2.000000 0.000000 5 0.000000 1.000000 6 0.000000 1.000000 7 0.0
18、00000 1.000000 8 4.000000 0.000000 9 3.000000 0.000000 10 1.000000 0.000000 11 992.0000 0.000000 12 0.000000 1.000000 13 0.000000 1.000000 14 0.000000 1.000000 15 0.000000 0.000000 16 0.000000 0.000000 17 0.000000 0.000000 最大流为v1到v2为3，最大流为v1到v3为5，最大流为v2到v3为0，最大流为v2到v4为2，最大流为v2到v5为1，最大流为v3到v5为5，最大流为v
19、4到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,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
20、): w(i,j)+d(j);for(arcs(i,j):p(i,j)=if(d(i)#eq#w(i,j)+d(j),1,0);data: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.000000 D( B3) 8.000000 D( C1) 4.000000 D( C2) 7.000000 D( C3) 9.000000 D( D1) 3.000000 D( D2) 4.000000 D( E) 0.000000 W( A, B1) 2.000000 W( A, B2) 5.000000 W( A, B3) 3.000000 W( B1, C1) 7.000000 W( B1, C2) 5.000000 W( B1, C3) 6.