【正文】 1 第六章 動態(tài)規(guī)劃 (Dynamic Programming) 教學(xué)要求： ?了解 動態(tài)規(guī)劃的基本思想 ?掌握 一維離散動態(tài)規(guī)劃的建模和求解方法應(yīng)用 ?會運用動態(tài)規(guī)劃方法解決一些基本應(yīng)用問題。 2 動態(tài)規(guī)劃是運籌學(xué)的一個分支，是求解多階段決策過程最優(yōu)化問題的數(shù)學(xué)方法。 動態(tài)規(guī)劃在經(jīng)濟管理、工程技術(shù)、工農(nóng)業(yè)生產(chǎn)及軍事部門中都有著廣泛的應(yīng)用，并且獲得了顯著的效果。 學(xué)習(xí)動態(tài)規(guī)劃，首先要了解多階段決策問題。 167。 動態(tài)規(guī)劃原理和模型 3 例 1：最短路徑問題 ：給定一個交通網(wǎng)絡(luò)圖如下，其中兩點之間的數(shù)字表示距離（或運費），試求從 A點到 G點的最短距離（總運輸費用最?。?。 1 2 3 4 5 6 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 3 4 用窮舉法的計算量 :從 A到 G的 6個階段，一共有 48條路線，比較 47次。 48122232 ??????5 例 2：背包問題 有一個徒步旅行者，其可攜帶物品重量的限度為 a 公斤，設(shè)有 n 種物品可供他選擇裝入包中。已知每種物品的重量及使用價值（作用），問此人應(yīng)如何選擇攜帶的物品（各幾件），使其背包所起作用（使用價值）最大？ 物品 1 2 … j … n 重量（ 公斤 /件 ） a1 a2 … aj … an 每件使用價值 c1 c2 … cj … 類似的還有工廠里的下料問題、運輸中的貨物裝載問題、人造衛(wèi)星內(nèi)的物品裝載問題等。 6 生產(chǎn)決策問題 ：企業(yè)在生產(chǎn)過程中，由于需求是隨時間變化的，因此企業(yè)為了獲得全年的最佳生產(chǎn)效益，就要在整個生產(chǎn)過程中逐月或逐季度地 根據(jù)庫存和需求決定生產(chǎn)計劃。 機器負荷分配問題 ：某種機器可以在高低兩種不同的負荷下進行生產(chǎn) 。 要求制定一個五年計劃 ， 在 每年開始時 ， 決定如何重新分配 完好的 機器在兩種不同的負荷下生產(chǎn)的數(shù)量 ， 使在五年內(nèi)產(chǎn)品的總產(chǎn)量達到最高 。 航天飛機飛行控制問題 ：由于航天飛機的運動的環(huán)境是不斷變化的，因此就要根據(jù)航天飛機飛行在不同環(huán)境中的情況，不斷地決定航天飛機的飛行方向和速度（狀態(tài)），使之能最省燃料和完成飛行任務(wù)（如軟著陸）。 7 ? 根據(jù)過程的特性可以將過程按空間、時間等標志分為若干個互相聯(lián)系又互相區(qū)別的階段。 ? 在每一個階段都需要做出決策，從而使整個過程達到最好的效果。 ? 各個階段決策的選取不是任意確定的，它依賴于當(dāng)前面臨的狀態(tài)，又影響以后的發(fā)展。 ? 當(dāng)各個階段的決策確定后，就組成了一個決策序列，因而也就決定了整個過程的一條活動路線，這樣的一個前后關(guān)聯(lián)具有鏈狀結(jié)構(gòu)的多階段過程就稱為多階段決策問題。 多階段決策過程： 8 針對多階段決策過程的最優(yōu)化問題，美國數(shù)學(xué)家 Bellman等人在 20世紀 50年代初提出了著名的最優(yōu)化原理， 把多階段決策問題轉(zhuǎn)化為一系列單階段最優(yōu)化問題 ，從而逐個求解， 創(chuàng)立了解決這類過程優(yōu)化問題的新方法：動態(tài)規(guī)劃。 對最佳路徑（最佳決策過程）所經(jīng)過的各個階段，其中每個階段始點到全過程終點的路徑，必定是該階段始點到全過程終點的一切可能路徑中的最佳路徑（最優(yōu)決策），這就是 Bellman提出的著名的最優(yōu)化原理。 簡言之， 一 個最優(yōu)策略的子策略必然也是最優(yōu)的 。 Bellman在 1957年出版的 《 Dynamic Programming》 是動態(tài)規(guī)劃領(lǐng)域的第一本著作。 9 動態(tài)規(guī)劃的基本概念 ? 最短路問題： 某運輸公司擬將一批貨物從 A地運往 E地，其間的交通系統(tǒng)網(wǎng)絡(luò)如下圖所示。圖上節(jié)點表示地點，邊表示兩地之間的道路，邊上的數(shù)字表示兩地間的運輸費用，求運輸費用最低的運輸路線。 A B1 B2 B3 C1 C2 C3 D1 D2 E 第 2階段 第 3階段 第 4階段 第 1階段的狀態(tài) 決策： 某階段狀態(tài)給定之后，從該狀態(tài)演變到下一階段某一狀態(tài)的選擇。比如從第一階段到第二階段選擇什么路線。 策略： 各階段決策確定后，組成的一個有序的決策序列。 第 2階段的狀態(tài) 第 1階段 一、動態(tài)規(guī)劃的基本概念 10 階段 （ k） 將所給問題的過程 ， 按時間或空間特征分解成若干相互聯(lián)系的階段 ， 以便按次序求解 。 狀態(tài) sk 能表示決策順序的離散的量 ， 階段可以確定地表示決策過程當(dāng)前特征的量 。 狀態(tài)可以是數(shù)量 ， 也可以是字符 ， 數(shù)量狀態(tài)可以是連續(xù)的 ， 也可以是離散的 。 11 決策 uk 從某一狀態(tài)向下一狀態(tài)過渡時所做的選擇 。表示決策的變量為決策變量 ， 用 uk(sk)表示第 k階段 ， 狀態(tài)為 sk時的決策變量 。 決策允許集合 Dk(sk)：在狀態(tài) sk下 ， 允許采取決策的全體 。 策略 Pk,n(sk) 從第 k階段開始到最后第 n階段的決策序列 ，稱 k子策略 。 PA,E(s1)即為全過程策略 。 12 狀態(tài)轉(zhuǎn)移方程 是確定過程由階段的一個狀態(tài)到下一階段另一狀態(tài)下的演變過程 ， 用公式 sk+1=Tk(sk, uk)表示 。 該公式描述了由第 k階段到第 k+1階段的 狀態(tài)轉(zhuǎn)移規(guī)律 。 13 階段指標函數(shù) vk(sk, uk) 從狀態(tài) sk出發(fā) ， 選擇決策 uk所產(chǎn)生的第 k階段指標 。 過程指標函數(shù) Vk,n(sk, uk, uk+1,… , un)：從狀態(tài) sk出發(fā) ，選擇決策 uk, uk+1, … , un所產(chǎn)生的過程指標 。 動態(tài)規(guī)劃要求過程指標具有可分離性 ， 即 Vk,n(sk, uk, uk+1, … , un) = Vk(sk, uk)+Vk+1(sk+1, uk+1, … , un) 稱指標具有可加性 。 Vk,n(sk, uk, uk+1, … , un) = Vk(sk, uk) Vk+1(sk+1, uk+1, … , un) 稱指標具有可乘性 。 14 基本方程 最優(yōu)指標函數(shù) fk(sk)：從狀態(tài) sk出發(fā) ， 對所有的策略Pk,n， 過程指標 Vk,n的最優(yōu)值 ， 即 )},({)( ,)(nkknksDxkk PsVsf optkkk ??15 對于可加性指標函數(shù) ， 上式可以寫為 上式中 “ opt”表示 “ max”或 “ min”。 對于可乘性指標函數(shù) ，上式可以寫為 以上式子稱為動態(tài)規(guī)劃最優(yōu)指標的 遞推方程 ， 是動態(tài)規(guī)劃的基本 方程 。 終端條件 ： 為了使以上的遞推方程有遞推的起點 ， 必須要設(shè)定最優(yōu)指標的終端條件 ， 一般最后一個狀態(tài) n+1下最優(yōu)指標 ， fn+1(sn+1) = 0。 nksfusvsf kkkkksDxkk optkkk,2,1)}(),({)( 11)(???? ???nksfusvsf kkkkksDxkk optkkk,2,1)}(),({)( 11)(???? ???16 例 3：某公司打算在三個不同的地區(qū)設(shè)置四個銷售點，據(jù)市場預(yù)測部門估計，在不同的地區(qū)設(shè)置不同數(shù)量的銷售點，每月可獲得的利潤如下表所示。試問在各個地區(qū)應(yīng)該如何設(shè)置銷售點，才能使每月獲得的總利潤最大？其值是多少？請用動態(tài)規(guī)劃方法分析求解。 地區(qū) 銷售點 0 1 2 3 4 A 0 3 6 8 10 B 0 4 5 8 11 C 0 6 7 9 12 各地區(qū)不同銷售點數(shù)量利潤表（單位：百萬元） 17 解：根據(jù)多階段決策問題的特征，將此問題轉(zhuǎn)化為三個階段的決策問題。 1. 階段 k = 1， 2， 3，分別代表 A， B， C三地區(qū)。 2. 狀態(tài)變量 Sk：表示第 k個地區(qū)設(shè)置銷售點時還可 設(shè)置的銷售點數(shù)量。 3. 決策變量 Uk：表示第 k個地區(qū)的銷售點數(shù)量。 6. 最優(yōu)指標函數(shù) f（ Sk）。 4. 狀態(tài)轉(zhuǎn)移方程： Sk+1 = Sk Uk 。 5. 階段指標值：利潤如表 V（ Sk ， Uk）。 18 7. 動態(tài)遞推方程： f（ Sk） = Max ? V（ Sk ， Uk） + f（ Sk+1） ? k = 2， 1 f（ S3） = Max ? V（ S3 ， U3） ? 19 階段 k =3 V（ S3 ， U3） f（ S3） U3 * U3 = 0 U3 = 1 U3 = 2 U3 = 3 U3=4 S3 = 0 0 0 0 S3 = 1 0 6 6 1 S3 = 2 0 6 7 7 2 S3 = 3 0 6 7 9 9 3 S3= 4 0 6 7 9 12 12 4 8. 逆序遞推求解動態(tài)方程： 表 1 20 階段 k =2 V（ S2 ， U2） + f（ S3） f（ S2） U2 * U2 = 0 U2 = 1 U2 = 2 U2 = 3 U2=4 S2 = 0 0 + 0 0 0 S2 = 1 0 + 6 4 + 0 6 0 S2 = 2 0 + 7 4 + 6 5 + 0 10 1 S2 = 3 0 + 9 4 + 7 5 + 6 8 + 0 11 1， 2 S2=4 0 + 12 4 + 9 5 + 7 8 + 6 12 + 0 14 3 表 2 21 階段 k =1 V（ S1 ， U1） + f（ S2） f（ S1） U1 * U1 = 0 U1 = 1 U1 = 2 U1 = 3 U1=4 S1 = 4 0 + 14 3 + 11 6 + 10 8 + 6 10+0 16 2 決策方案： 地區(qū) A——設(shè)置 2個銷售點； 地區(qū) B——設(shè)置 1個銷售點； 地區(qū) C——設(shè)置 1個銷售點。 此時公司可以獲得最大總利潤 16（百萬元）。 表 3 22 例 2： 從 A 地到 E 地要鋪設(shè)一條煤氣管道 ,其中需經(jīng)過三級中間站，兩點之間的連線上的數(shù)字表示距離，如圖所示。問應(yīng)該選擇什么路線，使總距離最短？ A B2 B1 B3 C1 C3 D1 D2 E 5 2 14 1 12 6 10 10 4 3 12 11 13 9 6 5 8 10 5 2 1 C2 23 解： 整個計算過程分四個 階段 ，從最后一個階段開始。 第四階段（ D → E）： D 有兩條路線到終點 E 。 顯然有 A B2 B1 B3 C1 C3 D1 D2 E 5 2 14 1 12 6 10 10 4 3 12 11 13 9 6 5 8 10 5 2 1 C2 2)(。5)( 2414 ?? DfDf24 首先考慮經(jīng)過 的兩條路線 第三階段（ C → D）： C 到 D 有 6 條路線。 (最短路線為