資源描述：
《動態(tài)規(guī)劃模型舉例》由會員上傳分享，免費在線閱讀，更多相關內容在教育資源-天天文庫。
1、§6動態(tài)規(guī)劃模型舉例10/16/20211以上討論的優(yōu)化問題大多數(shù)屬于靜態(tài)的，即不必考慮時間的變化，建立的模型——線性規(guī)劃、非線性規(guī)劃、整數(shù)規(guī)劃等，都屬于靜態(tài)規(guī)劃。多階段決策屬于動態(tài)優(yōu)化問題，即在每個階段（通常以時間或空間為標志）要根據(jù)過程的演變情況確定一個決策，使全過程的某個指標達到最優(yōu)。例如：（1）化工生產過程中包含一系列的過程設備，如反應器、蒸餾塔、吸收器等，前一設備的輸出為后一設備的輸入。因此，應該如何控制生產過程中各個設備的輸入和輸出，使總產量最大。（2）發(fā)射一枚導彈去擊中運動的目標，由于目標的行動是不斷改變的，因此應當如何根據(jù)目標運動的情況，不斷地決定導彈飛行的方向和速度，使
2、之最快地命中目標。10/16/20212（3）汽車剛買來時故障少、耗油低，出車時間長，處理價值和經濟效益高。隨著使用時間的增加則變得故障多，油耗高，維修費用增加，經濟效益差。使用時間俞長，處理價值也俞低。另外，每次更新都要付出更新費用。因此，應當如何決定它的使用年限，使總的效益最佳。動態(tài)規(guī)劃模型是解決這類問題的有力工具。下面結合具體例子闡述建立動態(tài)規(guī)劃模型的思路。例13最短路問題。圖2是一個線路網，連線上的數(shù)字表示兩點之間的距離（或費用），尋找一條由A到G的路線，使距離最短（或費用最省）。10/16/20213解：用窮舉法當然可以解決這個問題。不難算出，一共有48條從A到G的路線，用加法
3、得到每條路線的長度后，再作比較即可找出最短路線。顯然當路段很多時，計算工作量將是很大的。AB1B2C1C2C3C4D3D2D1E1E2E3F1F2G531368768433538622123366255343圖２10/16/20214用動態(tài)規(guī)劃解決問題的思路，來源于生活中這樣一個基本常識：如果已經找到由A到G的最短路線是A—B1—C2—D1—E2—F2—G（圖中粗線，記作L），那么當尋求L中的任何一點（如D1）到G的最短路時，它必然是L中的子路D1—E2—F2—G（記作L1）。因為否則，若D1到G的最短路是另一條路線L2，則把A—B1—C2—D1與L2連接起來，就會得到一條不同于L的從A
4、到G的最短路。根據(jù)最短路的這一特性，我們可以從最后一段開始，用逐步向前遞推的方法，依次求出路段上各點到G的最短路，最后得到A到G的最短路。10/16/20215具體實施如下：從A到G要走6個路段，是一個6階段決策問題，記k=1，2，…，6。用dk（xk，xk+1）表示第k段的點xk與第k+1段的點xk+1之間的（已知）距離（視k的不同，x分別代表A，B，…，F(xiàn)），用uk（xk）表示在xk的決策，即從xk向哪一點走，則xk+1可以記作xk+1=uk（xk）。設xk到終點G的最短距離為fk（xk），則k=6時，f(F1)=4,f(F2)=3,顯然u(F1)=G,u(F2)=G,k=5時，f5
5、(E1)=min=min=7表明E1到G的最短路是E1—F1—G，即E1的最優(yōu)決策為u(E1)=。10/16/20216表明E2到G的最短路是E2－F2－G，即E2的最優(yōu)決策為u5（E2）=F2。同法計算出f5(E3)=9，u5（E3）=F2，10/16/20217k=3時，k=2時,f2(B1)=13,u2(B1)=C2f2(B2)=16,u2(B2)=C3k=1時,f1(A)=18,u1(A)=B1,于是從A到G的最短距離為f1(A)=18，而最短路線則由A開始順次找出最優(yōu)決策來確定，即u1(A)=B1，u2(B1)=C2,u3(C2)=D1，u4(D1)=E2，u5(E2)=F2，
6、u6(F2)=G，最短路線為A——B1——C2——D1——E2——F2——G。10/16/20218不難看出，上述計算過程可以表示為如下的一般形式：(1)其中D（x）表示在x的允許決策集合，如D2（B1）=（C1，C2，C3)，X表示第k段的允許狀態(tài)集合，如X2=(B1，B2）。當按（1）式由k=6逆推至k=1時，就得到了最短距離，而最短路線由順推的最優(yōu)決策確定。在動態(tài)規(guī)劃中f（x）稱最優(yōu)值函數(shù)，（1）式稱最優(yōu)方程。10/16/20219需要指出，上例只是最短路問題的一種形式，實際問題中可以有多種形式，如：1）路線數(shù)目不定，如圖3，求任一點（如B）到E的最短路線（不論它由幾段組成）；2）
7、有向路網，如圖4，求V1到V6的有向最短路；3）旅行商問題，如圖3，求從A點出發(fā)，經每點一次又回到A點的最短路。EDABCV4V5V6V3V1V22535267510.528723116310圖３ 圖４10/16/202110下面介紹動態(tài)規(guī)劃相關的基本概念及其數(shù)學描述（1）階段整個問題的解決可分為若干個相互聯(lián)系的階段依次進行。通常按時間或空間劃分階段，描述階段的變量稱為階段變量，記為。（2）狀態(tài)狀態(tài)表示每個階段
