廣工09運籌學(A)試題及答案

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

二、判斷下列說法是否正確。正確的在括號內打“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ī)劃模型，因而求解結果也可能出現下列四種情況之一：有惟一最優(yōu)解，有無窮多最優(yōu)解，無界解，無可行解。 （ ）6、 如果運輸問題的單位運價表的某一行（或某一列）元素再乘上那個一個常數k，最有調運方案將不會發(fā)生變化。 （ ）7、目標規(guī)劃模型中，應同時包含絕對約束與目標約束。 （ ）8、線性規(guī)劃問題是目標規(guī)劃問題的一種特殊形式。 （ ）9、指派問題效率矩陣的每個元素都乘上同一常數k，將不影響最優(yōu)指派方案。（ ）三、解答題。（72分）maxz=3x+3x121、（20分）用單純形法求解■<X1+X2<41、（20分）用單純形法求解■<一x+x<2126x+2x<1812x>0,x>012c2c2的變化范圍；⑵若右邊常數向量變?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，試根據對偶理論來求出原問題的最優(yōu)解。12

3、（15分）用表上作業(yè)法求下表中給出的運輸問題的最優(yōu)解。銷地產地甲乙丙丁產量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分）用位勢法檢驗得：銷地產地甲乙丙丁戊UIQ450IIQ4Q30Q-9III31131V019593所有非基變量的檢驗數都大于零，所以上述即為最優(yōu)解且該問題有唯此時的總運費：minz二4x5+5x9+4x10+3x1+1x20+1x10+3x4二14、解:系數矩陣為：「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從系數矩陣的每行元素減去該行的最小元素，得：0 10 5 7 29 8 0 0 40 6 3 6 5（7分）最優(yōu)解。50。（2分）

"702"702430經變換之后最后得到矩陣：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-