運籌學(xué) 試卷及答案 卷1

《運籌學(xué)》期末考試試卷A專業(yè)班級姓名學(xué)號題號一二三四五六七八考試成績得分得分一、單選題(2分*10=20分)（）1、對一個極大化的線性規(guī)劃問題用單純形法求解，若存在某檢驗數(shù)，且它所在列的系數(shù)所有系數(shù)均不大于0，則該線性規(guī)劃問題。A．有唯一最優(yōu)解B．有無窮多最優(yōu)解C．為無界解D．無可行解（）2、若原問題中xj為自由變量，那么對偶問題中的第j個約束一定為。A．等式約束B．“≤”型約束C．“≥”約束D．無法確定（）3、有m個產(chǎn)地，n個銷地的產(chǎn)銷平衡的運輸問題中，用表上作業(yè)法求解得到時，表中空格數(shù)是。A．m×nB．m+n－1C．m+nD．m×n－(m+n－1)（）4、解最大化指派問題時，先轉(zhuǎn)化為最小化指派問題，轉(zhuǎn)化的方法是。A.用矩陣的最大元素減去所有元素；B．用矩陣的最小元素減去所有元素；C．每行的元素減去本行最小元素，然后再對各列的元素減去本列最小元素；D．用每行的最大元素減去本行元素，然后再用各列的最大元素減去對本列的元素。（）5、關(guān)于凸集，不正確的描述是。A．凸集里面的任意兩個點的連線上的點仍然在該凸集內(nèi);B．線性規(guī)劃問題的可行域一定是一個凸集;C．若線性規(guī)劃問題的可行域是凸集，則該凸集上任一個頂點都可能是最優(yōu)解;D．若線性規(guī)劃問題存在最優(yōu)解，則最優(yōu)解一定是可行域凸集上的某一個頂點或邊上。（）6、用沃格爾法求解運輸問題時，如果差值很大時，應(yīng)盡量優(yōu)先安排所在行或列的運輸。A．最小元素B．最大元素C．最大差D．最小差（）7、若一個指派問題的系數(shù)矩陣的某行各元素都加上常數(shù)得到一個新的矩陣，這一新矩陣對應(yīng)著一個新的指派問題，則。A．新問題與原問題有相同的最優(yōu)解B．新問題最優(yōu)目標(biāo)值大于原問題最優(yōu)目標(biāo)函數(shù)值C．新問題最優(yōu)解等于原問題最優(yōu)解加上D．新問題最優(yōu)解小于原問題最優(yōu)解（）8、下列命題中不正確的是。A．整數(shù)規(guī)劃問題的可行解一定是其松弛問題的可行解;B．整數(shù)規(guī)劃問題最優(yōu)目標(biāo)函數(shù)值不超過其松弛問題最優(yōu)目標(biāo)函數(shù)值;C．若松弛問題的最優(yōu)解是整數(shù)規(guī)劃問題的可行解,則它是整數(shù)規(guī)劃問題的最優(yōu)解;D．整數(shù)規(guī)劃一定存在最優(yōu)解.（）9、若是原問題為極小問題的可行解，而是其對偶問題的可行解，則有。；B．；C．；D．與沒有關(guān)系。（）10、當(dāng)某一cj發(fā)生改變，則（）A.原最優(yōu)解發(fā)生改變；B.原可行解可能改變；C.原可行解不變；D.不確定得分二、判斷題（2分*10=20分,把答案填在序號前）（）1、對偶問題的對偶問題等同于原問題。（）2、整數(shù)規(guī)劃問題的可行解集合是它的松弛問題可行解集合的一個子集。（）3、用位勢法求檢驗數(shù)時，位勢不同則求出的檢驗數(shù)不一定不同。（）4、對于最大化問題，其最終表檢驗數(shù)的相反數(shù)是對偶問題的最優(yōu)解。（）5、影子價格是指外部市場價格，它是機會成本，是邊際利潤。（）6、根據(jù)互補松弛定理，當(dāng)時，=0。（）7、圖解法同單純形法雖然求解的形式不同，但從幾何上理解，兩者是一致的。（）8、若某種資源的影子價格等于C，在其他條件不變的情況下，當(dāng)該種資源增加5個單位時，相應(yīng)的目標(biāo)函數(shù)值將增大5C。（）9、0-1規(guī)劃問題中，當(dāng)決策變量個數(shù)是4時，則它的可行解個數(shù)是32。（）10、采用分支定界法解整數(shù)規(guī)劃問題時，如果某個問題恰好獲得整數(shù)規(guī)劃問題的一個可行解，那么可以把它作為目標(biāo)函數(shù)值的“界限”。得分三、計算題（60分）1、寫出下面線性規(guī)劃的標(biāo)準(zhǔn)形式和對偶規(guī)劃。（8分）2、已知線性規(guī)劃問題（1）用單純形法求出最優(yōu)解。（8分）（2）約束條件右端項由變?yōu)?，最?yōu)解如何改變。（5分）（3）直接寫出對偶問題的最優(yōu)解。（5分）3、運用表上作業(yè)法求解下列運輸問題，表格中間的數(shù)字為運價。（12分）產(chǎn)銷甲乙丙丁產(chǎn)量A9181109B11681810C14122166銷量49754、求如下最大指派問題，系數(shù)矩陣為：（10分）5、下圖為一網(wǎng)絡(luò)圖，邊上數(shù)字為邊的容量或者長度：用Dijkstra算法求解從頂點1到頂點8最短路；（5分）求從頂點1到頂點8的最大流，并求最小割。（7分）VV1V2V4V3V5V7V6V85679446459754<運籌學(xué)>課程A卷參考答案一、選擇題（每小題2分，共20分）1--5、CADAB6--10、CADCC判斷題（每小題1分，共10分）1--5、√√√√×6--10、√√××√三、計算題1、則標(biāo)準(zhǔn)形式為：設(shè)對偶變量分別為y1，y2，y3，則對偶規(guī)劃為：或者2、解：（1）首先寫出線性規(guī)劃問題的標(biāo)準(zhǔn)形式（1分）Cj→23100θCBXBbx1x2x3x4x50x45111105/10x54-1[2]0014/2δj23100（2分）0x43[3/2]011-1/223x22-1/21001/2—δj5/2000-3/2（2分）2x12102/32/3-1/33x23011/31/31/3δj00-4/3-7/3-1/3（2分）此時，原問題得到最優(yōu)解為X*=(2，3，0，0，0)T，maxZ＝13（1分）（2）當(dāng)右邊向量b變?yōu)?3,7)T時，（2分）代入最終單純型表繼續(xù)迭代：Cj→23100CBXBbx1x2x3x4x52x1-1/3102/32/3[-1/3[3x210/3011/31/31/3δj00-4/3-7/3-1/3（2分）0x51-30-2-213x2311110δj-10-2-30（2分）所以X*=（0，3，0，0，1）T，Z*=9Y*=（7/3,1/3,0,0,4/3）（2分，1分，1分，1分，1分）x1x1x2x3x4x5y1y2y3y4y5（說明：如果本部分的思路正確，并且答案和第一步表中檢驗數(shù)案契合，僅僅扣掉1分。只寫出關(guān)鍵的y1和y2也給滿分）3.解：由最小元素法得初始運輸方案如下表所示：（初始解3分，檢驗數(shù)3分）甲乙丙丁產(chǎn)量uiA918110902(14)7(-1)B11681810219(5)(5)C1412216651(3)(-4)5銷量4975Vj94111因為σ14，σ33＜0，所以該方案不是最優(yōu)方案。進行調(diào)整：（調(diào)整2分，新檢驗數(shù)2分）甲乙丙丁產(chǎn)量uiA918110903(14)6(-5)B11681810219(5)(1)C141221661(4)(7)15銷量4975Vj94115因為σ14＜0，故該方案不是最優(yōu)方案，再調(diào)整。新方案如下：（再調(diào)整1分，檢驗數(shù)1分）甲乙丙丁產(chǎn)量uiA918110903(14)15B11681810219(5)(6)C141221661(4)(7)6(5)銷量4975Vj94110因為，所以該方案是最優(yōu)方案?？傔\費為155。（1分）（說明：此題如果采用差值法求初始方案時，則無需調(diào)整，直接通過計算檢驗數(shù)馬上可以得出最優(yōu)答案，計算過程會簡潔很多，最終結(jié)果都是155）4、首先變成最小化指派問題。B=35-Cij)5×5（2分）行列變換（2分）行列變換（2分）試指派2分，劃直線3分調(diào)整（2分）調(diào)整（2分）再指派2分即：S1→J5，S2→J1，S3→J2，S4→J3，S5→J3此時總得分W=33+19+41+35+19=147（1分）（說明：此題方案不唯一，但是最終結(jié)果都是147）（1）66(8,8)(14,14)V1V2V4V3V5V7V6V8571446459754(4,4)(9,9)(13,13)(6,6)(17,15)（5分）所以V1到V8的最短路長為15。路徑為：V1→V2→V5→V7→V8。（2分）（2）V1→V2→V4→V6→V84（1分）V1→V3→V5→V7→V86