中國(guó)計(jì)量學(xué)院運(yùn)籌學(xué)期末試卷C試題及答案

1、中國(guó)計(jì)量學(xué)院200 200 學(xué)年第 學(xué)期 運(yùn)籌學(xué) 課程考試試卷（ C ）開(kāi)課二級(jí)學(xué)院： 經(jīng)管學(xué)院 ，考試時(shí)間： 年_月_ _日 時(shí)考試形式：閉卷、開(kāi)卷，允許帶 計(jì)算器、鋼筆（圓珠筆）、學(xué)生證 入場(chǎng)裝訂線考生姓名： 學(xué)號(hào)： 專業(yè)： 班級(jí)： 題序一二三四五六總分得分評(píng)卷人一、單項(xiàng)選擇題（共20分，每題2分）1、當(dāng)線性規(guī)劃問(wèn)題的可行解集合非空時(shí)一定（ ） A、包含原點(diǎn) B、有界 C、無(wú)界 D、是凸集2、線性規(guī)劃具有無(wú)界解是指（ ）A、可行解集合無(wú)界 B、有相同的最小比值C、存在某個(gè)檢驗(yàn)數(shù)Ó0且aik 0(i=1,2,m) D、最優(yōu)表中所有非基變量的檢驗(yàn)數(shù)非零3. 對(duì)偶單純形法的適用條件是（

2、 ） A、對(duì)偶可行 ，原始不可行 B、對(duì)偶不可行 ，原始可行C、對(duì)偶可行 ，原始可行D、對(duì)偶不可行 ，原始不可行4、當(dāng)基變量Xi的系數(shù)Ci波動(dòng)時(shí)，最優(yōu)表中引起變化的是（ ）A、基變量XB的數(shù)值 B、所有非基變量的檢驗(yàn)數(shù) C、右端常數(shù)項(xiàng)b D、系數(shù)矩陣A5、具有m個(gè)產(chǎn)地n個(gè)銷地的平衡運(yùn)輸問(wèn)題模型具有特征為（ ）A、有 mn個(gè)約束條件 B、有m+n個(gè)非基變量 C、有mn-m-n-1個(gè)變量 D、有m+n-1個(gè)基變量6、max Z =3x1 + x2 ,4x1 + 3x2 7, x1+ 2x2 4 x1,x2= 0或1，最優(yōu)解是（ ） A、（0，0） B、（0，1） C、（1，0） D、（1，1）7、

3、連通圖G有n個(gè)點(diǎn)，其生成樹(shù)是T，則有（ ）A、T有n個(gè)點(diǎn)n條邊 B、T有n個(gè)點(diǎn)n-1條邊C、T中有m個(gè)點(diǎn)m-1條邊(m<n) D、T的長(zhǎng)度等于G的每條邊的長(zhǎng)度之和8、繪制網(wǎng)絡(luò)圖時(shí)，對(duì)引入的虛活動(dòng)說(shuō)法正確的是（ ）A、虛活動(dòng)是真實(shí)的活動(dòng) B、虛活動(dòng)需要耗用一定時(shí)間C、虛活動(dòng)用實(shí)箭線表示D、虛活動(dòng)僅表示相鄰活動(dòng)之間的銜接關(guān)系，不需要時(shí)間 9、對(duì)于不確定型的決策，某人采用樂(lè)觀主義準(zhǔn)則進(jìn)行決策，則應(yīng)在收益表中（ ）A、大中取大 B、大中取小C、小中取大 D、小中取小 10、下列錯(cuò)誤的結(jié)論是（ ）A、容量不超過(guò)流量 B、流量非負(fù)C、容量非負(fù) D、發(fā)點(diǎn)的流出合流等于流入收點(diǎn)的合流 單項(xiàng)選擇題答題表題

4、號(hào)12345678910答案二、判斷及改錯(cuò)題，正確打，錯(cuò)誤打×，并將修改建議簡(jiǎn)寫在對(duì)應(yīng)題號(hào)下的改錯(cuò)欄。 （共20分，每題2分）1、 任何線性規(guī)劃一定有最優(yōu)解。（ ）2、 線性規(guī)劃問(wèn)題減少一個(gè)變量，目標(biāo)值不會(huì)比原來(lái)變差。（ ）3、 高莫雷約束是將可行域中一部分非整數(shù)解切割掉。( )4、 運(yùn)輸問(wèn)題的檢驗(yàn)數(shù)就是對(duì)偶問(wèn)題松弛變量的值。（ ）5、 在指派問(wèn)題的效率表的某行加上一個(gè)非零數(shù)最優(yōu)解不變。（ ）6、 割集中弧的流量之和稱為割量。（ ）7、 事件i的最遲時(shí)間等于以i為開(kāi)工事件工序的最遲必須開(kāi)工時(shí)間的最小值（ ）8、 在網(wǎng)絡(luò)計(jì)劃中，總時(shí)差為0的工序成為關(guān)鍵工序（ ）9、 在不確定型決策中，

