【正文】 一階段狀態(tài)作出的選擇 。 狀態(tài)應(yīng)描述過程特征 。 反映狀態(tài)變化的量叫做狀態(tài)變量 。 一個階段 ， 就是需要作出一個決策的子問題 ， 通常 ， 階段是按決策進(jìn)行的時間或空間上先后順序劃分的 。 它的基本思想是 ， 把一個比較復(fù)雜的問題分解為一系列同類型的更易求解的子問題 ， 便于應(yīng)用計算機(jī) 。 接著考慮階段 3上可能的狀態(tài) v5 ,v6 , v7 , 到 v10的最優(yōu)決策和最優(yōu)后繼過程 ． 在狀態(tài) V5上 ，雖然到 v8是 8， 到 v9是 9， 但是綜合考慮后繼過程整體最優(yōu) ， 取最優(yōu)決策是到 v9,最優(yōu)后繼過程是v5→ v9 → v10 ， 最短距離是 12． 同理 ， 狀態(tài) v6的最優(yōu)決策是至 v8 ； v7的最優(yōu)決策是到 v9 。 動態(tài)規(guī)劃方法尋求該最短路問題的基本思想是 ，首先將問題劃分為 4個階段 ， 每次的選擇總是綜合后繼過程的一并最優(yōu)進(jìn)行考慮 ， 在各段所有可能狀態(tài)的最優(yōu)后繼過程都已求得的情況下 ， 全程的最優(yōu)路線便也隨之得到 。 第一種方法稱做 全枚舉法 或 窮舉法 。但是 ， 按照網(wǎng)絡(luò)中點的分布 ， 可以把它分為 4個階段 ， 而作為多階段決策問題來研究 。 2)設(shè)備更新問題 ： 一般企業(yè)用于生產(chǎn)活動的設(shè)備 ， 剛買來時故障少 ， 經(jīng)濟(jì)效益高 ， 即使進(jìn)行轉(zhuǎn)讓 ， 處理價值也高 ， 隨著使用年限的增加 ， 就會逐漸變?yōu)楣收隙?，維修費用增加 ， 可正常使用的工時減少 ，加工質(zhì)量下降 ， 經(jīng)濟(jì)效益差 ， 并且 ， 使用的年限越長 、 處理價值也越低 ， 自然 ， 如果賣去舊的買新的 ， 還需要付出更新費 ． 因此就需要綜合權(quán)衡決定設(shè)備的使用年限 ， 使總的經(jīng)濟(jì)效益最好 。其特點在于，它可以把一個 n 維決策問題變換為幾個一維最優(yōu)化問題，從而一個一個地去解決。 動態(tài)規(guī)劃是現(xiàn)代企業(yè)管理中的一種重要決策方法，可用于最優(yōu)路徑問題、資源分配問題、生產(chǎn)計劃和庫存問題、投資問題、裝載問題、排序問題及生產(chǎn)過程的最優(yōu)控制等。 動態(tài)規(guī)劃方法簡介 動態(tài)規(guī)劃是解決多階段決策過程最優(yōu)化問題的一種方法。 一 .多階段決策過程最優(yōu)化 多階段決策過程 是指這樣一類特殊的活動過程，他們可以按時間順序分解成若干相互聯(lián)系的階段，在每個階段都要做出決策，全部過程的決策是一個決策序列，所以多階段決策問題也稱為序貫決策問題 。 需指出：動態(tài)規(guī)劃是求解某類問題的一種方法， 是考察問題的一種途徑 ，而不是一種算法。 3)連續(xù)生產(chǎn)過程的控制問題 ： 一般化工生產(chǎn)過程中 ， 常包含一系列完成生產(chǎn)過程的設(shè)備 ， 前一工序設(shè)備的輸出則是后一工序設(shè)備的輸入 ， 因此 ， 應(yīng)該如何根據(jù)各工序的運行工況 ， 控制生產(chǎn)過程中各設(shè)備的輸入和輸出 ， 以使總產(chǎn)量最大 。 以上所舉問題的發(fā)展過程都與時間因素有關(guān) ， 階段的劃分常取時間區(qū)段來表示 ，并且各個階段上的決策往往也與時間因素有關(guān) ， 這就使它具有了 “ 動態(tài) ” 的含義 ，所以把處理這類動態(tài)問題的方法稱為動態(tài)規(guī)劃方法 。 它的基本思想是列舉出所有可能發(fā)生的方案和結(jié)果 ，再對它們一一進(jìn)行比較 ， 求出最優(yōu)方案 。 為了找出所有可能狀態(tài)的最優(yōu)后繼過程 ， 動態(tài)規(guī)劃方法總是從過程的最后階段開始考慮 ， 然后逆著實際過程發(fā)展的順序 ，逐段向前遞推計算直至始點 。 同樣 ， 當(dāng)階段 3上所有可能狀態(tài)的最優(yōu)后繼過程都已求得后 ， 便可以開始考慮階段 2上所有可能狀態(tài)的最優(yōu)決策和最優(yōu)后繼過程 ， 如 v2的最優(yōu)決策是到 v5,最優(yōu)路線是 v2→ v5→ v9→ v10 ， 最短距離是 15…依此類推 ， 最后可以得到從初始狀態(tài) v1的最優(yōu) 決 策 是 到 v3 最 優(yōu) 路 線 是v1→ v3→ v7→ v9→ v10 ， 全程的最短距離是18。 整個求解過程分為兩個階段 ， 先按整體最優(yōu)的思想逆序地求出各個子問題中所有可能狀態(tài)的最優(yōu)決策與最優(yōu)路線值 ， 然后再順序地求出整個問題的最優(yōu)策略和最優(yōu)路線 。用以描述階段的變量叫作階段變量 ， 一般以 k表示階段變量 ． 階段數(shù)等于多段決策過程從開始到結(jié)束所需作出決策的數(shù)目 ， 圖 1所示的最短路問題就是一個四階段決策過程 ， 。 狀態(tài)變量必須包含在給定的階段上確定全部允許決策所需要的信息 。能直接或間接觀測 。 用以描述決策變化的量稱之決策變量 ， 和狀態(tài)變量一樣 ， 決策變量可以用一個數(shù) ， 一組數(shù)或一向量來描述 ， 也可以是狀態(tài)變量的函數(shù) ， 記以 uk= uk(sk)， 表示于階段 k狀態(tài) sk時的決策變量 。 系統(tǒng)狀態(tài)的這種轉(zhuǎn)移 ， 用數(shù)學(xué)公式描述即有： ))(,(1 kkkkk susTs ??(1) （ 五 ） 、 策略 策略 (Policy)也叫決策序列 ． 策略有全過程策略和 k部子策略之分 ， 全過程策略是指具有 n個階段的全部過程 ， 由依次進(jìn)行的 n個階段決策構(gòu)成 的 決 策 序 列 ， 簡 稱 策 略 ， 表示為p1,n{u1,u2,…,un}。 它是定義在全過程或各子過程或各階段上的確定數(shù)量函數(shù) 。 用vk(sk,uk)表示第 k段處于 sk狀態(tài)且所作決策為uk(sk)時的指標(biāo) ， 則它就是第 k段指標(biāo)函數(shù) 。一般把這種遞推關(guān)系稱為動 態(tài)規(guī)劃的函數(shù)基本方程。 一般地 ， 狀態(tài)變量的選擇是從過程演變的特點中尋找 。 以上五步是建立動態(tài)規(guī)劃數(shù)學(xué)模型的一般步驟。 第一階段（ C → D）： C 有三條路線到終點 D 。 ROADS(CITIES,CITIES)/ 1, 2 1, 3 2, 4 2, 5 2, 6 3, 4 3, 5 3, 6 4, 7 5, 7 6, 7/:D。 END lINGO程序 Feasible solution found. Total solver iterations: 0 Variable Value F( 1) F( 2) F( 3) F( 4) F( 5) F( 6) F( 7) D( 1, 2) D( 1, 3) D( 2, 4) D( 2, 5) D( 2, 6) D( 3, 4) D( 3, 5) D( 3, 6) D( 4, 7) D( 5, 7) D( 6, 7) Row Slack or Surplus 1 2 3 4 5 6 7 運行結(jié)果 練習(xí) 1： A B1 B2 C1 C2 C3 C4 D1 D2 D3 E1 E2 E3 F1 F2 G 5 3 1 3 6 8 7 6 3 6 8 5 3 3 8 4 2 2 2 1 3 3 3 5 2 5 6 6 4 最優(yōu)路線為： A → B1 → C2 → D1 → E2 → F2 → G 路長 ＝ 18 求從 A到 G的最短路徑 3 有資金 4萬元，投資 A、 B、 C三個項目，每個項目的投資效益與投入該項目的資金有關(guān)。 MATLAB優(yōu)化工具箱簡介 類 型 模 型 基本函數(shù)名 一元函數(shù)極小 m in F （ x ） . x1 x x 2 x=fmin bnd ( ‘ F ’ ,x1,x2) 無約束極小 m in F ( X ) X=fminu nc ( ‘ F ’ ,X0) X=fmins earch ( ‘ F ’ ,X0) 線性規(guī)劃 m in Xc T . AX ≤ b X=l inprog (c,A,b) 二次規(guī)劃 m in 21xTHx + cTx . Ax ≤ b X=q uad p rog (H,c, A,b) 約束極小 （非線性規(guī)劃） m in F ( X ) . G ( X ) ≤ 0 X= fmincon ( ‘ FG ’ ,X0) 達(dá)到目標(biāo)問題 m in r . F ( x ) wr ≤ goal X= fgoalattain ( ‘ F ’ ,x, goal,w) 極小極大問題 m in m ax { F i ( x )} x { Fi( x )} . G ( x ) ≤ 0 X= f min i max( ‘ FG ’ ,x0) 使用優(yōu)化函數(shù)或優(yōu)化工具箱中其他優(yōu)化函數(shù)時 , 輸入變量見下表 : 變量 描 述 調(diào)用函數(shù) f 線性規(guī)劃的目標(biāo)函數(shù) f X 或二次規(guī)劃的目標(biāo)函數(shù) XT H X + f X 中線性項的系數(shù)向量 linprog,quadprog fun 非線性優(yōu)化的目標(biāo)函數(shù) .f u n 必須為行命令對象或 M 文件、嵌入函數(shù)、或 MEX 文件的名稱 fminbnd,fminsearch,fminunc, fmincon ,lsqcurvefit,ls