動(dòng)態(tài)規(guī)劃習(xí)題答案0001

1、2.某公司有資金 4百萬(wàn)元向 A,B 和 C3個(gè)項(xiàng)目追加投資，各個(gè)項(xiàng)目可 以有不同的投資額（百萬(wàn)元計(jì)） ，相應(yīng)的效益如表所示。問(wèn)怎樣分配 資金，使總效益值最大？ #表 8 47Wk （X k） （項(xiàng)目 k#投資額01234#1#（A）41486066#2#（B ）40425060#3#（C）64687884解：設(shè) S1A,B,C 項(xiàng)目的總投資額， S2B、C 項(xiàng)目的總投資額S3C 項(xiàng)目的投資額；Xkk 項(xiàng)目的投資額；（X1A 項(xiàng)目的投資額，X2B 項(xiàng)目的投資額，X3C項(xiàng)目的投資額） Wk（Sk,Xk）對(duì) K 項(xiàng)目投資 Xk后的收益： Wk（ Sk,X k） W k （Xk） Tk （Sk,Xk

2、） Sk+1=Sk -X kfk （Sk）當(dāng) K 至第 3項(xiàng)目允許的投資額為 Sk 時(shí)所能獲得的最大收益。 為獲得最大利潤(rùn)，必須將 4 百萬(wàn)全部投資，假設(shè)有 4 階段存在，有 S40，建立遞歸方程f4 （Sk）=0k=3,2,1fk (Sk)=max W k (X k)+f k +1 (Sk+1)XkDk(Sk)第一步， K=3f4(S4)=0f3 (S3)=maxW 3 (X3)+f4 (S4)X 3 D3(S3)S4=S3-X 3S3f3 (S3)X3*1641268237834844第二步：K=2f2 (S2)=maxW 2 (X2)+f3 (S3)X2D2(S2)W2 (X 2)+f

3、3 (S2-X2)S2X2 =0X2 =1X2 =2X2 =3f2 (S2)X2 *140+641040240+6842+641080340+7842+6850+641180440+8442+7850+6860+641240，3第三步：K=1f1 (S1) =max W1 (X1)+ f2 (S2)X1D1(S1)S2= S1- X1S1=4S2=1S3=1W1 (X1)+ f2 (S1- X1)S1X1=0X1=1X1=2X1=3f1 (S1)X1 *441+11848+160+101643084X1*=3X2*=0A 投資 3 百萬(wàn)，B 不投資X3*=1C 投資 1 百萬(wàn)總收益 164 百

4、萬(wàn)元。3. (最優(yōu)分配問(wèn)題)有一個(gè)儀表公司打算向它的 3 個(gè)營(yíng)業(yè)區(qū)設(shè) 立 6 家銷(xiāo)售店。每個(gè)營(yíng)業(yè)區(qū)至少設(shè)一家，所獲利潤(rùn)如表。問(wèn)設(shè)立的 6 家銷(xiāo)售店數(shù)應(yīng)如何分配，可使總利潤(rùn)最大？利潤(rùn)wk(x)營(yíng)業(yè)區(qū) AkA1A2A31200210180銷(xiāo)售2280220230店數(shù) x33302252604340230280#解： sk對(duì) k#,3 #營(yíng)業(yè)區(qū)允許設(shè)立的銷(xiāo)售店數(shù)#x k 對(duì) k 營(yíng)業(yè)區(qū)設(shè)立的銷(xiāo)售店數(shù)w k (s k,x k) 對(duì) k#營(yíng)業(yè)區(qū)設(shè)立 xk 銷(xiāo)售店后的利潤(rùn)：wk (s k,x k)= w k (x k)T k (s k, x k) sk +1 = s k - x kf k (s k ) 當(dāng)

5、第 k 至第 3 個(gè)營(yíng)業(yè)區(qū)允許設(shè)立的銷(xiāo)售店數(shù)為 sk時(shí)所能獲得的最大利潤(rùn)遞歸方程：f 4(s 4)=0fk (s k)=max wk (xk)+ fk+1(sk+1) , k=3,2,1xkDk(sk)k=3 時(shí)，有方程f 4 (s 4)=0f3(s3)= max w3(x3)+ f4(s4) x3D3(s3)s3=s2x2s3f3(s3)x3*11801223023260342804k=2, 有方程f2(s2)= max w2(x2)+ f3(s3) x2D2(s2)s3=s2x2w2(x2)+ f3(s2 x2)f2(s2)x2=1x2=2x2=3x2=4s22210+180/390132

