1、精選優(yōu)質(zhì)文檔-傾情為你奉上西華大學(xué)上機(jī)實(shí)驗(yàn)報(bào)告課程名稱：運(yùn)籌學(xué)年級(jí)/專業(yè)：09水利1班實(shí)驗(yàn)成績(jī)：指導(dǎo)教師：姓名：實(shí)驗(yàn)日期：2011年11月實(shí)驗(yàn)名稱：圖論、動(dòng)態(tài)規(guī)劃求解學(xué)號(hào)：實(shí)驗(yàn)學(xué)時(shí)： 3一、實(shí)驗(yàn)?zāi)康?掌握網(wǎng)絡(luò)圖的計(jì)算機(jī)輸入，求解最小樹、最短路、最大流問(wèn)題二、實(shí)驗(yàn)內(nèi)容或設(shè)計(jì)思想首先將欲求的網(wǎng)絡(luò)用計(jì)算機(jī)語(yǔ)言表達(dá)，再用lingo計(jì)算軟件求出模型問(wèn)題的解最小樹應(yīng)用破圈方法求解最大流算法用找流量可增鏈的方法求解網(wǎng)絡(luò)最短路運(yùn)用了動(dòng)態(tài)規(guī)劃，函數(shù)迭代、矩陣運(yùn)算等的基本原理求解三、實(shí)驗(yàn)環(huán)境與工具 計(jì)算機(jī)，lingo軟件，運(yùn)籌學(xué)軟件四、實(shí)驗(yàn)過(guò)程或?qū)嶒?yàn)數(shù)據(jù)1.最小樹問(wèn)題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分析過(guò)程 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）組成，最小支撐樹的樹長(zhǎng)為16.2 .最短路問(wèn)題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 分析過(guò)程 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的最短路長(zhǎng)為4，最短路徑為V1到V5V2到V5的最短路長(zhǎng)為4，最短路徑為V2到V5V3到V5的最短路長(zhǎng)為4，最短路徑為V3到V5V4到V5的最短路長(zhǎng)為4，最短路徑為V4到V3到V53.最大流問(wèn)題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分析過(guò)程 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.動(dòng)態(tài)規(guī)劃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過(guò)程分析 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