運籌學(xué)-第七章-動態(tài)規(guī)劃

1、2022-3-812022-3-81Dynamic Programming，DP美國數(shù)學(xué)家貝爾曼美國數(shù)學(xué)家貝爾曼(Richard Bellman, 19201984)創(chuàng)始時間創(chuàng)始時間上個世紀上個世紀50年代年代創(chuàng)始人創(chuàng)始人 動態(tài)規(guī)劃是運籌學(xué)的主要分支之一動態(tài)規(guī)劃是運籌學(xué)的主要分支之一, , 是現(xiàn)代是現(xiàn)代企業(yè)管理中的一種重要決策方法企業(yè)管理中的一種重要決策方法, , 它是解決它是解決多階段決策過程多階段決策過程的一種最優(yōu)化方法的一種最優(yōu)化方法2022-3-82本章主要內(nèi)容本章主要內(nèi)容n多階段決策過程及其問題舉例多階段決策過程及其問題舉例 q最短路問題最短路問題n 動態(tài)規(guī)劃的基本概念和基本方程動態(tài)

2、規(guī)劃的基本概念和基本方程 n動態(tài)規(guī)劃應(yīng)用舉例動態(tài)規(guī)劃應(yīng)用舉例q資源分配問題資源分配問題q背包問題背包問題q生產(chǎn)庫存問題生產(chǎn)庫存問題q2022-3-837.1 多階段決策過程及其問題舉例多階段決策過程及其問題舉例n動態(tài)規(guī)劃研究的問題動態(tài)規(guī)劃研究的問題多階段決策問題多階段決策問題q在時間或空間上可以劃分為若干階段，每一階段都需要根在時間或空間上可以劃分為若干階段，每一階段都需要根據(jù)現(xiàn)階段的情況做出決策據(jù)現(xiàn)階段的情況做出決策q決策者每段決策時，不僅要考慮決策者每段決策時，不僅要考慮本階段目標最優(yōu)本階段目標最優(yōu)，還應(yīng)考，還應(yīng)考慮慮之后各階段之后各階段的目標最優(yōu)的目標最優(yōu)，最終達到整個決策活動的，最終達

3、到整個決策活動的總體總體目標最優(yōu)目標最優(yōu)q當(dāng)各個階段的決策確定后，就構(gòu)成了一個決策序列當(dāng)各個階段的決策確定后，就構(gòu)成了一個決策序列q各階段的決策一般與時間有關(guān)，故稱各階段的決策一般與時間有關(guān)，故稱“動態(tài)動態(tài)”。但某些。但某些“靜態(tài)靜態(tài)”問題可通過引進問題可通過引進“時間時間”因素，用動態(tài)規(guī)劃方法因素，用動態(tài)規(guī)劃方法來處理來處理12狀態(tài)狀態(tài)狀態(tài)狀態(tài)狀態(tài)狀態(tài)n狀態(tài)狀態(tài)決策決策決策決策決策決策狀態(tài)狀態(tài)2022-3-84n動態(tài)規(guī)劃分類：動態(tài)規(guī)劃分類：q離散確定性離散確定性動態(tài)規(guī)劃動態(tài)規(guī)劃q離散隨機性離散隨機性動態(tài)規(guī)劃動態(tài)規(guī)劃q連續(xù)確定性連續(xù)確定性動態(tài)規(guī)劃動態(tài)規(guī)劃q連續(xù)隨機性連續(xù)隨機性動態(tài)規(guī)劃動態(tài)規(guī)劃2

4、022-3-85GD76543358109745EABCHF例例1 最短路徑問題最短路徑問題 第一階段第一階段 第二階段第二階段 第三階段第三階段 第四階段第四階段 求從求從 A 到到 H 的最短路徑的最短路徑2022-3-862022-3-86n第一種方法第一種方法稱做稱做枚舉法枚舉法（窮舉法窮舉法）：基本思想是列舉出所基本思想是列舉出所有可能發(fā)生的方案和結(jié)果，再對它們進行比較，求出最優(yōu)有可能發(fā)生的方案和結(jié)果，再對它們進行比較，求出最優(yōu)方案。這里，從方案。這里，從 A A 到到 H H 的路程共有的路程共有7 7條可能的路線，分條可能的路線，分別算出各條路線的距離，最后進行比較，可得最優(yōu)路線

5、別算出各條路線的距離，最后進行比較，可得最優(yōu)路線 當(dāng)節(jié)點很多時，用窮舉法求最優(yōu)路線的計算工作量將會十當(dāng)節(jié)點很多時，用窮舉法求最優(yōu)路線的計算工作量將會十分龐大，而且其中包含著許多重復(fù)計算分龐大，而且其中包含著許多重復(fù)計算n第二種方法第二種方法熟稱熟稱貪心算法貪心算法，亦即，亦即“局部最優(yōu)路徑局部最優(yōu)路徑”法，只法，只選擇當(dāng)前最短途徑，選擇當(dāng)前最短途徑，“逢近便走逢近便走”，錯誤地以為局部最優(yōu)，錯誤地以為局部最優(yōu)會致整體最優(yōu)。在這種想法指導(dǎo)下，所取決策必是會致整體最優(yōu)。在這種想法指導(dǎo)下，所取決策必是 A C G H，距離為，距離為 4+5+8=172022-3-87d(sk, uk)：第第 k 階