5、最小機(jī)會(huì)損失準(zhǔn)則比等可能性準(zhǔn)則保守性更強(qiáng)。（ ）10、 普通單純形法最小比值規(guī)則失效說(shuō)明問(wèn)題無(wú)界。（ ）判斷及改錯(cuò)題答題表題號(hào)12345678910答案改錯(cuò)三、（20分）對(duì)于如下的線性規(guī)劃問(wèn)題 min z = 3x1 + 2x2 +x3裝訂線s.t. x1 + x2 + x3 15 (1) 2x1 - x2 + x3 9 (2) -x1 + 2x2 +2x3 8 (3) x1 x2 x3 0 1、（5分）寫出題目中線性規(guī)劃問(wèn)題的對(duì)偶問(wèn)題； 2、（10分）分別求出原始問(wèn)題和對(duì)偶問(wèn)題的最優(yōu)解（求解的次序和方法不限）； 3、（5分）C3如何變化，使該問(wèn)題的最優(yōu)性保持不變。四、（15分）在一個(gè)3

6、15;3的運(yùn)輸問(wèn)題中，已知供應(yīng)量a115，a230，a385；而需求量b120，b230，b380，其最優(yōu)解運(yùn)輸量如下表所示：15525580又設(shè)各位勢(shì)為u1-2，u23，u35，v12，v25，v310，現(xiàn)問(wèn)：1、最優(yōu)總運(yùn)費(fèi)是多少？（10分）2、在保持上面解最優(yōu)解的條件下，各個(gè)非基變量的Cij的最小值是什么？（5分）五、（10分）某項(xiàng)目網(wǎng)絡(luò)圖如下，英文字母表示工序，數(shù)字表示該工序需要的時(shí)間。 a ,7 e,10 g,35 b,8 d,17 h,26裝訂線 C,12 f,24 i,17 j,34 1、 指出項(xiàng)目的關(guān)鍵路線；（5分）2、 求項(xiàng)目的完工期。（5分）六、（15分）1、求以下網(wǎng)絡(luò)的最小

7、支撐樹(shù)（5分）；2、求以下網(wǎng)絡(luò)從節(jié)點(diǎn)1到節(jié)點(diǎn)12的最短路徑（10分）。 3 4 7 6 2 5 1 1 9 8 4 8 6 3 7 2 4中國(guó)計(jì)量學(xué)院200 200 學(xué)年第 學(xué)期 運(yùn)籌學(xué) 課程試卷（ C ）參考答案及評(píng)分標(biāo)準(zhǔn)開(kāi)課二級(jí)學(xué)院：經(jīng)管學(xué)院 ，學(xué)生班級(jí)： ，教師： 一、單項(xiàng)選擇題（20分，每題2分）單項(xiàng)選擇題答題表題號(hào)12345678910答案DCABDDBDAA二、判斷及改錯(cuò)題（20分，每題2分） 判斷及改錯(cuò)題答題表題號(hào)12345678910答案×××改錯(cuò)可能有無(wú)界解目標(biāo)值變化不確定/割集弧的容量之和/ 三、（20分）對(duì)于如下的線性規(guī)劃問(wèn)題 min z =

8、 3x1 + 2x2 +x3s.t. x1 + x2 + x3 15 (1) 2x1 - x2 + x3 9 (2) -x1 + 2x2 +2x3 8 (3) x1 x2 x3 0 1、（5分，每個(gè)方程各1分）寫出題目中線性規(guī)劃問(wèn)題的對(duì)偶問(wèn)題； 解：max w = 15y1 + 9y2 + 8y3s.t. y1 + 2y2 - y3 3 (1) y1 - y2 + 2y3 2 (2) y1 + y2 + 2y3 1 (3) y10、 y2 0、y3 0 2、（10分，步驟為6分，結(jié)果為4分）分別求出原始問(wèn)題和對(duì)偶問(wèn)題的最優(yōu)解（求解的次序和方法不限）； 解：先將原問(wèn)題化成以下形式，則有 min

