【正文】 )}()({m i n)( 5544)(44444sfugsf sDu ?? ?)}({m i n)( 44)(44444ugsf sDu ?? u4 s4 g4（ u4） f4（ s4） u4 * s5 2 3 4 2 34 — — 34 2 0 3 34 31 — 31 3 0 4 34 31 25 25 4 0 5 34 31 25 25 4 0 6 34 31 25 25 4 0 k=3 ， 4≤s 3≤ 8， 計算得表 63。 2≤ uk≤ 4 允許決策集合： Dk（ sk） ={2≤ uk≤ sk } k=1， 2， 3， 4 狀態(tài)轉(zhuǎn)移方程： sk+1 = sk – uk gk(uk) 表示 uk個巡邏隊派往第 k個部位的預(yù)期損失值， fk(sk) 表示 sk個巡邏隊分配給第 k個部位至第 4個部位所得到的最小預(yù)期損失值 )}()({m i n)( 11)( ??? ?? kkkksDukk sfugsfkkk 先給 D部位派巡邏隊 ， 即： K=4 邊界條件 f5(s5) =0， 且 s5 =0 。 )}(30{m a x)( 443]/[033333sfusf wsu ?? ??j wj vj 1 2 65 2 3 80 3 1 30 ? 表 52 u3 Ｓ 3 30 u3 f3（ｓ 3） u3* 0 1 2 3 4 5 0 0 0 0 1 0 30 30 1 2 0 30 60 60 2 3 0 30 60 90 90 3 4 0 30 60 90 120 120 4 5 0 30 60 90 120 150 150 5 j=2 [ｓ 2/w2]=[5/3]=1 ∵ w 2的可能取值為從 0到 5，計算得下表 )}3(80{m a x)( 2232]/[022222usfusf wsu ??? ?? u2 Ｓ 2 80 u2+f3（ｓ 23 u2） f2（ｓ 2） u2* Ｓ 3 0 1 0 0+0=0 0 0 0 1 0+30=30 30 0 1 2 0+60=60 60 0 2 3 0+90=90 80+0=80 90 0 3 4 0+120=120 80+30=110 120 0 4 5 0+150=150 80+60=140 150 0 5 j=1 [ｓ 1/w1]=[5/2]=2 u1 計算得下表 回代可得 ， 當ｓ 1=5時 ， u1*=2， 此時 ， ｓ 2= ｓ 12u1=1， 故 u2*=0， 又ｓ 3= ｓ 23 u2=1， 故 u3*=1， f1（ 5） =160， 見下表 )}2(65{m a x)( 112120221usfusf u ??? ?? u1 Ｓ 1 65u1+f2（ｓ 12u1） f1（ｓ 1） u1 * Ｓ ２ 0 1 2 5 0+150=150 65+90=155 130+30 =160 160 2 ３ j 1 2 3 wj 5 1 1 uj* 2 0 1 ? Note 若對每種貨物 ,只有裝與不裝 (即uj=0或 1， j=1N)兩種選擇 ， 則該問題即為背包問題 。 解：若用 uj表示第 j種貨物的裝載件數(shù)，則問題歸結(jié)為如下整數(shù)規(guī)劃問題： ? . uj≥0 且為整數(shù) ???NjjjuvZ1m a x???Njjj Wuw1 將裝載 N種貨物看作依次分為 N個階段，用 j（ j=1， 2… N）來代表階段，第 j階段的狀態(tài)變量表示可用于第 j， j+1， … N階段的裝載重量，用ｓ j表示，用 uj表示第 j階段裝載第 j種物資的件數(shù)，則uj≤[ ｓ j/wj]，（ [a]表示 a的最大整數(shù)部分）。 該問題也可用順序解法 設(shè) sk表示給前 (k1)個廠已分配的設(shè)備套數(shù) ， k階段決策變量為 uk， 允許決策集合 Dk（ sk+1 ） ， S4=｛ 4， 5， 6｝ ， sk=sk+1uk 基本方程為： ??????? ??? ?0)(3,2,1)}()({m a x)(101)(11 sfksfugsf kkkksDukk kkkK=2 g1（ u1） + f0（ s1） f1（ s2） u1* s2 u1 0 1 2 3 4 5 6 0 0+0 0 0 1 3+0=3 3 1 2 5+0=5 5 2 3 6+0=6 6 3 4 7+0=7 7 4 5 6+0=6 6 5 6 5+0=5 5 6 表 15 K=2 g2（ u2） + f1（ s2） f2（ s3） u1* s3 u2 0 1 2 3 4 5 6 0 0+0 0 0 1 0+3=3 4+0=4 4 1 2 0+5=5 4+3=7 6+0=6 7 1 3 0+6=6 4+5=9 6+3=9 7+0=7 9 1,2 4 0+7=7 4+6=10 6+5=11 7+3=10 8+0=8 11 2 5 0+7=7 4+7=11 6+6=12 7+5=12 8+3=11 9+0=9 12 2,3 6 0+7=7 4+7=11 6+7=13 7+6=13 8+5=13 9+3=12 10+0=10 13 2,3,4 表 16 ? 表 17 K=3 g3（ u3） + f2（ s3） f3（ s4 ） u3* u3 s4 0 1 2 3 4 5 6 4 0+11=11 2+9=13 5+7=12 9+4=13 8+0=8 13 3 5 0+12=12 2+11=13 5+9=14 9+7=16 8+4=12 8+0=8 16 3 6 0+13=13 2+12=14 5+11=16 9+9=18 8+7=15 8+4=12 10+0=10 18 3 ∴ s 4=6時，即購 6套設(shè)備， f3(6) =18為最大值 ,反向追蹤可知最優(yōu)策略為 p1， 3（ s3=6） ={1， 2， 3}或 {2， 1， 3}。 狀態(tài)轉(zhuǎn)移方程： 允許決策集合： 令：最優(yōu)值函數(shù) fk（ sk）表示以數(shù)量為 sk的資源分配給第k種產(chǎn)品至第 n種產(chǎn)品所得到的最大總收入，遞推方程為： kkk uss ??? 1}0|{)( kkkkk suusD ???? ????????????????0)(1,2,2,1,)()(m a x)(1110nnkkkkksukksfnnnkusfugsfkk? 例 6 某廠為擴大生產(chǎn)能力 ， 擬訂購某種成套設(shè)備 4套 6套 ，以分配給所轄 1， 2， 3三個分廠使用 ， 預(yù)計各分廠分得不同套數(shù)的設(shè)備后 ， 每年創(chuàng)造的利潤 （ 萬元 ） 如下表所示 ， 該廠應(yīng)訂購幾套設(shè)備并如何分配才能使每年預(yù)計創(chuàng)利潤總額最大 ？ 套 數(shù) 利 潤 分 廠 0 1 2 3 4 5 6 1 0 3 5 6 7 6 5 2 0 4 6 7 8 9 10 3 0 2 5 9 8 8 7 解 ： 將問題按工廠分為三個階段 ， 以 k=1， 2， 3表示給三個分廠分配的順序 ， 狀態(tài)變量 sk表示可供第 k分廠到第 3分廠分配的設(shè)備套數(shù) ， 決策變量 uk表示分給 k分廠的套數(shù) ， gk(uk) 表示給 k分廠分配 uk套設(shè)備后的預(yù)計創(chuàng)利額 ， fk(sk)表示為 sk臺設(shè)備分配給第 k分廠至第 3分廠時所得到的最大盈利值 。 怎么辦 ？ 設(shè)狀態(tài)變量 sk表示分配用于生產(chǎn)第 k種產(chǎn)品至第 n種產(chǎn)品的資源數(shù)量 。 設(shè)有某種資源 ， 總數(shù)量為 a， 用于生產(chǎn) n種產(chǎn)品 ， 若分配數(shù)量 ui用于生產(chǎn)第 i種產(chǎn)品 ， 其收益為 gi（ ui） ， 問應(yīng)如何分配 ， 才能使生產(chǎn) n種產(chǎn)品的總收入最大 ？ 靜態(tài)規(guī)劃模型 ： max Z= g1(u1)+g2(u2)+… +gn(un) . u1+u2+… +un=a uj≥ 0， j=1， 2， … n 1○ . 當離散問題時 ， gi(ui) 較難表達 （ 分段函數(shù) ） 。 ? ?? ?%)101)(400(%)101(%)101(1m a x)400()( 12140001111????????? ?? uufsf u? ?? ? 039。 狀態(tài)轉(zhuǎn)移方程為： sk+1=（ sk uk） （ 1+10%） k=1，2， 3， fk（ sk） 表示第 k年年初公司有資金 sk， 從第 k年至第 4年末的效益和最大值 ， f1（ s1） = f1（ 400） 即為所求 ， 則： 基本方程 ： k=3 由一元函數(shù)導(dǎo)數(shù) 得： 則： 由狀態(tài)轉(zhuǎn)移方程 ????????? ????444110)(1,2,3)}({m a x)(ssfksfusf kkksukk kk? ? ? ?%)101)((m a x)()(m a x)( 333044330333333?????? ???? ususfsusf susu039。 j=0,1,… ,5,6 S． t． i=1， 2， 3 ????01ijx 否則套設(shè)備個分廠分配得第 ji? ?? ??3161m a xi jijij xcZ???601jijx? ?? ???316164i jijjx （ 資源連續(xù)分配問題 ） 某有限股份公司現(xiàn)有 400萬元款項 ， 計劃在四年內(nèi)使用 ， 現(xiàn)在要擬定一個最優(yōu)使用方案 。 ∴ f3（ s3） =3(12s3)20s3+280=24417s3， 取 u3=12s3 k=2時 = （單調(diào)下降） 其中， D2（ s2） 由 3=d3≤s 2+u2d2≤H=9 確定 即 max{0， 8s3}≤ u2≤ 14 s2 ∴ f 2(s2)=4（ 14s2） 17s2+329=27313s2， 取 u2=14s2 )( 333minsDu ??)( 22 sf