6、階段，采取策略段，采取策略 uk 所發(fā)生的距離所發(fā)生的距離 fk(sk)：第第 k 階段，在階段，在 sk 狀態(tài)時到終點狀態(tài)時到終點 H 的最短距離的最短距離動態(tài)規(guī)劃的基本思想：動態(tài)規(guī)劃的基本思想：如果起點如果起點 A 經(jīng)過經(jīng)過 B, E 而到而到 H最優(yōu)，則最優(yōu)，則由由 B 出發(fā)經(jīng)出發(fā)經(jīng) E 到到 H 這條子路線，必為從這條子路線，必為從 B 到到 H 的最短路線。的最短路線。所以，尋找最短路線，應(yīng)該從最后一段開始找，然后往前遞推所以，尋找最短路線，應(yīng)該從最后一段開始找，然后往前遞推假設(shè)假設(shè) sk：第第 k 階段初所處的節(jié)點階段初所處的節(jié)點 uk(sk)：在在 sk 狀態(tài)時第狀態(tài)時第 k 階

7、段所作的決定階段所作的決定GD76543358109745EABCHF2022-3-88 f4(H)=0GD76543358109745EABCHF2022-3-89 f4(H)=0GD76543358109745EABCHF f3(E)=3343( )()()303( )fEd EHfHu EEH2022-3-810 f4(H)=0GD76543358109745EABCHF f3(E)=3 f3(F)=5FHFuHfHFdFf)(505)()()(3432022-3-811GHGuHfHGdGf)(508)()()(343 f4(H)=0GD76543358109745EABCHF f3(

8、E)=3 f3(F)=5 f3(G)=82022-3-812 f4(H)=0GD76543358109745EABCHF f3(E)=3 f3(F)=5 f3(G)=8 f2(B)=13BEBuFfFBdEfEBdBf)(1359310min)(),()(),(min)(23322022-3-813CECuGfGCdFfFCdEfECdCf)(10855637min)(),()(),()(),(min)(23332 f4(H)=0GD76543358109745EABCHF f3(E)=3 f3(F)=5 f3(G)=8 f2(B)=13 f2(C)=102022-3-814DFDuGfGDd

9、FfFDdDf)(88453min)(),()(),(min)(2332 f4(H)=0GD76543358109745EABCHF f3(E)=3 f3(F)=5 f3(G)=8 f2(B)=13 f2(C)=10 f2(D)=82022-3-815ACAuDfDAdCfCAdBfBAdAf)(1487104135min)(),()(),()(),(min)(12221 f4(H)=0GD76543358109745EABCHF f3(E)=3 f3(F)=5 f3(G)=8 f2(B)=13 f2(C)=10 f2(D)=8 f1(A)=142022-3-816 f4(H)=0GD7654

10、3358109745EABCHF f3(E)=3 f3(F)=5 f3(G)=8 f2(B)=13 f2(C)=10 f2(D)=8f1(A)=14狀態(tài)狀態(tài) 最優(yōu)決策最優(yōu)決策 狀態(tài)狀態(tài) 最優(yōu)決策最優(yōu)決策 狀態(tài)狀態(tài) 最優(yōu)決策最優(yōu)決策 狀態(tài)狀態(tài) A （ AC） C （CE） E （EH） H從從A到到H的最短路徑：距離為的最短路徑：距離為14，路線為，路線為ACEH 2022-3-8172022-3-817多階段決策過程及實例：標號法多階段決策過程及實例：標號法B1AC3F2F1E3E2E1D3D2D1C4C2C1B2G531368766835342138223335526643437597681

11、310912131618第一階段第一階段第二階段第二階段第三階段第三階段第四階段第四階段第五階段第五階段第六階段第六階段從從G到到A的解法稱為的解法稱為逆序解法逆序解法注：因為從注：因為從A A到到G G的最短路與從的最短路與從G G到到A A的最短路是一樣的，因此的最短路是一樣的，因此也可以從也可以從A A出發(fā)來找。從出發(fā)來找。從A A到到G G的解法稱為的解法稱為順序解法順序解法2022-3-8182022-3-818 綜上可見，綜上可見，全枚舉法全枚舉法雖可找出最優(yōu)方案，但不是好算法；雖可找出最優(yōu)方案，但不是好算法；局部最優(yōu)法局部最優(yōu)法則完全是個錯誤方法；只有則完全是個錯誤方法；只有動態(tài)

12、規(guī)劃方法動態(tài)規(guī)劃方法屬于屬于科學(xué)有效的算法。它的基本思想是，科學(xué)有效的算法。它的基本思想是，把一個比較復(fù)雜的問把一個比較復(fù)雜的問題分解為一系列同類型的更易求解的子問題題分解為一系列同類型的更易求解的子問題2022-3-8197.2 動態(tài)規(guī)劃的基本概念和基本方程動態(tài)規(guī)劃的基本概念和基本方程 ( (一一) ) 基本概念和基本方程基本概念和基本方程(1) 階段：階段：k = 1, , n(2) 狀態(tài)變量狀態(tài)變量 sk ：第第 k 階段的自然狀況階段的自然狀況 (3) 決策變量決策變量 uk(sk) ：第第 k 階段的決定階段的決定 Dk(sk) ：決策變量的取值范圍：決策變量的取值范圍GD76543

13、358109745EABCHF2022-3-820(4) 狀態(tài)轉(zhuǎn)移方程狀態(tài)轉(zhuǎn)移方程 sk1 T (sk, uk)：描述第描述第 k 階段與第階段與第 k+1 階段的狀態(tài)變量的關(guān)系階段的狀態(tài)變量的關(guān)系(5) 指標指標 v (sk ,uk) ：第第 k 階段在狀態(tài)階段在狀態(tài) sk 下采取決策下采取決策 uk 得到的得到的 結(jié)果（距離、得益、成本等）結(jié)果（距離、得益、成本等） 指標函數(shù)指標函數(shù)是指各階段指標的累計。即是指各階段指標的累計。即 V (sk,uk, , sn,un, sn+1)=vk(sk,uk)*vk+1(sk+1,uk+1)*vn(sn,un) 它表示從第它表示從第 k 階段的狀態(tài)階

14、段的狀態(tài) sk 開始到第開始到第 n 階段的終止狀態(tài)的指標階段的終止狀態(tài)的指標累計。式中累計。式中*表示某種運算符，一般為表示某種運算符，一般為加法加法或或乘積乘積運算運算(6) 最優(yōu)指標函數(shù)最優(yōu)指標函數(shù) fk (sk) ：它表示從第它表示從第 k 階段的狀態(tài)階段的狀態(tài) sk 開始到開始到 第第 n 階段終止的過程中，采取最優(yōu)策略得到的指標函數(shù)值階段終止的過程中，采取最優(yōu)策略得到的指標函數(shù)值 ),()(1,nkknkuukksusVOPTsfnk2022-3-8212022-3-821逆推公式逆推公式 fk(sk)OPT v(sk,uk)+ fk+1(sk+1) k =n, 1 fn+1(sn

15、+1)0或或 fk(sk)OPTv(sk ,uk)+ fk+1(sk+1) k =n-1, 1 fn(sn) OPTv(sn ,un) 多階段決策問題中，常見的目標函數(shù)形式之一是取多階段決策問題中，常見的目標函數(shù)形式之一是取各階段效各階段效益之和的形式益之和的形式。有些問題，如系統(tǒng)可靠性問題，其目標函數(shù)。有些問題，如系統(tǒng)可靠性問題，其目標函數(shù)是取是取各階段效益的連乘積形式各階段效益的連乘積形式?？傊?，具體問題的目標函數(shù)?？傊唧w問題的目標函數(shù)表達形式需要視具體問題而定表達形式需要視具體問題而定Max 或或 Min2022-3-822對例對例1(1) 階段：階段：k1,2,3(2) 狀態(tài)變量狀

16、態(tài)變量 sk ：第第 k 階段初所處的位置階段初所處的位置, 狀態(tài)集合狀態(tài)集合 Sk, 如如 S2 =B , C, D(3) 決策變量決策變量 uk ：在第在第 k 段段 sk 狀態(tài)時的路徑選擇狀態(tài)時的路徑選擇(4) 狀態(tài)轉(zhuǎn)移方程狀態(tài)轉(zhuǎn)移方程 ：sk1 uk (sk)2022-3-823(5) 指標：指標： vk (sk ，uk) 為第為第 k 階段階段采取決策采取決策 uk 時到下一狀態(tài)的距離時到下一狀態(tài)的距離 指標函數(shù)指標函數(shù)(6) 最優(yōu)指標函數(shù)：最優(yōu)指標函數(shù)： fk (sk)：第第 k 階段，在階段，在 sk 狀態(tài)時到終點狀態(tài)時到終點 H 的最短距離的最短距離,( ,)nk njijj

17、kVv s ufk(sk)min vk (sk,uk)+ fk+1(sk+1) k=3, 1f4(s4)02022-3-8242022-3-824（二）（二）貝爾曼貝爾曼最優(yōu)化原理最優(yōu)化原理最優(yōu)策略具有這樣的性質(zhì)：不論初始最優(yōu)策略具有這樣的性質(zhì)：不論初始狀態(tài)與初始策略如何，對于先前決策狀態(tài)與初始策略如何，對于先前決策所造成的狀態(tài)而言，余下所有決策必所造成的狀態(tài)而言，余下所有決策必構(gòu)成最優(yōu)決策。即：構(gòu)成最優(yōu)決策。即：最優(yōu)策略的子策最優(yōu)策略的子策略也是最優(yōu)的！略也是最優(yōu)的！A BMII II 2022-3-825（三）解法步驟（三）解法步驟q首先將問題劃分為若干個階段，然后選擇狀態(tài)變量與決首先將問

18、題劃分為若干個階段，然后選擇狀態(tài)變量與決策變量，并寫出轉(zhuǎn)移方程和指標函數(shù)，列出基本方程策變量，并寫出轉(zhuǎn)移方程和指標函數(shù)，列出基本方程q反向條件優(yōu)化反向條件優(yōu)化q正向求最優(yōu)解正向求最優(yōu)解fk(sk)OPT vk (sk,uk) + fk+1(sk+1) k=n, 1fn+1(sn+1)0fk(sk)OPT vk (sk,uk) fk+1(sk+1) k=n, 1fn+1(sn+1)12022-3-8267.3 應(yīng)用舉例應(yīng)用舉例例例2 資源分配問題資源分配問題()()例例3 資源分配問題資源分配問題()()例例4 背包問題背包問題例例5 生產(chǎn)庫存問題生產(chǎn)庫存問題例例6 可靠性問題可靠性問題例例7

19、機器負荷分配問題機器負荷分配問題2022-3-827例例 2 資源分配問題資源分配問題()()某公司準備將某公司準備將 5 臺設(shè)備分配給所屬的三個子工廠，各工廠臺設(shè)備分配給所屬的三個子工廠，各工廠獲得設(shè)備后的可盈利情況如表所示。獲得設(shè)備后的可盈利情況如表所示。問：如何分配這五臺問：如何分配這五臺設(shè)備，才能使公司獲得的收益最大？設(shè)備，才能使公司獲得的收益最大？ 工廠工廠 盈利（萬元）盈利（萬元）設(shè)備數(shù)設(shè)備數(shù)工廠工廠1工廠工廠2工廠工廠300001354271063101111412111251411122022-3-828分析分析(1) 階段：階段：k =1，2，3(3) 決策變量決策變量 uk

20、 ：對第對第 k 階段的分配數(shù)階段的分配數(shù)(2) 狀態(tài)變量狀態(tài)變量 sk ：可分配給第可分配給第 k 個至第個至第 3 個企業(yè)的個企業(yè)的 設(shè)備數(shù)（設(shè)備數(shù)（亦即第亦即第 k 階段初可供分配的設(shè)備數(shù)階段初可供分配的設(shè)備數(shù)）(4) 狀態(tài)轉(zhuǎn)移方程：狀態(tài)轉(zhuǎn)移方程： sk1 sk - uk(5) 指標函數(shù)指標函數(shù) gk (uk) ：分配分配 uk 臺設(shè)備給第臺設(shè)備給第 k 個工廠所產(chǎn)生個工廠所產(chǎn)生 的收益的收益(6) 最優(yōu)指標函數(shù)最優(yōu)指標函數(shù) fk (sk) ：第第 k 至至 第第 3 階段采取最優(yōu)階段采取最優(yōu) 分配策略可產(chǎn)生的最大收益分配策略可產(chǎn)生的最大收益2022-3-829 fk(sk) max g

21、k ( uk)+ fk+1(sk+1) （k = 3,2,1） f4(s4)0逆推公式：逆推公式：其中其中()kkkuD s(): 0kkkkD sus2022-3-8302022-3-830k=3, S3 = 0,1,2,3,4,5, f3(s3) maxg3(u3)+0g3(u3)+0max u3s3012345f3(s3)u3000010441204662304611113404611121245046111212124,5330su 2022-3-8312022-3-831k=2, S2 = 0,1,2,3,4,5, f2(s2) maxg2(u2)+ f3(s3)g2(u2)+ f3

22、(s3)max最優(yōu)最優(yōu)決策決策 u2s2012345f2(s2)u200+000(0,0)10+45+051(1,0)20+65+410+0102(2,0)30+115+610+411+0142(2,1)40+125+1110+611+411+0161,2(1,3) (2,2)50+125+1210+1111+611+411+0212(2,3)S3=S2-u3220su 2022-3-8322022-3-832g1(u1)+ f2(s2)max最優(yōu)決策最優(yōu)決策 u1s1012345f1(s1)u150+213+167+1410+1012+514+0210,2(0,2,3)(2,2,1)k=1,

23、 S1 = 5, f1(s1) max g1(u1)+ f2(s2)得到兩種方案：得到兩種方案：u1*0，u2*2，u3*3: 工廠工廠1分配分配0臺，工廠臺，工廠2 分配分配2臺，工廠臺，工廠3分配分配3臺臺u1*2，u2*2，u3*1: 工廠工廠1分配分配2臺，工廠臺，工廠2 分配分配2臺，工廠臺，工廠3分配分配1臺臺總盈利均為總盈利均為21萬元萬元2*2u5052s21*f3*3u3253s同理得到另一同理得到另一組最優(yōu)解組最優(yōu)解0*1u51s110su 2022-3-833一般分配問題一般分配問題某種資源的總量為某種資源的總量為 a，用于用于 n 種生產(chǎn)種生產(chǎn)若分配若分配 uk 于第于

24、第 k 種生產(chǎn)時，收益為種生產(chǎn)時，收益為 gk(xk) 問：應(yīng)如何分配才能使總收入最大？問：應(yīng)如何分配才能使總收入最大？該問題的數(shù)學(xué)模型為該問題的數(shù)學(xué)模型為Max z = g1 (u1 )+ g2 (u2 )+ gn (un) s.t. u1 +u2 +un= a uk0 2022-3-834分析分析 (1) 階段：階段：k =1，2，., n(3) 決策變量決策變量 uk ：對第對第 k 階段的分配數(shù)階段的分配數(shù)(2) 狀態(tài)變量狀態(tài)變量 sk ：第第 k 階段初可供分配的資源數(shù)階段初可供分配的資源數(shù)(4) 狀態(tài)轉(zhuǎn)移方程：狀態(tài)轉(zhuǎn)移方程： sk1 sk - uk(5) 指標函數(shù)指標函數(shù) gk (

25、uk) ：uk 臺設(shè)備分配給第臺設(shè)備分配給第 k 種生產(chǎn)所產(chǎn)生種生產(chǎn)所產(chǎn)生 的收益的收益(6) 最優(yōu)指標函數(shù)最優(yōu)指標函數(shù) fk (sk) ：第第 k 至至 n 階段采取最優(yōu)分配策階段采取最優(yōu)分配策 略可產(chǎn)生的最大收益略可產(chǎn)生的最大收益2022-3-835fk(sk) max gk ( uk)+ fk+1(sk+1) k = n,2,1 fn+1(sn+1)0逆推公式：逆推公式：kksu 02022-3-836例例3 資源分配問題資源分配問題()() 某工廠要進行某工廠要進行A,B,C三種新產(chǎn)品的試制，為提高三種產(chǎn)品三種新產(chǎn)品的試制，為提高三種產(chǎn)品研制成功的概率，決定調(diào)撥經(jīng)費研制成功的概率，決定

26、調(diào)撥經(jīng)費2百萬，并要求資金集中百萬，并要求資金集中使用，也即以百萬為單位進行分配，其增加研發(fā)費與新產(chǎn)使用，也即以百萬為單位進行分配，其增加研發(fā)費與新產(chǎn)品不成功概率的關(guān)系如表所示。品不成功概率的關(guān)系如表所示。問：如何分配資金，可使問：如何分配資金，可使三種產(chǎn)品都研制不成功的概率最??？三種產(chǎn)品都研制不成功的概率最?。?產(chǎn)品產(chǎn)品 不成功概率不成功概率費用（百萬）費用（百萬）ABC00.40.60.810.20.40.520.150.20.32022-3-837分析分析(1) 階段：階段：k = 1，2，3(3) 決策變量決策變量 uk ：對第對第 k 階段分配金額階段分配金額(2) 狀態(tài)變量狀態(tài)變量

27、 sk ：第第 k 階段初的可用金額階段初的可用金額(4) 狀態(tài)轉(zhuǎn)移方程：狀態(tài)轉(zhuǎn)移方程： sk1 sk - uk(5) 最優(yōu)指標函數(shù)最優(yōu)指標函數(shù) fk (sk) ：第第 k 至至 3 階段采取最優(yōu)階段采取最優(yōu) 分配策略時的最小不成功概率的值分配策略時的最小不成功概率的值2022-3-838 fk(sk) min gk ( uk) * fk+1(sk+1) k=3,2,1 f4(s4)1逆推公式：逆推公式：其中其中 gk (uk) 是階段函數(shù)是階段函數(shù)kksu 02022-3-839 u3s3g3(u3)minu3=0u3=1u3=2f3(s3)u*3(s3)00.80.8010.80.50.5

28、120.80.50.30.32k=3, S3 = 0,1,2, f3(s3) ming3(u3)*1330su 2022-3-840220su u2s2g2(u2)* f3(s3)minu2=0u2=1u2=2f2(s2)u*2(s2)00.6*0.80.48010.6*0.50.4*0.80.3020.6*0.30.4*0.50.2*0.80.162k=2, S2 = 0,1,2, f2(s2) ming2(u2)*f3(s3)2022-3-841g1(u1)* f2(s2)mins1 u1012f1(s1)u1* (s1)20.4*0.16=0.0640.2*0.3=0.060.15*0.

29、48=0.0720.061k=1, S1 = 2, f1(s1) max g1(u1)* f2(s2)得到方案：得到方案：u1*1，u2*0，u3*1: 產(chǎn)品產(chǎn)品 A分配分配 1百萬，產(chǎn)百萬，產(chǎn)品品 B分配分配0，產(chǎn)品，產(chǎn)品 C分配分配1百萬，百萬，f *=0.06110su 1*1u21s0*2u1122s06. 0*f1*3u0013s2022-3-842例例4 背包問題背包問題 某卡車載重能力為某卡車載重能力為10噸，現(xiàn)要裝三種產(chǎn)品，已知每件噸，現(xiàn)要裝三種產(chǎn)品，已知每件產(chǎn)品的重量和利潤如表。又規(guī)定產(chǎn)品產(chǎn)品的重量和利潤如表。又規(guī)定產(chǎn)品3至多裝至多裝2件。件。問：問：如何安排運輸可使總利潤最

30、大？如何安排運輸可使總利潤最大？產(chǎn)品種類產(chǎn)品種類 k重量重量 tk (噸噸/件件)利潤利潤 rk (元元/件件) 1 4 150 2 3 120 3 2 802022-3-843n階段：階段：k=1,2,3n狀態(tài)變量狀態(tài)變量 sk：第第 k 階段初的可裝載能力階段初的可裝載能力n決策變量決策變量 uk：第第 k 階段的裝載件數(shù)階段的裝載件數(shù)n狀態(tài)轉(zhuǎn)移方程：狀態(tài)轉(zhuǎn)移方程： （tk 為為 k 產(chǎn)品的單件重量）產(chǎn)品的單件重量）n最優(yōu)指標函數(shù)最優(yōu)指標函數(shù) fk(sk)：第第k-3階段采取最優(yōu)策略時的最大利潤階段采取最優(yōu)策略時的最大利潤n遞推公式：遞推公式： k=3,2,1 f4(s4)=0 kkkku

31、tss1()11()max ()kkkkkkkkDkusfsr ufs動態(tài)規(guī)劃方法求解動態(tài)規(guī)劃方法求解2022-3-844物品物品1物品物品2物品物品3k=1k=2k=3k=4s1=10s2s3s4階段階段狀態(tài)變量狀態(tài)變量：裝載前背包裝載前背包的容量的容量決策變量決策變量：裝載的件數(shù)裝載的件數(shù)u1u2u3決策允許集合決策允許集合：裝載件數(shù)的范圍裝載件數(shù)的范圍0u1s1/t1u1為整數(shù)為整數(shù)狀態(tài)轉(zhuǎn)移方程狀態(tài)轉(zhuǎn)移方程：背包容背包容量和裝載件數(shù)的關(guān)系量和裝載件數(shù)的關(guān)系階段指標階段指標： vk(sk,uk)=rkuk 在背包中第在背包中第k種物品的價值種物品的價值最優(yōu)指標最優(yōu)指標： fk(sk)=ma

32、xrkuk+fk+1(sk+1)終端條件終端條件：f4(s4)=0 s2s1-t1u1 s3=s2-t2u2 s4=s3-t3u30u2s2/t2u2為整數(shù)為整數(shù)0u3mins3/t3, 2u3為整數(shù)為整數(shù)2022-3-845nk =3 u3s3r3u3+0=80u3maxu3=0u3=1u3=2f3(s3)u3*010002308080141008016016023333333()0min,2 ,sDsuuut整0)()(max)(444433)(33333sfsfursfsDuC的單件重量為的單件重量為t3=2 2022-3-846) )=120u=120u2 2+f+f3 3(s(s2

33、2-3u-3u2 2) )u u2 2=2=2240+160240+160400400k=2：裝載物品：裝載物品B，f2(s2)B的單件重量為的單件重量為t2=32022-3-847u u1 1=0=00+4000+400k=1：裝載物品：裝載物品A， f1(u1)最優(yōu)解：物品最優(yōu)解：物品A裝裝0件，物品件，物品B裝裝2件，物品件，物品C裝裝2件件 最大價值為最大價值為400元元2*2u100102s400*f2*3u43*2103s0*1u101sA的單件重量為的單件重量為t1=42022-3-848 例例5 生產(chǎn)庫存問題生產(chǎn)庫存問題q某廠在年末估計，來年某廠在年末估計，來年4個季度市場對該

