利用動(dòng)態(tài)規(guī)劃數(shù)學(xué)模型求最短路徑

1、利用動(dòng)態(tài)規(guī)劃數(shù)學(xué)模型求最短路徑杜彥娟(黑龍江科技學(xué)院蒿山校區(qū),黑龍江哈爾濱150000摘要:隨著科技的發(fā)展,數(shù)學(xué)模型已廣泛應(yīng)用到社會(huì)生活的各個(gè)領(lǐng)域。文中介紹了數(shù)學(xué)模型的定義及建立動(dòng)態(tài)規(guī)劃數(shù)學(xué)模型步驟,并通過建立動(dòng)態(tài)規(guī)劃數(shù)學(xué)模型解決了求最短路徑問題,具有廣泛的實(shí)際意義。關(guān)鍵詞:數(shù)學(xué)模型;動(dòng)態(tài)規(guī)劃;最短路徑;結(jié)點(diǎn)中圖分類號:T B11文獻(xiàn)標(biāo)識(shí)碼:A 文章編號:1008-8725(200501-0094-020概述在日常生活和生產(chǎn)中,我們經(jīng)常遇到與求最短路徑的問題。例如,某人因?yàn)楣ぷ餍枰?常常往返于城市A 與城市B 之間,那么就希望知道從城市A 到城市B 的眾多路徑中,選擇哪一條路徑的路途最短。經(jīng)濟(jì)

2、管理中的貨物存貯、設(shè)備更新、資源分配、任務(wù)均衡、系統(tǒng)可靠性等問題,都需要?jiǎng)討B(tài)規(guī)劃數(shù)學(xué)模型來解決。數(shù)學(xué)模型(Mathematical M odel 是指對于現(xiàn)實(shí)世界的一個(gè)特定對象,為了一個(gè)特定目的,根據(jù)特有的內(nèi)在規(guī)律,作出一些必要的簡化、假設(shè),運(yùn)用適當(dāng)?shù)臄?shù)學(xué)工具得到的一個(gè)數(shù)據(jù)結(jié)構(gòu)。動(dòng)態(tài)規(guī)劃是尋求多階段生產(chǎn)計(jì)劃的方法,它是求解多階段優(yōu)化決策問題的有效工具。建立動(dòng)態(tài)規(guī)劃數(shù)學(xué)模型的主要步驟為:劃分階段;定義狀態(tài)和決策;建立狀態(tài)轉(zhuǎn)移律;確定允許狀態(tài)集合和允許決策集合;列出最優(yōu)方程并確定終端條件。1實(shí)例分析111問題的提出現(xiàn)有一張城市地圖,如圖1表示,每個(gè)結(jié)點(diǎn)代表城市,邊上的加權(quán)值表示城市間距離。在此介紹

