运筹学实验二 图论、动态规划求解.doc

西华大学能源与环境学院学生上机实验报告西华大学上机实验报告课程名称：运筹学年级/专业：2009/水利水电工程实验成绩：指导教师：施浩然姓名：丁冬冬实验日期：2011年11月实验名称：图论、动态规划求解学号：312009080801417实验学时： 3 一、实验目的掌握网络图的计算机输入，求解最小树、最短路、最大流问题二、实验内容或设计思想首先将欲求的网络用计算机语言表达，再用lingo计算软件求出模型问题的解。最小树应用破圈方法求解最大流算法用找流量可增链的方法求解网络最短路运用了动态规划，函数迭代、矩阵运算等的基本原理求解三、实验环境与工具计算机，lingo软件，运筹学软件。四、实验过程或实验数据1、最小数问题给定6个点,各点之间的距离如下程序所示。试用LINGO软件解网络最短路。model:sets: city / 1. 5/: u; link( city, city): dist, x;endsets data: dist = 0 4 6 14 999999 4 0 6 8 7 6 6 0 8 999999 14 8 8 0 6 999999 7 999999 6 0;enddata N=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程序运行结果为： Global optimal solution found. Objective value: 23.00000 Extended solver steps: 0 Total solver iterations: 8 Variable Value Reduced Cost N 5.000000 0.000000 U( 1) 0.000000 0.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) 4.000000 0.000000 DIST( 1, 3) 6.000000 0.000000 DIST( 1, 4) 14.00000 0.000000 DIST( 1, 5) 999999.0 0.000000 DIST( 2, 1) 4.000000 0.000000 DIST( 2, 2) 0.000000 0.000000 DIST( 2, 3) 6.000000 0.000000 DIST( 2, 4) 8.000000 0.000000 DIST( 2, 5) 7.000000 0.000000 DIST( 3, 1) 6.000000 0.000000 DIST( 3, 2) 6.000000 0.000000 DIST( 3, 3) 0.000000 0.000000 DIST( 3, 4) 8.000000 0.000000 DIST( 3, 5) 999999.0 0.000000 DIST( 4, 1) 14.00000 0.000000 DIST( 4, 2) 8.000000 0.000000 DIST( 4, 3) 8.000000 0.000000 DIST( 4, 4) 0.000000 0.000000 DIST( 4, 5) 6.000000 0.000000 DIST( 5, 1) 999999.0 0.000000 DIST( 5, 2) 7.000000 0.000000 DIST( 5, 3) 999999.0 0.000000 DIST( 5, 4) 6.000000 0.000000 DIST( 5, 5) 0.000000 0.000000 X( 1, 1) 0.000000 0.000000 X( 1, 2) 1.000000 4.000000 X( 1, 3) 1.000000 6.000000 X( 1, 4) 0.000000 14.00000 X( 1, 5) 0.000000 999999.0 X( 2, 1) 0.000000 4.000000 X( 2, 2) 0.000000 0.000000 X( 2, 3) 0.000000 6.000000 X( 2, 4) 0.000000 8.000000 X( 2, 5) 1.000000 7.000000 X( 3, 1) 0.000000 6.000000 X( 3, 2) 0.000000 6.000000 X( 3, 3) 0.000000 0.000000 X( 3, 4) 0.000000 8.000000 X( 3, 5) 0.000000 999999.0 X( 4, 1) 0.000000 14.00000 X( 4, 2) 0.000000 8.000000 X( 4, 3) 0.000000 8.000000 X( 4, 4) 0.000000 0.000000 X( 4, 5) 0.000000 6.000000 X( 5, 1) 0.000000 999999.0 X( 5, 2) 0.000000 7.000000 X( 5, 3) 0.000000 999999.0 X( 5, 4) 1.000000 6.000000 X( 5, 5) 0.000000 0.000000 Row Slack or Surplus Dual Price 1 0.000000 0.000000 2 23.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.000000 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.0000002、最短路问题 给定10个点,各点城市之间的距离和路线如下程序所示。试用LINGO软件解网络最短路。model:data: n=10;enddatasets: cities/1.10/: F; roads(cities,cities)/ 1,2 1,3 2,4 2,5 2,6 3,4 3,5 3,6 4,7 4,8 5,7 5,8 5,9 6,8 6,9 7,10 8,10 9,10 /: D, P;endsetsdata: D= 6 7 3 4 9 7 5 11 5 1 8 7 3 4 12 5 7 6;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: 0 Variable Value N 10.00000 F( 1) 17.00000 F( 2) 11.00000 F( 3) 14.00000 F( 4) 8.000000 F( 5) 9.000000 F( 6) 11.00000 F( 7) 5.000000 F( 8) 7.000000 F( 9) 6.000000 F( 10) 0.000000 D( 1, 2) 6.000000 D( 1, 3) 7.000000 D( 2, 4) 3.000000 D( 2, 5) 4.000000 D( 2, 6) 9.000000 D( 3, 4) 7.000000 D( 3, 5) 5.000000 D( 3, 6) 11.00000 D( 4, 7) 5.000000 D( 4, 8) 1.000000 D( 5, 7) 8.000000 D( 5, 8) 7.000000 D( 5, 9) 3.000000 D( 6, 8) 4.000000 D( 6, 9) 12.00000 D( 7, 10) 5.000000 D( 8, 10) 7.000000 D( 9, 10) 6.000000 P( 1, 2) 1.000000 P( 1, 3) 0.000000 P( 2, 4) 1.000000 P( 2, 5) 0.000000 P( 2, 6) 0.000000 P( 3, 4) 0.000000 P( 3, 5) 1.000000 P( 3, 6) 0.000000 P( 4, 7) 0.000000 P( 4, 8) 1.000000 P( 5, 7) 0.000000 P( 5, 8) 0.000000 P( 5, 9) 1.000000 P( 6, 8) 1.000000 P( 6, 9) 0.000000 P( 7, 10) 1.000000 P( 8, 10) 1.000000 P( 9, 10) 1.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 14 0.000000 15 0.000000 16 0.000000 17 0.000000 18 0.000000 19 0.000000 20 0.000000 21 0.000000 22 0.000000 23 0.000000 24 0.000000 25 0.000000 26 0.000000 27 0.000000 28 0.0000003、最大流问题 给定6个点,各点之间的方向和流量如下程序所示。试用LINGO软件解网络最短路。 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:cap=5,7,3,3,2,6,5,3,8,1000;enddataend程序运行结果为：Global optimal solution found. Objective value: 11.00000 Total solver iterations: 4 Variable Value Reduced Cost CAP( 1, 2) 5.000000 0.000000 CAP( 1, 3) 7.000000 0.000000 CAP( 2, 3) 3.000000 0.000000 CAP( 2, 4) 3.000000 0.000000 CAP( 2, 5) 2.000000 0.000000 CAP( 3, 5) 6.000000 0.000000 CAP( 4, 6) 5.000000 0.000000 CAP( 5, 4) 3.000000 0.000000 CAP( 5, 6) 8.000000 0.000000 CAP( 6, 1) 1000.000 0.000000 FLOW( 1, 2) 5.000000 0.000000 FLOW( 1, 3) 6.000000 0.000000 FLOW( 2, 3) 0.000000 1.000000 FLOW( 2, 4) 3.000000 0.000000 FLOW( 2, 5) 2.000000 0.000000 FLOW( 3, 5) 6.000000 0.000000 FLOW( 4, 6) 3.000000 0.000000 FLOW( 5, 4) 0.000000 0.000000 FLOW( 5, 6) 8.000000 0.000000 FLOW( 6, 1) 11.00000 0.000000 Row Slack or Surplus Dual Price 1 11.00000 1.000000 2 0.000000 1.000000 3 1.000000 0.000000 4 3.000000 0.000000 5 0.000000 0.000000 6 0.000000 0.000000 7 0.000000 1.000000 8 2.000000 0.000000 9 3.000000 0.000000 10 0.000000 0.000000 11 989.0000 0.000000 12 0.000000 1.000000 13 0.000000 0.000000 14 0.000000 1.000000 15 0.000000 0.000000 16 0.000000 0.000000 17 0.000000 0.0000004、动态规划Lingo程序如下：model:sets:Nodes/a,b1,b2,b3,b4,c1,c2,c3,c4,d1,d2,e/:d;Arcs(nodes, nodes)/a,b1 a,b2 a,b3 a,b4 b1,c1 b1,c2 b1,c3 b1,c4 b2,c1 b2,c2 b2,c3 b2,c4 b3,c1 b3,c2 b3,c3 b3,c4b4,c1 b4,c2 b4,c3 b4,c4 c1,d1 c1,d2 c2,d1 c2,d2 c3,d1 c3,d2 c4,d1 c4,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);Data:W= 3 7 3 7 5 6 5 2 4 5 1 5 1 4 6 3 4 6 3 4 3 5 6 3 5 6 3 4 7 2 ;EnddataEnd计算结果如下： Feasible solution found. Total solver iterations: 0 Variable Value N 12.00000 D( A) 11.00000 D( B1) 8.000000 D( B2) 9.000000 D( B3) 8.000000 D( B4) 10.00000 D( C1) 7.000000 D( C2) 5.000000 D( C3) 8.000000 D(