34、廠某產(chǎn)品的需求量個季度市場對該廠某產(chǎn)品的需求量均為均為 dk=3 (k=1, 2, 3, 4)，而該廠每季度生產(chǎn)此產(chǎn)品的能力為，而該廠每季度生產(chǎn)此產(chǎn)品的能力為 bk=5 (k=1, 2, 3, 4)q每季度生產(chǎn)該產(chǎn)品的固定成本為每季度生產(chǎn)該產(chǎn)品的固定成本為 F=13 (不生產(chǎn)時則為不生產(chǎn)時則為 0)，該產(chǎn)品的單位生產(chǎn)成本為該產(chǎn)品的單位生產(chǎn)成本為 C=2q如果當(dāng)季度產(chǎn)品不能售出，則需發(fā)生庫存費用如果當(dāng)季度產(chǎn)品不能售出，則需發(fā)生庫存費用 g=1/件，倉件，倉庫能貯存產(chǎn)品的最大數(shù)量庫能貯存產(chǎn)品的最大數(shù)量 Ek=4 (k=1, 2, 3, 4) q年初年末庫存為年初年末庫存為 0，而，而每個季度可以銷

35、售的產(chǎn)品是本季度初每個季度可以銷售的產(chǎn)品是本季度初的庫存及本季度的產(chǎn)量的庫存及本季度的產(chǎn)量 試問：在滿足市場需求的前提下，如何安排試問：在滿足市場需求的前提下，如何安排 4 個季度的生個季度的生產(chǎn)使生產(chǎn)和庫存的總費用最小產(chǎn)使生產(chǎn)和庫存的總費用最小?2022-3-849分析分析(1) 階段：階段：k = 1, 2, 3, 4(2) 狀態(tài)變量狀態(tài)變量 sk ：第第 k 季度初的庫存量季度初的庫存量(3) 決策變量決策變量 uk ：第第 k 個季度的產(chǎn)量個季度的產(chǎn)量(4) 轉(zhuǎn)移方程：轉(zhuǎn)移方程： sk1 sk +uk - dk(5) 最優(yōu)指標函數(shù)最優(yōu)指標函數(shù) fk (sk) ：第第 k 至第至第 4

