《動(dòng)態(tài)規(guī)劃模型舉例》PPT課件

《《動(dòng)態(tài)規(guī)劃模型舉例》PPT課件》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。

1、§6動(dòng)態(tài)規(guī)劃模型舉例10/3/20211以上討論的優(yōu)化問(wèn)題大多數(shù)屬于靜態(tài)的，即不必考慮時(shí)間的變化，建立的模型——線性規(guī)劃、非線性規(guī)劃、整數(shù)規(guī)劃等，都屬于靜態(tài)規(guī)劃。多階段決策屬于動(dòng)態(tài)優(yōu)化問(wèn)題，即在每個(gè)階段（通常以時(shí)間或空間為標(biāo)志）要根據(jù)過(guò)程的演變情況確定一個(gè)決策，使全過(guò)程的某個(gè)指標(biāo)達(dá)到最優(yōu)。例如：（1）化工生產(chǎn)過(guò)程中包含一系列的過(guò)程設(shè)備，如反應(yīng)器、蒸餾塔、吸收器等，前一設(shè)備的輸出為后一設(shè)備的輸入。因此，應(yīng)該如何控制生產(chǎn)過(guò)程中各個(gè)設(shè)備的輸入和輸出，使總產(chǎn)量最大。（2）發(fā)射一枚導(dǎo)彈去擊中運(yùn)動(dòng)的目標(biāo)，由

2、于目標(biāo)的行動(dòng)是不斷改變的，因此應(yīng)當(dāng)如何根據(jù)目標(biāo)運(yùn)動(dòng)的情況，不斷地決定導(dǎo)彈飛行的方向和速度，使之最快地命中目標(biāo)。10/3/20212（3）汽車剛買(mǎi)來(lái)時(shí)故障少、耗油低，出車時(shí)間長(zhǎng)，處理價(jià)值和經(jīng)濟(jì)效益高。隨著使用時(shí)間的增加則變得故障多，油耗高，維修費(fèi)用增加，經(jīng)濟(jì)效益差。使用時(shí)間俞長(zhǎng)，處理價(jià)值也俞低。另外，每次更新都要付出更新費(fèi)用。因此，應(yīng)當(dāng)如何決定它的使用年限，使總的效益最佳。動(dòng)態(tài)規(guī)劃模型是解決這類問(wèn)題的有力工具。下面結(jié)合具體例子闡述建立動(dòng)態(tài)規(guī)劃模型的思路。例13最短路問(wèn)題。圖2是一個(gè)線路網(wǎng)，連線上的

3、數(shù)字表示兩點(diǎn)之間的距離（或費(fèi)用），尋找一條由A到G的路線，使距離最短（或費(fèi)用最?。?。10/3/20213解：用窮舉法當(dāng)然可以解決這個(gè)問(wèn)題。不難算出，一共有48條從A到G的路線，用加法得到每條路線的長(zhǎng)度后，再作比較即可找出最短路線。顯然當(dāng)路段很多時(shí)，計(jì)算工作量將是很大的。AB1B2C1C2C3C4D3D2D1E1E2E3F1F2G531368768433538622123366255343圖２10/3/20214用動(dòng)態(tài)規(guī)劃解決問(wèn)題的思路，來(lái)源于生活中這樣一個(gè)基本常識(shí)：如果已經(jīng)找到由A到G的最短路線

4、是A—B1—C2—D1—E2—F2—G（圖中粗線，記作L），那么當(dāng)尋求L中的任何一點(diǎn)（如D1）到G的最短路時(shí)，它必然是L中的子路D1—E2—F2—G（記作L1）。因?yàn)榉駝t，若D1到G的最短路是另一條路線L2，則把A—B1—C2—D1與L2連接起來(lái)，就會(huì)得到一條不同于L的從A到G的最短路。根據(jù)最短路的這一特性，我們可以從最后一段開(kāi)始，用逐步向前遞推的方法，依次求出路段上各點(diǎn)到G的最短路，最后得到A到G的最短路。10/3/20215具體實(shí)施如下：從A到G要走6個(gè)路段，是一個(gè)6階段決策問(wèn)題，記k=1，

5、2，…，6。用dk（xk，xk+1）表示第k段的點(diǎn)xk與第k+1段的點(diǎn)xk+1之間的（已知）距離（視k的不同，x分別代表A，B，…，F(xiàn)），用uk（xk）表示在xk的決策，即從xk向哪一點(diǎn)走，則xk+1可以記作xk+1=uk（xk）。設(shè)xk到終點(diǎn)G的最短距離為fk（xk），則k=6時(shí)，f(F1)=4,f(F2)=3,顯然u(F1)=G,u(F2)=G,k=5時(shí)，f5(E1)=min=min=7表明E1到G的最短路是E1—F1—G，即E1的最優(yōu)決策為u(E1)=。10/3/20216表明E2到G的最

6、短路是E2－F2－G，即E2的最優(yōu)決策為u5（E2）=F2。同法計(jì)算出f5(E3)=9，u5（E3）=F2，10/3/20217k=3時(shí)，k=2時(shí),f2(B1)=13,u2(B1)=C2f2(B2)=16,u2(B2)=C3k=1時(shí),f1(A)=18,u1(A)=B1,于是從A到G的最短距離為f1(A)=18，而最短路線則由A開(kāi)始順次找出最優(yōu)決策來(lái)確定，即u1(A)=B1，u2(B1)=C2,u3(C2)=D1，u4(D1)=E2，u5(E2)=F2，u6(F2)=G，最短路線為A——B1——C

7、2——D1——E2——F2——G。10/3/20218不難看出，上述計(jì)算過(guò)程可以表示為如下的一般形式：(1)其中D（x）表示在x的允許決策集合，如D2（B1）=（C1，C2，C3)，X表示第k段的允許狀態(tài)集合，如X2=(B1，B2）。當(dāng)按（1）式由k=6逆推至k=1時(shí)，就得到了最短距離，而最短路線由順推的最優(yōu)決策確定。在動(dòng)態(tài)規(guī)劃中f（x）稱最優(yōu)值函數(shù)，（1）式稱最優(yōu)方程。10/3/20219需要指出，上例只是最短路問(wèn)題的一種形式，實(shí)際問(wèn)題中可以有多種形式，如：1）路線數(shù)目不定，如圖3，求任一點(diǎn)（

8、如B）到E的最短路線（不論它由幾段組成）；2）有向路網(wǎng)，如圖4，求V1到V6的有向最短路；3）旅行商問(wèn)題，如圖3，求從A點(diǎn)出發(fā)，經(jīng)每點(diǎn)一次又回到A點(diǎn)的最短路。EDABCV4V5V6V3V1V22535267510.528723116310圖３　　　　　　　　　　　　圖４10/3/202110下面介紹動(dòng)態(tài)規(guī)劃相關(guān)的基本概念及其數(shù)學(xué)描述（1）階段整個(gè)問(wèn)題的解決可分為若干個(gè)相互聯(lián)系的階段依次進(jìn)行。通常按時(shí)間或空間劃分階段，描述階段的變量稱為階段變量，記為。（2）狀態(tài)狀態(tài)表示每個(gè)階段開(kāi)始時(shí)所處的自然狀況