《運(yùn)籌學(xué)》試卷08-答案

《運(yùn)籌學(xué)》試卷庫-試卷8答案一、單項(xiàng)選擇題(15分）1.B 2.C 3.A 4.D 5.C二、判斷正誤（×5分）1.× 2.× 3.√ 三、(30分）解:(5分）設(shè)產(chǎn)品Ⅰ、Ⅱ、Ⅲ在計(jì)劃期內(nèi)產(chǎn)量分別為

LPmaxz40x1

45x2

50x34x5x

7x 210 18x2

33x 120.6xx1 2 3jjcj40C00BXBxcj40C00BXBx45x50x0x0xb3060x4x5j4045500003552.57j80/765/70 -50/73552.57j80/765/70 -50/70-1500∴31234545[7]1021068301120

換出:50x4/75/711/70300x[30/7]41/70-3/71305040x3x1j5040x3x1j010-1/1541/30-19/31 2/5 -2/15 260 -1/10 7/30 70 -6 -8/3 -1580∴1

換出:j∵0，∴得最優(yōu)解:X*=(7,0,26,0,0)T，最優(yōu)值z*=1580j3.∵x’0，即c-=19/3，亦即

’154/3時(shí)，原最優(yōu)解仍是最優(yōu)解。2 2 2 2 2對(duì)偶問題為：minw=210y1

+120y24y+6y

401 35y+8y1 7y+3y1

4550y,y01 2對(duì)偶問題最優(yōu)解：Y*=(6,8/3)T，最優(yōu)值w*=1580評(píng)分標(biāo)準(zhǔn)::2LP:31132,353.5分。4:32個(gè)別數(shù)據(jù)錯(cuò)誤酌情扣分。(10、Cx1,x2,x3，由題意，該問題的GPmin{Pd,Pd,P(dddd),Pd}1 1 2 2 3 3 4 5 5 4 62x2.5x

3x

dd240 1

3 1 11x1801

200x d

d

25000x

2 3 dd

21001 3 3x

d4x d

d4d

80703 5 5 ddd

60 1 6 6x 0,jd,dj i i

0,i1, ,6評(píng)分標(biāo)準(zhǔn):正確設(shè)定決策變量:2分；正確列出目標(biāo)規(guī)劃模型:8分。個(gè)別條件列錯(cuò)酌情扣分。7 7 912 9 0 0 2 5 2 8 9 6 6 6 五、(15分）:變換系數(shù)矩:C1712712710 5 0 5C' 614 61510 C’0

10 7 4 6

6 6 3 0 2

2252252002723232030407105571055-2583038948940801146632663+22-244100C’4002-2,被直線覆蓋的列中每個(gè)元素+2圈出0元素:0272345833811444150:IBCD做A工作；VE7+6+7+6+6=32（天。評(píng)分標(biāo)準(zhǔn):變換系數(shù)矩陣得到C’：450六、(10分)解:建立該問題的動(dòng)態(tài)規(guī)劃模型如下:(1)采用逆序解法(順序解法亦可);狀態(tài)變量k(4)S1=b，S4=0，0Skb,k=2,3(5)決策變量xk

為分配第k個(gè)項(xiàng)目的資金，k＝1,2,3(6)允許決策集合:0xS,k=1,2,3k k(7)狀態(tài)轉(zhuǎn)移方程=s-x，k＝1,2,3k+1 k k(8)階段指標(biāo):v(s,x)=g(x)，k＝1,2,3k k k k k最優(yōu)指標(biāo)函數(shù)f(s)表示第ks時(shí),采取最優(yōu)策略,從第k3k k段的最大投資收益。DPfk(s

)max (xk k

)

k

(sk

)k3,2,1f(s4 4

0xSkk)0kk評(píng)分標(biāo)準(zhǔn):(1)～(10)項(xiàng)每項(xiàng)1分.七、(10分）解:vs(0，+∞)的相鄰未標(biāo)號(hào)點(diǎn)，發(fā)現(xiàn)v1、符合標(biāo)號(hào)條件，故給v以標(biāo)號(hào)(v,min｛+∞,cs1-fs1｝)=(vs,2)；給v2以標(biāo)號(hào)(vs,min｛+∞,cs2-fs2})=(vs,1)。繼續(xù)標(biāo)號(hào)1 s過程，給v以標(biāo)號(hào)(v1,min｛2,c14-f14｝)=(v1,2)；給v3以標(biāo)號(hào)(-v4,min｛2,f4})=(-v4,2)；給vt434以標(biāo)號(hào)(v,min｛2,c3t–f3t})=(v,2)。至此v已得到標(biāo)號(hào)，說明存在一條可增廣鏈。轉(zhuǎn)調(diào)整過程。3 3(vs,2) v1

tv(v1,2)v4(6,4)(0,+∞)vs (10,9)圖1v圖1

(3,3)(4,4)(5,5)

(6,3)(9,5)v3

(8,8)

(v,2)vt(vs,1)

(-v

,2)4s 1 4 3 t 調(diào)整過程可增廣鏈：→v→vv→v1δ=v=2，即令可增廣鏈上所有前向弧的流量增加222s 1 4 3 t v1(6,6)(0,+∞）vs (10,9)v2

(3,3)(3,3)(4,4)(5,5)

v4(6,3)(9,7)v3

(8,8)vt(vs,1)

2重新標(biāo)號(hào)：去掉所有標(biāo)號(hào)，對(duì)新的可行流重新標(biāo)號(hào)。s v標(biāo)（0,+∞）,v2(vs,min｛+∞,cs2-fs2})=(vs,1)vs 4t3標(biāo)號(hào)，說圖的流已是最大流。最大流量w(f*)=f+f =154t3最小割集SS={(v,v),(v,v),(v,v)}2+s 1 2 3 2 4 s1c +c =6+5+4=15, 與最大流的流量相等。23 24(1(2（、圖、圖2各2八、(15分）解:閉回路法求得表中基可行解的非基變量的檢驗(yàn)數(shù)，填入表1中空格的左下角?！?<0，∴表中基可行解不是最優(yōu)解。34銷地產(chǎn)地A銷地產(chǎn)地A1A2A3B1B2B3B4產(chǎn)量76244105046020330257335054532需求量252303545-34050—用閉回路法對(duì)表中的解進(jìn)行調(diào)整，閉回路為（x ）x —x x （x ，調(diào)整量為minx ，—34 14 24 33 34 14x }=352。33銷地B1銷地B1B2B3B4產(chǎn)量產(chǎn)地A1A2A3需求量7624114515602033025766505254