《運(yùn)籌學(xué)》試卷庫(kù)-試卷9答案一、單項(xiàng)選擇題（1x5分）1.B2.B3.C4.D5.A二、判斷正誤（對(duì)者打“J”，錯(cuò)者打“x”.1x5分）1.V2.x3.x4.x5.V三、（25分）解:1.（3分）設(shè)產(chǎn)品i、n、m在計(jì)劃期內(nèi)產(chǎn)量分別為x1、々、演，由題意，該問題的LP模型為:maxz=20x+15x+18x123‘2x+3x+4x<100123s.t.《4x+2x+3x<80123x>0,j=1,2,3j2.（15分）在約束中分別添加松弛變量x4、x5將LP化為標(biāo)準(zhǔn)形式，列單純形表求解:cj20151800b0CBXBx1x2x3x4x50x423410100500x5[4]23018020o.-i201518000??.x1換入、x5換出:50x40[2]5/21-1/260300x111/23/401/42040o.i0530-5-400??.x2換入、x4換出:50x2015/41/2-1/43040x1101/8-1/41/85o.-i00-13/4-5/2-15/4-550?.?VOj<0，.?.得最優(yōu)解:X*=（5,30,0,0,0）t，最優(yōu)值z(mì)*=550.Vx3是非基變量，故當(dāng)。3'<0，即Ac3<-。3=13/4,亦即c37<85/4時(shí)，原最優(yōu)解仍是最優(yōu)解。.對(duì)偶問題為：minw=100yl+80y2廣2y1+4y3>20J3y1+2y2>154y1+3y2>18、yry2>0對(duì)偶問題最優(yōu)解：Y*=（5/2，15/4）t，最優(yōu)值w*=550評(píng)分標(biāo)準(zhǔn):.正確設(shè)定決策變量：1分；正確列出LP模型：2分。.化標(biāo)準(zhǔn)形式、答案各1分，第1張單純形表3分,第2,3張單純形表各5分；.3分。.正確列出對(duì)偶問題模型：3分；最優(yōu)解1分。個(gè)別數(shù)據(jù)錯(cuò)誤酌情扣分。

四、（10分）解：設(shè)計(jì)劃期內(nèi)A、B、C三種產(chǎn)品的產(chǎn)量分別為11,%2,%3，由題意，該問題的GP模型為:+d+),Pd-，Pd-,Pd+}3+d+),Pd-，Pd-,Pd+}3243546d--d+=9011d--d+=7022d--d+=5033TOC\o"1-5"\h\z1112,i+三+2,%+3.t.《150%+180%+200%+d--d+=30000

123442%+2.5%+3%+d--d+=48012355d++d--d+=40

566%>0,j=1,2,3,d-,d+>0,i=1,…，6ii評(píng)分標(biāo)準(zhǔn):正確設(shè)定決策變量:2分；正確列出目標(biāo)規(guī)劃模型:8分。個(gè)別條件列錯(cuò)酌情扣分。一94646-一50202-5635323020五、（15分）解：化簡(jiǎn)系數(shù)矩陣:。=4149119-010575=C'1211437981042858406362圈出C,中的獨(dú)立0元素:_d__1@2021@202巧0202-2—_3__一0_2__.@2—-3---0-2---@43020⑨10575/⑨10575-2一08353二C'’91-8■一丁b—9-1-8-丁R-■Z-—1181046362」/L06362--2L_0414qJ/+2C,中只有4個(gè)獨(dú)立0元素，需要繼續(xù)變換:用最少直線數(shù)覆蓋所有0元素，未被直線覆蓋的元素中的最小元素是2,則未被直線覆蓋的行中每個(gè)元素-2,被直線覆蓋的列中每個(gè)元素+2‘得到C’‘。圈出C’'中的獨(dú)立0元素：7?20243?20?83531181?49414?L已得到5個(gè)獨(dú)立0元素。，最優(yōu)指派方案為:I做B工作；II做C工作；III做A工作；IV做D工作；V做E工作?？偤臅r(shí)為4+3+4+3+4=18（天）。評(píng)分標(biāo)準(zhǔn)：變換系數(shù)矩陣得到C,：3分；進(jìn)一步變換系數(shù)矩陣得到C”：7分；圈出5個(gè)獨(dú)立0元素、給出最優(yōu)指派方案：5分。個(gè)別數(shù)據(jù)錯(cuò)誤酌情扣分。六、（10分）解:建立該問題的動(dòng)態(tài)規(guī)劃模型如下:（1）采用逆序解法（順序解法亦可）;⑵階段：按產(chǎn)品劃分階段，每種產(chǎn)品為一個(gè)階段，k=1,2，…,n

