【文章內(nèi)容簡介】 － xk s1=a ?????????????njxaxxxxgxgxgzjnnn,2,1 0 )()()( m a x212211??????????????????0)(1,1, )]()([m a x)(1111)(nnkkkksDxkksfnnksfxgsfkkk?狀態(tài)變量 sk及決策變量 xk都是連續(xù)變量 ， 對其進(jìn)行離散化處理 ， 具體做法是： 1. 對區(qū)間 [0， a]進(jìn)行分割，分割數(shù) m= ，其中 Δ 是分割后的小區(qū)間的長度，其大小可以根據(jù)所求解問題要求的精度及計算機運算能力而定，分割點為 0， Δ ，2Δ ， … ， mΔ= a 。 2. 規(guī)定狀態(tài)變量 sk及決策變量 xk僅在離散點 0， Δ ，2Δ ， … ， mΔ 處取值，最優(yōu)指標(biāo)函數(shù) fk（ sk） 也定義在這些離散點上。動態(tài)規(guī)劃基本方程可以寫為： 其中 sk=qΔ ， xk=pΔ 。 3. 由后向前逐段遞推，直至求出整個過程最優(yōu)解。 ?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所示。 ????????? ????1)(1,2,3 )]()([m a x)(44110sfksfxgsf kkkksxkk kk333333 )(m a x)(33sxsfsx???表 7－ 1 取值 k=2時， 計算結(jié)果見表 72 )]([m a x)]([m a x)( 223203320222222xsfxsfxsf sxsx ????? ???? k=1時， 其中 s1=6， 計算結(jié)果見表 73所示。 由表 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。 本例也可用經(jīng)典解析法求得各段的極值，讀者可自行求解，二者結(jié)論完全相同。需要指出的是當(dāng)連續(xù)變量離散化處理以后，由于狀態(tài)變量和決策變量只在給定的離散點上取值，故有可能漏掉最優(yōu)解，因此需要慎重選擇參數(shù) m與 Δ 。 )]([m a x)]([m a x)( 11221022210111111xsfxsfxsf sxsx ????? ???? 資源分配問題就是將一定數(shù)量的一種或若干種資源（原材料、資金、設(shè)備等）合理分配給若干使用者，使得資源分配后總結(jié)果最優(yōu)。一種資源的分配問題稱為一維資源分配問題，兩種資源的分配問題稱為二維資源分配問題。 四、 資源分配問題 假設(shè)有一種資源，數(shù)量為 a，將其分配給 n個使用者，分配給第 i個使用者數(shù)量 xi時，相應(yīng)的收益為 gi（ xi），問如何分配使得總收入最大？這就是一維資源分配問題，該問題的數(shù)學(xué)模型為： 這是一個靜態(tài)規(guī)劃問題，應(yīng)用動態(tài)規(guī)劃方法求解時人為賦予時間概念，將其看作是一個多階段決策問題。 ?????????????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） 即為所求問題的最大收益 。 ???????????????0)(1, )]()([m a x)(11110nnkkkksxkksfnksfxgsfkk?【 例 76】 某公司打算在 3個不同的地區(qū)設(shè)置 4個銷售點 ， 根據(jù)市場部門估計 ， 在不同地區(qū)設(shè)置不同數(shù)量的銷售點每月可得到的利潤如表 74所示 。 試問在各地區(qū)如何設(shè)置銷售點可使每月總利潤最大 。 表 74 解 如前所述 ， 建立動態(tài)規(guī)劃數(shù)學(xué)模型： 將問題分為 3個階段 ， k=1， 2， 3； 決策變量 xk表示分配給第 k個地區(qū)的銷售點數(shù)； 狀態(tài)變量為 sk表示分配給第 k個至第 3個地區(qū)的銷售點總數(shù)； 狀態(tài)轉(zhuǎn)移方程： sk+1=sk－ xk， 其中 s1=4； 允許決策集合： Dk（ sk） =｛ xk|0≤xk≤sk｝ 階段指標(biāo)函數(shù)： gk（ xk） 表示 xk個銷售點分配給第 k個地區(qū)所獲得的利潤； 最優(yōu)指標(biāo)函數(shù) fk（ sk） 表示將數(shù)量為 sk的銷售點分配給第 k個至第 3個地區(qū)所得到的最大利潤，動態(tài)規(guī)劃基本方程為： ?????????? ???0)(1,2,3 )]()([m a x)(4410sfkxsfxgsf kkkkksxkk kk k=3時， 數(shù)值計算如下表 75 表 75 )]([m a x)( 333333xgsf sx ??k=2時， 計算結(jié)果見下表 76 表 76 )]()([m a x)( 2232202222xsfxgsf sx ??? ??k=1時， k=1時，只有 s1=4的情況。 計算結(jié)果如表 77所示 。 所以 最優(yōu)解 為： x1*=2， x2*=1， x3*=1， f1(4)=47， 即在第 1個 地區(qū)設(shè)置 2個銷售點 ， 第 2個 地區(qū)設(shè)置 1個銷售點 ， 第 3個 地區(qū)設(shè)置 1個銷售點 ， 每月可獲利潤 47。 表 77 )]()([m a x)( 1121101111xsfxgsf sx ??? ??)]4()([m a x)( 121140111xfxgsf x ??? ??【 例 77】 機器負(fù)荷問題 某工廠有 100臺機器，擬分四期使用，每一期都可在高、低兩種不同負(fù)荷下進(jìn)行生產(chǎn)。若把 x臺機器投入高負(fù)荷下進(jìn)行生產(chǎn)，則在本期結(jié)束時將有 1/3x臺機器損壞報廢；余下的機器全部投入低負(fù)荷下進(jìn)行生產(chǎn)，則在期末有 1/10的機器報廢。如果高負(fù)荷下生產(chǎn)時每臺機器可獲利潤為 10，低負(fù)荷下生產(chǎn)時每臺機器可獲利潤為 7，問怎樣分配機器使四期的總利潤最大？ 解 將問題按周期分為 4個階段， k=1， 2， 3， 4； 狀態(tài)變量 sk表示第 k階段初完好的機器數(shù) ， s1=100， 0≤sk≤100； 決策變量 xk表示第 k階段投入高負(fù)荷下生產(chǎn)的機器數(shù) ， 則 sk－ xk表示第 k階段投入低負(fù)荷下生產(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???????????????????