36、個季度采取最優(yōu)策略個季度采取最優(yōu)策略 時的最小總費用時的最小總費用2022-3-850fk(sk)minwk(uk,sk)+fk+1(sk+1) k=4, 3, 2, 1f5(s5)041141max(0,)min(,)0min(,(),)kkkkkkkiki kkkkiiiii kdsub EdsdssEbdd逆推公式：逆推公式：0)(0)(kkkkkkkkkudusgCuFudsgwdk=3: 需求需求 bk=5: 生產(chǎn)能力生產(chǎn)能力F=13: 固定成本固定成本 C=2: 單位生產(chǎn)成本單位生產(chǎn)成本g=1: 單位庫存費用單位庫存費用 Ek=4: 倉庫儲存能力倉庫儲存能力()kkkuD s202

37、2-3-8511110()3,4,5sD s2022-3-852nk = 441141max(0,3)=max(0,)min(,)min(5,7,3)0min(,(),)min(4,6,3)kkkkkkkkikkki kkkkiiiii ksdsub EdsdssssEbdd u4s4w4+0min0123f4(s4)u4*0191931171722151513000()3,0()132(3),0kkkkkkkkkkkkkg sdsuwFCug sudusuu2022-3-853nk = 330min 4,4,64s3333max 0,3min 5,6,7suss3333333132(3),0

38、3,0usuuwsu u3s3w3+f4(s4)min012345f3(s3)u3*019+1922+1725+15383117+1920+1723+1526+0265215+1918+1721+1524+024430+1916+1719+1522+019041+1717+1520+01802022-3-854nk = 220min 4,2,9s22227 ,9 , 5min3 , 0maxssus030),3(2132222222usuusuw u2s2w2+f3(s3)min12345f2(s2)u2*019+3822+2625+24484117+3820+2623+2426+194552

39、15+3818+2621+2424+1927+184342022-3-855nk = 167*f u1s1w1+f2(s2)min345f1(s1)u1*019+4822+4525+43673, 40543*4*3*2*1uuuu3054*4*3*2*1uuuu1111111132(3),030usuuwsu2022-3-856可用總費用為可用總費用為 C，總重量為總重量為 Wck 為第為第 k 個部件裝配一個備用件的費用個部件裝配一個備用件的費用wk 為第為第 k 個部件裝配一個備用件的重量個部件裝配一個備用件的重量Pk 第第 k 個部件的故障概率個部件的故障概率某機器工作系統(tǒng)由某機器工作系

40、統(tǒng)由 n 個部件組成，這些部件正常工作關(guān)系個部件組成，這些部件正常工作關(guān)系為串聯(lián)。為提高系統(tǒng)工作的可靠性，考慮對每個部件都配為串聯(lián)。為提高系統(tǒng)工作的可靠性，考慮對每個部件都配備備用件。備用件越多，可靠性越大，但系統(tǒng)的成本、重備備用件。備用件越多，可靠性越大，但系統(tǒng)的成本、重量、體積都會變大。已知：量、體積都會變大。已知：例例6 可靠性問題可靠性問題問：在這兩個限制條件下，應(yīng)如何選用部件的備用件個數(shù)，問：在這兩個限制條件下，應(yīng)如何選用部件的備用件個數(shù)，使得正常工作的可靠性最大使得正常工作的可靠性最大？2022-3-857設(shè)設(shè) uk 為第為第 k 個部件裝配備用件的個數(shù)，個部件裝配備用件的個數(shù)，

41、dk(sk, uk) 為第為第 k 個個部件裝配部件裝配 uk 個備用件時機器正常工作的概率個備用件時機器正常工作的概率(,)1 ()kukkkkds uP 111max(,). .0nkkknkkknkkkkd s ustc uCw uWu為整數(shù)2022-3-858動態(tài)規(guī)劃模型動態(tài)規(guī)劃模型(1) 階段：階段：k = 1, 2, , n(3) 決策變量決策變量 uk ：第第 k 個部件上裝的備用件個數(shù)個部件上裝的備用件個數(shù)(2) 狀態(tài)變量狀態(tài)變量 sk ：第第 k 至第至第 n 個部件允許的總費用個部件允許的總費用(4) 狀態(tài)轉(zhuǎn)移：狀態(tài)轉(zhuǎn)移： sk+1 = sk - ckuk tk+1 = t

42、k - wkuk (5) 最優(yōu)指標函數(shù)最優(yōu)指標函數(shù) fk (sk , tk)：第第 k 至第至第 n 個部件，采取最個部件，采取最優(yōu)策略時機器正常工作的概率優(yōu)策略時機器正常工作的概率tk ：第第 k 至第至第 n 個部件允許的總重量個部件允許的總重量2022-3-859逆推公式：逆推公式：fk (sk, tk) = maxdk (sk, uk )* fk+1 (sk+1, tk+1) fn+1 (sn+1 , tn+1)=1 k=n, ,12022-3-860 某系統(tǒng)由某系統(tǒng)由 A, B, C 三個部分串聯(lián)而成，已知：三個部分串聯(lián)而成，已知： A、B、C 相互獨立相互獨立 各部分的單件故障率分

43、別為各部分的單件故障率分別為 P1=0.4， P2=0.2， P3=0.5 每個部分的單件價格為：每個部分的單件價格為：A 部分單價部分單價 c1=1 萬元；萬元； B 部分單價部分單價 c2=2 萬元；萬元；C 部分單價部分單價 c3=3 萬元萬元 可投資購置部件的金額為可投資購置部件的金額為10萬元萬元 問：問：A, B, C 三部分各應(yīng)購置多少部件才能使系統(tǒng)的總可三部分各應(yīng)購置多少部件才能使系統(tǒng)的總可靠率最大？（假設(shè)每部分至少購置一件）靠率最大？（假設(shè)每部分至少購置一件）2022-3-861n階段：階段：購置購置 A、B、C 分別為階段分別為階段1、2、3n狀態(tài)變量狀態(tài)變量 sk：第第

44、k 階段初可用來購買部件的費用階段初可用來購買部件的費用n決策變量決策變量 uk：第第 k 階段購置的件數(shù)階段購置的件數(shù)n狀態(tài)轉(zhuǎn)移方程：狀態(tài)轉(zhuǎn)移方程：sk+1 = sk - ckuk n指標函數(shù)：指標函數(shù)：第第 k 階段本身的可靠率階段本身的可靠率n最優(yōu)指標函數(shù)最優(yōu)指標函數(shù) fk(sk) ：第第 k 階段尚有資金階段尚有資金 sk 時可能獲得時可能獲得 的的最高可靠率最高可靠率n遞推方程遞推方程 fk(sk)= max dk(sk, uk)fk+1(sk+1) k=3,2,1 f4(s4)=1(,)1 ()kukkkkds uP ku2022-3-862第第3階段階段此時此時 C 應(yīng)至少配備應(yīng)

45、至少配備 1 個部件，故個部件，故 s2c3=3同時同時 A, B 部件已經(jīng)至少配備部件已經(jīng)至少配備 1個部件，故個部件，故 s210-c1-c2=7 u3s3u31u32f3(s3)=maxd3(s3,u3)u3*35670.50.51- -0.250.50.7512總費用：總費用：10 (萬元萬元)單價：單價：c1=1, c2=2, c3=3故障率：故障率：P1=0.4, P2=0.2, P3=0.53333443( ,)()1uds ufsP 2022-3-863第第2階段階段此時此時 B、C 應(yīng)至少各配制應(yīng)至少各配制 1 個部件，故個部件，故 s2c2+c3=2+3=5同時同時 A 部

46、件已經(jīng)至少配備部件已經(jīng)至少配備 1個部件，故個部件，故 s2101=9 u2s2u21u22u23f2(s2)u2*567890.80.50.80.50.80.750.80.750.960.50.960.50.960.50.9920.50.40.480.60.61211總費用：總費用：10 (萬元萬元)單價：單價：c1=1, c2=2, c3=3故障率：故障率：P1=0.4, P2=0.2, P3=0.5222233233(,)()(1)()uds ufsPfs2022-3-86461*283s第第1階段階段 u1s1u11u12u13u14u15f1(s1)u1*100.60.60.840.

47、60.9360.480.97440.40.990.40.50422*1u101s1*2u81*2102s504. 0*f*32u 111122122( ,)()(1)()uds ufsPfs總費用：總費用：10 (萬元萬元)單價：單價：c1=1, c2=2, c3=3故障率：故障率：P1=0.4, P2=0.2, P3=0.52022-3-865例例7 機器負荷分配問題機器負荷分配問題（其它情形之一）（其它情形之一） 某廠有某廠有 120 臺同一規(guī)格完好的機器，每臺機床全年臺同一規(guī)格完好的機器，每臺機床全年在高負荷下工作可創(chuàng)利在高負荷下工作可創(chuàng)利 9 萬元，但機器的報廢率高，萬元，但機器的報廢

48、率高，每年將有每年將有 的機器報廢；在低負荷下工作可創(chuàng)利的機器報廢；在低負荷下工作可創(chuàng)利 6 萬元，每年將有萬元，每年將有 的機器報廢的機器報廢 試擬定連續(xù)試擬定連續(xù) 3 年的分配計劃，使得總利潤最大年的分配計劃，使得總利潤最大 2022-3-866n階段：階段：k1、2、3n狀態(tài)變量狀態(tài)變量 sk：第第 k 階段完好的機器數(shù)量階段完好的機器數(shù)量n決策變量決策變量 uk：第第 k 階段用于高負荷工作的機器數(shù)量階段用于高負荷工作的機器數(shù)量n狀態(tài)轉(zhuǎn)移方程：狀態(tài)轉(zhuǎn)移方程：n指標函數(shù)：指標函數(shù)： n最優(yōu)指標函數(shù)最優(yōu)指標函數(shù) fk(sk)：第第 k 階段尚有機器數(shù)量為階段尚有機器數(shù)量為 sk 時可能時可

49、能獲得總收益獲得總收益n遞推方程：遞推方程：kkkkkksuusug63)(691 , 2 , 30)(44ksfkkkkkkususus25. 075. 0)(75. 05 . 011+10()max36()kkkkkkkkusfsusfs2022-3-867采用反向動態(tài)規(guī)劃法，從第采用反向動態(tài)規(guī)劃法，從第3階段算起：階段算起：33*333333330( )max3609( )usf sussuss2222222232222200*222()max36(0.750.25)max0.7512.75 13.5()ususfsusfsuussuss1111111121111100*11( )max

50、36(0.750.25 )max16.1250.375 16.125( )0ususf susfsususus 1201s4525. 075. 0,9025. 075. 0223112ussuss*1230,90,45,1935uuuf2022-3-868例例8 不確定采購問題不確定采購問題（其它情形之二）（其它情形之二）某廠某廠 5 周內(nèi)需采購一批原料，周內(nèi)需采購一批原料，價格波動見右表價格波動見右表試求：在哪周，以什么價格購試求：在哪周，以什么價格購進，期望價格最低？進，期望價格最低？單價單價 P500 0.3600 0.3700 0.42022-3-869(1) 階段：階段：k =1,

51、2, 3, 4, 5 (2) 狀態(tài)變量狀態(tài)變量 sk：第第 k 周的實際價格周的實際價格Sk =500，600，700(3) 決策變量決策變量 uk：1 第第 k 周采購周采購0 第第 k 周等待周等待(4) 指標函數(shù)指標函數(shù) SkE ：第第 k 周等待，以后再采購的最低期望價格周等待，以后再采購的最低期望價格(5) 最優(yōu)指標函數(shù)最優(yōu)指標函數(shù) fk( sk)：第第 k 到第到第 5 周采用最優(yōu)采購策略時周采用最優(yōu)采購策略時 的最低期望價格的最低期望價格2022-3-870基本方程基本方程fk( sk)= min sk, SkE k=4,3,2,1f5( s5)= s5k=5 f5( s5)=

52、s5 u5=1 s5 500 600 700f5( s5) 500 600 700 u5 1 1 12022-3-871k=4 f4( s4)= min s4, S4E S4E= 0.3 f5 (500)+ 0.3 f5 (600)+ 0.4 f5 (700)=610 f4 (s4)= min s4, 610=500, 當(dāng)當(dāng) s4 =500600, 當(dāng)當(dāng) s4 =600610, 當(dāng)當(dāng) s4 =700 u4 =0 u4 =1k=3 S3E = 0.3 f4 (500)+ 0.3 f4 (600)+ 0.4 f4 (700) =0.3500+ 0.3600+ 0.4610 =5742022-3-8

53、72 f3( s3)= min s3, S3E = min s3, 574 500, 當(dāng)當(dāng) s3 =500 u3 =1574, 當(dāng)當(dāng) s3 =600,700 u3 =0= f2( s2) = min s2, 551.8500, 當(dāng)當(dāng) s2 =500 u2 =1551.8, 當(dāng)當(dāng) s2 =600,700 u2 =0= k=2 S2E = 0.3 f3 (500)+ 0.3 f3 (600)+ 0.4 f3 (700) = 0.3500+ 0.3574+ 0.4574 = 551.82022-3-873 f1( s1) = min s1, 536.26500, 當(dāng)當(dāng) s1 =500 u1 =1536.26, 當(dāng)當(dāng) s1 =600,700 u1 =0= uk500500600600700700第第1 1周周1 1 0 0 0 0 第第2 2周周1 10 00 0第第3 3周周1 10 00 0第第4 4周