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

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

2、念和基本方程 動態(tài)規(guī)劃應用舉例資源分配問題背包問題生產(chǎn)庫存問題………,2024/3/21,3,7.1 多階段決策過程及其問題舉例,動態(tài)規(guī)劃研究的問題—多階段決策問題在時間或空間上可以劃分為若干階段，每一階段都需要根據(jù)現(xiàn)階段的情況做出決策決策者每段決策時，不僅要考慮本階段目標最優(yōu)，還應考慮之后各階段的目標最優(yōu)，最終達到整個決策活動的總體目標最優(yōu)當各個階段的決策確定后，就構(gòu)成了一個決策序列各階段的決策一般與時間有關(guān)，

3、故稱“動態(tài)”。但某些“靜態(tài)”問題可通過引進“時間”因素，用動態(tài)規(guī)劃方法來處理,2024/3/21,4,動態(tài)規(guī)劃分類：離散確定性動態(tài)規(guī)劃離散隨機性動態(tài)規(guī)劃連續(xù)確定性動態(tài)規(guī)劃連續(xù)隨機性動態(tài)規(guī)劃,2024/3/21,5,例1 最短路徑問題,第一階段 第二階段 第三階段 第四階段 求從 A 到 H 的最短路徑,2024/3/21,6,2024/3/21,6,第一種方法稱

4、做枚舉法（窮舉法）：基本思想是列舉出所有可能發(fā)生的方案和結(jié)果，再對它們進行比較，求出最優(yōu)方案。這里，從 A 到 H 的路程共有7條可能的路線，分別算出各條路線的距離，最后進行比較，可得最優(yōu)路線 當節(jié)點很多時，用窮舉法求最優(yōu)路線的計算工作量將會十分龐大，而且其中包含著許多重復計算第二種方法熟稱貪心算法，亦即“局部最優(yōu)路徑”法，只選擇當前最短途徑，“逢近便走”，錯誤地以為局部最優(yōu)會致整體最優(yōu)。在這種想法指導下，所取決策必是

5、 A → C → G → H，距離為 4+5+8=17,,2024/3/21,7,d(sk, uk)：第 k 階段，采取策略 uk 所發(fā)生的距離 fk(sk)：第 k 階段，在 sk 狀態(tài)時到終點 H 的最短距離,動態(tài)規(guī)劃的基本思想：如果起點 A 經(jīng)過 B, E 而到 H最優(yōu)，則由 B 出發(fā)經(jīng) E 到 H 這條子路線，必為從 B 到 H 的最短路線。所以，尋找最短路線，應該從最后一段開始找，然后往前遞推假設 sk：第 k

6、階段初所處的節(jié)點,uk(sk)：在 sk 狀態(tài)時第 k 階段所作的決定,2024/3/21,8,2024/3/21,9,f3(E)=3,2024/3/21,10,f3(F)=5,2024/3/21,11,f3(G)=8,2024/3/21,12,f2(B)=13,2024/3/21,13,f2(C)=10,2024/3/21,14,f2(D)=8,2024/3/21,15,f1(A)=14,2024/3/21,16,狀態(tài) 最優(yōu)決策

7、 狀態(tài) 最優(yōu)決策 狀態(tài) 最優(yōu)決策 狀態(tài),A （ AC） C （CE） E （EH） H從A到H的最短路徑：距離為14，路線為A→C→E→H,2024/3/21,17,2024/3/21,17,多階段決策過程及實例：標號法,,,,,,,4,3,7,5,9,7,,6,,8,,13,,10,,9,,12,,13,,16,,18,從G到A的解法稱

8、為逆序解法,注：因為從A到G的最短路與從G到A的最短路是一樣的，因此也可以從A出發(fā)來找。從A到G的解法稱為順序解法,2024/3/21,18,2024/3/21,18,綜上可見，全枚舉法雖可找出最優(yōu)方案，但不是好算法；局部最優(yōu)法則完全是個錯誤方法；只有動態(tài)規(guī)劃方法屬于科學有效的算法。它的基本思想是，把一個比較復雜的問題分解為一系列同類型的更易求解的子問題,2024/3/21,19,7.2 動態(tài)規(guī)劃的基本概念和基本方程,(一) 基本概念和

