《管理運(yùn)籌學(xué)》習(xí)題6解答

本文格式為Word版，下載可任意編輯——《管理運(yùn)籌學(xué)》習(xí)題6解答《管理運(yùn)籌學(xué)》習(xí)題6解答

（復(fù)習(xí)參考題）1.某公司從銀行獲得貸款300萬(wàn)元，現(xiàn)有3個(gè)項(xiàng)目A、B、C可供投資，投資不同項(xiàng)目所獲收益（單位：十萬(wàn)元）不同，如表1所示。問(wèn)：公司如何分派這300萬(wàn)元資金用于以下三個(gè)項(xiàng)目，才能使公司總收益最大？要求：

（1）請(qǐng)建立該問(wèn)題的動(dòng)態(tài)規(guī)劃模型，要求說(shuō)明各變量與指標(biāo)的實(shí)際意義。（2）請(qǐng)用逆序解法求解，并寫(xiě)出最優(yōu)分派方案的結(jié)論。表1123收益投資額0(十萬(wàn)(百萬(wàn)元)元)項(xiàng)目ABC000454710691111解：（1）建立動(dòng)態(tài)規(guī)劃模型，如下：

①將問(wèn)題按項(xiàng)目個(gè)數(shù)分為三個(gè)階段，k=1,2,3，分別對(duì)應(yīng)項(xiàng)目A、B、C。每個(gè)階段決定給項(xiàng)目k分派一定數(shù)量的資金。

②設(shè)狀態(tài)變量sk表示第k階段初尚未分派的資金數(shù)（單位：百萬(wàn)元），也是項(xiàng)目k到項(xiàng)目3所分派資金的總和。顯然s1=3,s4=0。s2和s3的取值可以為0至3之間的任何一個(gè)整數(shù)。③設(shè)決策變量uk表示分派給第k個(gè)項(xiàng)目的資金額（單位：百萬(wàn)元）。顯然uk∈Dk(sk)={0,1,…,sk}。④狀態(tài)轉(zhuǎn)移方程：sk+1=sk－uk。⑤指標(biāo)函數(shù)：階段指標(biāo)函數(shù)dk(uk)表示從Sk百萬(wàn)元中拿出uk百萬(wàn)元資金分派給項(xiàng)目k所能創(chuàng)造的收益（單位：十萬(wàn)元）,見(jiàn)表1所示。最優(yōu)指標(biāo)函數(shù)fk(sk)表示sk百萬(wàn)元的資金分派給第k至第3個(gè)項(xiàng)目時(shí)所得到的最大總收益（單位：十萬(wàn)元）。⑥逆序解法的基本方程如下：?fksk?maxdksk,uk?fk?1sk?1,k?3,2,1?uk?Dk(sk)

??fs?044?

（2）用逆序解法求解

當(dāng)n=3時(shí)，u3=s3,f4(s4)=f4(0)=0,計(jì)算過(guò)程如下表所示：u3f3(s3)=d3(u3)**f3(s3)u3s30123??????????012304611046110123*u2當(dāng)n＝2時(shí)，0≤u2≤s2，s3＝s2-u2,計(jì)算過(guò)程如下表所示：u2f2(s2)=d2(u2)＋f3(s2-u2)*f2(s2)s20123010+0=00+4=45+0=5050123u1s130+6=60+11=115+4=95+6=1110+0=1010+4=1411+0=11101422*u1當(dāng)n=1時(shí)，0≤u1≤3，s2＝3-u1,計(jì)算過(guò)程如下表所示：00+14f1(s1)=d1(u1)＋f2(3-u1)124+107+539+0f1*(3)140或1此題有兩個(gè)最優(yōu)方案：

**方案一：u1＝0，u*2＝2u1＝1*****s*2=s1-u1＝3-0＝3s3=s2-u2＝3-2＝1

即項(xiàng)目A、項(xiàng)目B、項(xiàng)目C分別分派0、2、1百萬(wàn)元，最大總收益為f1*(3)=14百萬(wàn)元。

**方案二：u1＝1，u*2＝2u1＝0*****s*2=s1-u1＝3-1＝2s3=s2-u2＝2-2＝0

即項(xiàng)目A、項(xiàng)目B、項(xiàng)目C分別分派1、2、0百萬(wàn)元（…1分），最大總收益為f1*(3)=14百萬(wàn)元。