3、如何找出某人從城市A 經(jīng)城市B ,C ,D 到達(dá)城市E 的最短路徑的方法。K =1K =2K =3K =4112問題分析與求解把整個(gè)過程劃分4個(gè)階段,用K 表示,K =1,2,3,4。K =1(第一階段:從A 結(jié)點(diǎn)到B 級結(jié)點(diǎn)(B 1,B 2;K =2(第二階段:從B 級結(jié)點(diǎn)(B 1,B 2到級結(jié)點(diǎn)(C 1,C 2;K =3(第三階段:從C 級結(jié)點(diǎn)(C 1,C 2到級結(jié)點(diǎn)(D 1,D 2,D 3;K =4(第四階段:從D 級結(jié)點(diǎn)(D 1,D 2,D 3到E 結(jié)點(diǎn)。顯然,每兩個(gè)結(jié)點(diǎn)間距離是一定的,用d (i ,j 表示,且d (i ,j =d (j ,i 。圖1示意圖從一個(gè)路徑的每一結(jié)點(diǎn)到達(dá)下一

4、路徑的那個(gè)結(jié)點(diǎn),是由階段初的城市名、階段未的城市名確定,圖中用結(jié)點(diǎn)間的連線表示,再將本階段的兩城市間路程作為兩結(jié)點(diǎn)間的距離,標(biāo)在結(jié)點(diǎn)間的連線上,這樣求解決某人從城市A 經(jīng)城市B 、城市C 、城市D 至城市DE 的路程最短問題就轉(zhuǎn)化為尋找從階段1的結(jié)點(diǎn)A 至階段4的結(jié)點(diǎn)E 的一條最短路徑問題。求最短路徑問題有兩種解法:順序遞推法和逆序遞推法。順序遞推法即從前向后求解,逆序遞推法即從后向前求解。因?yàn)閺腁 至E 的最短路徑與從E 至A 的最短路徑相同,所以兩種解法的結(jié)果是唯一確定的;并且若某一路徑為最短路徑,則它的任一子路徑也必為最短路徑。收稿日期:2004-10-10;修訂日期:2004-11-0

5、5作者簡介:杜彥娟(1970-,女,講師,現(xiàn)在黑龍江科技學(xué)院蒿山校區(qū)從事數(shù)學(xué)教學(xué)工作。第24卷第1期2005年1月煤炭技術(shù)C oal T echnologyV ol 124,N o 101Jan ,200511211順序遞推法K=1時(shí),考慮第一個(gè)階段。第一階段的最短路程記作f1(B ii=1,2,則f1(B i=5,f1(B2=8。K=2時(shí),聯(lián)合考慮前兩個(gè)階段。第一階段、第二階段至B i結(jié)點(diǎn)的最短路程之和記為f2(C ii=1, 2。f2(C i=mind(B1,C1+f1(B1,d(B2,C2+ f1(B2=min2+5,1+8=7,即從A結(jié)點(diǎn)至C1結(jié)點(diǎn)最短路徑為AB1C,f2(C2=min

6、d(B1,C2 +f1(B1,d(B1,C2+f1(B2=min3+5,2+8= 8,即從A結(jié)點(diǎn)至C2結(jié)點(diǎn)最短路徑為AB1C2。K=3時(shí),聯(lián)合考慮前三個(gè)階段。前三個(gè)階段至D i結(jié)點(diǎn)的最短路程記作f3(D ii=1,2,3。f3(D i= mind(C1,D i+f2(C1,d(C2,D i+f2(C2f3(D1 =mind(C1,D1+f2(C1,d(C2,D1+f2(C2= min8+7,4+8=12,即從A結(jié)點(diǎn)至D1結(jié)點(diǎn)最短路徑為AB1C1D1,f3(D2=mind(C1,D2+ f2(C1,d(C1,D2+f2(C3=min7+7,2+8= 10,即從A結(jié)點(diǎn)至D2結(jié)點(diǎn)最短路徑為AB1C2

7、D2,f3(D3=mind(C1,D3+f2(C1,d(C2, D3+f2(C3=min8+7,4+8=12,即從A結(jié)點(diǎn)至D3結(jié)點(diǎn)最短路徑為AB1C2D3。K=4時(shí),聯(lián)合考慮前四個(gè)階段。完成前四個(gè)階段至E結(jié)點(diǎn)的最短路程記作f4(E,f4(E=mind (D1,E+f3(D1,d(D2,E+f3(D2,d(D3,E+ f3(D3=min4+12,8+10,3+12=15,即從A到E的最短路徑為AB1C2D3E。也就是說,從城市A經(jīng)B1、C2、D3至城市E為最短路程。11212逆序遞推法K=4時(shí),考慮第四個(gè)階段,從E結(jié)點(diǎn)開始,從后向前推導(dǎo),與前面順序遞推法類似。用f4(D K表示從E結(jié)點(diǎn)至D i結(jié)

8、點(diǎn)的最短路程,f4(D1=4, f4(D2=8,f4(D3=3。K=3時(shí),聯(lián)合考慮后兩個(gè)階段。用f3(C1表示第四、第三階段至C1結(jié)點(diǎn)的最短路程,i=1,2。f3(C1=mind(D1,C1+f4(D1,d(D2,C1+f4(D2,d(D3,C1+f4(D3=min8+4,7+8,8+3 =11,即此階段至C1最短路徑為ED3C1,f3(C2d(C2,D1+f4(D1,d(C2,D2+f4(D2,d (C2,D3+f4(D3=min4+4,2+8,4+3=7。所以此階段至C2最短路徑為ED3C2。K=2時(shí),聯(lián)合考慮后三個(gè)階段。f2(B i表示后三個(gè)階段至B i結(jié)點(diǎn)的最短路程。f2(B i=mi

9、n d(B i,C1+f3(C1,d(B i,C2+f3(C2f2(B1=mind(B1,C1+f3(C1,d(B1,C2 +f3(C2=min2+11,3+7=10所以此時(shí)至B1終點(diǎn)最短路徑為ED3C2B1。f2(B2=mind(B2,C1+f3(C1,d(B2,C2 +f3(C2=min1+11,2+7=9,所以此時(shí)至B2終點(diǎn)最短路徑為ED3C2B2。K=1時(shí),聯(lián)合考慮前四個(gè)階段。f1(A=min d(A,B1+f2(B1,d(A,B2+f2(B2=min5+ 10,8+9=15,即最短路徑為AB1C2D3E。且從A至E的最短路程為f1(A=15。2結(jié)語運(yùn)用此模型,可以解決隨機(jī)需求下,最優(yōu)

10、生產(chǎn)計(jì)劃問題。動(dòng)態(tài)規(guī)劃模型具有靜態(tài)規(guī)劃模型無法比擬的優(yōu)越性。如能得到全局最優(yōu)方案;可以得到一組最優(yōu)解;在計(jì)算時(shí),可以利用實(shí)際知識(shí)和個(gè)人經(jīng)驗(yàn)提高求解效率。但是它也具有一些缺點(diǎn),如沒有統(tǒng)一的標(biāo)準(zhǔn)模型;用數(shù)值方法求解時(shí)存在維數(shù)災(zāi)等。愿我們能揚(yáng)長避短,運(yùn)用動(dòng)態(tài)規(guī)劃數(shù)學(xué)模型解決更多的實(shí)際問題。參考文獻(xiàn):1姜啟源,等1數(shù)學(xué)模型M1北京:高等教育出版社,200312黃國瑜,等1數(shù)學(xué)結(jié)構(gòu)M1北京:清華大學(xué)出版,20011Solving the shortest path by the mobile planning m athem atical modleDU Y an-juan(Heilongjiang Institute of Science and T echnology,Harbin150008,ChinaAbstract:With the development of the science and technology,mathematical m odle has been used in many fields of the s ociety.This thesis gives out the defination of the mathematical m odle and steps of selling up