1、第1，5章動態(tài)計劃，不要過河拆橋，第2，動態(tài)計劃動態(tài)計劃，50年代牙齒代表貝爾曼(B. E. Bellman)的研究結(jié)果可以歸結(jié)為一系列以長期利益為目標的決策最優(yōu)化原理，這是現(xiàn)代控制理論的一部分。5.1動態(tài)編程的最優(yōu)化原理和解決算法5.1.1牙齒多級決策過程的方法示例可以列舉20條路徑，例如5.1.1最短路問題、3、決策樹方法、最短路徑長度16，4、示例5.1.1最短路問題等。無論如何到達牙齒狀態(tài)，都可以從B向后搜索，以找到最短路徑、5，5.1.2動態(tài)計劃的基本概念和迭代公式、1，基本概念1)階段。將多階段決策問題分為互連的多個階段。通常，K是2)狀態(tài)，即每個階段開始時的狀態(tài)。一個階段的狀態(tài)由

2、狀態(tài)變量s k表示，k階段的所有狀態(tài)集由S k表示，每個階段的所有狀態(tài)集由S表示。s k S kS，動態(tài)計劃的狀態(tài)必須滿足非滯后性。3)決定：特定階段K狀態(tài)s k的決定用決定變量x k(s k)表示。K階段狀態(tài)s k的允許判定集由D k(s k)表示，K階段每個狀態(tài)的允許判定集由D k表示，所有階段每個狀態(tài)的允許判定集由D表示。x k(s k)d k(s k)d k d 4)策略。也就是說，從特定階段的特定狀態(tài)到端點按順序排列的決策組合的集合。Pk(s k)=x k(s k)、x k-1(s k-1)、x 1(s 1)表示從K階段狀態(tài)s k到端點的子策略。k階段狀態(tài)s k到端點允許的策略集為P

3、。Pk(s k)P。5)狀態(tài)轉(zhuǎn)移方程：反映兩個相鄰階段的狀態(tài)和決定變量之間的相互關(guān)系。s k-1=Tks k，x k(s k)=g(sk，x k)，6，5.1.2動態(tài)計劃的基本概念和迭代公式，6) 7)總效果函數(shù)：子戰(zhàn)略Pk(s k)的函數(shù)，從k階段狀態(tài)s k到結(jié)束Vk=Vk Pk(s k) 8)最佳效果函數(shù)：表示從特定階段的特定狀態(tài)采用最佳策略到終點的最佳效果值。2、記住最優(yōu)化原理和動態(tài)計劃迭代關(guān)系1、最優(yōu)化原理：最優(yōu)策略的子策略也是最優(yōu)的。2，遞歸關(guān)系：7，3，動態(tài)規(guī)劃階段，1)分割階段將研究的問題劃分為K階段，并對階段編號。通常使用逆向編號進行編號。2)正確識別狀態(tài)變量s k確定狀態(tài)變量

4、s k，以便同時說明過程的演變和非滯后性。3)寫決定變量x k(s k)和允許的決定集d k (s k)決定4)狀態(tài)轉(zhuǎn)移方程S K-1=G (S K，x k)。5)確定直接效果函數(shù)6)列出最佳金志洙函數(shù)的迭代關(guān)系7)邊界條件確定，8，5.2動態(tài)計劃模型示例，5.2.1資源分配問題示例5.2.1一家公司有4名在北京、上海和廣州三個市場銷售商品的銷售人員，在牙齒三個市場中職員數(shù)和收益的關(guān)系如表5.2.1銷售人員數(shù)和收益，解釋1，和收益的關(guān)系2，確定狀態(tài)變量s k狀態(tài)變量s k表示在步驟K開始時未分配的銷售人員數(shù)。顯然，s3=4、S2和S1的可能范圍為0 4。9，3，決策決策變量x k決策變量x k

5、表示分配給k階段市場的銷售人員數(shù)量。很明顯，x k s k4，根據(jù)確定狀態(tài)轉(zhuǎn)移方程之前定義的狀態(tài)變量s k和確定變量x k的含義，狀態(tài)轉(zhuǎn)移方程為S K-1=S K-X K。5.確定直接效果函數(shù)d k (s k，x k)表示在K階段初期，銷售人員數(shù)s k分配給K市場x k銷售人員時產(chǎn)生的直接效果。這些收益指標見表5.2.1。6.最佳指標函數(shù)是金志洙函數(shù)累積的形式，因為三個市場的總收益等于三個市場的總收益之和。因此，最佳金志洙函數(shù)為7，邊界條件F0 (s 0)=0。每個階段的計算過程是教材P(138139)，10，5.2.2項目選擇問題某工廠預(yù)計明年將有4個新項目A，B，C，D，每個項目的投資額w

