圖與網(wǎng)絡(luò)分析物流運籌學(xué)-文庫吧資料
2025-01-22 11:58本頁面
【正文】 7 12 18 25 年份 1 2 3 4 5 購置費 18 20 21 23 24 使用年數(shù) 0~1 1~2 2~3 3~4 4~5 維修費 5 7 12 18 25 28 v1 v2 v3 v4 v5 v6 23 25 26 29 30 42 60 85 32 44 62 33 45 30 四、 最大流問題 （ 一 ） 、 基本概念 設(shè)一個賦權(quán)有向圖 D=（ V, E） ,在 V中指定一個發(fā)點vs和一個收點 vt ,其它的點叫做中間點 。若購置設(shè)備，每年需支付購置費用；若繼續(xù)使用舊設(shè)備，需要支付維修與運行費用，而且隨著設(shè)備的老化會逐年增加。 2）求解 （標號法） W12 =11+5=16 W13 =11+5+6=22 W14 =11+5+6+8=30 W15 =11+5+6+8+11=41 W16 =11+5+6++8+11+18=59 W23 =11+5=16 W24 =11+5+6=22 W25 =11+5+6+8=30 W26 =11+5+6+8+11=41 W45 =12+5=17 W46 =12+5+6=23 W56 =13+5=18 W34 =12+5=17 W35 =12+5+6=23 W36 =12+5+6+8=31 例四、 某工廠使用一種設(shè)備，這種設(shè)備在一定的年限內(nèi)隨著時間的推移逐漸損壞。 第 i年度 1 2 3 4 5 購置費 11 11 12 12 13 設(shè)備役齡 01 12 23 34 45 維修費用 5 6 8 11 18 （ 2） 方法：將此問題用一個賦權(quán)有向圖來描述 ， 然后求這個賦權(quán)有向圖的最短路 。 }{min 11 jiiij lPP ?? ),2,1(1)1(1 njlP jj ??? ）（ nklPjikiikj ,3,2][min )1(1)(1 ???? ?)(1kjP ）（ njPP tjtj ,2,1)1(1)(1 ??? ? ）（ njP tj ,2,1)(1 ??例二、 － 1 8 v1 v2 v3 v4 v5 － 2 6 － 3 － 5 － 1 － 3 － 5 2 1 － 1 2 1 1 v6 v7 v8 3 7 v1 v2 v3 v4 v5 v6 v7 v8 P(1) P(2) P(3) P(4) v1 0 1 2 3 0 0 0 0 v2 6 0 2 1 5 5 5 v3 3 0 5 1 2 2 2 2 v4 8 0 2 3 7 7 7 v5 1 0 1 3 3 v6 1 0 1 7 1 1 1 v7 1 0 5 5 5 v8 3 5 0 6 6 求圖中 v1到 各點的最短路 － 1 8 v1 v2 v3 v4 v5 － 2 6 － 3 － 5 － 1 － 3 － 5 2 1 － 1 2 1 1 v6 v7 v8 3 7 （ 0， 0） （ v3 ， 5） （ v1 ， 2） （ v3 ， 7） （ v2 ， 3） （ v4 ， 5） （ v3 ， 1） （ v6 ， 6） 例三、求： 5年內(nèi)，哪些年初購置新設(shè)備，使 5年內(nèi)的總費用最小。 設(shè) P1j表示從 v1到 vj的最短路長 ， P1i表示從 v1到vi的最短路長 ， 則有下列方程： 開始時 ， 令 即用 v1到 vj的直接距離做初始解 。 顯然 ， 從 v1到 vj的最短路是從 v1出發(fā) ， 沿著這條路到某個點 vi再沿弧 (vi,vj)到 vj。將從V1 到 任一點的最短路權(quán)標在圖上，即可求出從 V1 到 任一點的最短路線。 3 V 1 V 2 V V 4 V 5 V V 6 7 V 8 3 7 2 1 2 3 3 4 1 2 2 6 V1 V2 V3 V4 V5 V6 V7 V8 ① P=0 T=+∞ T=+∞ T=+∞ T=+∞ T=+∞ T=+∞ T=+∞ ② P=T=3 T=+∞ T=7 T=+∞ T=+∞ T=+∞ T=+∞ ③ T=6 T=7 P=T=5 T=+∞ T=+∞ T=+∞ ④ P=T=6 T=6 T=8 T=+∞ T=+∞ ⑤ P=T=6 T=8 T=9 T=12 ⑥ P=T=8 T=10 T=10 ⑦ P=T=9 T=11 再無其它 T 標號 ， 所以 T(V8)=P(V8)=10。 0)( 1 ?v)6,3,2()( ????? ivT i（ 2） （ 3） 3]30,min[])(,)(min[)( 12122 ??????? lvPvTvT 5]50,min[])(,)(min[) 13133 ??????? lvPvT3)( 2 ?vP（ 4） 4]13,5min[])(,)(min[)( 23233 ????? lvPvTvT 5]23,min[])(,)(min[)( 24244 ??????? lvPvTv 5]23,min[])(,)(min[) 25255 ??????? lvPvTTv1 v2 v3 v4 v6 v5 3 5 2 2 4 2 4 2 1 4)( 3 ?vP（ 5） （ 6） 8]44,6min[])(,)(min[)( 35355 ????? lvPvTvT 5)( 4 ?vP 5)( 5 ?vP 9]45,min[])(,)(min[)( 46466 ??????? lvPvTvT 7]25,min[])(,)()(56566 ?????l7)( 6 ?vP（ 7） （ 8） （ 9） （ 10） 反向追蹤得 v1到 v6的最短路為： 6521 vvvv ???2 3 7 1 8 4 5 6 6 1 3 4 10 5 2 7 5 9 3 4 6 8 2 求從 1到 8的最短路徑 2 3 7 1 8 4 5 6 6 1 3 4 10 5 2 7 5 9 3 4 6 8 2 X={1}, w1=0 min {c12,c14,c16}=min {0+2,0+1,0+3}=min {2,1,3}=1 X={1,4}, p4=1 p4=1 p1=0 2 3 7 1 8 4 5 6 6 1 3 4 10 5 2 7 5 9 3 4 6 8 2 X={1,4} min {c12,c16,c42,c47}=min {0+2,0+3,1+10,1+2}=min {2,3,11,3}=2 X={1,2,4}, p2=2 p1=0 p4=1 p2=2 2 3 7 1 8 4 5 6 6 1 3 4 10 5 2 7 5 9 3 4 6 8 2 X={1,2,4} min {c13,c23,c25,c47}=min {0+3,2+6,2+5,1+2}=min {3,8,7,3}=3 X={1,2,4,6}, p6=3 p2=2 p4=1 p1=0 p6=3 2 3 7 1 8 4 5 6 6 1 3 4 10 5 2 7 5 9 3 4 6 8 2 X={1,2,4,6} min {c23,c25,c47,c67}=min {2+6,2+5,1+2,3+4}=min {8,7,3,7}=3 X={1,2,4,6,7}, p7=3 p2=2 p4=1 p1=0 p6=3 p7=3 2 3 7 1 8 4 5 6 6 1 3 4 10 5 2 7 5 9 3 4 6 8 2 X={1,2,4,6,7} min {c23,c25,c75,c78}=min {2+6,2+5,3+3,3+8}=min {8,7,6,11}=6 X={1,2,4,5,6,7}, p5=6 p2=2 p4=1 p1=0 p6=3 p7=3 p5=6 2 3 7 1 8 4 5 6 6 1 3 4
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1