廣東工業(yè)大學期中考試試卷（A）課程名稱： 運籌學 考試時間：第十六周星期二（12月17日）題號-一一-二二三四五六七八九十總分評卷得分一、單項選擇題。下列每題給出的四個答案中只有一個是正確的，將表示正確答案的字母寫這答題紙上。（10分，每小題2分）1、 使用人工變量法求解極大化線性規(guī)劃問題時，當所有的檢驗數(shù)b<0，在j基變量中仍含有非零的人工變量，表明該線性規(guī)劃問題（）有唯一的最優(yōu)解；B.有無窮多個最優(yōu)解；C.無可行解；D.為無界解2、 對偶單純形法解最大化線性規(guī)劃問題時，每次迭代要求單純形表中（）A.b列元素不小于零 B.檢驗數(shù)都大于零C.檢驗數(shù)都不小于零 D.檢驗數(shù)都不大于零3、 在產(chǎn)銷平衡運輸問題中，設產(chǎn)地為m個，銷地為n個，那么基可行解中非零變量的個數(shù)（）A.不能大于（m+n-1）；B.不能小于（m+n-1）；C.等于（m+n-1）；D.不確定。4、如果要使目標規(guī)劃實際實現(xiàn)值不超過目標值。則相應的偏離變量應滿足艾A.d+>0 B.d+=0 C.d-=0 D.d->0,d+>05、下列說法正確的為（）如果線性規(guī)劃的原問題存在可行解，則其對偶問題也一定存在可行解如果線性規(guī)劃的對偶問題無可行解，則原問題也一定無可行解在互為對偶的一對原問題與對偶問題中，不管原問題是求極大或極小，原問題可行解的目標函數(shù)值都一定不超過其對偶問題可行解的目標函數(shù)如果線性規(guī)劃問題原問題有無界解，那么其對偶問題必定無可行解

二、判斷下列說法是否正確。正確的在括號內(nèi)打“V”，錯誤的打“X”。（18分，每小題2分）TOC\o"1-5"\h\z1、 如線性規(guī)劃問題存在最優(yōu)解，則最優(yōu)解一定對應可行域邊界上的一個點。（ ）2、 單純形法計算中，如不按最小比列原則選取換出變量，則在下一個解中至少有一個基變量的值為負。 （）3、任何線性規(guī)劃問題存在并具有惟一的對偶問題。 （ ）4、 若線性規(guī)劃的原問題有無窮多最優(yōu)解，則其最偶問題也一定具有無窮多最優(yōu)解。（）5、 運輸問題是一種特殊的線性規(guī)劃模型，因而求解結果也可能出現(xiàn)下列四種情況之一：有惟一最優(yōu)解，有無窮多最優(yōu)解，無界解，無可行解。 （ ）6、 如果運輸問題的單位運價表的某一行（或某一列）元素再乘上那個一個常數(shù)k，最有調(diào)運方案將不會發(fā)生變化。 （ ）7、目標規(guī)劃模型中，應同時包含絕對約束與目標約束。 （ ）8、線性規(guī)劃問題是目標規(guī)劃問題的一種特殊形式。 （ ）9、指派問題效率矩陣的每個元素都乘上同一常數(shù)k，將不影響最優(yōu)指派方案。（ ）三、解答題。（72分）maxz=3x+3x121、（20分）用單純形法求解■<X1+X2<41、（20分）用單純形法求解■<一x+x<2126x+2x<1812x>0,x>012c2c2的變化范圍；⑵若右邊常數(shù)向量變?yōu)锽二5220，分析最優(yōu)解的變化。（15分）已知線性規(guī)劃問題:maxz=x+2x+3x+4x12 3 4”x+2x+2x+3x<20J2X+x+3x3+2x<20

I1 2 3 4-XXXX>0I 1'2'3'4—其對偶問題最優(yōu)解為Y二1.2,Y二0.2，試根據(jù)對偶理論來求出原問題的最優(yōu)解。12

3、（15分）用表上作業(yè)法求下表中給出的運輸問題的最優(yōu)解。銷地產(chǎn)地甲乙丙丁產(chǎn)量I327650II752360III254525銷量604020154、（12分）求下表所示效率矩陣的指派問題的最小解,'、、工作工人'、、、ABCDE甲127979乙89666丙71712149丁15146610戊14107109minz=x+1.5x12/八、er、rr、—S..X+3x>35、（10分）用大M法求解4 1 2x+x>2

12x>0,x>0v12廣東工業(yè)大學期中考試試卷參考答案及評分標準（A卷）課程名稱:運籌學課程名稱:運籌學考試時間:單項選擇題：1-5CDABD2009年12月17日（第16周星期四）考試時間:單項選擇題：1-5CDABD2009年12月17日（第16周星期四）（每題2分）二、判斷題:二、判斷題:6-10XXVXV（每題26-10XXVXV三、解答題：1、解：加入人工變量，化問題為標準型式如下：maxz=3x+3x+0x+0x+0xTOC\o"1-5"\h\z1 2 3 4 5x+x+x=41 2 3—x+x+x=2 （3分）s.“ 1 2 46x+2x+x=181 2 5x,x,x,x,x>0V1 2 3 4 5下面用單純形表進行計算得終表為：cj33000CB基bx1x2x3x4x50x3102/310-1/60x4504/3011/63x1311/3001/6czj-j0000-1/2TOC\o"1-5"\h\z（5分）所以原最優(yōu)解為X*=（3,0,1,5,0）t （2分）

I459II44III31138銷量35463（5分）用位勢法檢驗得：銷地產(chǎn)地甲乙丙丁戊UIQ450IIQ4Q30Q-9III31131V019593所有非基變量的檢驗數(shù)都大于零，所以上述即為最優(yōu)解且該問題有唯此時的總運費：minz二4x5+5x9+4x10+3x1+1x20+1x10+3x4二14、解:系數(shù)矩陣為：「12 7 9 7 9_8 9 6 6 67 17 12 14 915 14 6 6 10[4 10 7 10 9 _（3分）「5 0 2 0 22 3 0 0 0從系數(shù)矩陣的每行元素減去該行的最小元素，得：0 10 5 7 29 8 0 0 40 6 3 6 5（7分）最優(yōu)解。50。（2分）

"702"702430經(jīng)變換之后最后得到矩陣：0831180_041-01000-00010相應的解矩陣：0000100100_10000_0200500443（13分）由解矩陣得最有指派方案：甲一B,乙一D,丙一E,丁一C,戊一A或者甲一B,乙一C,丙一E,丁一D,戊一A （2分）所需總時間為：Minz=32所需總時間為：Minz=32（2分）5、解：將問題標準后，構造輔助為：minz=x+1.5x+M(x+x)TOC\o"1-5"\h\z1 2 5 6s.tx+3x-x+x=3V 1 2 3 5x+x-x+x=212 4 6x>0, ,x>0J1 6以x,x為初始基變量，列單純形表計算如下:5 6cj11.500MMCB基bx1x2x3x4x5x60x5313-10103x62110-101czj-j1-2M1.5-4MMM000x211/31-1/301/30

0x612/301/3-1-1/31czj-