【正文】 即 設(shè)部件 i的一個備用元件的費用為 ci，重量為 wi，要求整個系統(tǒng)所裝備用元件的總費用不超過 C，總重量不超過 W ?Niii zPP1)(??第三節(jié) 動態(tài)規(guī)劃在經(jīng)濟和管理中的應(yīng)用 ? Xk表示由第 k個到。因此，最優(yōu)化問題是在考慮上述限制條件下，應(yīng)如何選擇各部件的備用元件數(shù)，使整個系統(tǒng)的工作可靠性最大？ 第三節(jié) 動態(tài)規(guī)劃在經(jīng)濟和管理中的應(yīng)用 設(shè)部件 i上裝有 zi個備用元件時，它正常工作的概率是 pi(zi)。顯然，備用元件越多，整個系統(tǒng)正常工作的可靠性越大。 ? 基本方程 ? 確定邊界條件 因為在第 1階段時的資源為總資源，到第 n+1階段時資源已分配完畢，所以 so=a， sn+1=0,fn+1(sn+1)=0. ?????????? ???? )()(1,1 )}()({m a x)( 110nnnnkkkkaxkksrsfnksfxrsfk?第三節(jié) 動態(tài)規(guī)劃在經(jīng)濟和管理中的應(yīng)用 ? 復(fù)合系統(tǒng)可靠性問題 ? 若某種機器的工作系統(tǒng)有 N個部件組成，只要有一個部件失靈，整個系統(tǒng)就不能正常工作。 ? 決策變量 xk表示分配給第 k個產(chǎn)品的資源數(shù)。問如何分配，才能使生產(chǎn) n種產(chǎn)品的總收入最大？ 。 ? 建立狀態(tài)轉(zhuǎn)移方程 ?動態(tài)規(guī)劃的基本方程 ???????? RxKxsskkkk 1 11 當(dāng)當(dāng)11 11( ) m a x { ( , ) ( ) } , , 1 , , 1( ) 0xk k k k k k kx K o r Rnnf s v s x a f s k n nfs?????? ? ? ?????( ) ( ) ( , )( 0 ) ( 0 ) ( ) k k k k kk k kk k k k kr s u s x Kv s xr u c s x R???? ?? ? ??當(dāng) 當(dāng) 第三節(jié) 動態(tài)規(guī)劃在經(jīng)濟和管理中的應(yīng)用 ? 資源分配問題 ? 將一種或多種有限的資源，分配給若干個使用者，而使目標(biāo)達(dá)到最優(yōu) ? 設(shè)有一原料，總量為 a，用于生產(chǎn) n種產(chǎn)品。當(dāng)然，設(shè)備越舊越不值錢，購買新設(shè)備又需要一定數(shù)額的購買費，這就是設(shè)備的更新決策問題。一般來說，一臺新設(shè)備出故障少，維護費用低，帶來的經(jīng)濟效益就高；隨著使用年限的增加，新設(shè)備逐漸變舊，維護費用增加，效用降低。從經(jīng)濟上分析，一種設(shè)備應(yīng)該使用多少年后進行更新最合算。 第三節(jié) 動態(tài)規(guī)劃在經(jīng)濟和管理中的應(yīng)用 ? 劃分階段 將三個月分為三個階段，每個月為一個階段 ? 狀態(tài)變量 sk表示第 k個月初的庫存數(shù) ? 決策變量 xk表示第 k月生產(chǎn)的單位數(shù) ? 建立狀態(tài)轉(zhuǎn)移方程 ，其中 為一隨機需求量或為1或為 2 ? 最優(yōu)指標(biāo)函數(shù) fk(sk)表示第 k個月初的庫存是時，第 k個月至第 3個月內(nèi)的最小期望費用。在第 1月的月初，公司有 1單位的庫存。但同時要求必須及時滿足需求。每個月末檢查庫存，1個單位的庫存費用是 1元。每月最多生產(chǎn) 4個單位，每月的需求是隨機的，或為 1或為 2單位。 ? 基本方程 ? 確定邊界條件 so=開始庫存量， sn=0 )}(m i n {)( 11 ???? kkkkkk sfuasf第三節(jié) 動態(tài)規(guī)劃在經(jīng)濟和管理中的應(yīng)用 ? 貨物存儲問題 ? 考慮下面三個月的庫存問題，在每月初，公司必須決定在本月內(nèi)，應(yīng)生產(chǎn)多少產(chǎn)品。已知總裝車間的各個月份的需求量以及在加工車間生產(chǎn)該部件每單位數(shù)量所需工時，倉庫容量 H=9和開始庫存量 2，要求最終庫存量為 0，要制定一個半年的逐月生產(chǎn)計劃，既滿足需要和倉庫容量的限制，又使生產(chǎn)這種部件的總耗費工時數(shù)最少。問旅行者應(yīng)如何選擇攜帶物品的件數(shù)，使總價值最大？ ? 劃分階段 將可裝入物品按排序，每階段裝一種物品，共劃分為 n個階段， ? 狀態(tài)變量 表示在第 k階段開始時，背包中允許裝入前 k種物品的總重量，記為 sk ? 決策變量 裝入第 k 種物品的件數(shù) xk ? 建立狀態(tài)轉(zhuǎn)移方程 sk+1=skwkxk ? 允許決策集合 ? 確定指標(biāo)函數(shù) ? 確定邊界條件 背包所能承受的重量為 w千克 }],/[0|{)( 11 為整數(shù)kkkkkkk xwsxxsD ?? ?????????????????? 0)(,2,1) } ,()({ m a x )(10]/1[,1,0111 sfnkxwsfxpsfkwkskxkkkkkkkk??第三節(jié) 動態(tài)規(guī)劃在經(jīng)濟和管理中的應(yīng)用 ? 生產(chǎn)計劃問題 ? 已知企業(yè)產(chǎn)品的生產(chǎn)費用、存儲費用和市場的需求量，在其生產(chǎn)能力和存儲能力許可的前提下，怎樣制定各個時期的生產(chǎn)計劃，既能完成交貨任務(wù)，又使總支出最小。 我們不妨用此模型去求解例 3， 也一定得出同樣的結(jié)果 。 一旦咨詢的工作日不是減少而是增加 ， 那么我們不僅要重新計 算第一階段 ， 而且要在第二 、 第三 、 第四階段的計算表上補上增加 的工作日的新的信息 ， 也可得到新的結(jié)果 。 現(xiàn)在我們不妨假設(shè)該咨詢公司的工作計劃有所改變 ， 只有 8個工作日來處理這四類咨詢項目 ， 那么該咨詢公司如何選擇 客戶使得獲利最大呢 ？ 我們不必從頭開始重做這個問題 ， 而只 要在第一階段上把 改成 8， 重新計算就可得到結(jié)果 ， 如表 10－ 14所示 ， 這是動態(tài)規(guī)劃的一個好處 。 其數(shù)值計算 見表 10－ 13。其數(shù)值計算 見表 10－ 12。其數(shù)值計算 見表 10－ 11。 已知 ＝ 10 并有 kx1s,),( 111112 xsxsTs ???ks第三節(jié) 動態(tài)規(guī)劃在經(jīng)濟和管理中的應(yīng)用 并從 與 的定義可知 從第四階段開始計算： 顯然將 個工作日 盡可能分配給第四 類咨詢項目 ， 即 時 ， 第四階段的指標(biāo)值為最大 ， 其中 ， 表示取不大于 的最大整數(shù) ， 符號 為 取整符號 ， 故有 由于第四階段是最后的階段 ， 故有 ,3),( 222223 xsxsTs ???.4),( 333334 xsxsTs ???ks kx 44 7 xs ?4s )10,1,0( 4 ??s? ?7/44 sx ?? ?7/4s ? ?7/4s ??? ?).7/,(),(m a x 4444444ssrxsrx ??? ?),7/,(),(m a x)( 4444*44444ssrxsrsfx???第三節(jié) 動態(tài)規(guī)劃在經(jīng)濟和管理中的應(yīng)用 因為 至多為 10， 其數(shù)值計算見表 10－ 10。 我們設(shè) ＝分配給第 k種咨詢項目到第四種咨詢項目的所 有客戶的總工作日 （ 第 k階段的狀態(tài)變量 ） 。 顯然該公 司在 10天內(nèi)不能處理完所有的客戶 ， 它可以自己挑選一些客 戶 ， 其余的請其他咨詢公司去做 ， 應(yīng)如何選擇客戶使得在這 10 個工作日中獲利最大 ？ 咨詢項目類型 待處理客戶數(shù) 處理每個客戶所需工作日數(shù) 處理每個客戶所獲利潤 1 2 3 4 4 3 2 2 1 3 4 7 2 8 11 20 第三節(jié) 動態(tài)規(guī)劃在經(jīng)濟和管理中的應(yīng)用 解：用動態(tài)規(guī)劃來求解此題 。 設(shè) 階段變量 k：第 k次裝載第 k種物品 （ k=1, 2, … , n） 狀態(tài)變量 sk：第 k次裝載時背包還可以裝載的重量； 決策變量 uk = xk：第 k次裝載第 k種物品的件數(shù)； 決策允許集合： Dk(sk) = { xk | 0? xk?sk/wk， xk為整數(shù) }； 狀態(tài)轉(zhuǎn)移方程： sk+1 = sk? wkxk； 階段指標(biāo)： vk = ckxk； 最優(yōu)過程指標(biāo)函數(shù) fk(sk)：第 k到 n階段容許裝入物品的最大使 用價值； 遞推方程： fk(sk) = max {ckxk+fk+1(sk+1)} = max {ckxk+fk+1(sk? wkxk)}； x?Dk(sk) 終端條件： fn+1(sn+1) = 0。 設(shè) xi為第 i種 物品裝入背包的件數(shù) （ i =1, 2, … , n） ， 背包中物品的總 價值為 z， 則 Max z = c1x1+c2x2+ … +xn . w1x1+w2x2+… +wnxn≤W x1, x2, … , xn?0 且為整數(shù) 。 現(xiàn)有一只可裝載重量為 W 公斤的背包 ， 求各種物品應(yīng)各取多少件放入背包 ， 使背 包中物品的價值最高 。 22* ?x 1232*23 ????? xss 133* ?? sx第三節(jié) 動態(tài)規(guī)劃在經(jīng)濟和管理中的應(yīng)用 二 、 背包問題 設(shè)有 n種物品 ， 每一種物品數(shù)量無限 。 ， 根據(jù) ， 查表 10－ 7可 )5( 11 ?ss)],5(),5([m a x)5( 111111xfxrf x ??? 1x01* ?x 5051*12 ????? xss22* ?x 3252*23 ????? xss 333* ?? sx21* ?x 3251*12 ????? xss第三節(jié) 動態(tài)規(guī)劃在經(jīng)濟和管理中的應(yīng)用 知 ， 再由 ,求得 ， 即分配給甲廠 2臺 ， 乙廠 2臺 ， 丙廠 1臺 。 42 ?s 12 ?x16115)3()1,4()14()1,4()(),( 3232223222 ?????????? frfrxsfxsr)1,4(2r5)1,4(2 ?r )3()14( 33 ff ??)3(3f )3(3f 22 ?x16610)2()2,4()24()2,4()(),( 3232223222 ?????????? frfrxsfxsr02 ?x 12120)04()0,4( 32 ????? fr 32x411)34()3,4( 32 ???? fr 42 ?x11011)44()4,4( 32 ????? fr 42 ?s52 ?x )54()5,4( 32 ?? fr)4(2f )4(2f)(),( 223222 xsfxsr ??2x第三節(jié) 動態(tài)規(guī)劃在經(jīng)濟和管理中的應(yīng)用 第一階段： 把 臺設(shè)備分配給第 1， 第 2， 第 3廠時 ， 最大 盈利為 其中 可取值 0,1,2,3,4,5. 數(shù)值計算見表 10－ 8 然后按計算表格的順序推算 ， 可知最優(yōu)分配方案有兩個： ， 根據(jù) ， 查表 10－ 7可 知 ， 再由 ， 求得 。 從 這些數(shù)值中取得最大即得 ， 即有 =16。 同樣可知當(dāng) 時 ， 可知 。12)4,4(3 ?r,12)4(3 ?f 43* ?x 43 ?s 43 ?x)5,4,3,2,1,0( 22 ?ss2s)](),([m a x)( 33222222sfxsrsf x ??第三節(jié) 動態(tài)規(guī)劃在經(jīng)濟和管理中的應(yīng)用 因為 上式也可寫成 其數(shù)值計算如表 10－ 7所示 。 其數(shù)值計算見表 )5,4,3,2,1,0( 33 ?ss).,(),(m a x)( 333333333ssrxsrsf x ??3x),(),(max 3333333ssrxsrx ?33 xs ?第三節(jié) 動態(tài)規(guī)劃在