9、基本方程,(1) 階段：k = 1, ……, n,(2) 狀態(tài)變量 sk ：第 k 階段的自然狀況,(3) 決策變量 uk(sk) ：第 k 階段的決定 Dk(sk) ：決策變量的取值范圍,2024/3/21,20,(4) 狀態(tài)轉(zhuǎn)移方程 sk＋1 ＝T (sk, uk)：描述第 k 階段與第 k+1 階段的狀態(tài)變量的關(guān)系,(5) 指標 v (sk ,uk) ：第 k 階段在狀態(tài) sk 下采取決策 uk 得到的 結(jié)

10、果（距離、得益、成本等） 指標函數(shù)是指各階段指標的累計。即 V (sk,uk, …, sn,un, sn+1)=vk(sk,uk)*vk+1(sk+1,uk+1)…*vn(sn,un) 它表示從第 k 階段的狀態(tài) sk 開始到第 n 階段的終止狀態(tài)的指標累計。式中*表示某種運算符，一般為加法或乘積運算,(6) 最優(yōu)指標函數(shù) fk (sk) ：它表示從第 k 階段的狀態(tài) sk 開始到 第 n 階段終止的過

11、程中，采取最優(yōu)策略得到的指標函數(shù)值,,2024/3/21,21,2024/3/21,21,逆推公式,或,多階段決策問題中，常見的目標函數(shù)形式之一是取各階段效益之和的形式。有些問題，如系統(tǒng)可靠性問題，其目標函數(shù)是取各階段效益的連乘積形式?？傊?，具體問題的目標函數(shù)表達形式需要視具體問題而定,Max 或 Min,2024/3/21,22,對例1,(1) 階段：k＝1,2,3,(2) 狀態(tài)變量 sk ：第 k 階段初所處的位置,

12、 狀態(tài)集合 Sk, 如 S2 ={B , C, D},(3) 決策變量 uk ：在第 k 段 sk 狀態(tài)時的路徑選擇,(4) 狀態(tài)轉(zhuǎn)移方程 ：sk＋1 ＝uk (sk),2024/3/21,23,(5) 指標： vk (sk ，uk) 為第 k 階段采取決策 uk 時到下一狀態(tài)的距離 指標函數(shù),(6) 最優(yōu)指標函數(shù)： fk (sk)：第 k 階段，在 sk 狀態(tài)時到終點 H

13、的最短距離,,2024/3/21,24,2024/3/21,24,（二）貝爾曼最優(yōu)化原理最優(yōu)策略具有這樣的性質(zhì)：不論初始狀態(tài)與初始策略如何，對于先前決策所造成的狀態(tài)而言，余下所有決策必構(gòu)成最優(yōu)決策。即：最優(yōu)策略的子策略也是最優(yōu)的！,,2024/3/21,25,（三）解法步驟首先將問題劃分為若干個階段，然后選擇狀態(tài)變量與決策變量，并寫出轉(zhuǎn)移方程和指標函數(shù)，列出基本方程反向條件優(yōu)化正向求最優(yōu)解,2024/3/21,26,7

14、.3 應用舉例,例2 資源分配問題(Ⅰ)例3 資源分配問題(Ⅱ)例4 背包問題例5 生產(chǎn)庫存問題例6 可靠性問題例7 機器負荷分配問題……,2024/3/21,27,例 2 資源分配問題(Ⅰ),某公司準備將 5 臺設備分配給所屬的三個子工廠，各工廠獲得設備后的可盈利情況如表所示。問：如何分配這五臺設備，才能使公司獲得的收益最大？,,,,,2024/3/21,28,分析,(1) 階段：k =1，2，3,(3)

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

16、 分配策略可產(chǎn)生的最大收益,2024/3/21,29,逆推公式：,其中,2024/3/21,30,2024/3/21,30,k=3, S3 = {0,1,2,3,4,5}, f3(s3)＝ max{g3(u3)+0},,,,,,,,,,,,,,,2024/3/21,31,2024/3/21,31,k=2, S2 = {0,1,2,3,4,5}, f2(s2)＝ max{g2(u2)+ f3(s3)}

17、,,,S3=S2-u3,2024/3/21,32,2024/3/21,32,k=1, 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萬元,,,,同理得到另一組最優(yōu)解,2024/3/21

