【正文】 m a x)2()2,0()1()1,0()0()0,0(m a x)0(2323233 ?????????????????????????????fpfpfpf 1*3 ?u? ???????? ???1)(3,2,1,)(),(m a x)(10111sfksfuspsf kkkkkkk46 有一個(gè)徒步旅行者，其可攜帶物品重量的限度為 a 公斤，設(shè)有n 種物品可供他選擇裝入包中。 所以問(wèn)題就是求 fn(a) 48 其遞推關(guān)系式為： ? ?nkxayfxcyf kkkkkayxkkk????? ???2 10其中)(m a x)(當(dāng) k=1 時(shí)，有： 的最大整數(shù)表示不超過(guò)其中1111111 )(ayayaycxcyf??????????????????49 例 3：求下面背包問(wèn)題的最優(yōu)解 ??????????且為整數(shù)0,55231258m a x321321321xxxxxxxxxZ 物品 (xi ) x1 x2 x3 重量（ ai） 3 2 5 使用價(jià)值 8 5 12 解 ： a＝ 5 ，問(wèn)題是求 f3(5) ? ? )55(12m a x)5( 323503333xfxfxax?????整數(shù)50 ? ?)( ma x)( 323503 55125333xfxfxax?????整數(shù)? ?)( m a x 323550551233xfxxx????整數(shù)＝? ? )( m ax 32310 55123xfxx ??，＝＝?????? ???? )( )()( ),(m a x 10223301250xxff＝物品 (xi ) x1 x2 x3 重量（ ai） 3 2 5 使用價(jià)值 8 5 12 51 ? ?? ?? ???????????????????????? 5 5 )( 2)1()0(1112122,10212250212502222222222)1(10),3(5),5(0m a x)25(m a x)25(m a x)25(5m a x)5(xxxxxxxaxfffxfxxfxxfxf＝＝＝，＝整數(shù)整數(shù)物品 (xi ) x1 x2 x3 重量（ ai） 3 2 5 使用價(jià)值 8 5 12 ?????? ???? )()()()(m a x)(1022333012505x xf, f＝f52 ? ?? ?? ?)0( )0(0m a x )20(5 m a x )20(5 m a x )20(5 m a x)0(1 )0( 12120212 200212 0022222222ffxfxxfxxfxfxxxxxax????????????????????＝＝＝＝整數(shù)整數(shù) 物品 (xi ) x1 x2 x3 重量（ ai） 3 2 5 使用價(jià)值 8 5 12 ?????????? )1()0(22333)0(12)5(0m a x)5(x xf, f＝f53 )0(0308)0()0(0318)1()1(8338)3()1(8358)5(1111111111111111????????????????????xxcfxxcfxxcfxxcf ? ? )1,1(1310,85,8m a x)1(10),3(5),5(0m a x)5(212)1()0(1112222???????????????????xxffffxxx )( 54 )0,0(0)0()0(0m a x)0( 211)0(122????????????xxfffx＝? ? )0,1,1(13012,130m a x)0(12),5(0m a x)5(321)1()0(22333??????????????????xxxfffxx＝所以，最優(yōu)解為 X＝（ 1 . 1 . 0）， 最優(yōu)值為 Z = 13。 問(wèn)題：如何確定各工廠的資金數(shù)，使得總的利潤(rùn)為最大。上式可變?yōu)椋? ? ?)()(m ax)( , yxfygxf kkxyk ??? ?? 1210 ?所以，根據(jù)動(dòng)態(tài)規(guī)劃的最優(yōu)化原理，有下式： 58 例 4： 設(shè)國(guó)家撥給 60萬(wàn)元投資，供 四 個(gè)工廠擴(kuò)建使用，每個(gè)工廠擴(kuò)建后的利潤(rùn)與投資額的大小有關(guān)，投資后的利潤(rùn)函數(shù)如下表所示。顯然有 f1(x) ＝ g1(x)，得到下表 投資 利潤(rùn) 0 10 20 30 40 50 60 f1(x) ＝ g1(x) 0 20 50 65 80 85 85 最優(yōu)策略 0 10 20 30 40 50 60 第二階段：求 f2(x)。 ? ?)60()(m ax)60( 1260,10,02 yfygf y ??? ? ?61 ? ?105)0()50()10()40()20()30()30()20()40()10()50()0( )50()(m a x)50(1212121212121250,10,02??????????????????????????????????fgfgfgfgfgfgyfygfy ?最優(yōu)策略為（ 30， 20），此時(shí)最大利潤(rùn)為 105萬(wàn)元。 f2(0) ＝ 0。此時(shí)需考慮第一、第二及第三個(gè)工廠如何進(jìn)行投資分配，以取得最大的總利潤(rùn)。即問(wèn)題的最優(yōu)策略。 1. n 1 排序問(wèn)題 即 n 種零件經(jīng)過(guò) 1 種設(shè)備進(jìn)行加工，如何安排？ 14 6 8 20 23 交貨日期（ d） 4 5 1 7 3 加工時(shí)間（ t） 零件代號(hào) 2j1j 3j 4j 5j例： 三、排序問(wèn)題 69 （ 1）平均通過(guò)設(shè)備的時(shí)間最小 按零件加工時(shí)間非負(fù)次序排列順序，其時(shí)間最小。 地區(qū) 銷(xiāo)售點(diǎn) 0 1 2 3 4 1 2 3 0 0 0 16 12 10 25 17 14 30 21 16 32 22 17 x1=2， x2=1， x3=1， f3(4)=47 81 練習(xí) 1：某廠生產(chǎn)三種產(chǎn)品，各種產(chǎn)品重量與利潤(rùn)的關(guān)系如表所示。已知總裝車(chē)間的各個(gè)月份的需求量以及在加工車(chē)間生產(chǎn)該部件每單位數(shù)量所需工時(shí)，倉(cāng)庫(kù)容量和開(kāi)始庫(kù)存量，要求最終庫(kù)存量為 0，要制定一個(gè)半年的逐月生產(chǎn)計(jì)劃，既滿足需要和倉(cāng)庫(kù)容量的限制，又使生產(chǎn)這種部件的總耗費(fèi)工時(shí)數(shù)最少。每月最多生產(chǎn) 4個(gè)單位，每月的需求是隨機(jī)的，或?yàn)?1或?yàn)?2單位。但同時(shí)要求必須及時(shí)滿足需求。 ? 劃分階段 將三個(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)用。一般來(lái)說(shuō)，一臺(tái)新設(shè)備出故障少，維護(hù)費(fèi)用低，帶來(lái)的經(jīng)濟(jì)效益就高；隨著使用年限的增加，新設(shè)備逐漸變舊，維護(hù)費(fèi)用增加，效用降低。 ? 建立狀態(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) 89 資源分配問(wèn)題 ? 將一種或多種有限的資源，分配給若干個(gè)使用者，而使目標(biāo)達(dá)到最優(yōu) ? 設(shè)有一原料，總量為 a，用于生產(chǎn) n種產(chǎn)品。 ? 決策變量 xk表示分配給第 k個(gè)產(chǎn)品的資源數(shù)。顯然，備用元件越多，整個(gè)系統(tǒng)正常工作的可靠性越大。即 ? 設(shè)部件 i的一個(gè)備用元件的費(fèi)用為 ci，重量為 wi，要求整個(gè)系統(tǒng)所裝備用元件的總費(fèi)用不超過(guò) C，總重量不超過(guò) W ?Niii zPP1)(??91 ? Xk表示由第 k個(gè)到第 n個(gè)部件所容許使用的總費(fèi)用 ? Yk表示由第 k個(gè)到第 n個(gè)部件所容許使用的總重量 ? Xk+1=xkzkck ? Yk+1=ykzkwk ? 允許決策集合 ? 動(dòng)態(tài)規(guī)劃基本方程 復(fù)合系統(tǒng)可靠性問(wèn)題 ])}/[],/m i n ( [0:{),( kkkkkkkkk wycxzzyxD ?????????????????1),(1,1,)],()([m a x),(1111),(nnnkkkkkkkkkyxDzkkkyxfnnkzwyzcxfzPyxfkkkk?