【正文】 d( B1,C3 ) + f3 (C3 ) 1+4 4 = min 6 = 4 5 第二階段（ B → C）： B 到 C 有六條路線。 f1(A)1 = d(A, B1 )＋ f2 ( B1 ) ＝ 2＋ 4＝ 6 f1 (A)2 = d(A, B2 )＋ f2 ( B2 ) ＝ 4＋ 3＝ 7 ∴ f1 (A) = min = min｛ 6,7｝ =6 d(A, B1 )＋ f2 ( B1 ) d(A, B2 )＋ f2 ( B2 ) (最短路線為 A→B 1→ C1 → D) A B1 B2 C1 C2 C3 D 2 4 3 3 3 3 2 1 1 1 4 A B1 B2 C1 C2 C3 D 2 4 3 3 3 3 2 1 1 1 4 最短路線為 A→B 1→ C1 → D 路長為 6 三、非線性規(guī)劃問題 【 例 74】 用動態(tài)規(guī)劃方法解下列非線性規(guī)劃問題 ???????????3,2,1 0 m a x3213221ixcxxxxxxzi解： 解決這一類靜態(tài)規(guī)劃問題 ， 需要人為地賦予時間概念 ， 從而將該問題轉(zhuǎn)化為多階段決策過程 。 032 222222 ??? xsxdxdh22 32 sx ?22222262 xsdx hd ?? 0232 2222222????ssxdxhd22 32 sx ?32222222 274)32()32()( sssssf ??? 2*2 32 sx ?k=1時， 令 解得： x1=s1（舍） 所以 是極大值點。 例如靜態(tài)規(guī)劃模型 其動態(tài)規(guī)劃基本方程為： 狀態(tài)轉(zhuǎn)移方程為 sk+1=sk－ xk s1=a ?????????????njxaxxxxgxgxgzjnnn,2,1 0 )()()( m a x212211??????????????????0)(1,1, )]()([m a x)(1111)(nnkkkksDxkksfnnksfxgsfkkk?狀態(tài)變量 sk及決策變量 xk都是連續(xù)變量 ， 對其進行離散化處理 ， 具體做法是： 1. 對區(qū)間 [0， a]進行分割，分割數(shù) m= ，其中 Δ 是分割后的小區(qū)間的長度，其大小可以根據(jù)所求解問題要求的精度及計算機運算能力而定，分割點為 0， Δ ，2Δ ， … ， mΔ= a 。動態(tài)規(guī)劃基本方程可以寫為： 其中 sk=qΔ ， xk=pΔ 。 ?a?????????????????0)(1,1, )]()([m a x)(111,2,1,0nnkkkqpkksfnnkpsfpgsf ??【 例 75】 解 按變量個數(shù)將原問題分為三個階段 ， 階段變量 k=1， 2，3； 選擇 xk為決策變量； 狀態(tài)變量 sk表示第 k階段至第 3階段決策變量之和； 取小區(qū)間長度 Δ=1 ，小區(qū)間數(shù)目 m=6/1=6，狀態(tài)變量sk的取值點為： 狀態(tài)轉(zhuǎn)移方程： sk+1=sk－ xk； 允許決策集合： Dk（ sk） =｛ xk|0≤xk≤sk｝ k=1， 2， 3 xk， sk均在分割點上取值； ???????????3,2,1 06 m a x32133221jxxxxxxxzj??????62 6,5,4,3,2,1,01sks k 階段指標(biāo)函數(shù)分別為： g1（ x1） =x12 g2（ x2） =x2 g3（ x3） =x33， 最優(yōu)指標(biāo)函數(shù) fk（ sk） 表示從第 k階段狀態(tài) sk出發(fā)到第 3階段所得到的最大值，動態(tài)規(guī)劃的基本方程為： k=3時， s3及 x3取值點較多，計算結(jié)果以表格形式給出，見表 71所示。 由表 73知 ， x1*=2， s1=6， 則 s2= s1－ x1*=6－ 2=4， 查表 72得： x2*=1， 則 s3= s2－ x2*=4－ 1=3， 查表 71得：x3*=3， 所以最優(yōu)解為： x1*=2， x2*=1， x3*=3， f1(s1)=108。需要指出的是當(dāng)連續(xù)變量離散化處理以后，由于狀態(tài)變量和決策變量只在給定的離散點上取值，故有可能漏掉最優(yōu)解，因此需要慎重選擇參數(shù) m與 Δ 。一種資源的分配問題稱為一維資源分配問題，兩種資源的分配問題稱為二維資源分配問題。 ?????????????nixaxxxxgxgxgzinnn,2,1 0 )()()( m a x212211???按變量個數(shù)劃分階段 ， k=1， 2， … ， n； 設(shè)決策變量 uk=xk， 表示分配給第 k個使用者的資源數(shù)量； 設(shè)狀態(tài)變量為 sk， 表示分配給第 k個至第 n個使用者的總資源數(shù)量； 狀態(tài)轉(zhuǎn)移方程： sk+1=sk－ xk， 其中 s1=a； 允許決策集合： Dk（ sk） =｛ xk|0≤xk≤sk｝ 階段指標(biāo)函數(shù)： vk（ sk， uk） =gk（ xk） 表示分配給第 k個使用者數(shù)量 xk時的收益； 最優(yōu)指標(biāo)函數(shù) fk（ sk） 表示以數(shù)量 sk的資源分配給第 k個至第 n個使用者所得到的最大收益 ， 則動態(tài)規(guī)劃基本方程為： 由后向前逐段遞推 ， f1（ a） 即為所求問題的最大收益 。 試問在各地區(qū)如何設(shè)置銷售點可使每月總利潤最大 。 計算結(jié)果如表 77所示 。 表 77 )]()([m a x)( 1121101111xsfxgsf sx ??? ??)]4()([m a x)( 121140111xfxgsf x ??? ??【 例 77】 機器負荷問題 某工廠有 100臺機器，擬分四期使用，每一期都可在高、低兩種不同負荷下進行生產(chǎn)。如果高負荷下生產(chǎn)時每臺機器可獲利潤為 10，低負荷下生產(chǎn)時每臺機器可獲利潤為 7，問怎樣分配機器使四期的總利潤最大？ 解 將問題按周期分為 4個階段， k=1， 2， 3， 4； 狀態(tài)變量 sk表示第 k階段初完好的機器數(shù) ， s1=100， 0≤sk≤100； 決策變量 xk表示第 k階段投入高負荷下生產(chǎn)的機器數(shù) ， 則 sk－ xk表示第 k階段投入低負荷下生產(chǎn)的機器數(shù)； 允許決策集合： Dk（ sk） =｛ xk|0≤xk≤sk｝ 狀態(tài)轉(zhuǎn)移方程： sk+1=Tk（ sk， xk）， 即第 k+1階段初擁有的完好機器數(shù) sk+1為： )(109321 kkkk xsxs ???? 階段指標(biāo)函數(shù)： vk（ sk， xk） =10xk+7（ sk－ xk） 表示第 k階段所獲得的利潤； 最優(yōu)指標(biāo)函數(shù) fk（ sk） 表示從第 k階段初完好機器數(shù)為 sk至 第四階段的最大利潤，動態(tài)規(guī)劃基本方程為： k=4時， x4*=s4 k=3時， ∴ x3*=s3 ????????? ????0)(1,2,3,4 )](),([m a x)(55110sfksfxsvsf kkkkksxkk kk4440444044 10)73(m a x)](710[m a x)( 4444 ssxxsxsf sxsx ?????? ????333033333304333044333033350 )1632(m a x )](10932[10)(710m a x ]10)(710[m a x )]()(710[m a x)(33333333ssxxsxxsxsxsxsfxsxsfsxsxsxsx???????????????????????????????k=2時， ∴ x2*=0 k=1時， ∴ x1*=0 22202222220322203322202222 )9822(m a x )](10932[350)(710m a x ]350)(710[m a x )]()(710[m a x)(22222222sxsxsxxsxsxsxsfxsxsfsxsxsxsx???????????????????????????????11101111110211102211101151 3 4 )153251 3 4(m a x