（復(fù)習(xí)參考題）2.某工廠有100臺(tái)機(jī)器，擬分四期使用，每一期都可在高、低兩種不同負(fù)荷下進(jìn)行生產(chǎn)。若把x臺(tái)機(jī)器投入高負(fù)荷下進(jìn)行生產(chǎn)，則在本期終止時(shí)將有1/3的機(jī)器損壞報(bào)廢；余下的機(jī)器全部投入低負(fù)荷下進(jìn)行生產(chǎn)，則在期末有1/10的機(jī)器報(bào)廢。假使高負(fù)荷下生產(chǎn)時(shí)每臺(tái)機(jī)器可獲利潤(rùn)為10，低負(fù)荷下生產(chǎn)時(shí)每臺(tái)機(jī)器可獲利潤(rùn)為7，問(wèn)怎樣分派機(jī)器使四期的總利潤(rùn)最大？要求：（1）建立該問(wèn)題完整的動(dòng)態(tài)規(guī)劃模型。（2）用逆序解法求解，給出最優(yōu)分派方案。解：（1）建立動(dòng)態(tài)規(guī)劃模型

①將問(wèn)題按年度分為四個(gè)階段，k=1,2,3,4。每個(gè)階段初決定投入高、低兩種負(fù)荷生產(chǎn)的機(jī)器數(shù)量。

②設(shè)狀態(tài)變量sk表示第k階段初擁有的完好機(jī)器的臺(tái)數(shù)。s1=100

③設(shè)決策變量uk表示第k期初投入高負(fù)荷生產(chǎn)的機(jī)器臺(tái)數(shù)，則投入低負(fù)荷生產(chǎn)的機(jī)器臺(tái)數(shù)vk=sk-uk。顯然uk∈Dk(sk)={uk|0≤uk≤sk}。

④狀態(tài)轉(zhuǎn)移方程：sk+1=auk+bvk=2/3uk+9/10(sk-uk)。

⑤指標(biāo)函數(shù)：階段指標(biāo)函數(shù)dk(Sk,uk)表示第k期從Sk臺(tái)設(shè)備中抽出uk臺(tái)投入高負(fù)荷生產(chǎn)時(shí)得到的利潤(rùn)。dk(Sk,uk)＝10uk+7(sk-uk)；最優(yōu)指標(biāo)函數(shù)fk(sk)表示sk臺(tái)設(shè)備在第k至第4期分派時(shí)所得到的最大利潤(rùn)總和.⑥逆序解法的基本方程如下：?fsmaxdk?sk,uk??fk?1?sk?1?,k?4，3,2,1k?k???uk?Dk(sk)???f5?s5??0??（2）用逆序解法求解①第4階段，k=4

s5=2/3×u4+9/10×(s4–u4)

f4(s4)?max[10x4?7(s4?u4)?f5(s5)]?max(3u4?7s4)?10s40?u4?s40?u4?s4

∴u4=s4時(shí)f4(s4)最大。

②第3階段，k=3s4=2/3u3+9/10(s3–u3)

*

f3(s3)?max[10u3?7(s3?u3)?f4(s4)]0?u3?s3?max[10u3?7(s3?u3)?10s4]0?u3?s329???max?10u3?7(s3?u3)?10[u3?(s3?u3)]?0?u3?s3310??2?max(u3?16s3)0?u3?s33

50?s33∴u3=s3時(shí)f3(s3)最大。

③第2階段，k=2s3=2/3u2+9/10(s2–u2)

*

f2(s2)?max[10u2?7(s2?u2)?f3(s3)]0?u2?s2

