運(yùn)籌學(xué) 試卷及答案 卷2

課程名稱:課程名稱:運(yùn)籌學(xué)題號(hào)一二三四五六七八九十總分評(píng)卷得分評(píng)卷簽名復(fù)核得分復(fù)核簽名一、單項(xiàng)選擇（每題2分，共20分）1、對(duì)一個(gè)極大化的線性規(guī)劃問(wèn)題用單純形法求解，若對(duì)所有的檢驗(yàn)數(shù)，但對(duì)某個(gè)非基變量，有，則該線性規(guī)劃問(wèn)題（）A．有唯一最優(yōu)解B．有無(wú)窮多最優(yōu)解C．為無(wú)界解D．無(wú)可行解2、下列描述錯(cuò)誤的是（）A．對(duì)偶問(wèn)題的對(duì)偶問(wèn)題等同于原問(wèn)題B．有些線性規(guī)劃問(wèn)題通過(guò)對(duì)偶問(wèn)題的求解可以簡(jiǎn)化原問(wèn)題的求解C．若原問(wèn)題和對(duì)偶問(wèn)題均存在最優(yōu)解時(shí)，則它們相應(yīng)的目標(biāo)函數(shù)值相等D．當(dāng)對(duì)偶問(wèn)題有解時(shí)，原問(wèn)題也有解3、線性規(guī)劃原問(wèn)題第j個(gè)約束是嚴(yán)格不等式，則對(duì)偶問(wèn)題中第j個(gè)變量是。A．xj≥0B．xj≤0C．xj=0D．不一定4、對(duì)于m個(gè)產(chǎn)地、n個(gè)銷地的產(chǎn)銷平衡的運(yùn)輸問(wèn)題，敘述錯(cuò)誤的是。A．該問(wèn)題的系數(shù)矩陣有m×n列

B．該問(wèn)題的系數(shù)矩陣有m+n行C．該問(wèn)題的系數(shù)矩陣的秩必為m+n-1