18、,33,一般分配問題,某種資源的總量為 a，用于 n 種生產(chǎn)若分配 uk 于第 k 種生產(chǎn)時，收益為 gk(xk),問：應如何分配才能使總收入最大？該問題的數(shù)學模型為,Max z = g1 (u1 )+ g2 (u2 )+…+ gn (un),s.t. u1 +u2 +…+un= a uk≥0,,2024/3/21,34,分析,(1) 階段：k =1，2，….., n,(3) 決策變量 uk

19、：對第 k 階段的分配數(shù),(2) 狀態(tài)變量 sk ：第 k 階段初可供分配的資源數(shù),(4) 狀態(tài)轉(zhuǎn)移方程： sk＋1 ＝sk - uk,(5) 指標函數(shù) gk (uk) ：uk 臺設備分配給第 k 種生產(chǎn)所產(chǎn)生 的收益(6) 最優(yōu)指標函數(shù) fk (sk) ：第 k 至 n 階段采取最優(yōu)分配策 略可產(chǎn)生的最大收益,2024/3/21,35,逆推公式：,20

20、24/3/21,36,例3 資源分配問題(Ⅱ),某工廠要進行A,B,C三種新產(chǎn)品的試制，為提高三種產(chǎn)品研制成功的概率，決定調(diào)撥經(jīng)費2百萬，并要求資金集中使用，也即以百萬為單位進行分配，其增加研發(fā)費與新產(chǎn)品不成功概率的關(guān)系如表所示。問：如何分配資金，可使三種產(chǎn)品都研制不成功的概率最??？,,2024/3/21,37,分析,(1) 階段：k = 1，2，3,(3) 決策變量 uk ：對第 k 階段分配金額,(2) 狀態(tài)變量 sk ：

21、第 k 階段初的可用金額,(4) 狀態(tài)轉(zhuǎn)移方程： sk＋1 ＝sk - uk,(5) 最優(yōu)指標函數(shù) fk (sk) ：第 k 至 3 階段采取最優(yōu) 分配策略時的最小不成功概率的值,2024/3/21,38,逆推公式：,其中 gk (uk) 是階段函數(shù),2024/3/21,39,k=3, S3 = {0,1,2}, f3(s3)＝ min{g3(u3)*1},,,,,2024/3/21,40,k=2, S2 = {0,1,2}

22、, f2(s2)＝ min{g2(u2)*f3(s3)},,2024/3/21,41,k=1, S1 = {2}, f1(s1)＝ max {g1(u1)* f2(s2)},,得到方案：u1*＝1，u2*＝0，u3*＝1: 產(chǎn)品 A分配 1百萬，產(chǎn)品 B分配0，產(chǎn)品 C分配1百萬，f *=0.06,,,,2024/3/21,42,例4 背包問題 某卡車載重能力為10噸，現(xiàn)要裝三種產(chǎn)品，已知每件產(chǎn)品的重量和利潤如表。又規(guī)

23、定產(chǎn)品3至多裝2件。問：如何安排運輸可使總利潤最大？,2024/3/21,43,階段：k=1,2,3狀態(tài)變量 sk：第 k 階段初的可裝載能力決策變量 uk：第 k 階段的裝載件數(shù)狀態(tài)轉(zhuǎn)移方程： （tk 為 k 產(chǎn)品的單件重量）最優(yōu)指標函數(shù) fk(sk)：第k-3階段采取最優(yōu)策略時的最大利潤遞推公式：

24、 k=3,2,1 f4(s4)=0,動態(tài)規(guī)劃方法求解,2024/3/21,44,物品1,物品2,物品3,,,,,k=1,k=2,k=3,k=4,s1=10,s2,s3,s4,階段,狀態(tài)變量：裝載前背包的容量,決策變量：裝載的件數(shù),,,,u1,u2,