50s3]0?u2?s235029???max?10u2?7(s2?u2)?[u2?(s2?u2)]?0?u2?s23310??8?max(22s2?u2)0?u2?s29?22s2?max[10x2?7(s2?u2)?∴u3=0時(shí)f2(s2)最大。

④第1階段，k=1s2=2/3u1+9/10(s1–u1)

*

f1(s1)?max[10u1?7(s1?u1)?f2(s2)]0?u1?s1

?max[10u1?7(s1?u1)?22s2]0?u1?s129???max?10u1?7(s1?u1)?22[u1?(s1?u1)]?0?u1?s1310??13432?max(s1?u1)0?u1?s1515∴u3=0時(shí)f1(s1)=134/5×100=2680，這就是四期的最大總利潤(rùn)和。結(jié)論：最優(yōu)分派方案如下：s1=100，第一期投入高負(fù)荷機(jī)器臺(tái)數(shù)u1*=0臺(tái)，低負(fù)荷機(jī)器臺(tái)數(shù)100-0=100臺(tái)；其次期投入高負(fù)荷機(jī)器臺(tái)數(shù)u2*=0臺(tái)，低負(fù)荷90-0=90臺(tái)；2*9*s2?u1?(s1?u1)?903102*9*s3?u2?(s2?u2)?81310第三期投入高負(fù)荷機(jī)器臺(tái)數(shù)u3*=s3=81，低負(fù)荷81-81＝0臺(tái)；

*

s4?2*9u3?(s3?u*3)?54310第四期投入高負(fù)荷機(jī)器臺(tái)數(shù)u4*=s4=54，低負(fù)荷54-54＝0臺(tái)。

3.某企業(yè)某種產(chǎn)品在第一、二、三月的需求量分別為3、4、3百件。假定該單位生產(chǎn)的固定成本為8元（假使沒(méi)有產(chǎn)量依舊存在），單位產(chǎn)品變動(dòng)成本為2元，每月末沒(méi)有售出的產(chǎn)品要收取存儲(chǔ)費(fèi)每單位2元，第一月初庫(kù)存為1百件，第四月末都沒(méi)有庫(kù)存。生產(chǎn)最大能力和儲(chǔ)存能力分別為6百件、4百件。求該企業(yè)在滿足市場(chǎng)需求條件下每月應(yīng)生產(chǎn)多少產(chǎn)品，使總成本最??？要求：（1）建立動(dòng)態(tài)規(guī)劃模型；（2）用逆序解法求解，并畫(huà)出狀態(tài)轉(zhuǎn)移圖。解：（1）建立動(dòng)態(tài)規(guī)劃模型

①階段變量k表示第k個(gè)月，k=1,2,3。

②狀態(tài)變量vk表示第k月初的庫(kù)存量。顯然v1=1，v4=0。其中常數(shù)dk為第k個(gè)月的需求量，

nk?1為已知參數(shù)。0?vk?min[4,?dj,1??(6?dj)]j?kj?1

③決策變量uk表示第k月的生產(chǎn)量。允許決策集合Dk（vk）如下：

4

max[0,dk?vk]?uk?min(6,dk?vk,dk?3?vk)

j?k④狀態(tài)轉(zhuǎn)移方程為vk+1=vk+uk-dk

⑤指標(biāo)函數(shù)：階段指標(biāo)函數(shù)表示第k月生產(chǎn)、庫(kù)存的總費(fèi)用(包括每月產(chǎn)品的固定成本、總可變成本、存貯費(fèi)用)，具體形式Vk(vk,xk)=ck(xk)+2(vk+uk-dk)=8+2·uk+2(vk+uk-dk)；最優(yōu)指標(biāo)函數(shù)fk(vk)表示從第k月到第3月的最小總費(fèi)用。⑥動(dòng)態(tài)規(guī)劃的逆序遞推的基本方程如下：?fk(vk)?min??Vk(vk,uk)?fk?1(vk?1)??k=3,2,1?uk?Dk(vk)???f4(v4)?f4?0??0

?（2）用逆序解法求解：

①k＝3

v4=0=v3+u3-30?v3?min[4,3,1?(6?3)?(6?4)]?3v3取值只能是0,1,2,3，相應(yīng)u3取值為3,2,1,0。下面列表計(jì)算f4(v4)u[c33?u3??2(v3?u3?3)]?f4(v4)3212+0+0110+0+0f(v)333*v301412108u3210012314+0+08+0+0②k＝2

v3=v2+u2-40?v2?min[4,4?3,1?(6?3)]?4于是max[0,4?v2]?x2?min(6,(4?3)?v2,4?4?v2)

所以當(dāng)v2＝0時(shí)，u2=4,5,6;當(dāng)v2＝1時(shí)，u2=3,4,5,6;當(dāng)v2＝2時(shí)，u2=2,3,4,5;當(dāng)v2＝3時(shí)，u2=1,2,3,4;當(dāng)u2＝4時(shí)，u2=0,1,2,3下面列表計(jì)算f3(v3)

u2f322[c2?u2??2(v2?u2?4)]?(v?u?4)0123456f(v)222*v2u43210012348+0+1416+0+1418+2+1220+4+103026242214+0+1416+2+1218+4+1020+6+82812+0+1414+2+1216+4+1018+6+810+0+1412+2+1214+4+1016+6+810+2+1212+4+1014+6+8③k=1時(shí)，

v1=1,2?max[0,3?1]?u1?min(6,(3?4?3)?1,3?4?1)?6v2=1+x2-3u1[c1?u1??2(1?u1?3)]?f2(1?u1?3)2345f(v)11*v16u1112+0+3014+2+2816+4+2618+6+2420+8+22422結(jié)論：

由k=1順序遞推到k=3,可得各期最優(yōu)決策：

u1*=2,v2=1+2-3=0→u2*=4,v3=0+4-4=0→u3*=3,v4=0+3-3=0

最小總成本費(fèi)用為f1(v1)=42百元，每月最優(yōu)產(chǎn)量為2、4、3百件。此題逆序解法的狀態(tài)轉(zhuǎn)移圖如下：

U1*(1)=2U1*(0)=4U1*(0)=3v1*=1v2*=0v3*=0v4*=0231d1*(1,2)=12d2*(0,4)=16d3*(0,3)=14

3

4.（選做題：二維背包問(wèn)題）蛇口碼頭有一艘載重量為30t，最大容積為12×10m的船，由于運(yùn)輸需要,這艘船可用于裝載三種貨物到珠江口，它們的每件體積,每件重量及每件價(jià)值量見(jiàn)下表2?，F(xiàn)求如何裝載這三種貨物，使價(jià)值總量最大。

表2ABC每件體積（10m3）684每件重量（t）467每件價(jià)值量234要求：（1）建立動(dòng)態(tài)規(guī)劃模型；（2）用逆序解法求解。解：（1）建立動(dòng)態(tài)規(guī)劃模型

①按貨物種類(lèi)依次分為三個(gè)階段，k=1,2,3，分別對(duì)應(yīng)A、B、C三種產(chǎn)品。每個(gè)階段決定第k種貨物裝載的件數(shù)。

3

②設(shè)狀態(tài)變量sk表示第k階段初該船剩余的容積數(shù)（單位：10m），s1=12；設(shè)狀態(tài)變量wk表示第k階段初該船剩余的載重量（單位：t），w1=30。

③設(shè)決策變量uk表示第k階段裝載第k種產(chǎn)品的件數(shù)。顯然uk∈Dk(sk,wk)={uk|0≤uk≤min([sk/ak],[wk/bk])且為整數(shù)}。參數(shù)說(shuō)明：ak和bk分別表示第k種產(chǎn)品每件體積、每件重

量。

④狀態(tài)轉(zhuǎn)移方程：sk+1=sk－akuk；wk+1=wk－bkuk。⑤指標(biāo)函數(shù)：階段指標(biāo)函數(shù)dk(uk)表示第k階段裝載uk件第k種貨物得到的價(jià)值量之和。dk(uk)＝ckuk；最優(yōu)指標(biāo)函數(shù)fk(sk,wk)表示從第k階段至第3階段裝載貨物所得到的最大價(jià)值量總和。參數(shù)說(shuō)明：ck表示第k種產(chǎn)品的每件價(jià)值量。⑥逆序解法的基本方程如下：?fs,wmaxdk?uk??fk?1?sk?1,wk?1?,k?3,2,1k?kk???uk?Dk(sk,wk)???f4?s4,w4??0??（2）用逆序解法求解

K=3時(shí)，U3的取值范圍：D3(s3,w3)={u3|0≤u3≤min([s3/4],[w3/7]且為整數(shù)}狀態(tài)轉(zhuǎn)移方程：S4=s3－4u3；w4=w3－7u3最優(yōu)指標(biāo)函數(shù)：

3333333

K=2時(shí)，D2(s2,w2)={u2|0≤u2≤min([s2/8],[w2/6])且為整數(shù)}S3=s2－8u2；w3=w2－6u2

f3?s3,w3??u?D?s,wmax?d?u??f?s,w????33444?4u3?u?D?s,w?max3

22222222

K=1時(shí)，D1(s1,w1)={u1|0≤u1≤min([12/6],[30/4])且為整數(shù)}={u1=0,1,2}S1=12－6u1；w1=30－4u1

f2?s2,w2??u?D(s,w)max?d?u??f?s,w???22333u?D(s,w)max?3u2?f3?s2?8u2,w2?6u2??

接著計(jì)算：

當(dāng)s2＝12,w2＝30時(shí)，由0≤u2≤min([12/8],[30/6])且為整數(shù)得出u2＝0,1

f?12,30??max3u?f?12?8u,30?6u??maxf?12,30?,3?f?4,24?2232233u2?0,1