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

溫馨提示：一些概念性的東西大家首次看搞不懂的話不必過(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)，如何分配才能使總收益最大？

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

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

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

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

解題思路：

1、劃分階段k：通常把資源分配給一個(gè)或幾個(gè)使用者的過(guò)程作為一個(gè)階段，比如第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)活動(dòng)間分配的資源量

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

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

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

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

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

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

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

(單位：萬(wàn)元)

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

【解析】

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

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

如果還不理解，再舉個(gè)例子：

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

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

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

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

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

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

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

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

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

采用逆推法求解：

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

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

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

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

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

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

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

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

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

至此我們就得出答案了:

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