D．該問(wèn)題的最優(yōu)解必唯一5、一個(gè)無(wú)向連通圖可以一筆畫(huà)的充分必要條件是（）A．圖中沒(méi)有奇點(diǎn)B．圖中恰好有兩個(gè)奇點(diǎn);C．圖中沒(méi)有偶點(diǎn);D．圖中的奇點(diǎn)數(shù)為0或者26、下列敘述正確的是。A．線性規(guī)劃問(wèn)題，若有最優(yōu)解，則必是一個(gè)基變量組的可行基解學(xué)院：專業(yè)：學(xué)號(hào)：姓名：裝訂線B．線性規(guī)劃問(wèn)題一定有可行基解C．線性規(guī)劃問(wèn)題的最優(yōu)解只能在頂點(diǎn)上達(dá)到D．單純形法求解線性規(guī)劃問(wèn)題時(shí)每換基迭代一次必使目標(biāo)函數(shù)值下降一次7、若一個(gè)指派問(wèn)題的系數(shù)矩陣的某行各元素都加上常數(shù)得到一個(gè)新的矩陣，這一新矩陣對(duì)應(yīng)著一個(gè)新的指派問(wèn)題，則（）。A．新問(wèn)題與原問(wèn)題有相同的最優(yōu)解B．新問(wèn)題最優(yōu)目標(biāo)值大于原問(wèn)題最優(yōu)目標(biāo)函數(shù)值C．新問(wèn)題最優(yōu)解等于原問(wèn)題最優(yōu)解加上D．新問(wèn)題最優(yōu)解小于原問(wèn)題最優(yōu)解8、用單純形法求解線性規(guī)劃問(wèn)題時(shí)引入的松弛變量在目標(biāo)函數(shù)中的系數(shù)為。A．0 B．很大的正數(shù)C．很大的負(fù)數(shù) D．19、下列敘述正確的是。A．目標(biāo)規(guī)劃中的正偏差變量取正值，負(fù)偏差變量取負(fù)值B．在目標(biāo)規(guī)劃模型中，應(yīng)同時(shí)包含絕對(duì)約束與目標(biāo)約束C．目標(biāo)規(guī)劃可以求解多階段決策問(wèn)題D．要求不超過(guò)目標(biāo)值，則目標(biāo)規(guī)劃的目標(biāo)函數(shù)表示為min{f（d+）}10、以下敘述中，不正確的是。A．樹(shù)的點(diǎn)數(shù)為邊數(shù)加1 B．樹(shù)的任意兩點(diǎn)間只有一條路C．圖的點(diǎn)數(shù)大于邊數(shù) D．任何不連通圖都不是樹(shù)二、判斷題（每題2分，共20分）1、如果線性規(guī)劃問(wèn)題的原問(wèn)題存在可行解，則其對(duì)偶問(wèn)題也一定存在可行解。（）2、若線性規(guī)劃問(wèn)題的最優(yōu)解存在，則最優(yōu)解或最優(yōu)解之一（如果有無(wú)窮多的話）一定是可行域的凸集的某個(gè)頂點(diǎn)。（）3、序列6，6，5，5，3，3可以是某個(gè)圖的點(diǎn)的次的序列。（）4、若在無(wú)圈圖中，任意增加一條邊就可以得到唯一的一個(gè)圈，則該圖為樹(shù)。5、圖解法同單純形法雖然求解的形式不同，但從幾何上理解，兩者是一致的。（）6、有m個(gè)產(chǎn)地，n個(gè)銷地的產(chǎn)銷平衡的運(yùn)輸問(wèn)題中，用表上作業(yè)法求解得到時(shí)，表中空格數(shù)是m×n－(m＋n－1)。（）7、對(duì)一個(gè)有n個(gè)變量、m個(gè)約束條件的標(biāo)準(zhǔn)型的線性規(guī)劃問(wèn)題，其可行域的頂點(diǎn)恰好為Cnm個(gè)。（）8、在目標(biāo)規(guī)劃中，絕對(duì)約束相應(yīng)的目標(biāo)函數(shù)其優(yōu)先等級(jí)一定是P1級(jí)。（）9、若某種資源的影子價(jià)格等于C，在其他條件不變的情況下，當(dāng)該種資源增加5個(gè)單位時(shí)，相應(yīng)的目標(biāo)函數(shù)值將增大5C。（）10、產(chǎn)銷平衡的運(yùn)輸問(wèn)題可能存在可行解也可能無(wú)解。（）三、解答題（共60分）1、（24分）已知線性規(guī)劃問(wèn)題（1）用單純形法求解線性規(guī)劃問(wèn)題，并指出屬哪一類解。（16分）（2）用圖解法解上述線性規(guī)劃問(wèn)題。（8分）2、（10分）寫(xiě)出下列問(wèn)題的對(duì)偶問(wèn)題。3、（10分）試求下圖的最小生成樹(shù),并計(jì)算該樹(shù)的長(zhǎng)度。2525615461545353446376374、（16分）某公司要把4個(gè)有關(guān)能源工程項(xiàng)目承包給4個(gè)互不相關(guān)的外商投標(biāo)者，規(guī)定每個(gè)承包商只能且必須承包一個(gè)項(xiàng)目，試在總費(fèi)用最小的條件下確定各個(gè)項(xiàng)目的承包者，總費(fèi)用為多少？各承包商對(duì)工程的報(bào)價(jià)如下表所示：項(xiàng)目投標(biāo)者ABCD甲21097乙154148丙13141611丁415139《運(yùn)籌學(xué)》參考答案及評(píng)分細(xì)則一、單項(xiàng)選擇題（2分/題，共20分）1、B2、D3、C4、D5、D6、A7、A8、A9、D10、C二、判斷題（2分/題，共20分）1、╳2、√3、√4、√5、√6、√7、╳8、╳9、╳10、╳三、解答題1．（1）解：將原問(wèn)題化為標(biāo)準(zhǔn)形式如下：(2分)Cj→24000θCBXBbx1x2x3x4x50x34-1[2]1004/20x4101201010/20x521-1001-δj24000（4分）4x22-1/211/200-0x46[2]0-11030x541/201/2018δj40-200（5分）4x37/2011/41/402x1310-1/21/200x55/2003/4-1/41δj000-20（3分）因?yàn)棣?=0，所以此問(wèn)題有無(wú)窮多最優(yōu)解。（1分）其中一個(gè)最優(yōu)解為X*=(3，7/2，0，0，5/2)T，maxZ＝20（1分）（2）圖解法-4-4-252210AB-x1+2x2=4-x1+x2=2x1+2x2=10如圖示，目標(biāo)函數(shù)等值線與可行域的交點(diǎn)是線段AB，A（3，7/2），B（2，4），此問(wèn)題有無(wú)窮多最優(yōu)解，maxz=10（圖6分，結(jié)果2分）2．解：設(shè)對(duì)偶變量分別為y1，y2，y3，則對(duì)偶問(wèn)題為：3．解：利用破圈法得原圖的最小樹(shù)如下圖所示：3344312（8分）最小樹(shù)長(zhǎng)為：3+4+3+4+2+1＝17（2分）4．解：用“匈牙利法”求解。行減（2分）試指派（4分）列減行減（2分）試指派（4分）列減（1分）√√√√