25、u3,決策允許集合：裝載件數(shù)的范圍,0≤u1≤[s1/t1]u1為整數(shù),狀態(tài)轉(zhuǎn)移方程：背包容量和裝載件數(shù)的關(guān)系,階段指標： vk(sk,uk)=rkuk 在背包中第k種物品的價值,最優(yōu)指標： fk(sk)=max{rkuk+fk+1(sk+1)},終端條件：,,f4(s4)=0,,s2＝s1-t1u1,s3=s2-t2u2,s4=s3-t3u3,0≤u2≤[s2/t

26、2]u2為整數(shù),0≤u3≤min{[s3/t3], 2}u3為整數(shù),2024/3/21,45,k =3,,,,,,,C的單件重量為t3=2,2024/3/21,46,k=2：裝載物品B，f2(s2),,B的單件重量為t2=3,2024/3/21,47,k=1：裝載物品A， f1(u1),最優(yōu)解：物品A裝0件，物品B裝2件，物品C裝2件 最大價值為400元,,,,,A的單件重量為t1=4,2024/3/

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

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

29、度采取最優(yōu)策略 時的最小總費用,2024/3/21,50,逆推公式：,,,,dk=3: 需求 bk=5: 生產(chǎn)能力F=13: 固定成本 C=2: 單位生產(chǎn)成本g=1: 單位庫存費用 Ek=4: 倉庫儲存能力,2024/3/21,51,,,,2024/3/21,52,k = 4,,,,2024/3/21,53,k = 3,,,,,2024

30、/3/21,54,k = 2,,,,,,2024/3/21,55,k = 1,,,,2024/3/21,56,可用總費用為 C，總重量為 Wck 為第 k 個部件裝配一個備用件的費用,wk 為第 k 個部件裝配一個備用件的重量,Pk 第 k 個部件的故障概率,某機器工作系統(tǒng)由 n 個部件組成，這些部件正常工作關(guān)系為串聯(lián)。為提高系統(tǒng)工作的可靠性，考慮對每個部件都配備備用件。備用件越多，可靠性越大，但系統(tǒng)的成本、重量、體積都會變大。已知：

31、,例6 可靠性問題,問：在這兩個限制條件下，應如何選用部件的備用件個數(shù)，使得正常工作的可靠性最大？,2024/3/21,57,設 uk 為第 k 個部件裝配備用件的個數(shù)， dk(sk, uk) 為第 k 個部件裝配 uk 個備用件時機器正常工作的概率,,2024/3/21,58,動態(tài)規(guī)劃模型,(1) 階段：k = 1, 2, … , n,(3) 決策變量 uk ：第 k 個部件上裝的備用件個數(shù),(4) 狀態(tài)轉(zhuǎn)移：　　 sk+

32、1 = sk - ckuk 　　　tk+1 = tk - wkuk,(5) 最優(yōu)指標函數(shù) fk (sk , tk)：第 k 至第 n 個部件，采取最優(yōu)策略時機器正常工作的概率,tk ：第 k 至第 n 個部件允許的總重量,2024/3/21,59,2024/3/21,60,某系統(tǒng)由 A, B, C 三個部分串聯(lián)而成，已知：① A、B、C 相互獨立② 各部分的單件故障率分別為 P1=0.4， P2=0.

33、2， P3=0.5③ 每個部分的單件價格為：A 部分單價 c1=1 萬元； B 部分單價 c2=2 萬元；C 部分單價 c3=3 萬元④ 可投資購置部件的金額為10萬元 問：A, B, C 三部分各應購置多少部件才能使系統(tǒng)的總可靠率最大？（假設每部分至少購置一件）,2024/3/21,61,階段：購置 A、B、C 分別為階段1、2、3狀態(tài)變量 sk：第 k 階段初可用來購買部件的費用決策變量 uk：第 k

34、階段購置的件數(shù)狀態(tài)轉(zhuǎn)移方程：sk+1 = sk - ckuk 指標函數(shù)：第 k 階段本身的可靠率最優(yōu)指標函數(shù) fk(sk) ：第 k 階段尚有資金 sk 時可能獲得 的最高可靠率遞推方程 fk(sk)= max dk(sk, uk)×fk+1(sk+1) k=3,2,1 f4(s4)=1,2024/3/21,62,

35、第3階段此時 C 應至少配備 1 個部件，故 s2≥c3=3同時 A, B 部件已經(jīng)至少配備 1個部件，故 s2≤10-c1-c2=7,,總費用：10 (萬元)單價：c1=1, c2=2, c3=3故障率：P1=0.4, P2=0.2, P3=0.5,2024/3/21,63,第2階段此時 B、C 應至少各配制 1 個部件，故 s2≥c2+c3=2+3=5同時 A 部件已經(jīng)至少配備 1個部件，故 s2≤10－1=9,總費用：

