【正文】 我們已知 ， 又因?yàn)? ， 同樣有 因?yàn)? ,故 可取值為 0,1,2, … ,10。 其數(shù)值計(jì)算 見(jiàn)表 10－ 13。 表 10－ 13 101 ?s? ?.)(),(m a x)( 112111111xsfxsrsf x ???112 xss ??? ?.)10(),10(m a x)10( 121111xfxrf x ???101 ?s 1x第三節(jié) 動(dòng)態(tài)規(guī)劃在經(jīng)濟(jì)和管理中的應(yīng)用 從 表 10－ 13可知 ， 從而得 ＝ 10 － 0＝ 10， 在表 10－ 12的 的這一行可知 ， 由 ， 查表 10－ 11的 的這一行可知 ， 最后由 ， 查表 1010的 的這 一行得 ， 綜上所述得最優(yōu)解為： 此時(shí)最大盈利為 28。 現(xiàn)在我們不妨假設(shè)該咨詢公司的工作計(jì)劃有所改變 ， 只有 8個(gè)工作日來(lái)處理這四類咨詢項(xiàng)目 ， 那么該咨詢公司如何選擇 客戶使得獲利最大呢 ？ 我們不必從頭開(kāi)始重做這個(gè)問(wèn)題 ， 而只 要在第一階段上把 改成 8， 重新計(jì)算就可得到結(jié)果 ， 如表 10－ 14所示 ， 這是動(dòng)態(tài)規(guī)劃的一個(gè)好處 。 28)10(1 ?f 01* ?x 1*2 10 xs ??102 ?s 12* ?x73103 2*23 ????? xss 73 ?s03* ?x 7073*34 ????? xss 74 ?s14* ?x 0,1,0 3*2*1* ??? xxx,14* ?x4s第三節(jié) 動(dòng)態(tài)規(guī)劃在經(jīng)濟(jì)和管理中的應(yīng)用 表 10－ 14 如上一樣可從表 10－ 14,10－ 12,10－ 11,10－ 10得到兩組最優(yōu)解 如下： 它們的最優(yōu)解 （ 即最大盈利 ） 都為 22。 一旦咨詢的工作日不是減少而是增加 ， 那么我們不僅要重新計(jì) 算第一階段 ， 而且要在第二 、 第三 、 第四階段的計(jì)算表上補(bǔ)上增加 的工作日的新的信息 ， 也可得到新的結(jié)果 。 ????????????3042)4321xxxx?????????????1001)4*3*2*1*xxxx第三節(jié) 動(dòng)態(tài)規(guī)劃在經(jīng)濟(jì)和管理中的應(yīng)用 實(shí)際上 ， 背包問(wèn)題我們也可以用整數(shù)規(guī)劃來(lái)求解 ， 如果背包攜帶物品重量的限制為 W公斤 ， 這 N種物品中第 i種物品的重量為 ， 價(jià)值為 ， 第 i種物品的總數(shù)量的 ， 我們可以設(shè) 表示攜帶第 i種物品的數(shù)量 ， 則其數(shù)學(xué)模型為： . 且為整數(shù) 。 我們不妨用此模型去求解例 3， 也一定得出同樣的結(jié)果 。 iw ic inix,m a x1???Niii xcf0),2,1(1??????iiiNiiixNinxWxw?第三節(jié) 動(dòng)態(tài)規(guī)劃在經(jīng)濟(jì)和管理中的應(yīng)用 整數(shù) 432143214321223410743202282m a xixxxxxxxxxxxxxf????????????X1=0,x2=1,x3=0,x4=1 max f=28 背包問(wèn)題 ：一位旅行者攜帶背包旅游，已知他的背包所能承受的重量為w千克，現(xiàn)有 n種物品可供他選擇裝入包中，第 i種物品的單件重量為 wi 千克，其價(jià)值是攜帶數(shù)量 xi的函數(shù) pi(xi)。問(wèn)旅行者應(yīng)如何選擇攜帶物品的件數(shù)，使總價(jià)值最大？ ? 劃分階段 將可裝入物品按排序，每階段裝一種物品，共劃分為 n個(gè)階段， ? 狀態(tài)變量 表示在第 k階段開(kāi)始時(shí)，背包中允許裝入前 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é) 動(dòng)態(tài)規(guī)劃在經(jīng)濟(jì)和管理中的應(yīng)用 ? 生產(chǎn)計(jì)劃問(wèn)題 ? 已知企業(yè)產(chǎn)品的生產(chǎn)費(fèi)用、存儲(chǔ)費(fèi)用和市場(chǎng)的需求量，在其生產(chǎn)能力和存儲(chǔ)能力許可的前提下，怎樣制定各個(gè)時(shí)期的生產(chǎn)計(jì)劃，既能完成交貨任務(wù)，又使總支出最小。 ? 例某中轉(zhuǎn)倉(cāng)庫(kù)要按月在月初供應(yīng)一定數(shù)量的某種部件給總裝車間，由于生產(chǎn)條件的變化，生產(chǎn)車間在各月份中生產(chǎn)每單位這種部件所需耗費(fèi)的工時(shí)不同，各月份的生產(chǎn)量于當(dāng)月的月底前，全部要存入倉(cāng)庫(kù)以備后用。已知總裝車間的各個(gè)月份的需求量以及在加工車間生產(chǎn)該部件每單位數(shù)量所需工時(shí)，倉(cāng)庫(kù)容量 H=9和開(kāi)始庫(kù)存量 2，要求最終庫(kù)存量為 0，要制定一個(gè)半年的逐月生產(chǎn)計(jì)劃，既滿足需要和倉(cāng)庫(kù)容量的限制，又使生產(chǎn)這種部件的總耗費(fèi)工時(shí)數(shù)最少。 第三節(jié) 動(dòng)態(tài)規(guī)劃在經(jīng)濟(jì)和管理中的應(yīng)用 ? 劃分階段 按月份劃分階段，每個(gè)月為一個(gè)階段， k=1,2,…… ,n. ? 狀態(tài)變量 第 k階段開(kāi)始時(shí)（即本階段需求送出之前，上階段產(chǎn)品送入之后）部件庫(kù)存量，記為 sk ? 決策變量 第 k階段內(nèi)的部件生產(chǎn)量，記為 uk ? 建立狀態(tài)轉(zhuǎn)移方程 sk+1=sk+ukdk ? 最優(yōu)指標(biāo)函數(shù) fk(sk)表示在第 k階段開(kāi)始的庫(kù)存量為 sk時(shí)，從第 k階段到最后一階段生產(chǎn)部件的最小 累計(jì)工時(shí)數(shù)。 ? 基本方程 ? 確定邊界條件 so=開(kāi)始庫(kù)存量， sn=0 )}(m i n {)( 11 ???? kkkkkk sfuasf第三節(jié) 動(dòng)態(tài)規(guī)劃在經(jīng)濟(jì)和管理中的應(yīng)用 ? 貨物存儲(chǔ)問(wèn)題 ? 考慮下面三個(gè)月的庫(kù)存問(wèn)題，在每月初，公司必須決定在本月內(nèi)，應(yīng)生產(chǎn)多少產(chǎn)品。在一個(gè)月內(nèi)生產(chǎn) x單位的產(chǎn)品，所需成本為 c(x)，其中 c(0)=0，當(dāng) x0時(shí)， c(x)=3+2x。每月最多生產(chǎn) 4個(gè)單位，每月的需求是隨機(jī)的，或?yàn)?1或?yàn)?2單位。如果生產(chǎn)的數(shù)量大于需求，就出現(xiàn)庫(kù)存。每個(gè)月末檢查庫(kù)存，1個(gè)單位的庫(kù)存費(fèi)用是 1元。因?yàn)閹?kù)存能力有限，每月末的庫(kù)存量不能超過(guò) 3單位。但同時(shí)要求必須及時(shí)滿足需求。在第 3個(gè)月末要把現(xiàn)有的庫(kù)存以每單位 2元的價(jià)格售出。在第 1月的月初，公司有 1單位的庫(kù)存。如何制定生產(chǎn)策略使三個(gè)月內(nèi)的期望費(fèi)用最小。 第三節(jié) 動(dòng)態(tài)規(guī)劃在經(jīng)濟(jì)和管理中的應(yīng)用 ? 劃分階段 將三個(gè)月分為三個(gè)階段，每個(gè)月為一個(gè)階段 ? 狀態(tài)變量 sk表示第 k個(gè)月初的庫(kù)存數(shù) ? 決策變量 xk表示第 k月生產(chǎn)的單位數(shù) ? 建立狀態(tài)轉(zhuǎn)移方程 ，其中 為一隨機(jī)需求量或?yàn)?或?yàn)?2 ? 最優(yōu)指標(biāo)函數(shù) fk(sk)表示第 k個(gè)月初的庫(kù)存是時(shí)，第 k個(gè)月至第 3個(gè)月內(nèi)的最小期望費(fèi)用。 kkkk axss ???? 1 ka第三節(jié) 動(dòng)態(tài)規(guī)劃在經(jīng)濟(jì)和管理中的應(yīng)用 設(shè)備更新問(wèn)題 在企業(yè)中，經(jīng)常遇到設(shè)備陳舊或部分損壞需要更新的問(wèn)題。從經(jīng)濟(jì)上分析，一種設(shè)備應(yīng)該使用多少年后進(jìn)行更新最合算。這就是要研究的問(wèn)題。一般來(lái)說(shuō)，一臺(tái)新設(shè)備出故障少，維護(hù)費(fèi)用低，帶來(lái)的經(jīng)濟(jì)效益就高；隨著使用年限的增加，新設(shè)備逐漸變舊，維護(hù)費(fèi)用增加，效用降低。在適當(dāng)?shù)臅r(shí)候，就要賣掉舊設(shè)備，購(gòu)買新設(shè)備。當(dāng)然，設(shè)備越舊越不值錢，購(gòu)買新設(shè)備又需要一定數(shù)額的購(gòu)買費(fèi)，這就是設(shè)備的更新決策問(wèn)題。 現(xiàn)有一臺(tái)效益函數(shù)為 r(t)的設(shè)備，其維修費(fèi)用為 u(t)，更新費(fèi)用為 c(t)，需要在 n 年內(nèi)的每年年初做出決策，是繼續(xù)使用舊設(shè)備還是更新一臺(tái)新設(shè)備，使 n年總效益最大？ 第三節(jié) 動(dòng)態(tài)規(guī)劃在經(jīng)濟(jì)和管理中的應(yīng)用 ? rk(t)：在第 k年設(shè)備已使用過(guò) t年，再使用 1年的效益 ? uk(t)：在第 k年設(shè)備已使用過(guò) t年，再使用 1年的維修費(fèi)用 ? ck(t)：在第 k年賣掉一臺(tái)已使用過(guò) t年的設(shè)備，買進(jìn)一臺(tái)新設(shè)備的更新費(fèi)用 ? a：折扣因子，表示一年以后的單位收入價(jià)值相當(dāng)于現(xiàn)在的 a單位 ? fk(t)：已使用了 t年的舊設(shè)備，從第 k年開(kāi)始在以后繼續(xù)使用到規(guī)定的第 n年未知幾年內(nèi)的總回收額 第三節(jié) 動(dòng)態(tài)規(guī)劃在經(jīng)濟(jì)和管理中的應(yīng)用 ? 劃分階段 k表示計(jì)劃使用該設(shè)備的年限數(shù) ? 狀態(tài)變量 sk表示第 k年初，設(shè)備已使用過(guò)的年數(shù) ? 決策變量 xk表示第 k年初更新，還是繼續(xù)使用舊設(shè)備，分別用 R和 K表示 。 ? 建立狀態(tài)轉(zhuǎn)移方程 ?動(dòng)態(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é) 動(dòng)態(tài)規(guī)劃在經(jīng)濟(jì)和管理中的應(yīng)用 ? 資源分配問(wèn)題 ? 將一種或多種有限的資源，分配給若干個(gè)使用者，而使目標(biāo)達(dá)到最優(yōu) ? 設(shè)有一原料，總量為 a，用于生產(chǎn) n種產(chǎn)品。若分配數(shù)量 xi用于生產(chǎn)第 i種產(chǎn)品，其產(chǎn)生的效益為 ri(xi)。問(wèn)如何分配，才能使生產(chǎn) n種產(chǎn)品的總收入最大？ 。 第三節(jié) 動(dòng)態(tài)規(guī)劃在經(jīng)濟(jì)和管理中的應(yīng)用 ? 劃分階段 將 n種產(chǎn)品按 1,2,…… ,n的序號(hào)排列 ,每種產(chǎn)品為一個(gè)階段 ,分為 n個(gè)階段 ,k=1,2,…… ,n. ? 狀態(tài)變量 sk表示分配給第 k個(gè)產(chǎn)品至第 n 種產(chǎn)品的資源數(shù)。 ? 決策變量 xk表示分配給第 k個(gè)產(chǎn)品的資源數(shù)。 ? 建立狀態(tài)轉(zhuǎn)移方程 sk+1=skxk ? 最優(yōu)指標(biāo)函數(shù) fk(sk)表示在擁有資源 sk，分配給第 k種產(chǎn)品至第 n 種產(chǎn)品所得到的最大總收入。 ? 基本方程 ? 確定邊界條件 因?yàn)樵诘?1階段時(shí)的資源為總資源，到第 n+1階段時(shí)資源已分配完畢，所以 so=a， sn+1=0,fn+1(sn+1)=0. ?????????? ???? )()(1,1 )}()({m a x)( 110nnnnkkkkaxkksrsfnksfxrsfk?第三節(jié) 動(dòng)態(tài)規(guī)劃在經(jīng)濟(jì)和管理中的應(yīng)用 ? 復(fù)合系統(tǒng)可靠性問(wèn)題 ? 若某種機(jī)器的工作系統(tǒng)有 N個(gè)部件組成，只要有一個(gè)部件失靈，整個(gè)系統(tǒng)就不能正常工作。這些部件的正常工作關(guān)系為串接關(guān)系，為提高系統(tǒng)工作的可靠性，在每一個(gè)部件上均裝有主要元件的備用件，并且設(shè)計(jì)了備用件自動(dòng)投入裝臵。顯然，備用元件越多，整個(gè)系統(tǒng)正常工作的可靠性越大。但備用元件多了，整個(gè)系統(tǒng)的成本、重量、體積均相應(yīng)加大，工作精度也降低。因此，最優(yōu)化問(wèn)題是在考慮上述限制條件下，應(yīng)如何選擇各部件的備用元件數(shù)，使整個(gè)系統(tǒng)的工作可靠性最大？ 第三節(jié) 動(dòng)態(tài)規(guī)劃在經(jīng)濟(jì)和管理中的應(yīng)用 設(shè)部件 i上裝有 zi個(gè)備用元件時(shí)，它正常工作的概率是 pi(zi)。因此，整個(gè)系統(tǒng)正常工作的可靠性，可以用它的正常工作的概率來(lái)衡量。即 設(shè)部件 i的一個(gè)備用元件的費(fèi)用為 ci，重量為 wi，要求整個(gè)系統(tǒng)所裝備用元件的總費(fèi)用不超過(guò) C，總重量不超過(guò) W ?Niii zPP1)(??第三節(jié) 動(dòng)態(tài)規(guī)劃在經(jīng)濟(jì)和管理中的應(yīng)用 ? Xk表示由第 k個(gè)到