廣工09運(yùn)籌學(xué)(A)試題及答案

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

二、判斷下列說(shuō)法是否正確。正確的在括號(hào)內(nèi)打“V”，錯(cuò)誤的打“X”。（18分，每小題2分）TOC\o"1-5"\h\z1、 如線性規(guī)劃問(wèn)題存在最優(yōu)解，則最優(yōu)解一定對(duì)應(yīng)可行域邊界上的一個(gè)點(diǎn)。（ ）2、 單純形法計(jì)算中，如不按最小比列原則選取換出變量，則在下一個(gè)解中至少有一個(gè)基變量的值為負(fù)。 （）3、任何線性規(guī)劃問(wèn)題存在并具有惟一的對(duì)偶問(wèn)題。 （ ）4、 若線性規(guī)劃的原問(wèn)題有無(wú)窮多最優(yōu)解，則其最偶問(wèn)題也一定具有無(wú)窮多最優(yōu)解。（）5、 運(yùn)輸問(wèn)題是一種特殊的線性規(guī)劃模型，因而求解結(jié)果也可能出現(xiàn)下列四種情況之一：有惟一最優(yōu)解，有無(wú)窮多最優(yōu)解，無(wú)界解，無(wú)可行解。 （ ）6、 如果運(yùn)輸問(wèn)題的單位運(yùn)價(jià)表的某一行（或某一列）元素再乘上那個(gè)一個(gè)常數(shù)k，最有調(diào)運(yùn)方案將不會(huì)發(fā)生變化。 （ ）7、目標(biāo)規(guī)劃模型中，應(yīng)同時(shí)包含絕對(duì)約束與目標(biāo)約束。 （ ）8、線性規(guī)劃問(wèn)題是目標(biāo)規(guī)劃問(wèn)題的一種特殊形式。 （ ）9、指派問(wèn)題效率矩陣的每個(gè)元素都乘上同一常數(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ī)劃問(wèn)題: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—其對(duì)偶問(wèn)題最優(yōu)解為Y二1.2,Y二0.2，試根據(jù)對(duì)偶理論來(lái)求出原問(wèn)題的最優(yōu)解。12

3、（15分）用表上作業(yè)法求下表中給出的運(yùn)輸問(wèn)題的最優(yōu)解。銷(xiāo)地產(chǎn)地甲乙丙丁產(chǎn)量I327650II752360III254525銷(xiāo)量604020154、（12分）求下表所示效率矩陣的指派問(wèn)題的最小解,'、、工作工人'、、、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è)大學(xué)期中考試試卷參考答案及評(píng)分標(biāo)準(zhǔn)（A卷）課程名稱(chēng):運(yùn)籌學(xué)課程名稱(chēng):運(yùn)籌學(xué)考試時(shí)間:單項(xiàng)選擇題：1-5CDABD2009年12月17日（第16周星期四）考試時(shí)間:單項(xiàng)選擇題：1-5CDABD2009年12月17日（第16周星期四）（每題2分）二、判斷題:二、判斷題:6-10XXVXV（每題26-10XXVXV三、解答題：1、解：加入人工變量，化問(wèn)題為標(biāo)準(zhǔn)型式如下：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下面用單純形表進(jìn)行計(jì)算得終表為：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銷(xiāo)量35463（5分）用位勢(shì)法檢驗(yàn)得：銷(xiāo)地產(chǎn)地甲乙丙丁戊UIQ450IIQ4Q30Q-9III31131V019593所有非基變量的檢驗(yàn)數(shù)都大于零，所以上述即為最優(yōu)解且該問(wèn)題有唯此時(shí)的總運(yùn)費(fèi)：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相應(yīng)的解矩陣：0000100100_10000_0200500443（13分）由解矩陣得最有指派方案：甲一B,乙一D,丙一E,丁一C,戊一A或者甲一B,乙一C,丙一E,丁一D,戊一A （2分）所需總時(shí)間為：Minz=32所需總時(shí)間為：Minz=32（2分）5、解：將問(wèn)題標(biāo)準(zhǔn)后，構(gòu)造輔助為：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為初始基變量，列單純形表計(jì)算如下:5 6cj11.500MMCB基bx1x2x3x4x5x60x5313-10103x62110-101czj-j1-2M1.5-4MMM000x211/31-1/301/30

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