36、10 (萬元)單價：c1=1, c2=2, c3=3故障率：P1=0.4, P2=0.2, P3=0.5,2024/3/21,64,第1階段,,,,總費用：10 (萬元)單價：c1=1, c2=2, c3=3故障率：P1=0.4, P2=0.2, P3=0.5,2024/3/21,65,例7 機器負荷分配問題（其它情形之一）,某廠有 120 臺同一規(guī)格完好的機器，每臺機床全年在高負荷下工作可創(chuàng)利 9 萬元，但機器的報廢率高，每

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

38、2024/3/21,67,采用反向動態(tài)規(guī)劃法，從第3階段算起：,,,,,,,,2024/3/21,68,例8 不確定采購問題（其它情形之二）,某廠 5 周內(nèi)需采購一批原料，價格波動見右表試求：在哪周，以什么價格購進，期望價格最低？,2024/3/21,69,(1) 階段：k =1, 2, 3, 4, 5,(5) 最優(yōu)指標函數(shù) fk( sk)：第 k 到第 5 周采用最優(yōu)采購策略時 的最低期望價格,2024/3/21

39、,70,2024/3/21,71,k=4 f4( s4)= min{ s4, S4E},k=3 S3E = 0.3 f4 (500)+ 0.3 f4 (600)+ 0.4 f4 (700) =0.3×500+ 0.3×600+ 0.4×610 =574,2024/3/21,72,k=2 S2E = 0.3

40、f3 (500)+ 0.3 f3 (600)+ 0.4 f3 (700) = 0.3×500+ 0.3×574+ 0.4×574 = 551.8,2024/3/21,73,k=1 S1E = 0.3 f2 (500)+ 0.3 f2 (600)+ 0.4 f2 (700) = 0.3&

41、#215;500+ 0.3×551.8+ 0.4×551.8 = 536.26,2024/3/21,74,最優(yōu)策略：第 1- 3周，價格為500時采購；否則等待 第4周，價格為500, 600時采購；否則等待 第5周，什么價格均買,2024/3/21,75,總結(jié),特點解決多階段決策問題，依次在每

42、一階段上決策逐階段優(yōu)化一個解，最終產(chǎn)生一個完整的最優(yōu)解鏈動態(tài)規(guī)劃是一種方法，并沒有具體的算法，需要對不同問題要設計不同解算過程,2024/3/21,76,優(yōu)點：應用廣泛、靈活，可以解決某些非線性和整數(shù)規(guī)劃，對含有隨機因素的問題與確定型的線性優(yōu)化問題解起來幾乎一樣容易求解方便缺點：決策者不能簡單地將問題應用已有的商品化的動態(tài)規(guī)劃的軟件包解決,2024/3/21,77,研究范圍：線性規(guī)劃，非線性規(guī)劃，整數(shù)規(guī)劃，網(wǎng)絡分

43、析，控制工程分類離散確定型，連續(xù)確定型，離散隨機型，連續(xù)隨機型,決策變量,狀態(tài)變量,2024/3/21,78,線性規(guī)劃LP模型（模型建立：變量、目標、約束；標準型）圖解法單純形算法大M法，兩階段法，注意的幾個問題（Max和Min，解的四種情況）對偶規(guī)劃及其性質(zhì)（互補松弛性）對偶規(guī)劃的最優(yōu)解（求解，經(jīng)濟解釋－影子價格）對偶單純形法靈敏度分析（A,b,c的變化）,2024/3/21,79,運輸問題數(shù)學模

44、型產(chǎn)銷平衡的運輸問題的求解初始解（西北角法，最小元素法，伏格爾法）最優(yōu)解的求解（位勢法）產(chǎn)銷不平衡的運輸問題的求解化為平衡問題,2024/3/21,80,整數(shù)規(guī)劃模型（是非/選擇問題，大型設備，人數(shù)等）投資問題集合覆蓋問題運輸問題生產(chǎn)計劃問題（固定成本，批量生產(chǎn)等）排序問題等算法分支定界法割平面法(隱)枚舉法指派問題：匈牙利法,2024/3/21,81,網(wǎng)絡優(yōu)化各種網(wǎng)絡模型與最小費用流問題的關(guān)系圖上