信息系統(tǒng)項(xiàng)目管理師計算題考點(diǎn)：動態(tài)規(guī)劃-資源分配問題

溫馨提示：一些概念性的東西大家首次看搞不懂的話不必過多糾結(jié)，直接看試題解析，當(dāng)然文字描述的效果是趕不上視頻講解的，建議大家多看視頻講解。

有總數(shù)量為a的某種資源，用于生產(chǎn)n件產(chǎn)品，若分配數(shù)量x_i用于生產(chǎn)第i種產(chǎn)品的收益為g_i(x_i)，(i=1,2,…,n)，如何分配才能使總收益最大？

這種問題就是資源分配問題，準(zhǔn)確來說是一維離散資源分配問題，因?yàn)樾畔⑾到y(tǒng)項(xiàng)目管理師第4版官方教材上介紹的便是這種，所以一維連續(xù)資源分配問題、二維資源分配問題等就不介紹了，大家有興趣的可以自己去查找相關(guān)資料看看。

該問題的數(shù)學(xué)模型可以表示為：

當(dāng)收益函數(shù)g_i(x_i)均為線性函數(shù)時，該問題是一個線性規(guī)劃問題，可以利用單純形法進(jìn)行求解；當(dāng)收益函數(shù)為非線性函數(shù)時，問題變?yōu)橐粋€非線性規(guī)劃問題，如果我們采用非線性規(guī)劃的方法求解將會非常麻煩。所以根據(jù)此類問題的特點(diǎn)，我們可以把它看成一個多階段決策問題，利用動態(tài)規(guī)劃的方法求解。

對于此類資源分配問題我們用動態(tài)規(guī)劃的方法求解時，通常把資源分配給一個或幾個使用者的過程作為一個階段，將問題中的xi作為決策變量，將累計的量或隨遞推過程變化的量選為狀態(tài)變量。

解題思路：

1、劃分階段k：通常把資源分配給一個或幾個使用者的過程作為一個階段，比如第1階段就是資源分配給產(chǎn)品1，第二階段就是分配給產(chǎn)品1和2，以此類推。

2、正確選擇狀態(tài)變量S_k：狀態(tài)變量X_k可選擇k階段初所擁有的資源量，即X是要在第k項(xiàng)到第n項(xiàng)活動間分配的資源量

3、確定決策變量及允許決策集合：決策變量uk常常選對活動k的資源投放量，決策變量的允許集合是：0≤u_k≤X_k

4、確定狀態(tài)轉(zhuǎn)移方程：在選取上述狀態(tài)變量和決策變量的情況下，狀態(tài)轉(zhuǎn)移方程是：X_k+1=X_k-u_k，取投放資源時的效益為指標(biāo)函數(shù)，則g_k(u_k)為階段效益指標(biāo)

5、確定階段指標(biāo)函數(shù)和最優(yōu)指標(biāo)函數(shù)，建立動態(tài)規(guī)劃基本方程：設(shè)f_k（x_k)為k階段到n階段按最優(yōu)分配方案獲得的最大收益，則動態(tài)規(guī)劃基本方程是:

按基本方程，逆序計算，就可求得這類資源分配問題的最優(yōu)解。

當(dāng)然只看上面的內(nèi)容，可能有很多考生是看不懂的，我們結(jié)合信息系統(tǒng)項(xiàng)目管理師第4版官方教材中的例子來說明下：

【例題講解】某公司現(xiàn)有400萬元用于投資甲、乙、丙三個項(xiàng)目，限制投資以百萬元計，已知甲、乙、丙三項(xiàng)投資的可能方案及相應(yīng)增加的收益如表所示，試確定使總收益最大的投資方案。

表 項(xiàng)目投資收益值

(單位：萬元)

表中“—”表示不允許該項(xiàng)投資，即丙項(xiàng)目不能不投資，甲、乙項(xiàng)目都不能投資400萬元。

【解析】

第一步：將對甲、乙、丙項(xiàng)目投資看作按順序排列的3個階段，即：甲（K=1）、乙（K=2）、丙（K=3）

第二步：確定狀態(tài)變量SK：第K階段初還剩余的投資額，比如K=1時，表示給甲投資之前還剩余的投資額，給甲投資之前也就是還沒開始投資，當(dāng)然就還剩400萬。也可以說是第k階段到第n階段的總投資額。當(dāng)K=1時，第1階段到第3階段，即給甲、乙、丙的投資總額為400萬。

如果還不理解，再舉個例子：

比如說給甲（第1階段，K=1）投資了100萬，這時候投資額還剩余400-100=300萬元可以投資給乙和丙，也就是說在給乙投資之前（第2階段K=2初，第1階段K=2-1末）還剩300萬（即：S2=300萬元，也就是說給甲投資完后乙和丙的總投資額為300萬元）。

第三步：確定決策變量及允許的決策集合：

決策變量X_k：對第K個項(xiàng)目的投資額。這個很好理解，比如給甲投資了100萬，就是XK=100

允許的決策集合：0≤X_k≤S_K。這個就很好理解了，投出去的額度肯定要小于等于投之前還剩下的投資額，S₁=400，在給甲投資之前還剩下400萬，總不可能給甲投資（XK）超過400萬吧。

第四步：確定狀態(tài)轉(zhuǎn)移方程：S_k+1=S_K-X_k。搞清楚了前面幾個概念，這個公式就很好理解了，比如給甲投資了100萬，那么K=1時，即S₂（給甲投資了之后，準(zhǔn)備給乙投資之前還剩余的總投資額）=給甲投資之前剩余的投資額（S₁）-給甲的投資額（X_K）=400-100=300。

第五步：確定階段指標(biāo)函數(shù)和最優(yōu)指標(biāo)函數(shù)，建立動態(tài)規(guī)劃基本方程：

設(shè)階段指標(biāo)函數(shù)為：V_k(S_K，X_K)：X_k投資到第K個項(xiàng)目的收益。比如K=1時，V_K就表示投資到甲的收益。

最優(yōu)指標(biāo)函數(shù)f_k(S_k)：S_k投資到第K個項(xiàng)目至第n個項(xiàng)目時的最大收益。比如K=1時就表示投資甲、乙、丙的最大收益，也就是該題目的要求。

動態(tài)規(guī)劃基本方程：

采用逆推法求解：

第一步：求第3階段，K=3時，即給丙投資時收益最大值為：

由f₄(S₄)到f₃(S₃)的遞推過程：

根據(jù)題意S₃可能為400、300、200、100，S₃=X₃≠0。我可以得到下表：

第二步：求第2階段，K=2時，即給乙投資時收益最大值為：

由f3(S3)到f2(S2)的遞推過程：

根據(jù)題意S₂可能為400、300、200、100萬元，X₂≠400，S₃=S₂-X₂≠0

第三步：求第1階段，K=1時，即給甲投資時收益最大值為：

由f₂(S₂)到f₁(S₁)的遞推過程：

根據(jù)題意S₁為400萬元，X₁≠400，S₂=S₁-X₁≠0

至此我們就得出答案了:

當(dāng)S₁=400萬元時，最優(yōu)決策得X^*₁=0元，于是S₂=S₁-X₁=400-0=400萬元，從而查得最優(yōu)決策X^*₂=200萬元，所以X₃=400-200=200萬元，所以給甲不投資，給乙投資200萬元，給丙投資200萬元時收益最大，收益為1800萬元。