⑶狀態(tài)變量狀態(tài)變量sk=(Xk，Yk),其中：Xk分配用于生產(chǎn)第k至第n種產(chǎn)品的第一種資源數(shù);Yk分配用于生產(chǎn)第k至第n種產(chǎn)品的第二種資源數(shù)。⑷狀態(tài)集合：S1=(a,b),S1=(0,0),(0,0)<Sk<(a,b),k=2,3,...,n⑸決策變量uk=(xk，yk)，其中％k:用于第k種產(chǎn)品生產(chǎn)的第一種資源數(shù),yk：用于第k種產(chǎn)品生產(chǎn)的第二種資源數(shù)。(6)允許決策集合:Dk(Xk，Yk)={(x卜，yk)|0<xk<Xk，0<yk<Yk},k=1,2，…,n(7)狀態(tài)轉(zhuǎn)移方程：Xk+1=Xk-xk,Yk+1=Yk-yk,k=1,2,…用⑻階段指標(biāo)：gk(xk,yk)，k=1,2,…,n(9)最優(yōu)指標(biāo)函數(shù)f(Xk,Yk)表示表示當(dāng)分配于第k種產(chǎn)品至第n種產(chǎn)品兩種資源數(shù)量為X.和Y^時(shí)的最大收益。(10)DP基本方程為:kkmax{g(X,J)+f(X-x,Y-y)}k=n,n-1,…,2,1kkkkkk+1kkkkf(f(s)=0n+1n+10<x<X0<ykk<yKk評(píng)分標(biāo)準(zhǔn):⑴~(10)項(xiàng)每項(xiàng)1分七、(15分)解：⑴標(biāo)號(hào)過程：先給Vs標(biāo)以(0，+8)。檢查vs的相鄰未標(biāo)號(hào)點(diǎn)，發(fā)現(xiàn)v1、v2符合標(biāo)號(hào)條件，故給V以標(biāo)號(hào)(vs,min{+叫cs1fs1})=(vs,2)；給v2以標(biāo)號(hào)(vs,min{+<?,cs2fs2})=(vs,2)。繼續(xù)標(biāo)號(hào)過程，給v以標(biāo)號(hào)(v2,min{2,c23f23})=(丫2,2)；給vt以標(biāo)號(hào)(v,min{2,c3t-3t})=(v,2)。至此vt已得到標(biāo)號(hào)，說明存在一條可增廣鏈：vs-V2-v-vt，如圖1。3轉(zhuǎn)調(diào)整過程。3⑵調(diào)整過程：沿可增廣鏈調(diào)整流量，調(diào)整量3=3vt=2,即令可增廣鏈上所有前向弧的流量增加2。調(diào)整后得到的可行流如圖2：(3)重新標(biāo)號(hào)：去掉所有標(biāo)號(hào)，對(duì)新的可行流重新標(biāo)號(hào)。給vs標(biāo)(0,+g),給V1以標(biāo)號(hào)(vs,min{+8,cs1fs1})=(vs,2)。至此標(biāo)號(hào)進(jìn)行不下去，而vt未得到標(biāo)號(hào)，說明圖中的流已是最大流。最大流量w(f*)=f4t+f3t=16。評(píng)分標(biāo)準(zhǔn)：評(píng)分標(biāo)準(zhǔn)：兩個(gè)表中的基可行解的檢驗(yàn)和解的調(diào)整各5分。個(gè)別數(shù)據(jù)錯(cuò)誤酌情扣分。最小割集《,S){…(、),(v1,v4)},如圖2中的虛線所示。最小割集的容量為：c(S,S)=cs1+c13+c14=10+3+3=16,與最大流的流量相等。評(píng)分標(biāo)準(zhǔn):(1)、(2)、(3)、圖1、圖2各3分。若算法步驟和圖不完整,可適當(dāng)扣分。八、(15分)解:閉回路法求得表中基可行解的非基變量的檢驗(yàn)數(shù)，填入表1中空格的左下角。?.?o11<0,??.表中基可行解不是最優(yōu)解。表1F??7肖地產(chǎn)地B1B2B3B4產(chǎn)量AiU-2L510匕3U5060A2匕40匕35U.8也875A31.80U.0U.70142090需求量40457070用閉回路法對(duì)表中的解進(jìn)行調(diào)整，閉回路為：(x11)—x12—x22—x21—(%”),調(diào)整量為min{/2,%21}=10,調(diào)整后得到一個(gè)新的基可行解,如表2。表2?理地產(chǎn)地'、、、B1B2B3B4產(chǎn)量A110口L5