【正文】 令： fk(x) 表示 以數(shù)量為 x 的資金分配給 前 k 個 工廠，所得到的最大利潤值。 總結(jié)： 解動態(tài)規(guī)劃的一般方法 :從終點逐段向始點方向?qū)ふ易钚?(大 )的方法。已知每種物品的重量及使用價值（作用），問此人應(yīng)如何選擇攜帶的物品（各幾件），使背包其所起作用（使用價值）最大？ 物品 1 2 … j … n 重量（ 公斤 /件 ） a1 a2 … aj … an 每件使用價值 c1 c2 … cj … 一、背包問題 167。 167。 ? 根據(jù)以上對狀態(tài)變量和決策變量的規(guī)定，有： ),(1 kkk usTs ??kkk uss ??? 142 ? 5. 確定邊界條件 ? 過程開始和結(jié)束的狀態(tài)。同時還要狀態(tài)滿足無后效性，即若已知過程現(xiàn)在處于某一階段的某一狀態(tài)，則該階段以后過程的演變，不再受以前各階段狀態(tài)的影響。描述階段的變量稱為階段變量，常用自然數(shù) k表示。現(xiàn)把這批研制費分配給各新產(chǎn)品（不分配、分配給 1萬元或分配給 2萬元），使這三種新產(chǎn)品都研制成功的概率最大。 ? 動態(tài)規(guī)劃方法只適用于求解具有無后效性狀態(tài)的多階段決策問題。 33 動態(tài)規(guī)劃適用于求解哪一類問題？ ? 每個階段的最優(yōu)決策過程只與本階段的初始狀態(tài)有關(guān)，而與以前各階段的決策（即為了到達本階段的初始狀態(tài)而采用哪組決策路線無關(guān)）。也就是說， 一個最優(yōu)策略的子策略也是最優(yōu)的 。其特點在于， 它可以把一個 n 維決策問題變換為幾個一維最優(yōu)化問題 ，從而一個一個地去解決。5)( 2414 ?? DfDf24 首先考慮經(jīng)過 的兩條路線 第三階段（ C → D）： C 到 D 有 6 條路線。 表 3 22 例 2： 從 A 地到 E 地要鋪設(shè)一條煤氣管道 ,其中需經(jīng)過三級中間站，兩點之間的連線上的數(shù)字表示距離，如圖所示。 4. 狀態(tài)轉(zhuǎn)移方程： Sk+1 = Sk Uk 。 1. 階段 k = 1， 2， 3，分別代表 A， B， C三地區(qū)。 終端條件 ： 為了使以上的遞推方程有遞推的起點 ， 必須要設(shè)定最優(yōu)指標的終端條件 ， 一般最后一個狀態(tài) n+1下最優(yōu)指標 ， fn+1(sn+1) = 0。 動態(tài)規(guī)劃要求過程指標具有可分離性 ， 即 Vk,n(sk, uk, uk+1, … , un) = Vk(sk, uk)+Vk+1(sk+1, uk+1, … , un) 稱指標具有可加性 。 12 狀態(tài)轉(zhuǎn)移方程 是確定過程由階段的一個狀態(tài)到下一階段另一狀態(tài)下的演變過程 ， 用公式 sk+1=Tk(sk, uk)表示 。表示決策的變量為決策變量 ， 用 uk(sk)表示第 k階段 ， 狀態(tài)為 sk時的決策變量 。 第 2階段的狀態(tài) 第 1階段 一、動態(tài)規(guī)劃的基本概念 10 階段 （ k） 將所給問題的過程 ， 按時間或空間特征分解成若干相互聯(lián)系的階段 ， 以便按次序求解 。圖上節(jié)點表示地點，邊表示兩地之間的道路，邊上的數(shù)字表示兩地間的運輸費用，求運輸費用最低的運輸路線。 對最佳路徑（最佳決策過程）所經(jīng)過的各個階段，其中每個階段始點到全過程終點的路徑，必定是該階段始點到全過程終點的一切可能路徑中的最佳路徑（最優(yōu)決策），這就是 Bellman提出的著名的最優(yōu)化原理。 ? 在每一個階段都需要做出決策，從而使整個過程達到最好的效果。 機器負荷分配問題 ：某種機器可以在高低兩種不同的負荷下進行生產(chǎn) 。 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次。 動態(tài)規(guī)劃在經(jīng)濟管理、工程技術(shù)、工農(nóng)業(yè)生產(chǎn)及軍事部門中都有著廣泛的應(yīng)用，并且獲得了顯著的效果。 2 動態(tài)規(guī)劃是運籌學(xué)的一個分支，是求解多階段決策過程最優(yōu)化問題的數(shù)學(xué)方法。 動態(tài)規(guī)劃原理和模型 3 例 1：最短路徑問題 ：給定一個交通網(wǎng)絡(luò)圖如下，其中兩點之間的數(shù)字表示距離（或運費），試求從 A點到 G點的最短距離（總運輸費用最?。? 6 生產(chǎn)決策問題 ：企業(yè)在生產(chǎn)過程中，由于需求是隨時間變化的，因此企業(yè)為了獲得全年的最佳生產(chǎn)效益，就要在整個生產(chǎn)過程中逐月或逐季度地 根據(jù)庫存和需求決定生產(chǎn)計劃。 7 ? 根據(jù)過程的特性可以將過程按空間、時間等標志分為若干個互相聯(lián)系又互相區(qū)別的階段。 多階段決策過程： 8 針對多階段決策過程的最優(yōu)化問題，美國數(shù)學(xué)家 Bellman等人在 20世紀 50年代初提出了著名的最優(yōu)化原理， 把多階段決策問題轉(zhuǎn)化為一系列單階段最優(yōu)化問題 ，從而逐個求解， 創(chuàng)立了解決這類過程優(yōu)化問題的新方法：動態(tài)規(guī)劃。 9 動態(tài)規(guī)劃的基本概念 ? 最短路問題： 某運輸公司擬將一批貨物從 A地運往 E地，其間的交通系統(tǒng)網(wǎng)絡(luò)如下圖所示。 策略： 各階段決策確定后，組成的一個有序的決策序列。 11 決策 uk 從某一狀態(tài)向下一狀態(tài)過渡時所做的選擇 。 PA,E(s1)即為全過程策略 。 過程指標函數(shù) Vk,n(sk, uk, uk+1,… , un)：從狀態(tài) sk出發(fā) ，選擇決策 uk, uk+1, … , un所產(chǎn)生的過程指標 。 對于可乘性指標函數(shù) ，上式可以寫為 以上式子稱為動態(tài)規(guī)劃最優(yōu)指標的 遞推方程 ， 是動態(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)化為三個階段的決策問題。 6. 最優(yōu)指標函數(shù) f（ Sk）。 此時公司可以獲得最大總利潤 16（百萬元）。 顯然有 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)(。 （最短距離為 19） 31 動態(tài)規(guī)劃是用來解決多階段決策過程最優(yōu)化的一種數(shù)量方法。 二 . 動態(tài)規(guī)劃的原理 最優(yōu)化原理： 作為整個過程的最優(yōu)策略具有這樣的性質(zhì)：無論過去的狀態(tài)和決策如何，相對于前面的決策所形成的狀態(tài)而言，余下的決策序列必然構(gòu)成最優(yōu)子策略。 即從邊界條件開始，逐段遞推尋優(yōu)，在每一個子問題的求解中，均利用了它前面的子問題的最優(yōu)化結(jié)果，依次進行，最后一個子問題所得的最優(yōu)解，就是整個問題的最優(yōu)解。 ? 具有這種性質(zhì)的狀態(tài)稱為無后效性（即馬爾科夫性）狀態(tài)。據(jù)估計，把增加的研制費用于各種新產(chǎn)品研制時，研制成功的概率見下表。一個階段表示需要做出一次決策的子問題，建立動態(tài)規(guī)劃模型要求每個階段問題具有同一模式。狀態(tài)必須包含表示系統(tǒng)情況和確定決策所需要的全部信息，使其能反映過程的演變特征。 把給第 K種新產(chǎn)品的研制費用的數(shù)量作為決策變量 uk, 顯然， uk不能超過當(dāng)時擁有的金額 sk 即： uk≤sk 41 ? 4. 建立狀態(tài)轉(zhuǎn)移方程 根據(jù)狀態(tài)變量和決策變量的含義，寫出狀態(tài) 轉(zhuǎn)移方程。 基本方程為 ? ???????? ??)(1)(1,2,3,)(),(m a x)(4411必然事件sfksfuspsf kkkkkkk44 第三階段 )}(),(m a x {)( 4433333 sfuspsf ?? 04 ?s 33 us ?? s3=0 ? s3=1 ? s3=2 } a x {)}0()0,0(m a x {)0( 433 ????? fpf 0*3 ?u} a x {)}0()1,1(m a x {)1( 433 ????? fpf 1*3 ?u} a x {)}0()2,2(m a x {)2( 433 ????? fpf *3 ?u第二階段 )}(),(m a x {)( 22322222 usfuspsf ???} a x {)}0()0,0(m a x {)0( 322 ????? fpf 0*2 ?u? s2=0 ? s2=1 ? s2=2 a x)11()1,1( )01()0,1(m a x)1(32322 ??????? ????????? ?? ??? fp fpf 0*2 ?um a x)22()2,2()12()1,2()02()0,2(m a x)2(3232322 ????????????????????????????????fpfpfpf 1*2 ?u第一階段 )}(),(m a x {)( 11111111 usfuspsf ???m a x)22()2,2()12()1,2()02()0,2(m a x)2(2121211 ????????????????????????????????fpfpfpf 0*1 ?u只有 S1=2 s2=s1u1* =20=2 s3=s2u2* =21=1 最優(yōu)解 011 從最后一個階段開始，逐階段向前，直至第一階段，即可求出全過程最優(yōu)策略和指標函數(shù)的最優(yōu)值。 第一階段 ? s2=0 ? s2=1 ? s2=2 )}(),(m a x {)( 1012121 sfuspsf ?? 1 ?s} a x {)}2()2,0(m a x {)0( 011 ????? fpf 2*1 ?u} a x {)}2()1,1(m a x {)1( 011 ????? fpf 1*1 ?u} a x {)}2()0,2(m a x {)2( 011 ????? fpf 0*1 ?u1*2 ?u第二階段 ? s3=0 ? s3=1 ? s3=2 )}(),(m a x {)( 2123232 sfuspsf ??m a x)2()2,0()1()1,0()0()0,0(m a x)0(1212122 ?????????????????????????????fpfpfpf 1*2 ?u a x)2()1,1( )1()0,1(m a x)1(12122 ???????????????????fpfpf} a x {)}2()0,2(m a x {)2( 122 ???? fpf 0*2 ?u22 uss ??第三階段 )}(),(m a x {)( 3234343 sfuspsf ?? 343 uss ?? 04?s