【正文】 。 表 720 ? ?? ?)3()(m a x )(])1(1[m a x)(223)(332)(2222222222xsfsfpsfxsDxxsDx??????????k=1時(shí) ， 計(jì)算結(jié)果如表 721所示 。 ????????? 為整數(shù)且 kkkkkkk xcsxxsD ],[0)(kxkp )1( ?k=3時(shí) ， 由于 A、 B至少要購置 1件 ， 用于購置 C的最高金額為s3=10－ 2－ 3=5萬元 ， 計(jì)算結(jié)果如表 719所示 。 ?????? ??? 為整數(shù)且kkkkkkkkkk uwycxuuyxD ] ) ,[],m i n ( [0),(?????????????????1),(1,1, )],()([m a x),(111111),(nnnkkkkkyxDukkkyxfnnkyxfupyxfkkkk?【 例 711】 某廠設(shè)計(jì)的一種電子設(shè)備由三種元件A、 B、 C串聯(lián)而成 ， 已知三種元件的價(jià)格及可靠性如表 718所示 ， 要求設(shè)計(jì)中使用元件的總費(fèi)用不超過 10萬元 ， 問如何設(shè)計(jì)使設(shè)備的可靠性達(dá)到最大 （ 不考慮重量限制 ） 。 七、復(fù)合系統(tǒng)工作可靠性問題 某個(gè)機(jī)器工作系統(tǒng)由 n個(gè)部件串聯(lián)而成，其中只要有一個(gè)部件失效，則整個(gè)系統(tǒng)不能正常工作，因此為了提高系統(tǒng)工作的可靠性，在設(shè)計(jì)時(shí)，每個(gè)主要部件上都裝有備用元件，一旦某個(gè)主要部件失效，備用元件會(huì)自動(dòng)投入系統(tǒng)工作，顯然備用元件越多，系統(tǒng)工作可靠性越大，但是備用元件越多，系統(tǒng)的成本、重量、體積相應(yīng)增大，工作精度降低，因此在上述限制條件下，應(yīng)選擇合理的備用元件數(shù)，使整個(gè)系統(tǒng)的工作可靠性最大。 表 716 )]3(130[m a x )](130[m a x)(2232]3[,1,0332]3[,1,0222222xsfxsfxsfsxsx?????????k=1時(shí) ， 計(jì)算結(jié)果如表 717所示 。 背包問題的數(shù)學(xué)模型為： ?????????????),2,1(0 )()()( m ax22112211nixaxaxaxaxcxcxczinnnn???且為整數(shù)下面用動(dòng)態(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件時(shí)的價(jià)值； 最優(yōu)指標(biāo)函數(shù) fk（ sk） 表示第 k階段裝入物品總重量為 sk時(shí)的最大價(jià)值 ， 動(dòng)態(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ù)按前述方法建立動(dòng)態(tài)規(guī)劃模型； k=3時(shí) ， 計(jì)算結(jié)果如表 715所示 。 六、背包問題 有人攜帶背包上山 ， 其可攜帶物品的重量限度為 a公斤 ， 現(xiàn)有 n種物品可供選擇 ， 設(shè)第 i種物品的單件重量為ai公斤 ， 其在上山過程中的價(jià)值是攜帶數(shù)量 xi的函數(shù) ci（ xi） ， 問應(yīng)如何安排攜帶各種物品的數(shù)量 ， 使總價(jià)值最大 。 已知倉庫最多可存儲(chǔ) 600件這種商品 ， 已知 1月初存貨 200件 ， 根據(jù)預(yù)測知 1至 4月份各月的單位購貨成本及銷售價(jià)格如表 713所示 ， 每月只能銷售本月初的庫存 ， 當(dāng)月進(jìn)貨供以后各月銷售 ， 問如何安排進(jìn)貨量和銷售量 ， 使該公司四個(gè)月獲得利潤最大 （ 假設(shè)四月底庫存為零 ） 。 表 79 4 4 44 4 44 4 4 4 4 5 5()4 4 4()( ) m in [ ( , ) ( ) ] m i n [ ( , ) ]x D sx D sf s r s x f sr s x?????k=3時(shí) ， 計(jì)算結(jié)果如下表： 3 3 33 3 33 3 3 3 3 4 4()3 3 3 4 3 3()( ) m in [ ( , ) ( ) ] m in [ ( , ) ( 2) ]x D sx D sf s r s x f sr s x f s x????? ? ? ?k=2時(shí) ， 計(jì)算結(jié)果如下表 2 2 22 2 22 2 2 2 2 3 3()2 2 2 3 2 2()( ) m in [ ( , ) ( ) ] m in [ ( , ) ( 3 ) ]x D sx D sf s r s x f sr s x f s x????? ? ? ?k=1時(shí) ， 計(jì)算結(jié)果見表 712所示 逆向追蹤可得： x1*=5， s2=3， x2*=0， s3=0， x3*=6，s4=4， x4*=0，即第 1時(shí)期生產(chǎn) 5個(gè)單位，第 3時(shí)期生產(chǎn) 6個(gè)單位，第 2， 4時(shí)期不生產(chǎn)，可使總費(fèi)用最小，最小費(fèi)用為 。 解 以每個(gè)時(shí)期作為一個(gè)階段 ， 該問題分為 4個(gè)階段 ， k=1，2， 3， 4； 決策變量 xk表示第 k階段生產(chǎn)的產(chǎn)品數(shù)； 狀態(tài)變量 sk表示第 k階段初的庫存量； 以 dk表示第 k階段的需求，則狀態(tài)轉(zhuǎn)移方程： sk+1=sk+xk－ dk k=4， 3， 2， 1 由于期初及期末庫存為 0， 所以 s1=0， s5=0； 允許決策集合 Dk（ sk） 的確定： 當(dāng) sk≥ dk時(shí)， xk可以為 0，當(dāng) skdk時(shí)，至少應(yīng)生產(chǎn) dk－ sk， 故 xk的下限為 max（ 0， dk－ sk） ；每期最大生產(chǎn)能力為 6， xk最大不超過 6，由于期末庫存為 0， xk還應(yīng)小于本期至 4期需求之和減去本期的庫存量 ，所以 xk的上限為 min（ ， 6），故有： Dk（ sk） =｛ xk| max（ 0,dk－ sk） ≤ xk≤ min（ ,6）｝ 4jkjkds???4jkjkds???4jkjkds???階段指標(biāo)函數(shù) rk（ sk， xk） 表示第 k期的生產(chǎn)費(fèi)用與存貯費(fèi)用之和： 最優(yōu)指標(biāo)函數(shù) fk（ sk） 表示第 k期庫存為 sk到第 4期末的生產(chǎn)與存貯最低費(fèi)用 ， 動(dòng)態(tài)規(guī)劃基本方程為： 0 . 5 0( , )3 0 . 5 1 , 2 , 3 , 4 , 5 , 6kkk k kk k ksxr s xx s x??? ?? ? ??11()55( ) m i n [ ( , ) ( ) ] 4 , 3 , 2 , 1( ) 0k k kk k k k k k kx D sf s r s x f s kfs???? ? ??????? 先求出各狀態(tài)允許狀態(tài)集合及允許決策集合 ， 如表 78所示 。 90)(10932 *11*12 ???? xsxs81)(10932 *22*23 ???? xsxs54)(10932 *33*34 ???? xsxs五、生產(chǎn)計(jì)劃問題 在企業(yè)生產(chǎn)經(jīng)營活動(dòng)中，經(jīng)常會(huì)遇到如何合理安排生產(chǎn)、庫存及銷售計(jì)劃，使總效益最高的問題，這一類問題統(tǒng)稱為生產(chǎn)計(jì)劃問題。若把 x臺(tái)機(jī)器投入高負(fù)荷下進(jìn)行生產(chǎn)，則在本期結(jié)束時(shí)將有 1/3x臺(tái)機(jī)器損壞報(bào)廢；余下的機(jī)器全部投入低負(fù)荷下進(jìn)行生產(chǎn)，則在期末有 1/10的機(jī)器報(bào)廢。 所以 最優(yōu)解 為： x1*=2， x2*=1， x3*=1， f1(4)=47， 即在第 1個(gè) 地區(qū)設(shè)置 2個(gè)銷售點(diǎn) ， 第 2個(gè) 地區(qū)設(shè)置 1個(gè)銷售點(diǎn) ， 第 3個(gè) 地區(qū)設(shè)置 1個(gè)銷售點(diǎn) ， 每月可獲利潤 47。 表 74 解 如前所述 ， 建立動(dòng)態(tài)規(guī)劃數(shù)學(xué)模型： 將問題分為 3個(gè)階段 ， k=1， 2， 3； 決策變量 xk表示分配給第 k個(gè)地區(qū)的銷售點(diǎn)數(shù)； 狀態(tài)變量為 sk表示分配給第 k個(gè)至第 3個(gè)地區(qū)的銷售點(diǎn)總數(shù)； 狀態(tài)轉(zhuǎn)移方程： sk+1=sk－ xk， 其中 s1=4； 允許決策集合： Dk（ sk） =｛ xk|0≤xk≤sk｝ 階段指標(biāo)函數(shù)： gk（ xk） 表示 xk個(gè)銷售點(diǎn)分配給第 k個(gè)地區(qū)所獲得的利潤； 最優(yōu)指標(biāo)函數(shù) fk（ sk） 表示將數(shù)量為 sk的銷售點(diǎn)分配給第 k個(gè)至第 3個(gè)地區(qū)所得到的最大利潤，動(dòng)態(tài)規(guī)劃基本方程為： ?????????? ???0)(1,2,3