6、10+230220+180/44014210+260220+230225+180/47015210+280220+260225+230230+1804901k=1, 有方程w1(x1)+ f2(s2) f1(s1)= max x1D1(s1) s2=s1x1w1(x 1)+ f2(s 1x1)f 1(s 1x1*s1x1=1x1=2x1=3x1=4)6200+490280+470330+440340+3907703s1=6 s2=3 s3=2x1*=3 x 2*=1 x 3*=2分別 A1、A2、A3營(yíng)業(yè)區(qū)設(shè)立 3家、1 家、2 家銷(xiāo)售店，最大利潤(rùn)為7704用動(dòng)態(tài)規(guī)劃方法求解下列模型： max

7、f=10X1+4X2+5X3s.t. 3X1+5 X2+4 X3150X12 0X22 X30 ，Xj 為整數(shù) j=1,2,3 解：收費(fèi) C1=10 C2=4 C3=5X1為貨物 1 的裝載件數(shù)X2為貨物 2 的裝載件數(shù)X3為貨物 3 的裝載件數(shù)分 3 階段S1為貨物 1、2、3允許的裝載重量（ 3X1+5 X2+4 X3的允許值）S2為貨物 2、3允許裝載的重量（ 5 X2+4 X3的允許值）S3 為貨物 3允許裝載的重量（ 4 X3的允許值） 第一步： K=3f4（S4）=0f3（S3）= max5X 3+ f4（S4）| X3D3（S3）S4= S3 -4 X3S303478111215

8、D3(S3)00,10,1,20,1,2,3S3X3=0X3=1X3=2X3=3f3 (S3)X3*030+000470+05+0518110+05+010+010212150+05+010+015+0153第二步： K=2f2(S2)= max4X 2+ f3(S3)| X2D2(S2)S3= S2 -5 X2S204591015D2 (S2)00,10,1,2劃分點(diǎn)：0481200481255913171010141822S24X2+ f3(S2 -5 X2)f2 (S2)X2*X2=0X2=1X2=2030+00040+550570+54+05080+104+010090+104+510

9、010110+104+58+0100120+154+58+0150130+154+108+015014150+154+108+5150第三步： K=1f1(S3)= max10X 1+ f2(S2)| X1D1(S1)S1X1=0X1=1X1=2f1 (S1)X1*150+1510+1520+10302S2= S1-3 X110X1+ f2(S1-3 X1)順序追蹤：最優(yōu)策略為 S1=15 S2=9S3=9X3*=2 X1*=2 X2*=0最優(yōu)裝載方案為：貨物 1裝2件；貨物 2不裝；貨物 3裝 2件 裝載收費(fèi)為 30 元5.用動(dòng)態(tài)規(guī)劃方法解下列 01 背包問(wèn)題： Max f =12x 1+1

10、2x 2+9x 3+16x 4+30x 5； s.t. 3x 1+4x 2+3x 3+4x 4+6x 5 12;xj=0,1, j=1, ， 5 解： 本問(wèn)題分為 5 個(gè)階段。令skakxk+a4x4 的允許值 xk第 k 階段 xk 取值， xk=0， 1wk(sk, xk)xk產(chǎn)生的價(jià)值： wk(sk, xk)=c kxkTk(sk, xk) sk+1 =sk- akxkfk(sk)在 akxk+ a4x 4 sk 的條件下， c kxk+c 4x4能取得的最大值。s530x5f5(s5)x5*x5=0x5=105000612030301f4(s4)=max16x 4+f5(s5)x4 D

11、4(s4)遞歸方程為f6(s6)=0k=5fk(sk)=maxc kxk+fk+1(sk+1),k=5,4,3,2,1xk Dk(sk)f5(s5)=mDax30x 5k=4s 5=s4-4x 4s416x4+f5(s4-4x4)f4(s4)x4*x4=0x4=1030+000450+016+0161690+3016+030010120+3016+30461k=3f3(s3)=max9x 3+f 4(s4) x3 D3(s3)s39x 3+f 4(s3-3x 3)f3(s3)x3*x3=0x3=1020+00030+09+091450+169+016060+309+0300780+309+16

12、30090+309+3039110120+469+30460s 4=s3-3x 3s3=s2-4x 2k=2k=1s2=s1-3x 1s1=12f 2(s2)=max12x 2+f3(s3) x2D2(s2)s212x2+f3(s2-4x2)f 2(s2)x2*x2=0x2=1020+00030+990450+1612+016060+3012+030070+3012+930080+3012+1630090+3912+16390100+4612+3046011120+4612+30460f1(s1)=max12x 1+f2(s2) x1 D1(s1)s112x1+f2(s1-3x1)f1(s1)