6、k和投資后收益vk顯示在右側(cè)表格中。投資總額為30萬韓元，問如何選擇項目才能最大化總收益。上述問題的靜態(tài)計劃模型如下：這是0-1計劃問題。牙齒問題是經(jīng)典的旅行背包問題。牙齒問題是NP-complete，11。解決方案：項目選擇順序為A、B、C、D。步驟1K=1、2、3、4分別對應(yīng)于項目D、C、B、A的選擇過程2、K的狀態(tài)sk，表示步驟K開始時未分配的投資額3、K的決策變量xk。指示k階段項目是否被選定為4，狀態(tài)轉(zhuǎn)移表達式是否為SK1。Xk)=vk或0 6，總收益遞歸公式，牙齒問題的難點在于確定每個階段的狀態(tài)，隨著階段的增加，狀態(tài)數(shù)呈指數(shù)增長。以下使用決策樹確定每個步驟的可能狀態(tài)：12，13，5

7、.2.3生產(chǎn)和庫存管理問題一家工廠生產(chǎn)特定產(chǎn)品的月生產(chǎn)能力為10件，據(jù)了解，今后4個月的產(chǎn)品成本和銷售量列在表中。如果本月產(chǎn)量超過銷售量，可以儲存，以后每月銷售，一個產(chǎn)品的月存儲費為2元，制定每月生產(chǎn)計劃，1，保證滿足每月銷售量，計劃開始和期末庫存為0。2、計劃生產(chǎn)能力允許范圍內(nèi)的每月生產(chǎn)計劃，以最小化產(chǎn)品總成本(即生產(chǎn)成本存儲成本)。14，實例1產(chǎn)品生產(chǎn)計劃日程表，如果將xk設(shè)置為k階段生產(chǎn)，則直接成本dk(sk，xk)=CK xk 2sk狀態(tài)轉(zhuǎn)移公式sk-1=sk xk- yk總成本迭代公式，步驟1:(四月)邊界條件和狀態(tài)轉(zhuǎn)移公式s0=為了降低產(chǎn)品的次品率，為了最大限度地提高產(chǎn)品的成品率指

8、標，決定支出5萬韓元進行技術(shù)改造。目前提出了以下四個茄子改進方案：方案1:不支出，機器保持原狀。房間2:安裝監(jiān)視設(shè)備，每臺機器需要1萬韓元。房間3:安裝設(shè)備，每臺機器需要2萬元。方案4:同時安裝監(jiān)視和控制設(shè)備，每臺機器需要3萬元。采用各方案后，各機器的次品率如下表所示。16，5.2.5連續(xù)性變量動態(tài)計劃問題解決，計劃一家工廠全年生產(chǎn)某種產(chǎn)品A。那個第四季度的訂購量分別為600公斤、700公斤、500公斤、1200公斤。已知產(chǎn)品A的生產(chǎn)成本與產(chǎn)品的平方成正比，系數(shù)為0.005。工廠內(nèi)有可以存放商品的倉庫，倉儲費為每公斤一元。尋求最佳生產(chǎn)安排，將年度總成本降至最低。解決方案：第4季度包含4個步驟，

9、使用工序號和分支順序。如果將Sk設(shè)置為K季度現(xiàn)有量，則邊界條件設(shè)置為s1=s5=0，xk設(shè)置為K季度產(chǎn)量，yk設(shè)置為K季度訂貨量。Sk，xk，yk均為實數(shù)，狀態(tài)轉(zhuǎn)換方程sk 1=sk xk-yk仍使用反向遞歸，但步驟編號為正向目標函數(shù)17，生產(chǎn)庫存管理問題(連續(xù)變量)，步驟1:(第4季度)總效果F4 (SK解決方法：x4*)F4 *(S4)=0.005(1200 S4)2 S4=7200 11 S4 0.005 s42第二個X3)=0.005 x32 S3 F4 *(S4)S4=S3 X3 500至f3(s3X3*=800，S4 *=300X4*=900。20，5.2.6動態(tài)計劃方法非線性計劃解決，解決：這是資源分配問題。將分配順序設(shè)置為x1、x2、x3、階段向前編號，但反向迭代可以從約束條件中獲得邊界條件s1=27、s4=0。步驟3:(指定x3)，邊界條件和狀態(tài)切換方程式為s4=s3x3=0，即x3 *=s3是。因此，步驟2:(x2分配)，在狀態(tài)轉(zhuǎn)換方程中：s3=s2x2，替代表達式，21，5.2.6解析動態(tài)計劃方法非線性計劃，步驟1:(x1分配)2，fk*(sk)是從步驟k到步驟3的最佳1)狀態(tài)轉(zhuǎn)移方程式：sk=sk-1-xk-1，s1=10，s4=0 2) F3*(s3)=4x3=步驟4 S3 2 F2(S2)