工業(yè)大學運籌學期末考試試卷及答案

工業(yè)大學試卷用紙，共3頁，第5頁工業(yè)大學考試試卷(A)課程名稱:運籌學工業(yè)大學考試試卷(A)課程名稱:運籌學考試時間:第十九周星期三(01月09日)題號一二三四五六七八九十總分評卷得分評卷簽名復核得分復核簽名單項選擇題。下列每題給出的四個答案中只有一個是正確的，將表示正確答案的字母填入題后的括號中。（10分）1、對一個極大化的線性規(guī)劃問題用單純形法求解，若對所有的檢驗數(shù)，但對某個非基變量，有，則該線性規(guī)劃問題（）A.有唯一的最優(yōu)解；B.有無窮多個最優(yōu)解；C.為無界解；D.無可行解。2、下列關于對偶問題的說法不正確的是（）A.任何線性規(guī)劃問題存在并具有唯一的對偶問題；B.對偶問題的對偶問題一定是原問題；C.當原問題為無界解時，其對偶問題無可行解；反之，當對偶問題無可行解時，其原問題具有無界解；D.原問題任一可行解的目標函數(shù)值是其對偶問題目標函數(shù)值的下界。3、在產(chǎn)銷平衡運輸問題中，設產(chǎn)地為m個，銷地為n個，那么解中非零變量的個數(shù)（）A.不能大于(m+n-1)；B.不能小于(m+n-1)；C.等于(m+n-1)；D.不確定。4、在求解目標規(guī)劃問題時，如果要使目標規(guī)劃實際實現(xiàn)值不超過目標值，則相應的偏離變量一定滿足（）A.；B.；C.；D.5、無向連通圖G是歐拉圖，當且僅當G中（）。A.無奇點；B.無偶點；C.無懸掛點；D.無孤立點。學院：專業(yè)：學號：姓名：裝訂線二、判斷下列說法是否正確。正確的在括號內(nèi)打“√”，錯誤的打“×”。（30分）1、線性規(guī)劃問題的每一個基解對應可行域的一個頂點。（）2、用單純形法求解標準型式的線性規(guī)劃問題時，與對應的變量都可以被選做換入變量。（）3、如線性規(guī)劃的原問題存在可行解，則其對偶問題也一定存在可行解。（）4、應用對偶單純形法計算時，若單純形表中某一基變量，又所在行的元素全部大于或等于零，則可以判斷其對偶問題具有無界解。（）5、運輸問題是一種特殊的線性規(guī)劃模型，因而求解結果也可能出現(xiàn)下列四種情況之一：有唯一最優(yōu)解，有無窮多最優(yōu)解，無界解，無可行解。（）6、正偏差變量應取正值，負偏差變量應取負值。（）7、整數(shù)規(guī)劃解的目標函數(shù)值優(yōu)于其相應的線性規(guī)劃問題的解的目標函數(shù)值。（）8、指派問題效率矩陣的每個元素都乘上同一常數(shù)k，將不影響最優(yōu)指派方案。（）9、在任一圖G中，當點集V確定后，樹圖是G中邊數(shù)最少的連通圖。（）10、求圖的最小生成樹的問題可以歸結為求解整數(shù)規(guī)劃問題。（）三、解答題。（60分）1、（15分）用單純形法求解以下線性規(guī)劃問題。（15分）已知線性規(guī)劃問題：寫出其對偶問題。若已知其對偶問題的最優(yōu)解為，，試用對偶問題的性質(zhì)，求原問題的最優(yōu)解。（10分）用表上作業(yè)法求下表中給出的運輸問題的最優(yōu)解。銷地產(chǎn)地甲乙丙丁戊產(chǎn)量Ⅰ102059109Ⅱ21083064Ⅲ12071048銷量35463（10分）有4個工人，要指派他們分別完成4項工作，每人做各項工作所消耗的時間如下表所示。問：指派哪個工人完成哪項工作，可使總消耗時間為最??？工作工人ABCD甲15182124乙19232218丙26171619丁19212317245223313253222（10分）求下圖的最小生成樹24522331325322222 PAGE12工業(yè)大學試卷用紙，共4頁，第12頁PAGE工業(yè)大學試卷參考答案及評分標準(A卷)課程名稱:運籌學考試時間:2008年01月09日(第19周星期三)一、單項選擇題：1-5BCABA（每題2分）二、判斷題：1-5×√×√×6-10×××√√（每題1分）三、解答題：1、解：將問題化為標準型式如下：(3分)下面用單純形表進行計算：250000410100-0120[2]01060183200192500004101004560101/20-06[3]00-112200-5/20020011/3-1/3560101/2022100-1/31/3000-11/6-2/3（8分）最終結果表明：最優(yōu)解：（3分）目標函數(shù)最優(yōu)值：（1分）2、解：（1）該問題的對偶問題為：（5分）（2）因為最優(yōu)解為，，帶入上面各式并根據(jù)對偶問題的互補松弛性：③④為等式，故，①②為不等式，故，（4分）又有，，即原問題的約束條件應取等號。（2分）因此：解得：（2分）原問題的最優(yōu)解為：（1分）目標函數(shù)最優(yōu)值：（1分）3、解：因為銷量：3+5+6+4+3=21；產(chǎn)量：9+4+8=21；為產(chǎn)銷平衡的運輸問題。（1分）由最小元素法求初始解：銷地產(chǎn)地甲乙丙丁戊產(chǎn)量Ⅰ459Ⅱ44Ⅲ31138銷量35463（5分）用位勢法檢驗得：銷地產(chǎn)地甲乙丙丁戊UⅠeq\o\ac(○,10)eq\o\ac(○,1)45eq\o\ac(○,7)0Ⅱeq\o\ac(○,11)4eq\o\ac(○,12)eq\o\ac(○,30)eq\o\ac(○,12)-9Ⅲ31eq\o\ac(○,1)131V019593（7分）所有非基變量的檢驗數(shù)都大于零，所以上述即為最優(yōu)解且該問題有唯一最優(yōu)解。此時的總運費：。（2分）4、解：系數(shù)矩陣為：（3分）從系數(shù)矩陣的每行元素減去該行的最小元素，得：再從每列元素減去該列的最小元素，得：（4分）圈定獨立零元素：（3分）此時獨立零元素個數(shù)為3<4，給第四行打，給第四列打√，給第二行打√，將第1，3行畫一橫線，第4列畫一縱線，得√√√變換矩陣后得：（3分）√√√給第1，4列打√，第1，2，4行打√，給第1，4列畫一縱線，第3行畫一橫線，變換矩陣得：（5分）得到最優(yōu)指派方案為：甲—B，乙—A，丙—C，丁—D所消耗的總時間為：18+19+16+17=