9、z = 3x1 + 2x2 + x3s.t. x1 + x2 + x3 + x4 = 15 (1) -2x1 + x2 - x3 + x5 = -9 (2) -x1 + 2x2 +2x3 +x6 = 8 (3) x1 x2 x3 x4 x5 x6 0X1X2X3X4X5X6右端z-3-2-1000X411110015X5-21-1010-9X6-1220018X1X2X3X4X5X6右端z-1-300-109X4-1201106X32-110-109X6-540021-10X1X2X3X4X5X6右端z0-19/500-7/5-1/511X406/5013/5-1/58X303/510-1/5

10、2/55X11-4/500-2/5-1/52 原始問(wèn)題的最優(yōu)解為（X1 X2 X3 X4 X5 X6）=（2，0，5，8，0，0），minz=11 對(duì)偶問(wèn)題的最優(yōu)解為（y1 y2 y3 y4 y5 y6）=（0，7/5，-1/5，0，19/5，0），maxw=11 3、（5分）C3如何變化，使該問(wèn)題最優(yōu)性不變。 解：設(shè)有C3+q,當(dāng)C3=1時(shí)，取最優(yōu)表變形為： X1X2X3X4X5X6右端z0-19/5-q0-7/5-1/511X406/5013/5-1/58X303/510-1/52/55X11-4/500-2/5-1/52 X1X2X3X4X5X6右端z0-19/5+3q/500-7/5-

11、q/5-1/5+2q/511+5qX406/5013/5-1/58X303/510-1/52/55X11-4/500-2/5-1/52則若使最優(yōu)解不變，應(yīng)有：-19/5+3q/5 0和 -7/5-q/5 0和-1/5+2q/50同時(shí)成立，則有-7q 1/2，即有-61+q3/2因此當(dāng)C3在-6，3/2的范圍內(nèi)變化時(shí)，最優(yōu)性不變。 四、（15分）150552585108015根據(jù)位勢(shì)法原理：基變量cijui+vj計(jì)算各基變量的運(yùn)價(jià)（如上圖所示）最優(yōu)總運(yùn)費(fèi)為0×15+5×5+25×5+10×5+80×151475（結(jié)果6分，步驟4分）根據(jù)位勢(shì)法原理

12、非基變量ijcij-（ ui+vj）所有的ij滿足大于零。12c12-（-2+5）0，所以c123，最小值為313c13-（-2+10）0，所以c128，最小值為823c23-（3+10）0，所以c1213，最小值為1311c11-（5+2）0，所以c127，最小值為7（結(jié)果3分，步驟2分）五、 （10分）求項(xiàng)目的完工期和關(guān)鍵路線。 a ,7 e,10 g,35 b,8 d,17 h,26 C,12 f,24 i,17 j,34TES(1,2)= TES(1,3)= TES(1,4)=0TES(2,4)= TES(1,2)+t12 =0+7=7= TES(2,5)TES(3,4)= TES(1

13、,3)+t13 =0+12=12= TES(3,7)TES(4,6)=maxTES(2,4)+t24, TES(1,4)+t14, TES(3,4)+t34, =12TES(5,9)= TES(2,5)+t25 =7+10=17TES(6,9)= TES(4,6)+t46 =12+17=29TES(7,8)= TES(7,9) = TES(3,7)+t37 =12+24=36TES(8,9)= TES(7,8)+t78 =36+34=70TEF(5,9)= TES(5,9)+t59 =17+35=52TEF(6,9)= TES(6,9)+t69 =29+26=55TEF(8,9)= TES(8

14、,9)+t89 =70+0=70所以完工期為T=70天，結(jié)果為5分。 TLS(5,9)= T-t59 =70-35=35TLS(6,9)= T-t69 =70-26=34TLS(7,9)= T-t79 =70-17=53TLS(8,9)= T-t89 =70-0=70TLS(7,8)= TLS(8,9)-t78 =70-34=36TLS(2,5)= TLS(5,9)-t25 =35-10=25TLS(4,6)= TLS(6,9)-t46 =34-17=17TLS(3,7)= min TLS(7,9)-t37, TLS(7,8)-t37=12TLS(3,4)= TLS(3,7)-t34 =12-0=12TLS(2,4)= TLS(2,5)-t24 =25-0=25TLS(1,2)= min TLS(