運(yùn)籌學(xué) 第八章

專業(yè)代碼11專業(yè)名稱信息管理與信息系統(tǒng)課程代碼18課程名稱運(yùn)籌學(xué)試題類型

代碼08試題類型名稱計(jì)算題出題人管理員出題

日期2005-11-4知識點(diǎn)

代碼評分標(biāo)準(zhǔn)1118080110噸集裝箱最多只能裝9噸，現(xiàn)有3種貨物供裝載，每種貨物的單位重量及相應(yīng)單位價(jià)值如表所示。應(yīng)該如何裝載貨物使總價(jià)值最大。貨物編號123單位加工時(shí)間234單位價(jià)值345【解】設(shè)裝載第I種貨物的件數(shù)為xi(i=1,2,3)則問題可表為：maxz=3x+4x+5xJ2x+3x+4x<9[x,x,x>0且為整數(shù)t123利用背包問題的前向動態(tài)規(guī)劃計(jì)算，建立動態(tài)規(guī)劃模型。由于決策變量離散型值，所以可用列表法求解。當(dāng)R=1時(shí)，f(s)=max(3x)。計(jì)算結(jié)果如下：難度系數(shù)較難認(rèn)知分類分析建建議議分時(shí)數(shù)間1214設(shè)有兩種資源，第一種資源有x單位，第二種資源有y單位，計(jì)劃分配給n個(gè)部門。把第一種資源有xi單位，第二種資源有yi單位分配給部門i所得的利潤為記為r設(shè)有兩種資源，第一種資源有x單位，第二種資源有y單位，計(jì)劃分配給n個(gè)部門。把第一種資源有xi單位，第二種資源有yi單位分配給部門i所得的利潤為記為ri(xi，yi)。如xKr1(x，y)r2(x，y)r3(x，y)012301230123001360246035814567146725792567846894791136789681011691113設(shè)x=3，y=3，n=3，其利潤ri(x，y)列于表中，試用動態(tài)規(guī)劃方法如何分配這兩種資源到i個(gè)部門去，使總的利潤最大？當(dāng)R=3時(shí)，f(9)=max[5x+f(9-4x)](x為整數(shù))=max[f(9)，5+f(5)，10+f332332220<x3<20<x2<2(1)]=max[13，12，10]=13最優(yōu)決策為:x=0,y=0,x=2，y=0,x=0,y=3，最大利潤為16=fG，3)1122331中運(yùn)1012用s)0033669912122——x1*0011223344當(dāng)R=2時(shí)，f(s)=max[4x+f(s-3x)]2321320<x1<s2/4計(jì)算結(jié)果如下:s30123456789x20000101010120120120123C2+f2003346467978910812101112131112f2(s3)0034679101213x2*0001010101【解】由題意可得各種貨物利潤函數(shù)為g(x)=(15【解】由題意可得各種貨物利潤函數(shù)為g(x)=(15—x—5)x=10x—x211111g(x)=(18—2x—4)x=14x—2x222222原問題的數(shù)學(xué)模型歸結(jié)為maxz=(10x一x2)+(14x一2x2)1122Jx+x=10[x,x>0最優(yōu)解：x1=6，x2=4；z=48答案：兩種最優(yōu)分配方案總收益均為21千元A：P1=15-x1，B：P2=18-2x2其中x1、x2分別為貨物A、B的重量。如果要求貨物滿載，A和B各裝載多少，才能使總利潤最大某有限公司有五臺新設(shè)備，將有選擇的分配配給下屬的三個(gè)工廠，所得收益如表中所示。問該公司應(yīng)如何分配設(shè)備，可使總收益最大？單位：千元新設(shè)備臺數(shù)工廠IIIm000013542710639111141211125131112

某公司有5臺設(shè)備，分配給所屬A,B,C三個(gè)工廠。各工廠獲得不同的設(shè)備臺數(shù)所能產(chǎn)生效益（萬元）的情況如下表。求最優(yōu)分配方案，使總效益最大。（用動態(tài)規(guī)劃方法求解）答案：階段某公司有5臺設(shè)備，分配給所屬A,B,C三個(gè)工廠。各工廠獲得不同的設(shè)備臺數(shù)所能產(chǎn)生效益（萬元）的情況如下表。求最優(yōu)分配方案，使總效益最大。（用動態(tài)規(guī)劃方法求解）狀態(tài)變量\：分配第k個(gè)工廠前剩余的設(shè)備臺數(shù)；決策變量dk：分配給第k個(gè)工廠的設(shè)備臺數(shù)；決策允許集合：0WdkW\狀態(tài)轉(zhuǎn)移方程：xk+1=xk-dk階段指標(biāo)：匕（％土;）第k次分配產(chǎn)生的效益，見表中所示;遞推方程：f（x）=max{v（x,d）+f（x）}kkkkkk+1k+1較分12難析12xD3(x3)xv3（知婦v3(x3,d3)+f較分12難析12xD3(x3)xv3（知婦v3(x3,d3)+f4(x4)5d3*00077+0=0000177+0=71121101212+0=12*0277+0=72111212+0=12152201515+0=15*0377+0=7121212+0=123183211515+0=15301818+0=18*0477+0=7131212+0=124221515+00=18402020+0=20*0577+0=7141212+0=12231515+0=155235321818+0=18412020+0=20502323+0=23*k=4，f4(x4)=0k=3，分配給工廠C，0Wd3Wx。，x4=x3-d3x2D2(x2)x3v2(x2,d2)v2(x2,d2)+f3(x3)*d2*00055+7=121200155+12=171101717+7=24*2410255+15=202111717+12=29*291202020+7=270355+18=23121717+15=32*1或23212020+12=32*32302222+7=290455+20=25131717+18=35*4222020+15=35*351或2312222+12=34402323+7=300555+23=28141717+20=37232020+18=38*5322222+15=37382412323+12=35502424+7=31k=1，分配給工廠A，0Wd,Wx,，x=x,-d.xD,（x,）xv1(x")v1(x1,d1)+f2(x2)Edd*0500+38=38141010+35=455231515+32=47493322020+29=49*412323+24=47502525+12=37最優(yōu)解為x=5,d*=3,x=x-d=2,d*=1,x=x-d*=1,d=1,x=x-d=0，1121123223433即分配給工廠A設(shè)備3臺，工廠B設(shè)備1臺，工廠C設(shè)備1臺，最大效益為49萬元。某公司決定投資60萬元（以10萬元為單位），以提高三種主要產(chǎn)品A、B、C的產(chǎn)量?，F(xiàn)決定每種產(chǎn)品至少要投資10萬元。各種產(chǎn)品投資不同資金后可獲得的期望利潤如下：分配的投資金額利潤產(chǎn)品A產(chǎn)品B產(chǎn)品C1014.516.215.92016.418.418.43018.019.922.64019.624.124.2試確定如何安排對各種產(chǎn)品的投資數(shù)，可獲得最大總期望利潤?

階段：k=1,2,3,4分別考慮產(chǎn)品A、B、C和終止階段;狀態(tài)：sk表示第k階段初的現(xiàn)有資金數(shù)；決策：uk表示第k階段的投入資金數(shù)；狀態(tài)轉(zhuǎn)移方程：sk+1=sk-uk動態(tài)規(guī)劃基本方程:』ifk（sk）=max'k（sk，uk）+fk+1（sk+1）'f4（s4）=0最后得到解：產(chǎn)品A投資10萬，產(chǎn)品B投資10萬，產(chǎn)品C投資20萬.總的期望利潤為49.1萬。某公司準(zhǔn)備資金600萬元（以100萬元為單位），有四項(xiàng)可選擇投資的工程A、B、C、某公司準(zhǔn)備資金600萬元（以100萬元為單位），有四項(xiàng)可選擇投資的工程A、B、C、D?，F(xiàn)決定每項(xiàng)工程至少要投資100萬元。各項(xiàng)工程投資不同資金后可獲得的期望利潤如下：分配的投資金額利潤工程A工程B工程C工程D100150167164158200169189190185300185204226215試確定如何安排對各項(xiàng)工程的投資數(shù)，可使獲得的總期望利潤最大?階段：k=1,2,3,4,5分別考慮項(xiàng)目入、B、C、D和終止階段;狀態(tài)：sk表示第k階段初的資金數(shù)；決策：uk表示第k階段的投入資金數(shù)；狀態(tài)轉(zhuǎn)移方程：sk+1=sk-uk動態(tài)規(guī)劃基本方程：f(s)=max%(s,u)+f(s)}kkkkkk+1k+1f(s)=055最后得到解：項(xiàng)目入投資100萬，項(xiàng)目B投資100萬，項(xiàng)目C投資200萬，項(xiàng)目。投資200萬總的期望利潤為692萬星期(k)12345需求量(dk)單位：袋每袋生產(chǎn)成本(ck)10820625930123010現(xiàn)有一面粉加工廠，每星期上五天班。生產(chǎn)成本和需求量見表。面粉加工沒有生產(chǎn)準(zhǔn)備成本，每袋面粉的存儲費(fèi)為hk=0.5元/袋，按天交貨，分別比較下列兩種方案的最優(yōu)性，求成本最小的方案。星期一早上和星期五晚的存儲量為零，不允許缺貨，倉庫容量為S=40袋；其它條件不變，星期一初存量為8。有一個(gè)車隊(duì)總共有車輛100輛，分別送兩批貨物去A、B兩地，運(yùn)到A地去的利潤與車輛數(shù)目滿足關(guān)系100x，x為車輛數(shù)，車輛拋錨率為30%，運(yùn)到B地的利潤與車輛數(shù)y關(guān)系為80y，車輛拋錨率為20%，總共往返3輪。請?jiān)O(shè)計(jì)使總利潤最高的車輛分配方案?！窘狻縿討B(tài)規(guī)劃求解過程如下：階段k：日期，k=1,2,?,6狀態(tài)變量sk:第k天早上(發(fā)貨以前)決策變量xk:第k天的生產(chǎn)量狀態(tài)轉(zhuǎn)移方程：sk+1=sk+xk了dk；決策允許集合：巳(七)=，己>0,0階段指標(biāo)：vk(sk，xk)=ckxk+0.5sk終端條件：f(s)=0,s=0；遞推方程：f(x)=min(=min{xkeDk(sk)當(dāng)k=5時(shí)，因?yàn)閟6=0，有s=s+x-由于s5^15，f(s)=min55X法15-=150-k=4時(shí)，0<s<15，0<s+x-30:f(s)=min{144=君蓋備){2XeD(s)_Y-T145s=Sc4-9s+，I4k=3時(shí)，當(dāng)0W%W30時(shí)，0<s+x-25—s<x<55—sr333有D(s)=(x|max[0.25-s]<x<：f(s)=min{9x+0.5=3miii{9x+0.5=x3min3{-2.5x一一、3=宴豈+6603當(dāng)30Ws4W40時(shí)，x=0,30<s+xD(s)=Lf(1)(s)=min=x3留盅3){x3GD3(s3)顯然此決策不可行。當(dāng)k=2時(shí)，由0<s<30,0<s<25,4D2(y=kmf(s)=min{6x+0.5s22八,、，2="2min2{-2.5x-I=渤￥+717.5當(dāng)k=1時(shí)，由0<s2<20,0<s1+氣—1D(s)={xmf(s)=min11xeD(s)xe"i(s/=1min=797.5因?yàn)閟=0,x=10,s=10—10=0,x=45—s=s+x—20=25,x=55-s=s+x—25=30,x=30-s=s+x—30=0,x=15—(2)期初存儲量s「8,與前面計(jì)算相似，MinZ=772.5+2.5x-5s=737.5則總成本最小的方案是第二種。的冷庫存量s+x一d<4。}v(s'x)+fk+1(s+1)}僅(s,x)+f(s+x—d)}kkkk+1kkkd=0,x=15—s,{10x+0.5s)s55-59.5s,x*=15—s15,有30—s<x<45—s，2x+0.5s+f(s)}>.5x—9s+435}44+510s<30,x*=30—s43540<4s<304x*=04-25<30，彳得455—s}3s3+f4(s4)}is—11.5s+510}3411s+797.5}3取上界：x*=55—s33-25<40，有55—s<x<65—s}3333{9x+0.5s+f(s)}3344)x+0.5s—9s+435}-8.5七+210},x3取任意值0<s+x—20<25,x的決策允許集合為222Iax[0,20—s]<x<45—s}+660—8.5s}3s+830}取上界：x*=45—s220<20，則x1的決策允許集合為ax[0,10—七〕<氣<30—sj{8x+0.5s+717.5—5.5s}{2.5\—5s1+772.5}s=45,2s=30,3s=0,4s=—15.xj2.【解】動態(tài)規(guī)劃求解過程如下。階段k：共往數(shù)k=1,2,3,4,k=1表示第一趟初，k=4表示第三趟末(即第六年初)；狀態(tài)變量sk:第k趟初完好的車輛數(shù)(k=1,2,3,4)，也是第k-1趟末完好的車輛數(shù)，其中s4表示第三趟末的完好車輛數(shù)。決策變量xk:第k年初投入高負(fù)荷運(yùn)行的機(jī)器數(shù)；狀態(tài)轉(zhuǎn)移方程：sk+1=0.7xk+0.8(sk-xk)決策允許集合：Dk(sk)={xk|0<xk<sk}階段指標(biāo)：vk(sk，xk)=100xk+80(sk-xk)終端條件：f(s)=0遞推方程：f(s)=max{v(s,x)+f(s)}kk—/、kkkk+1k+1xkeDk(sk\=maxU00x+80(s—x)+fL°.7x+0.8(s—x)Dkkkk+1kkk0<x<sf(x)表示第上趟初分配x輛車到A地，到第3趟末的最大總運(yùn)價(jià)為kkk()f(s)=max{100x+80(s—x)+f(s)}33333440<x3<s3=max{20x+80s}=100sx*=s最優(yōu)眼<333330<%<%f(s)=max{100x+80(s—x)+f(s)}220<x2勺22233=max{10x+160s}=170sx*=s最優(yōu)0<x2<s22222f(s)=max{100x+80(s—x)+f(s)}110<x1<s111122=max{3x+216s}=219sx*=s最優(yōu)因?yàn)閟=100，最大總運(yùn)價(jià)f(s)=21900元某公司有三個(gè)工廠，它們都可以考慮改造擴(kuò)建。每個(gè)工廠都有若干種方案可供選擇，每種方案的投資及所能取得的收益如表所示?，F(xiàn)公司有資金5千萬元，問應(yīng)如何分配投資使公司的總收益最大？m..（方案）工廠i=1工廠i=2工廠i=3C（投資）益）R(收C（投資）益）R(收C（投資）益）R(收1000000215281332639--4--412--最優(yōu)方案有三個(gè)。即(m].,m2.,m3)=(3,2,2)或(2,3,2)或(2,4,1),總的收益為17千萬元中運(yùn)1012用貨物代號重量/t容積/m3價(jià)值/千元1223232434254536若該卡車的最大載重為15t,最大允許裝載容積為10m3,在許可的條件下，每輛裝載每（注：表中-表示無此方案）設(shè)有一輛載重卡車，現(xiàn)有4種貨物均可用此車運(yùn)輸。已知這4種貨物的重量、容積及價(jià)值關(guān)系如表(1)x1=1,x2=3,x3=1,x=0(2)x=2,x=1,x=2,x=01234(3)x=0,x=5,x=0,x=01234最優(yōu)解有三個(gè):最大價(jià)值為20千元11180802種貨物的件數(shù)不限。問應(yīng)如何搭配這四種貨物，才能使每車裝載貨物的價(jià)值最大。在設(shè)備負(fù)荷分配問題中，n=10，a=0.7，b=0.85，g=15，h=10，期初有設(shè)備1000臺。試確定10期的設(shè)備最優(yōu)負(fù)荷方案?！窘狻坑晒健阛<g~h<^ar得,=0gb-a)i=0(g-h)/g(b-a)=0.2222,ao+a1+a2=1+0.7+0.49=2.19V2.222Va0+a1+a2+a3=2.533,n—t—1=2，t=7表。則廣6年低負(fù)荷運(yùn)行，7~10年為高負(fù)荷運(yùn)行。各年年初投入設(shè)備數(shù)如下年份

設(shè)備臺數(shù)8年份

設(shè)備臺數(shù)8910264184.812912345671000850723614522444377某工廠購進(jìn)100臺機(jī)器，準(zhǔn)備生產(chǎn)p1，p2兩種產(chǎn)品。若生產(chǎn)產(chǎn)品p1，每臺機(jī)器每年可收入第一年將100臺機(jī)器全部生產(chǎn)p2兩種產(chǎn)品，第二年把余下的機(jī)器繼續(xù)生產(chǎn)產(chǎn)品p2,第三45萬元，損壞率為65%；若生產(chǎn)產(chǎn)品p2，每臺機(jī)器每年可收入35萬元，損壞率為35%；估計(jì)三年后將有新的機(jī)器出現(xiàn)，舊的機(jī)器將全部淘汰。試問每年應(yīng)如何安排生產(chǎn)。使在三年內(nèi)收入最多？設(shè)某中機(jī)器可以在高、低兩種不同的負(fù)荷下生產(chǎn)。若機(jī)器在高負(fù)荷下生產(chǎn)，則產(chǎn)品的年產(chǎn)量a和投入的機(jī)器數(shù)量x的關(guān)系為a=8x，機(jī)器的年折損率為P=0.3；若機(jī)器在低負(fù)荷下生年把余下的所有機(jī)器全部生產(chǎn)產(chǎn)品p1。三年的總收入為7676.25萬元。答案：四年中分配在高負(fù)荷下工作的機(jī)器臺數(shù)分別為0,900,630和441,四年最高產(chǎn)量為207187產(chǎn)，則產(chǎn)品年產(chǎn)量b和投入的機(jī)器數(shù)量x的關(guān)系為b=5x，機(jī)器的年折損率為a=0.1；設(shè)開始時(shí)有完好機(jī)器1000臺，要求制定一個(gè)四年計(jì)劃，每年年初分配完好機(jī)器在不同負(fù)荷下工作，使四年產(chǎn)品總產(chǎn)量達(dá)到最大。某工廠使用一種關(guān)鍵設(shè)備，每年年初設(shè)備科需對該設(shè)備的更新與否做出決策?，F(xiàn)已知在五答案：兩種方案，五年的總費(fèi)用均為53000元。年內(nèi)購置該種設(shè)備的費(fèi)用和各年內(nèi)設(shè)備維修費(fèi)用如表中所示。試制定五年內(nèi)的設(shè)備更新計(jì)一臺設(shè)備的價(jià)格為P,運(yùn)行壽命為n年，每年的維修費(fèi)用是設(shè)備役齡的函數(shù)，記為C（t）,新設(shè)備的役齡為t=0。舊設(shè)備出售的價(jià)格是設(shè)備役齡的函數(shù)，記為S（t）。在n一臺設(shè)備的價(jià)格為P,運(yùn)行壽命為n年，每年的維修費(fèi)用是設(shè)備役齡的函數(shù)，記為C（t）,新設(shè)備的役齡為t=0。舊設(shè)備出售的價(jià)格是設(shè)備役齡的函數(shù)，記為S（t）。在n年末，役齡為t的設(shè)備殘值為R（t）?，F(xiàn)有一臺役齡為T的設(shè)備，在使用過程中，使用者每年都面臨“繼續(xù)使用”或“更新”的策略。（列出動態(tài)規(guī)劃模型）答案：階段k：運(yùn)行年份；狀態(tài)變量xk:設(shè)備的役齡t；[R決策變量dk:dk=]K(Replace)更新(Keep)繼續(xù)使用狀態(tài)轉(zhuǎn)移方程:階段指標(biāo):_IP+C(0)-S(x)d=RVk=jC(x)kdk=K_JP+C(0)-S(t)d=R=[C(t)d：=K遞推方程:=mi」^+C(°)-S(xk)+fk+1(氣+1).(氣)—mm[ax*)+七+i(x：+1)[p+C(0)-S(t)+f(1)=min〈k+1[C(t)+fk+1(t+1)d=Rdk=Kd=RkJ*=K終端條件:fn(t)=-R(t)較分1214難析劃，使總的支，付費(fèi)用最少。第i年初12345購置費(fèi)用1111121213第i年12345維修費(fèi)用5681118

可提高設(shè)備正常運(yùn)轉(zhuǎn)的可靠性，但增加了費(fèi)用，而投資額僅為8000元。已知備用零件數(shù)與它的可靠性和費(fèi)用的關(guān)系如表所示。備件數(shù)增加的可靠性設(shè)備的費(fèi)用/千元E1E2E3E1E2E3Z=10.30.20.1132Z=20.40.50.2253Z=30.50.90.7364現(xiàn)要求在既不超出投資額的限制，又能盡量提高設(shè)備運(yùn)轉(zhuǎn)的可靠性的條件下，問各種零件的備件數(shù)量應(yīng)是多少為好？3B116C132D1108E112A5B,45D9F2342727C211E|1322B337D3911180803系統(tǒng)可靠性問題。一個(gè)工作系統(tǒng)由〃個(gè)部件串聯(lián)組成，見圖1。只要有一個(gè)部件失靈，整個(gè)系統(tǒng)就不能工作。為提高系統(tǒng)的可靠性，可以增加部件的備用件。例如，用5個(gè)部件1并聯(lián)起來作為一個(gè)部件與部件2串聯(lián)，如果其中一個(gè)部件失靈其它4個(gè)部件仍能正常工作。由于系統(tǒng)成本(或重量、體積)的限制，應(yīng)如何選擇各個(gè)部件的備件數(shù)，使整個(gè)系統(tǒng)的可靠性最大。圖1假設(shè)部件i(i=1,2,…,n)上裝有土個(gè)備用件，該部件正常工作的概率為Pj(?。設(shè)裝一個(gè)部件i的備用件的成本為七，要求備件的總費(fèi)用為C。11180803系統(tǒng)可靠性問題。一個(gè)工作系統(tǒng)由〃個(gè)部件串聯(lián)組成，見圖1。只要有一個(gè)部件失靈，整個(gè)系統(tǒng)就不能工作。為提高系統(tǒng)的可靠性，可以增加部件的備用件。例如，用5個(gè)部件1并聯(lián)起來作為一個(gè)部件與部件2串聯(lián)，如果其中一個(gè)部件失靈其它4個(gè)部件仍能正常工作。由于系統(tǒng)成本(或重量、體積)的限制，應(yīng)如何選擇各個(gè)部件的備件數(shù)，使整個(gè)系統(tǒng)的可靠性最大。圖1假設(shè)部件i(i=1,2,…,n)上裝有土個(gè)備用件，該部件正常工作的概率為Pj(?。設(shè)裝一個(gè)部件i的備用件的成本為七，要求備件的總費(fèi)用為C。那么該問題模型為：'1maxP=Hp(x)i=1(8.8)乙尤VCiii=1x>0并且為整數(shù)，i=1,2,...,n/同理，如果一個(gè)復(fù)雜的工作系統(tǒng)由n個(gè)部件并聯(lián)組成的，只有當(dāng)n個(gè)部件都失靈，整個(gè)系統(tǒng)就不能工作，見圖2。假設(shè)P,(勺為第i個(gè)部件失靈的概率，為提高系統(tǒng)的可靠性，可以增加部件的備用件。由于系統(tǒng)成本'(或重量、體積)的限制，應(yīng)如何選擇各個(gè)部件的備件數(shù)，使整個(gè)系統(tǒng)的可靠性最大。系統(tǒng)的可靠性為1-計(jì)P(x)，則該問題的數(shù)學(xué)模型歸結(jié)為

iii=1minP=Hp(尤)i=1(8.9)乙xVCiii=1x>0并且為整數(shù)，i=1,2,...,n/利用式(8.8)或(8.9)求解下列問題。工廠設(shè)計(jì)的一種電子設(shè)備，其中有一系統(tǒng)由三個(gè)電子元件串聯(lián)組成。已知這三個(gè)元件的價(jià)格和可靠性如表所示，要求在設(shè)計(jì)中所使用元件的費(fèi)用不超過200元，試問應(yīng)如何設(shè)計(jì)使設(shè)備的可靠性達(dá)到最大。元件單價(jià)可靠性1400.952350.83200.6設(shè)有一個(gè)由四個(gè)部門串聯(lián)組成的系統(tǒng)。為提高系統(tǒng)的可靠性，考慮在每個(gè)部件上并聯(lián)1個(gè)、2個(gè)或3個(gè)同類元件。每個(gè)部件i(i=1,2,3,4)配備j個(gè)并聯(lián)元件(j=1,2,3)后的可靠性R/和成本％(單位：百元)，由下表給出。假設(shè)該系統(tǒng)的總成本允許為15千元。試問如何確ji=1i=2i=3i=4RijcjRjcjRjcjRjcj10.7040.6020.9030.80320.7550.804——0.82530.857——————定各部件配備元件的數(shù)目，使該系統(tǒng)的可靠性最大?為保證某一設(shè)備的正常運(yùn)轉(zhuǎn)，需備有三種不同的零件E1，E2,E3。若增加備用零件的數(shù)量，【解】數(shù)學(xué)模型為maxZ=(1-0.05%)(1-0.2x2)(1-0.4x3)J40x+35x+20xV200\x,x,x>0并且為整數(shù)v123最優(yōu)解X=(1，2，4)；可靠性Z=0.888653，總費(fèi)用190。答案：可靠性為0.432中運(yùn)1012用E1備用1個(gè)，E21個(gè)，E33個(gè)，皿、費(fèi)用為8000元岫設(shè)備的可靠性為0.042用動態(tài)規(guī)劃求解以下網(wǎng)絡(luò)從A到F的最短路徑，路徑上的數(shù)字表示距離。答案：最短路徑為A^BQCQDpEpF，長度為26。較分1212難析11180804求解下列非線性規(guī)劃maxZ=xxx(x+x+x=C[x>0,j=1,2,3【解】(1)設(shè)s=x,s+x=s,s+x=s=C33322211則有x=s,0WxWs,0WxWs=C用逆推法，從后向前依次有k=3,f(s)=max(x)=s及最優(yōu)解x*=s333333x3=S3k=2,f(s)=max[xf(x)=max[x(s-x)]=maxh(s,x)22o.x2頭2330節(jié)頭2220氣鳥222由^x=s一2x=0,貝Ux=2sd2h八八，，1,~，土」瓦了一2<0,故%-2s2為極大值點(diǎn)。2「，、111所以f(s2)=2s2一4s2=4s2及最優(yōu)解x2*=s2k=1時(shí)，f(s)=max[xf(s)]=maxx—(s-x)2=maxh(s,x)，11眼<122心<1411眼<111x^-^sx^-^sx^-^s、6h1,〃.c、八e1由一1=一(s2一4sx+3x2)=0,得x*=—s8氣41111131故f(s)=-1s(s―1s)2=-1s311121131271已知知x1+x2+X3=C,因而按計(jì)算的順序推算，可得各階段的最優(yōu)決策和最優(yōu)解如下x*—1Cf(C)-c3x1=3C，f1(C)=27由s=s—x*=2C/3,x*=1C,f(s)=1C21123229由s=s—x*=C/3,x*=-C,f(s)=-C2233333最優(yōu)解為：X=(營C,RC,NC)T；Z=〒C3求解下列非線性規(guī)劃minZ=x+x2+x2Jx+x+x=CIx,x,x>0、123【解】設(shè)s=x,s+x=s,s+x=s=C則有3x=s，oWxWs,，oWxWs=C用逆推法，3從后向前依次有11k=3,f(s)=min(x)=s2及最優(yōu)解x*=s33x3=s33333k=2,f(s)=min[x2+f(x)=min[x2+(s-x)2]=minh(s,x)220<x2<s22330<x<s2220<x<s2228h,c八頑1由萬金=4s—2x=0,貝Ux=2sd2h1合22=4>0,故x2=2s2為極小值點(diǎn)。因而有f(s)=-s2,x*=-s2222222k=1時(shí)，f(s)=min[x+—(s—x)2=minh(s,x)11八//1211八//1110<x<sJ0<x<sx^-^sx^-^s,8h1八，一.1q/、1由一1=1—s+x=0知x*=s-1,f(s)=s-—電11，1112得到最優(yōu)解X=(C-1,1/2,1/2)t；z=C-j求解下列非線性規(guī)劃maxZ=2x+3x+x2Jx+x+x=10Ix,x,x>0'123【解】設(shè)s=x,s+x=s,s+x=s=1033322211則有x=s,0WxWs,0WxWs=10用逆推法,從后向前依次有k=3時(shí)，f(s)=max(x)=s2及最優(yōu)解x=s333333"Jk=2時(shí)，f(s)=max[3x+(s-x)2]=maxh(s,x)22心<222心<222S<s230<x2<s2-x=3-2s+2x=0時(shí)x=—^+s而邑=2>0,故x=-3+s不是一個(gè)極大值點(diǎn)。辦2222討論端點(diǎn)：當(dāng)x「0時(shí)f(s2)=s；，x「s2時(shí)f(s2)=3s2如果s2>3時(shí)，f(s2)=s2k=1時(shí)，f(s)=max[2x+(s-x)2]=maxh(s,x)11眼<111眼<111U=：x〔=：s]U-2：:x〔=：s]^x=2—2s+2x=0時(shí)x=—1+s會=2>0,故氣=-1+%不是一個(gè)極大值點(diǎn)同理有，x=0,f(s)=s2=100,x=s,f(s)=2s=20(舍去)111111111得到最優(yōu)解X=(°，0，10)；Z=100求解下列非線性規(guī)劃maxZ=xxxfx+4x+2x=10|xj>0,j=1,2,3【解】設(shè)s=x,2s+4x=s,s+x=s=1033322211則有x=s,0WxWs/4,0WxWs=10用逆推法，3從后向前依次有11k=1,f(s)=max(x)=s及最優(yōu)解x*=s333333%=，31k=2,f(s)=max[x(—s-2x)=maxh(s,x)220<x2<s/422220<x2<s《4222由頭二2S2"4x2=0，^x2=1s2Sh.c1辦；=—4<0,故x2=8s2為極大值點(diǎn)。則f(s2)=奈及最優(yōu)解x2*=s2/8k=1,f(s)=max[上x(s-x)2]=maxh(s,x)11V/32111V/1110<x<sUJ0<x<sU-2：:x〔二：、sU-2：:x〔二：、s=—(s2—4sx+3x2)=0,x*=-s,故f(s)=—!—s3電321111131故112161得到最優(yōu)解X=(10/3,5/6,5/3)t;z=125/27

I\^解下列非線性規(guī)劃naxZ=xxx2x+4x+x<10x.>0,j=1,2,3【解】按問題中變量的個(gè)數(shù)分為三個(gè)階段si，s2，s3，且s3W10,%，x2,x3為各階段的決策變量，各階段指標(biāo)函數(shù)相乘。設(shè)s=2x,s+4x=s,s+x=sW10，則有x=s/2,0WxWs/4,0WxWs=1011122233112233用順推法，從前向后依次有k=1,f(s)=max(x)=土及最優(yōu)化解x*=s/211x1=s1/21211k=2,f(s)=max[—x(s—4x)=maxh(s,x)220<x2<s2/422220<x2<s2/4222由一2=—s—4x=0,貝x*=—s8x222，八282d2h.-1…、1c2=—4<0,故x=—s為極大值點(diǎn)。則f(s)=由s3辦228222322k=3,f(s)=max[—x(s-x)2]=maxh(s,x)330<x3<s3323330<x3<s3333由一3=—(s2—4sx+3x2)=0,x*=—s電32333/333故f(s)=?K3,由于sW10，貝0s=10時(shí)取取大值，x=10/3,s=sx=20/3,x3321633332332=5/6,s1=s2—4x2=10/3,x1=5/3得到最優(yōu)解X=(5/3,5/6,110/3)r獲=125/27I\^解下列非線性規(guī)劃naxZ=x2+2x+2x2+xx+x+x=8x,x,x>01123【解】設(shè)s=x,s+x=s,s+x=s=811122233k=1,f(s)=max(x2+2x)=s2+2s及最優(yōu)化解x*=s1111111x1=s1k=2,f(s)=max[2x2+(s一x)2+2(s一x)]=maxh(s,x)20<x2<s2222220<x2<s22228h/仁cSh/八—2=6x—2s—2,2=6>0dx22dx2x*=0時(shí)，f(s)=s2+2s,x*=s時(shí)，f(s)=2s22222222222故f(s)=max{s2+2s,2s2)k=3,①當(dāng)x*=0時(shí)，f(s)=max[x+(s一x)2+2(s一x)]=maxh(s,x)2330<x3<s3333330<x3<s3333同樣得x3*=0時(shí)，f3(s3)=s32+2s3x3*=s3時(shí)，f3(s3)=s3所以，f3(s3)=s32+2s3=80②當(dāng)x*=s時(shí)，f(s)=max[x+2(s-x)2]22333330<x3<s3同樣得x3*=0時(shí)，f3(s3)=2s32=128x*=s時(shí)，f(s)=s=8所以，f3(s3)=2s32=128最優(yōu)解為X=(0,8,0);z=128I日動態(tài)規(guī)劃求解下列線性規(guī)劃問題。naxZ=2x+4x2x+x<6x<2x2<4x,x>0【解】設(shè)s2=x2,s2+2x1=s1W6則有0Wx=sW4,0WxWs/2用逆推法，從后向前依次有f(s2)=4s2及最優(yōu)解x2*=s2f(s)=max[2x+f(s)]=max[4s—6x]110<x1<s1/21220<x1<s1/211由s=s—2xW4,sW6,取s=6,f(s)=max[24―6x]21111110<x1<s1/21又1W%W2,取x1=1,f(s1)=18最優(yōu)解X=(1,4)t；z=18用動maxst.<態(tài)規(guī)劃方法求解下列問題z=x2xx3123x+x+x<6x>0,i=1,2,3ix=2,x=1,x=3;z=108中運(yùn)用1012用動maxst.<態(tài)規(guī)劃求解下面問題z=5x1+10x2+3x3+6x4x+4x+5x+10x<11X>0:且為整數(shù):i=1,2,3,4ix=11,x=0,x=0,x=0,z=55用動maxst.<態(tài)規(guī)劃求解下面問題z=3x1（2-x1）+2x2（2-x2）x+x<3X>0，且為整數(shù)，i=1，2ix=1,x=1,z=3用動minst.<態(tài)規(guī)劃求解下面問題z=x2+x2+x2+x4x+x+x+x>101234x>0，且為整數(shù)，i=1，2,3,4i最優(yōu)解有6個(gè)x=2,x=3,x=3,x=2x=3,x=2,x=3,x=2x=3,x=3,x=2,x=2x=2,x=2,x=3,x=3x=2,x=3,x=2,x=3x=3,x=2,x=2,x=3最優(yōu)值均為z=26min用動態(tài)規(guī)劃方法求解下列問題maxz=5氣-xi+9x2—2x2[x+x<5stT^>0,i=1,2i氣=5/2,x2=9/4;z=131/811180805用動態(tài)規(guī)劃方法求解下列問題minz=3x2+4x2+x2用動態(tài)規(guī)劃方法求解下列問題maxz=6x廣7xi+5x2'xi+2x2J10st.R-3x2<9x>0,i=1,2i寫出問題的動態(tài)規(guī)劃的基本方程maxz=堂g(x)iii=1st.寸乙axi=10<x<c,i=1,2,—,nii用動態(tài)規(guī)劃方法求解下列問題maxz=8x2+4x2+x32x+x+10x=bst.jx.>0,i=1,2,3b為正數(shù)用動態(tài)規(guī)劃方法求解下列問題maxz=ax2+xx+xx12324x+x+x+x=10st."'>0,i=1,2,3,4a為實(shí)數(shù)用動態(tài)規(guī)劃方法求解下列問題。minz=x2+x2+x2+x2(x+x+x+x>10

s'[x>0且為整數(shù)(j=1,2,3,4)用動態(tài)規(guī)劃方法求解下列問題。maxf=xxxx1234[2x+3x+x+2x=11

s'[xj為非負(fù)整數(shù)(j=1,2,3,4)某商店在未來的4個(gè)月里，準(zhǔn)備利用商店里一個(gè)倉庫來專門經(jīng)銷某種商品，該倉庫最多能裝這種商品1000單位。假定商店每月只能賣出它倉庫現(xiàn)有的貨。當(dāng)商店決定在某個(gè)月購貨時(shí)，只有在該月的下個(gè)月才能得到該貨。據(jù)估計(jì)未來4個(gè)月商店買賣價(jià)格如表所示。假定商店在1月開始經(jīng)銷時(shí)，倉庫貯存商品有500單位。試問：如何指定這4個(gè)月的訂購與銷售計(jì)劃，使獲得利潤最大？（不考慮倉庫的存貯費(fèi)用）月份（k）買價(jià)（ck）賣價(jià)（pk）110122993111341517氣=1.82,x2=1.574,x3=3.147;z=29.751氣=9.6,x2=0.2;z=702.92基本方程八)=max{g(x)+f(s)}kkkkk+1xkeDk筆)k=n,n一1,???,1允許決策集合(s)=0I)=kk+1D(s)=jxI0<x可達(dá)狀態(tài)集合s={sI0<s<b}1s=b狀態(tài)轉(zhuǎn)移函數(shù)s=s一axb>4000,x=0,x=0,x=b/10;z=b3/1030<b<4000,氣=0,x2=b,x3=0;z=4b2a>1/4,x1=10,x2=0,x3=0,x4=0;z=100a-1/4<a<1/4,最優(yōu)決策有兩個(gè)：x=0,x=5,x=5,x=0;或x=0,x=5,x=0,x=5;z=2512341234maxa<-1/4,最優(yōu)決策有兩個(gè)：1020a20a八x=,x=,x=,x=0;140a+124a+134a+14十1020a八20a或x=,x=,x=0,x=;140a+124a+1344a+1100amax4a+1答案：最優(yōu)解有共6個(gè)：（2，3，3，2），（3，2，3，2），（3，3，2，2），（2,2，3，3），（2，3，2，3），（3，2，2，3）z.=26答案：最優(yōu)解有3個(gè)：（1，1，4，1），（2，1，2，1），（1，1，2，2），zmax=4月期前存貨（sk）售出量（xk）購進(jìn)量（yk）15005000200100031000100010004100010000各月份訂購與銷售的最優(yōu)決策為:利潤最大為16000較分1212難析總的最低費(fèi)用為36321元中運(yùn)1012用考慮一個(gè)有m個(gè)產(chǎn)地和n個(gè)銷地的運(yùn)輸問題。設(shè)a,為產(chǎn)地i（i=1，…，m）可發(fā)運(yùn)的物資數(shù)，bj為銷地j（j=1，…，n）所需要的物資數(shù)。又從產(chǎn)地i往銷地j發(fā)運(yùn)x,,單位物資所需的費(fèi)用為h,（x,），試將此問題建立動態(tài)規(guī)劃的模型。x.表示從產(chǎn)地i（i=1，—，m）分配給銷地k，k+1，...，n的物資的總數(shù)，則采用逆推算法時(shí)，動J態(tài)規(guī)劃的基本方程可寫為}k,xm一xmk較分1214難析kk、.竺-fk(x1,…，xm)=minZ〔hikxik1=1k0<xik<xi式中mzi=1H=b、(k=1，?..，n)fn+1=0并且有x2232A產(chǎn)品當(dāng)月的生產(chǎn)數(shù)量。倉庫存貨成本費(fèi)用是每月每單位1元。估計(jì)3個(gè)月的需求量分別為d1=100，d2=110，2232A產(chǎn)品當(dāng)月的生產(chǎn)數(shù)量。倉庫存貨成本費(fèi)用是每月每單位1元。估計(jì)3個(gè)月的需求量分別為d1=100，d2=110，d3=120。現(xiàn)設(shè)開始時(shí)第一個(gè)月月初存貨s0=0，第三個(gè)月月末存貨s3=0。試問：每月的生產(chǎn)數(shù)量應(yīng)是多少才能使總的生產(chǎn)和存貨費(fèi)用為最小。某公司打算在三個(gè)不同的地區(qū)設(shè)置4個(gè)銷售點(diǎn)，根據(jù)市場預(yù)測部門估計(jì)，在不同的地區(qū)設(shè)置不同數(shù)量的銷售店，每月可得到的利潤如表所示.試問在各個(gè)地區(qū)應(yīng)如何設(shè)置銷售點(diǎn)，才能使每月獲得的總利潤最大?其值是多少？在第一個(gè)地區(qū)設(shè)置2個(gè)銷售點(diǎn)，在第二個(gè)地區(qū)設(shè)置1個(gè)銷售點(diǎn)，在第三個(gè)地區(qū)設(shè)置1個(gè)銷售點(diǎn).每月獲得的總利潤為47銷售店、利潤、地區(qū)、、\01234101625303220121721223010141617某工廠生產(chǎn)三種產(chǎn)品，各種產(chǎn)品重量與利潤關(guān)系如表?，F(xiàn)將此三種產(chǎn)品運(yùn)往市場出售，運(yùn)輸能力總重量不超過10t，問如何安排運(yùn)輸使總的利潤最大？最優(yōu)解有兩個(gè)：x=3，x=0,x=1x=2，x=2，x=0總利潤為480元種類重量/(t?件-1)利潤/（元?件-1）123234100140180某紡織品公司計(jì)劃在今后四個(gè)月內(nèi)經(jīng)營一種高級成衣。根據(jù)預(yù)測，該種商品在5至8月份的每套進(jìn)價(jià)和售價(jià)如表所示。已知庫存能力為600套，5月初有庫存200套，并假定銷售是在月初進(jìn)行，至8月末全部銷售完，使對這四個(gè)月的銷購做出安排，使總的利潤最大？單位：元/套答案：5月份銷售200套，進(jìn)貨600套。6月份銷售600套，進(jìn)貨600套。7月份銷售0套，進(jìn)貨0套。8月份銷售600套，進(jìn)貨0套。總的利潤為13800元月價(jià)5678進(jìn)價(jià)40384042售價(jià)4542394411180806設(shè)有n種物品，每一種物品數(shù)量無限。第i種物品每件重量為Wj公斤，每件價(jià)值七元。現(xiàn)有一只可裝載重量為W公斤的背包，求各種物品應(yīng)各取多少件放入背包，使背包中物品的價(jià)值最高。(用動態(tài)規(guī)劃方法求解)答案：這個(gè)問題可以用整數(shù)規(guī)劃模型來描述。設(shè)第i種物品取Xj件(i=1,2,…,n，xi為非負(fù)整數(shù))，背包中物品的價(jià)值為z，貝0cx+cx+…+cx1122nnwx+wx+…+wxWW1122nnx1,X2,…，xn為非負(fù)整數(shù)maxz=s.t.階段k：第k次裝載第k種物品(k=1,2,…，n)狀態(tài)變量xk:第k次裝載時(shí)背包還可以裝載的重量；決策變量dk:第k次裝載第k種物品的件數(shù)；決策允許集合：D(x)={d|0<d<x/w，d為整數(shù)};kkkkkkk狀態(tài)轉(zhuǎn)移方程：xk+1=xk-wkdk階段指標(biāo)：vk=ckdk遞推方程：f(x)=max{cd+f(x)}=max{cd+f(x-wd)}kkkkk+1k+1kkk+1kkk終端條件：f4(x4)=0對于一個(gè)具體問題:cj65，c2=80，c3=30W1=2,w2=3,W3=1以及W=5用動態(tài)規(guī)劃求解對于k=3f(x)=max{cd+f(x)}330<d3<%/嶼3344max{30d}0<d3<X3/嶼3xD(x)x30d+f(x)f(x)d*0000+0=0001010+0=03011030+0=30*2020+0=06021130+0=302060+0=60*3030+0=09031230+0=302160+0=603090+0=90*4040+0=012041330+0=302260+0=603190+0=9040120+0=120*5050+0=015051430+0=302360+0=603290+0=9041120+0=12050150+0=150*列出f3(x3)的數(shù)值表f'M)對于k=2f(x)=max{cd+f(x)}22o<d2<x2/w22233max{80d+f(x-3d)}0<d2<"32322列出f2(x2)的數(shù)值表x―2—DzM)x380d2+f3(x3)fzM)d2*0000+f(0)=0+0=0*3001010+f3(1)=0+30=30*3002020+f2(2)=0+60=60*600301300+f3(3)=0+90=90*80+f(0)=80+0=803900401410+f3(4)=0+120=120*80+f3(1)=80+30=1101200501520+f3(5)=0+150=150*80+f(2)=80+60=1401500fzM)對于k=1f(x)=max{cd+f(x)}110<d1<x"1122max{65d+f(x-2d)}0<d1<x1/21211列出f1(x1)的數(shù)值表x—1—")x265d1+f2(x2)E)d1*0000+f2(0)=0+0=0*001010+f2(1)=0+30=30*3002020+f2(2)=0+60=606511065+f2(0)=65+0=65*3030+f2(3)=0+90=909511165+f2(1)=65+30=95*4040+f2(4)=0+120=12013021265+f2(2)=65+60=12520130+f2(0)=130+0=130*5050+f2(5)=0+150f2(3)=65+90=15521130+f2(1)=130+30=160*E)第10頁共17頁由題意知，x=5，由表f(x)、f(x)、f(x)，經(jīng)回朔可得:1112233d*=2，x=x-2d=1，d*=0，x=x-3d=1，d*=1，x=x-d=0121123223433較分1214難析用動態(tài)規(guī)劃求解以下背包問題maxz12x22x15x2x4x3x10s.tx「x2,x30且都為整數(shù)階段指標(biāo)：vk=ckdk遞推方程：f(x)=max{cd+f(x)}kkkkk+1k+1=max{cd+f(x-wd)}終端條件：f4(x4)=0用動態(tài)規(guī)劃求解對于k=3,列出f3(x3)的數(shù)值表f3(x3)x4=x3-3d2x3D3(x3)x：15d3+f：(x：)f3(x3)d3*0000+0=0'002020+0=0004040+0=01511115+0=15*060+0=061215+0=153022030+0=30*080+0=081515+0=153022230+0=30*0100+0=0101715+0=154532430+0=303145+0=45*對于k=2列出f2(x2)的數(shù)值表f2(x2)x3=x2-4d2xD(x)x22d+f(x)f(x)d*22232332220000+0=0002020+0=000040+15=1542211022+0=22*060+30=30*63001222+0=22080+30=3081422+15=374422044+0=44*0100+45=45101622+30=52*5212244+0=44對于k=1列出f1(x1)的數(shù)值表七(x1)x2=x1-2d1xD(x)x12d+f(x)f(x)d*11121221110100+53=53812+44=56624+30=54436+22=58248+0=485060+0=60*由題意知，x=10,由表f(x)、f(x)、f(x)，經(jīng)回朔可得：1112233d*=5,x=x-2d=0,d*=0,x=x-4d=0,d*=0,x=x-2d=0121123223433即應(yīng)取第一種物品5件，第二種物品0件，第三種物品0件，最高價(jià)值為60元，背包沒有余量。較難分析1214背包問題，這是運(yùn)籌學(xué)問題中白但背包重量有限制，總重量可不勺一個(gè)著名問題。某人外出旅游匚能超過13kg，物品重量及其價(jià)，需將五個(gè)物品放進(jìn)背包，'值的關(guān)系如下圖所示：答案：最優(yōu)解為裝A,B,E各一件，重6.5kg,最大價(jià)值為13.5元。中運(yùn)用1012物品重量（kg）價(jià)值（元）A79B54C43D32E10.5用動態(tài)規(guī)劃方法求解以下背包問題maxz-17x+72x+35xf10x+41x+20x<50X],x2,x3>0且都為整數(shù)s.t.答案：階段k：第k次裝載第k種物品(k=1,2,…,n)狀態(tài)變量x:第k次裝載時(shí)背包還可以裝載的重量；k決策變量d:第k次裝載第k種物品的件數(shù)；k決策允許集合：D(x)={d|0<d<x/w，d為整數(shù)};kkkkkkk狀態(tài)轉(zhuǎn)移方程：xk+i=xk-wkdk階段指標(biāo)：vk=ckdk遞推方程：f(x)=max{cd+f(x)}kkkkk+1k+1=max{ckdk+fk+i斜預(yù)&)}終端條件：f4(x4)=0用動態(tài)規(guī)劃求解對于k=3，列出f3(x3)的數(shù)值表較分1214難析f3(x3)x4=x3-20d2xD3(x3)x35d3+f4(x4)fgd3*0000+0=0009020+0=000100100+0=0000200+0=0201035+0=35*3510300+0=03011035+0=35*3510400+0=04012035+0=357022070+0=70*0500+0=05013035+0=3570221070+0=70*對于k=2列出f2(x2)的數(shù)值表f22x32D2Ex72d2+f3(x3)f±2d2*0000+0=0*00100100+0=0*00200200+35=35*350300300+35=35*350400400+70=70*7000500+70=70501972+0=72*721對于k=1列出f1(x1)的數(shù)值表f1(x1)x2=x1-10d1x1D1Ex2171+f2(x2)匚Ed1*0500+72=7214017+70=87*23034+35=695032051+35=8687141068+0=685085+0=85由題意知，x=50，由表f(x)、f(x)、f(x)，經(jīng)回朔可得：1112233d*=1，x=x-10d=40，d*=0，x=x-41d=40，d*=2，x=x-20d=0121123223433即應(yīng)取第一種物品1件,第三種物品0件,第三種物品2件,最高價(jià)值為87元,背包沒有余量。11180807(a)任務(wù)的指派分4個(gè)階段完成,用狀態(tài)變量sk表第k階段初未指派的"的集合,決策變量為較分1214難析ukj工作11180807(a)任務(wù)的指派分4個(gè)階段完成,用狀態(tài)變量sk表第k階段初未指派的"的集合,決策變量為較分1214難析ukj工作人1234115182124219232218326181619419212317已知某指派問題的有關(guān)數(shù)據(jù)(每人完成各項(xiàng)工作的時(shí)間)如表所示，試對此問題用動態(tài)規(guī)劃方法求解.要求：列出動態(tài)規(guī)劃的基本方程；用逆推解法求解.1k階段被指派完成第?項(xiàng)工作0,否則狀態(tài)轉(zhuǎn)移s.+1={D久(sk)偵當(dāng)Ukj=1}本問題的逆推關(guān)系式為f4min

u4JeD4IS4、Ja4jminuwD[(kjkISka..+

ij-Sk+1>(b)有兩組最優(yōu)解u-u-u-u-1或u-u-u-u-11124334212213344對第一人面試時(shí)對較滿意者不錄用，對第二人面試時(shí)，對較滿意者應(yīng)錄用，使錄用人員的總期望值為2.336分中運(yùn)1012用某公司去一所大學(xué)招聘一名管理專業(yè)應(yīng)屆畢業(yè)生.從眾多應(yīng)聘學(xué)生中，初選3名決定依次單對第一人面試時(shí)對較滿意者不錄用，對第二人面試時(shí)，對較滿意者應(yīng)錄用，使錄用人員的總期望值為2.336分中運(yùn)1012用設(shè)某臺機(jī)床每天可用工時(shí)為5h，生產(chǎn)每單位產(chǎn)品A或B都需要1h，其成本分別為4元和3元。已知各種單位產(chǎn)品的售價(jià)與該產(chǎn)品的產(chǎn)量具有如下線形關(guān)系：最優(yōu)決策為：產(chǎn)品A生產(chǎn)3件，產(chǎn)品B生產(chǎn)2件，最大利潤為27產(chǎn)品A產(chǎn)品B其中x1，生產(chǎn)多少，才能使總的利潤最大?X2分別為產(chǎn)品^的產(chǎn)量。P1=12—X1P2=13-2X2問如果要求機(jī)床每天必須工作5匕產(chǎn)品A和B各應(yīng)月份123456貨物量/百件404330各月份生產(chǎn)貨物數(shù)量的最優(yōu)決策為:月份123456貨物量/百件125321某工廠根據(jù)國家的需要其交貨任務(wù)如表所示。表中數(shù)字為月底的交貨量。該廠的生產(chǎn)能力為每月400件，該廠倉庫的存貨能力為300件，已知每100件貨物的生產(chǎn)費(fèi)為10000元，在進(jìn)行生產(chǎn)的月份，工廠要支出經(jīng)常費(fèi)4000元，倉庫保管費(fèi)為每百件貨物每月1000元。假定開始時(shí)及6月底交貨后無存貨。試問應(yīng)在每個(gè)月各生產(chǎn)多少件物品，才能既滿足交貨任務(wù)又使總費(fèi)用最?。吭O(shè)某商店一年分上、下半年兩次進(jìn)貨，上、下半年的需求情況是相同的，需求量y服從均勻分布，其概率密度函數(shù)為f(y)=<20<y<30，其進(jìn)貨價(jià)格和銷售價(jià)格在上、其他1=5,p2=4。年底若有剩貨時(shí)，以單價(jià)p3=1處理出售，可以清理完剩貨。設(shè)年初存貨為0，若不考慮存貯費(fèi)及其他開支，問兩次進(jìn)貨各應(yīng)為多少，才能獲得最大的期望利潤？下半年中是不同的，分別為q1=3,q2=2,p\倉庫預(yù)期事故、次數(shù)巡邏隊(duì)伍1234218381434316361231412301125某警衛(wèi)部門有12支巡邏隊(duì)負(fù)責(zé)4個(gè)倉庫的巡邏。按規(guī)定對每個(gè)倉庫分別派2~4支巡邏隊(duì)伍。由于所派隊(duì)伍數(shù)量上的差別，各倉庫一年內(nèi)預(yù)期發(fā)生事故的次數(shù)如表。試應(yīng)用動態(tài)規(guī)劃的方法確定派往各倉庫的巡邏隊(duì)數(shù)，使預(yù)期事故的總次數(shù)為最少。某人在每年年底要決策明年的投資與積累的資金分配。設(shè)開始時(shí)，他可利用的資金數(shù)為C，年利率為a(a>1)。在i年里若投資y，.所得到的效益用g,(yi)=by,(b為常數(shù))來表示。試用逆推解法來建立該問題在n年里獲得最大效益的動態(tài)規(guī)劃模型。某人在每年年底要決策明年的投資與積累的資金分配。設(shè)開始時(shí)，他可利用的資金數(shù)為C，年利率為a(a>1)。在i年里若投資y,所得到的效益用g,(y,)=by,(b為常數(shù))來表示。試用順推解法來建立該問題在n年里獲得最大效益的動態(tài)規(guī)劃模型.某制造廠根據(jù)合同，要在1至4月份的每個(gè)月底供應(yīng)零件分別為40，50，60，80件，該廠1月初并無存貨，至4月末也不準(zhǔn)備留存。已知每批的生產(chǎn)費(fèi)用為100元；若當(dāng)月生產(chǎn)的零件交運(yùn)不出去，需要倉庫存儲，存儲費(fèi)用為2元/件月，該廠每月的最大生產(chǎn)能力為100件。問應(yīng)如何安排生產(chǎn)，才能使費(fèi)用總和為最??？新產(chǎn)口'品不成功概率ABC00.400.600.8010.200.400.5020.150.200.30某工廠在一年內(nèi)進(jìn)行了A，B，C三種新產(chǎn)品試制，估計(jì)年內(nèi)這三種新產(chǎn)品研制不成功的概率分別為0.40，0.60，0.80。廠領(lǐng)導(dǎo)為了促進(jìn)三種新產(chǎn)品的研制，決定撥2萬元追加研制費(fèi)，假定這些追加研制費(fèi)(以萬元為單位)分配給不同新產(chǎn)品研制時(shí)，估計(jì)不成功的概率分別為表中所示。試問應(yīng)如何分配這筆追加研制費(fèi)，使這三種新產(chǎn)品都沒有研制成功的概率最小。有一名學(xué)生要從四個(gè)系中挑選十門選修課程。他必須從每個(gè)系中至少選一門課，他的目的是把十門課分到四個(gè)系中，使得他在四個(gè)領(lǐng)域中的“知識”最多，由于他對課程內(nèi)容的理解力和課程的內(nèi)容的重復(fù)，他認(rèn)為如果在一個(gè)系所選的課程超過一定數(shù)目時(shí)，他的知識就不能顯著的增加。為此，它采用100分作為衡量他的學(xué)習(xí)能力，并以此作為在每個(gè)系選修課程的依據(jù)。經(jīng)過詳細(xì)的調(diào)查分析得到表中各數(shù)據(jù)。試確定這個(gè)學(xué)生選修課程的最優(yōu)方案。(課程，分?jǐn)?shù)，系別)課程系別12345678910I25506080100100100100100100II207090100100100100100100100m406080100100100100100100100W1020904050607080901002最優(yōu)決策為：上半年進(jìn)貨263個(gè)單位，若上半年銷售后剩下s2個(gè)單位的貨，則下半年再進(jìn)21貨263-s2個(gè)單位的貨,這時(shí)獲得期望利潤為933****最優(yōu)策略為u1=2，u2=4，u3=2，u4=4，總預(yù)期事故為87設(shè)狀態(tài)變量sj表示第i年初擁有的資金數(shù)，則有逆推關(guān)系式[fn(n)=max

yn=snmax0<y<s,i=n-1，???，2，1"=設(shè)狀態(tài)變量si表示第i+1年初擁有的資金數(shù)，則有順推關(guān)系式'f(s)=max110<y<ac-s1f'iXmax<0<yWc-s.igi(yi)+fi-1iii=2,…，n答案：兩種最優(yōu)方案，最小總費(fèi)用為400元。新產(chǎn)品ABC補(bǔ)撥研制費(fèi)101答案：最小概率為0.06答案：總分?jǐn)?shù)為250分。101012101212141210101212考慮一家公司在今后五個(gè)時(shí)期內(nèi)確定勞動力多少的問題。如果五個(gè)時(shí)期中所需勞動力的最低數(shù)bi是5，7，8，4和6(單位:期所擁有的實(shí)際勞動力，若y>b.力的費(fèi)用為4+2(y.-y,「當(dāng)0其它’“答案：百人)(i=1，2，3，4，5)。設(shè)y,(>bi)是第i個(gè)時(shí)將導(dǎo)致額外的費(fèi)用c1=3(”b,)；若y,_1<y,則勞動(單位：千元)假定y0=5(百人)’使確定勞動力費(fèi)用支出最小的方案。(y,y,y,y,y)=(5,8,8,6,6)(單位：百人)，總費(fèi)用1.9萬元12345答案:階段k：月份，k=1,2,?,7,8；月份(k)1234567生產(chǎn)成本(ck)11181317201015需求量(rk)0853274一個(gè)工廠生產(chǎn)某種產(chǎn)品，1?7月份生產(chǎn)成本和產(chǎn)品需求量的變化情況如下表:為了調(diào)節(jié)生產(chǎn)和需求，工廠設(shè)有一個(gè)產(chǎn)品倉庫，庫容量H=9。已知期初庫存量為2,要求期末(七月低)庫存量為0。每個(gè)月生產(chǎn)的產(chǎn)品在月末入庫，月初根據(jù)當(dāng)月需求發(fā)貨。求七個(gè)月的生產(chǎn)量，能滿足各月的需求，并使生產(chǎn)成本最低。(列出動態(tài)規(guī)劃模型)設(shè)城市的道路結(jié)構(gòu)如右圖所示。兩個(gè)路口之間標(biāo)的數(shù)字表示通過這一段道路所需的費(fèi)用(單位：元)，該城市有一項(xiàng)奇怪的交通規(guī)則：車輛經(jīng)過每個(gè)路口時(shí)，向左或向右轉(zhuǎn)彎一次，要收取“轉(zhuǎn)彎費(fèi)”3元。現(xiàn)有一輛汽車從A點(diǎn)出發(fā)到P點(diǎn)的行駛路線。求包括轉(zhuǎn)彎費(fèi)用在內(nèi)，費(fèi)用最小，設(shè)有n個(gè)城市，其中每兩個(gè)城市之間都有道路相連，城市i和城市j之間的距離為Cij。從某城市出發(fā)周游所有城市，經(jīng)過每個(gè)城市一次且僅一次，最后回到出發(fā)地，求總行程最短的周游路線。對于一般的情況可以假設(shè)兩城市之間往返距離不相等。在此例中，為了簡化問題，設(shè)往返距離相等，即Cij.=Cji。(列出動態(tài)規(guī)劃模型即可)狀態(tài)變量xk:第k個(gè)月初(發(fā)貨以前)的庫存量;決策變量dk:第k個(gè)月的生產(chǎn)量；狀態(tài)轉(zhuǎn)移方程：xk+1=xk-rk+dk；決策允許集合：Dk(xk)={dk|dk>0,%={dk|dk>0，階段指標(biāo)：vk(xk,dk)=ckdk；終端條件：f8(x8)=0,x8=0；遞推方程：fk(xk)=min{vk(xk,dk)+fk+1""dkeDk(kxk)k""1=min{cd+f(x-r+d)}kkk+1kkkdkeDk(xk)k+1<xk+1<H}、+1<xk-rk+dk<H}；(Xk,1)}1214答案：為了滿足動態(tài)規(guī)劃的這一要求，必須重新構(gòu)造狀態(tài)變量?，F(xiàn)將這個(gè)問題的動態(tài)規(guī)劃模型構(gòu)造如下：階段k：設(shè)起點(diǎn)A為第一階段，到達(dá)B或C為第二階段，如此等等。到達(dá)終點(diǎn)P為第七階段。狀態(tài)變量：(％r),(k=1,2,…，6)，其中％為第k階段所在位置，r為從x出發(fā)行進(jìn)kkkkku(up)上行r=<k的方向：d(down)下行終點(diǎn)P的狀態(tài)變量為(P,中)，中表示行進(jìn)方向?yàn)榭占Ｓ蓤D可見，點(diǎn)G，J，K，M，N，O,P只有一個(gè)狀態(tài)，其余的點(diǎn)都有兩個(gè)狀態(tài)。由于狀態(tài)變量包括所在位置和行進(jìn)方向兩個(gè)因素，決策變量也就已經(jīng)包含在狀態(tài)變量之中了。最優(yōu)指標(biāo)：fk(xk,孔)表示從xk出發(fā)，按rk方向前進(jìn)括轉(zhuǎn)彎費(fèi)用)。階段指標(biāo)：uk(xk)—從xk出發(fā)上行一步的路程費(fèi)用(不包括轉(zhuǎn)彎費(fèi)用);dk(xk)—從xk出發(fā)下行一步的路程費(fèi)用(不包括轉(zhuǎn)彎費(fèi)用)。遞推方程：iH.步，最終到達(dá)P的最小費(fèi)用(包f(x,u)=min1214.|uk(xk)+fk+1(xk+1,u)u(x)+f(x,d)+3kkk+1k+1f(x,u)k+1k+1f(x,d)+3k+1k+1.|dk(xk)+fk](xk],u)+3

d(x)+f(x,d)kkk+1k+1-f(x,u)+3k+1k+1fk+1楫+1<)=u(x)+minf(x,d)=min=d(x)+min終端條件：f7(P,①)=0答案：由于此問題經(jīng)過的路線是一條經(jīng)過所有城市的閉合回路，因此從哪一點(diǎn)出發(fā)是無所謂的，因此不妨設(shè)從城市1出發(fā)。問題的動態(tài)規(guī)劃模型構(gòu)造如下:階段k：已經(jīng)歷過的城市個(gè)數(shù)，包括當(dāng)前所在的城市。k=1,2,…，n,n+1，k=1表示出發(fā)時(shí)位于起點(diǎn)，k=n+1表示結(jié)束時(shí)回到終點(diǎn)。狀態(tài)變量：xk=(i,Sk)，其中i表示當(dāng)前所在的城市，Sk表示尚未訪問過的城市的集合。很明顯S]={2,3,…,n}，…，S=S+1=中其中中表示空集。并且有xn=(i,①)i=2,3,…,n，xn+1=(1,中)決策變量：dk=(i,j)，其中i為當(dāng)前所在的城市，j為下一站將要到達(dá)的城市。狀態(tài)轉(zhuǎn)移方程：若當(dāng)前的狀態(tài)為xk=(i,Sk)采取的決策為dk=(i,j)則下一步到達(dá)的狀態(tài)為xk+1=T(xk,dk)=(j,『{j})階段指標(biāo)：vk(xk,dk)=Cij最優(yōu)指標(biāo)函數(shù)：fk(xk)=fk(i,Sk)表示從城市i出發(fā)，經(jīng)過Sk中每個(gè)城市一次且僅一次，最后返回城市1的最短距離。終端條件：fn+1(xn+1)=fn+1(1,中)=01214有三種新產(chǎn)品A,B,C有待研制。每種新產(chǎn)品在一年內(nèi)研制不成功的概率與投入該產(chǎn)品的研制費(fèi)用有關(guān)，有關(guān)數(shù)據(jù)如下表。設(shè)總的研制經(jīng)費(fèi)為3萬元。試求三個(gè)項(xiàng)目研制費(fèi)用的分配方案，使這三個(gè)產(chǎn)品研制全不成功的概率為最小。答案：階段k：每一種產(chǎn)品分配以前為一個(gè)階段；k=1為產(chǎn)品A分配以前，k=2為產(chǎn)品B分配以前，k=3為產(chǎn)品C分配以前，k=4為產(chǎn)品C分配以后。狀態(tài)變量\:第k次分配以前乘。余的資金(萬元)；決策變量dk：用于研制第k種產(chǎn)品的資金(萬元)；決策允許集合％(\)：0WdkWxk狀態(tài)轉(zhuǎn)移方程：xk+1=xk-dk階段指標(biāo)vk(xk,dk):第k個(gè)產(chǎn)品的研制費(fèi)用投入dk萬元，該產(chǎn)品研制不成功的概率；最優(yōu)指標(biāo)函數(shù)fk(xk):第k次分配前還剩余資金xk時(shí)，產(chǎn)品k，k+1，…，n研制都不成功的""概率。"遞推方程：f(x)=min{v(x,d)xf(x)}kkkkkk+1k+1終端條件：f4(x4)=1k=4，f4(x4)=1k=3，研制產(chǎn)品C，x,=x3-d3x3D3GDx,v3(x3,婦v3(x3，d3)xf,(x)3)d3*00011X1=1100111X1=10.801100.800.80X1=0.80*0211X1=1110.800.80X1=0.800.502200.500.50X1=0.50*0311X1=120.800.80X1=0.800.30310.500.50X1=0.50300.300.30X1=0.30*k=2，研制產(chǎn)品B，x3=x2-d2x2D2(x2)x3v2(x2,d2)v2(x2,d2)+f3(x3)f2(x2)d2*00011X1=1100111X0.8=0.80.61100.60.6X1=0.6*0211X0.5=0.5110.60.6X0.8=0.480.42200.40.4X1=0.4*0311X0.3=0.320.60.6X0.5=0.30.2310.40.4X0.8=0.32300.20.2X1=0.2*k=1，研制產(chǎn)品A，x^x^d]xD(x)xv(x,d)v(x,d)+f(x)f(x)d*111211-111-1221110311X0.2=0.220.40.4X0.4=0.1610.20.2X0.6=0.12*.300.150.15X1=0.15x=3，d*=2，x=x-d*=3-2=1，d*=1，x=x-d*=1-1=0，d*=0，x=x-d=01121123223433即產(chǎn)品A的研制投入2萬元，產(chǎn)品B的研制投入1萬元，產(chǎn)品C不研制，使三個(gè)產(chǎn)品全不成功的概率最小，為0.12。較難分析1214產(chǎn)品ABC1萬元2萬元3萬元0.400.600.800.200.400.500.150.200.30求以下貨郎擔(dān)問題的最小旅行費(fèi)用周游線路，以下是5個(gè)城市中從城市i到城市j的費(fèi)用。注意其中兩個(gè)城市之間往返的費(fèi)用是不相等的。(用動態(tài)規(guī)劃方法求解)答案：階段k：已經(jīng)歷過的城市個(gè)數(shù)，包括當(dāng)前所在的城市。k=1,2,…，n,n+1，k=1表示出發(fā)時(shí)位于起點(diǎn)，k=n+1表示結(jié)束時(shí)回到終點(diǎn)。較難分析121412345狀態(tài)箕量：xk=(I,七)，其中i表示當(dāng)刖所在的城市，Sk表示向木訪問過的城市的集合。很明顯S={2,3,…，n}，…，S=S=O1nn+1其中中表示空集。并且有xn=(i,①)i=2,3,…,n，xn+1=(1,中)決策變量：dk=(i,j)，其中i為當(dāng)前所在的城市，j為下一站將要到達(dá)的城市。狀態(tài)轉(zhuǎn)移方程：若當(dāng)前的狀態(tài)為xk=(i,Sk)采取的決策