【正文】 ） =42s2+3600 k=1時 ， 類似地求得： x1*=s1， y1*=600， f1（ s1） =45s1+4800=13800 )24002240(m ax ]2400)(403842[m ax )](3842[m ax)(222)(6000022222)(600003322)(6000022222222222222222???????????????????????????????yxsxysyxsfyxsfxsysxxsysxxsysx)3 6 0 02342(m a x ]3 6 0 0)(424045[m a x )](4045[m a x)(111)(6000011111)(600002211)(6000011111111111111111???????????????????????????????yxsxysyxsfyxsfxsysxxsysxxsysx逆向追蹤得各月最優(yōu)購貨量及銷售量： x1*=s1=200 y1*=600； x2*=s2=s1+ y1*－ x1*=600 y2*=600； x3*=0 y3*=600－ s3=600－ （ s2+ y2*－ x2*） =0 x4*=s4=（ s3+ y3*－ x3*） =600 y4*=0 即 1月份銷售 200件，進(jìn)貨 600件， 2月份銷售 600件，進(jìn)貨 600件， 3月份銷售量及進(jìn)貨量均為 0， 4月份銷售 600件，不進(jìn)貨，可獲得最大總利潤 13800。 六、背包問題 有人攜帶背包上山 ， 其可攜帶物品的重量限度為 a公斤 ， 現(xiàn)有 n種物品可供選擇 ， 設(shè)第 i種物品的單件重量為ai公斤 ， 其在上山過程中的價值是攜帶數(shù)量 xi的函數(shù) ci（ xi） ， 問應(yīng)如何安排攜帶各種物品的數(shù)量 ， 使總價值最大 。 這就是背包問題 ， 類似的貨物裝載問題 ， 下料問題都等同于背包問題 。 背包問題的數(shù)學(xué)模型為： ?????????????),2,1(0 )()()( m ax22112211nixaxaxaxaxcxcxczinnnn???且為整數(shù)下面用動態(tài)規(guī)劃方法求解： 按照裝入物品的種類劃分階段 ， k=1， 2， … ， n； 狀態(tài)變量 sk表示裝入第 k種至第 n種物品的總重量； 決策變量 xk表示裝入第 k種物品的件數(shù)； 狀態(tài)轉(zhuǎn)移方程為： sk+1=sk－ akxk 允許決策集合為： 其中 表示不超過 的最大整數(shù)； ????????? 為整數(shù)kkkkkkk xasxxsD ],[0)(][kkaskkas階段指標(biāo)函數(shù) ck（ xk） 表示第 k階段裝入第 k種商品 xk件時的價值； 最優(yōu)指標(biāo)函數(shù) fk（ sk） 表示第 k階段裝入物品總重量為 sk時的最大價值 ， 動態(tài)規(guī)劃基本方程為： ???????????????0)(1,1, )]()([m a x)(1111][,1,0nnkkkkasxkksfnnksfxcsfkkk??【 例 710】 某工廠生產(chǎn)三種產(chǎn)品 ， 各產(chǎn)品重量與利潤關(guān)系如表 714所示 ， 現(xiàn)將此三種產(chǎn)品運(yùn)往市場銷售 ， 運(yùn)輸能力總重量不超過 6噸 ， 問如何安排運(yùn)輸使總利潤最大 ？ 表 714 種類 1 2 3 單位重量（噸） 2 3 4 單位利潤（元） 80 130 180 解 設(shè) xi為裝載第 i種貨物的件數(shù) ， i=1， 2， 3， 該問題數(shù)學(xué)模型為： ???????????)3,2,1(06432 18013080 m ax321321ixxxxxxxzi 且為整數(shù)按前述方法建立動態(tài)規(guī)劃模型； k=3時 ， 計算結(jié)果如表 715所示 。 )1 8 0(m a x)( 3]4[,1,03333xsfsx ???k=2時 ， 計算結(jié)果如表 716所示 。 表 716 )]3(130[m a x )](130[m a x)(2232]3[,1,0332]3[,1,0222222xsfxsfxsfsxsx?????????k=1時 ， 計算結(jié)果如表 717所示 。 表 717 )]2(80[m ax )](80[m ax)(11213,2,1,02213,2,1,01111xsfxsfxsfxx???????反向追蹤得最優(yōu)方案 Ⅰ ： x1*=0， x2*=2， x3*=0； 最優(yōu)方案 Ⅱ ： x1*=1， x2*=0， x3*=1； 最大總利潤為 260元。 七、復(fù)合系統(tǒng)工作可靠性問題 某個機(jī)器工作系統(tǒng)由 n個部件串聯(lián)而成，其中只要有一個部件失效，則整個系統(tǒng)不能正常工作，因此為了提高系統(tǒng)工作的可靠性，在設(shè)計時，每個主要部件上都裝有備用元件，一旦某個主要部件失效，備用元件會自動投入系統(tǒng)工作，顯然備用元件越多，系統(tǒng)工作可靠性越大，但是備用元件越多，系統(tǒng)的成本、重量、體積相應(yīng)增大，工作精度降低，因此在上述限制條件下，應(yīng)選擇合理的備用元件數(shù)，使整個系統(tǒng)的工作可靠性最大。 設(shè)第 i（ i=1， 2， … ， n） 個部件上裝有 ui個備用元件 ， 正常工作的概率為 pi（ ui） ， 則整個系統(tǒng)正常工作的可靠性為 ， 裝第 i個部件的費(fèi)用為 ci， 重量為 wi， 要 求總費(fèi)用不超過 c， 總重量不超過 w， 則靜態(tài)規(guī)劃數(shù)學(xué)模型為： ???niii upP1)(????????????????????niuwuwcucupPiniiiniiiniii,2,10)(m ax111?且為整數(shù)按部件個數(shù)劃分階段 ， k=1， 2， … ， n； 決策變量 uk表示部件 k上的備用元件數(shù)； 狀態(tài)變量 xk表示從第 k個到第 n個部件的總費(fèi)用 ， yk表示從第 k個到第 n個部件的總重量； 狀態(tài)轉(zhuǎn)移方程為： xk+1=xk－ ckuk yk+1=yk－ wkuk 允許決策集合為： 階段指標(biāo)函數(shù)為 pk（ uk） ， 表示第 k個部件的正常工作概率； 最優(yōu)指標(biāo)函數(shù) fk（ xk， yk） 表示由狀態(tài) xk， yk出發(fā) ， 從部件 k到部件n的系統(tǒng)工作最大可靠性 ， 則動態(tài)規(guī)劃基本方程為： f1（ c， w）即為整個系統(tǒng)工作的最大可靠性。 ?????? ??? 為整數(shù)且kkkkkkkkkk uwycxuuyxD ] ) ,[],m i n ( [0),(?????????????????1),(1,1, )],()([m a x),(111111),(nnnkkkkkyxDukkkyxfnnkyxfupyxfkkkk?【 例 711】 某廠設(shè)計的一種電子設(shè)備由三種元件A、 B、 C串聯(lián)而成 ， 已知三種元件的價格及可靠性如表 718所示 ， 要求設(shè)計中使用元件的總費(fèi)用不超過 10萬元 ， 問如何設(shè)計使設(shè)備的可靠性達(dá)到最大 （ 不考慮重量限制 ） 。 表 718 解 如前所述建立動態(tài)規(guī)劃數(shù)學(xué)模型； 按元件種類劃分為 3個階段 ， k=1， 2， 3； 決策變量 xk表示第 k個部件配備的元件數(shù)； 狀態(tài)變量 sk表示從第 k階段到第 3階段配備元件的總費(fèi)用； 狀態(tài)轉(zhuǎn)移方程為： sk+1=sk－ ckxk 其中 ck表示第 k種部件的元件單價； 允許決策集合為： 以 pk表示第 k個部件中的 1個元件的正常工作概率，假定部件 k的 xk個元件是并聯(lián)的，則 為 xk個元件均 不正常工作的概率， fk（ sk）表示由狀態(tài) sk開始從第 k個到 第 3個部件的設(shè)備最大可靠性。 ????????? 為整數(shù)且 kkkkkkk xcsxxsD ],[0)(kxkp )1( ?k=3時 ， 由于 A、 B至少要購置 1件 ， 用于購置 C的最高金額為s3=10－ 2－ 3=5萬元 ， 計算結(jié)果如表 719所示 。 表 719 )(m a x ])1(1[m a x)(33333333)(3)(33xsDxxsDxpsf???????k=2時 ， 計算結(jié)果如表 720所示 。 表 720 ? ?? ?)3()(m a x )(])1(1[m a x)(223)(332)(2222222222xsfsfpsfxsDxxsDx??????????k=1時 ， 計算結(jié)果如表 721所示 。 表 721 ? ?? ?)2()(m a x )(])1(1[m a x)(112)(221)(1111111111xsfsfpsfxsDxxsDx??????????逆向追蹤得： x1*=2， s2=6， x2*=1， s3=3， x3*=3，即 A元件用 2個， B元件用 1個， C元件用 3個，最高可靠性為 。