13、x1*x1=0x1=1120+4612+39511s1=12s2=9s3=9s4=6 s5=6x1*=1x2*=0 x3*=1x4*=0 x5*=111今設(shè)計(jì)一種由 4 個(gè)元件串聯(lián)而成的部件，為提高部件的可靠性， 每一元件可以由 1個(gè)、2個(gè)或 3個(gè)并聯(lián)的單位元件組成。關(guān)于元件 K （K=1 ，2，3， 4）配備 j 個(gè)并聯(lián)單位元件（ j=1，2，3）后的可靠性 Rkj 和成本 Ckj 由表給出，假設(shè)該部件的總成本允許為 15 個(gè)單位，試 問(wèn)如何確定各元件的單位元件配備數(shù)目，使系統(tǒng)的可靠性最高？jK=1K=2K=3K=4R1jC1jR2jC2jR3jC3jR4jC4j10.740.620.930

14、.8320.7550.840.82530.857解：逆序解法。Sk儀表上配備 k#， 4#元件時(shí)允許使用的費(fèi)用X k K#元件所選用的單位元件Wk（Sk，Xk） K#元件采用單位元件時(shí)的可靠性，有Wk（Sk，Xk）=RkxkTk（Sk，Xk） Sk+1= Sk - Ckxk f k（ Sk） 在費(fèi)用限額為 Sk的條件下， k#，3#元件串聯(lián)時(shí)相應(yīng)部分可獲得的最大可靠性 遞歸方程 f4（S5） =1fk（Sk）= maxW k（ Sk， X k） f k+1 （ Sk+1 ），K=4,3,2,1. 第一步，對(duì) K=4,S4R4x4F4（ S1）X4*X4=1X4=230.70.8140.80.8

15、150.80.820.82260.70.820.822第二步:S3R3x3f 1（ S3 C3x3）f 2（ S2）X3*X3=160.90.80.72170.90.80.72180.90.820.738190.90.820.7381第三步，對(duì) K=2,S2R2x2f 3（ S2 C2x2）f2（S2）X2*X2=1X2=280.60.720.432190.60.720.4321100.60.7380.80.720.5762110.60.7380.80.720.5762第四步，對(duì) K=4, f4（S4） = maxR4x4f3（S3）S3= S4 C4x4，S4=15S1R1x1f2（S41C

16、1x1）f1（ S4）X* 1X1=1X1=2X1=3150.70.576 0.750.576 0.85 0.4320.4322S1=15 S3=10 S2=6 S1=3X1*=2X2*=2X3*=1X4*=1元件 1為2個(gè)，元件 2為2個(gè)，元件 3為1個(gè)，元件 4為1個(gè)，可靠 性為 0.432。順序解法：Sk儀表上配備 1#， K#元件時(shí)允許使用的費(fèi)用Xk K#元件所選用的單位元件Wk（Sk，Xk） K#元件采用單位元件時(shí)的可靠性，有Wk（Sk，Xk）=RkxkTk（Sk，Xk） Sk-1= Sk - Ckxkf k（ Sk） 在費(fèi)用限額為 Sk的條件下， 1#， ，K#元件串聯(lián)時(shí)相應(yīng) 部分

17、可獲得的最大可靠性遞歸方程 f0（S0） =1fk（Sk） = maxWk（Sk， Xk）fk-1（Sk-1 ），K=1，2，3，4第一步，對(duì) K=1, f1（S1） = maxR1x14 S1 7S1=4，5，6，7S14567D1（S1）11,21,21,2,3S1R1x1f1（S1）X1*X1=1X1=2X1=340.70.7150.70.750.75260.70.750.75270.70.750.80.83第二步，對(duì) K=2, f2（S2） = maxR2x2f1（S1）S1= S2 C2x26 S2 9S2=6，7，8，9S26789D2（S2）111,21,2S2R2x2f 1（ S2 C2x2）f 2（ S2）X2*X2=1X2=260.60.70.42170.60.750.45180.60.750.80.70.56290.60.80.80.750.62第三步，對(duì) K=3, f3（S3） = maxR3x3f2（S2）S2= S3 C3x39 S2 12S2=9，10，11，12S39101112D3（S3）1111S3R3x3f 2（ S