(整理)運(yùn)籌學(xué)復(fù)習(xí)題

1、精品文檔運(yùn)籌學(xué)復(fù)習(xí)題線性規(guī)劃的基本概念一、填空題1 .線性規(guī)劃問題是求一個(gè)線性目標(biāo)函數(shù)在一組線性約束條件下的極值問題。2 .圖解法適用于含有兩個(gè)變量的線性規(guī)劃問題。3 .線性規(guī)劃問題的可行解是指滿足所有約束條件的解。4 .在線性規(guī)劃問題的基本解中，所有的非基變量等于零。 _5 .在線性規(guī)劃問題中，基可行解的非零分量所對(duì)應(yīng)的列向量線性無差6 .若線性規(guī)劃問題有最優(yōu)解，則最優(yōu)解一定可以在可行域的頂點(diǎn)（極點(diǎn)）達(dá)到。7 .線性規(guī)劃問題有可行解，則必有基可行解。8 .如果線性規(guī)劃問題存在目標(biāo)函數(shù)為有限值的最優(yōu)解，求解時(shí)只需在其基可行解的集合中進(jìn)行搜索即可得到最優(yōu)解。9 .滿足非負(fù)條件的基本解稱為基本可行

2、解。10 .在將線性規(guī)劃問題的一般形式轉(zhuǎn)化為標(biāo)準(zhǔn)形式時(shí)，引入的松馳數(shù)量在目標(biāo)函數(shù)中的系數(shù)為莖11 .將線性規(guī)劃模型化成標(biāo)準(zhǔn)形式時(shí)，“w”的約束條件要在不等式左 端加入松弛變量。12 .線性規(guī)劃模型包括決策（可控）變量，約束條件，目標(biāo)函數(shù)三個(gè)要素。13 .線性規(guī)劃問題可分為目標(biāo)函數(shù)求極大值邳極小 值兩類。14 .線性規(guī)劃問題的標(biāo)準(zhǔn)形式中，約束條件取等式，目標(biāo)函數(shù)求極大值，而所有變量必須非負(fù)。二、單選題1 .如果一個(gè)線性規(guī)劃問題有 n個(gè)變量，m個(gè)約束方程（m<n）,系數(shù)矩陣的數(shù)為 m則基可 行解的個(gè)數(shù)最多為_C_。A. m 個(gè)B . n個(gè) C.GmD . Cn 個(gè)2 .下列圖形中陰影部分構(gòu)成

3、的集合是凸集的是ACA)CU)3 .在下列線性規(guī)劃問題的基本解中，屬于基可行解的是_BA. (一 1, 0, O)T B . (1 , 0, 3, 0)T C . (一 4, 0, 0, 3)T D. (0 , 1, 0, 5) T精品文檔7 .關(guān)于線性規(guī)劃模型的可行域，下面_D_的敘述正確。A.可行域內(nèi)必有無窮多個(gè)點(diǎn)B.可行域必有界C.可行域內(nèi)必然包括原點(diǎn)D.可行域必是凸的8 .下列關(guān)于可行解，基本解，基可行解的說法錯(cuò)誤的是_B_.A.可行解中包含基可行解B.可行解與基本解之間無交集C.線性規(guī)劃問題有可行解必有基可行解D .滿足非負(fù)約束條件的基本解為基可行解9 .線性規(guī)劃問題有可行解，則 A

4、A必有基可行解B必有唯一最優(yōu)解C無基可行解D 無唯一最優(yōu)解10 .為化為標(biāo)準(zhǔn)形式而引入的松弛變量在目標(biāo)函數(shù)中的系數(shù)應(yīng)為 A A 0B 1 C 2 D 311 .若線性規(guī)劃問題沒有可行解，可行解集是空集，則此問題 BA沒有無窮多最優(yōu)解B沒有最優(yōu)解C 有無界解 D 無有界解三、多選題1 .在線性規(guī)劃問題的標(biāo)準(zhǔn)形式中，不可能存在的變量是D .A可控變量B.松馳變量c.剩余變量D.人工變量2 .下列選項(xiàng)中符合線性規(guī)劃模型標(biāo)準(zhǔn)形式要求的有BCDA.目標(biāo)函數(shù)求極小值 B.右端常數(shù)非負(fù)C.變量非負(fù)D.約束條件為等式E.約束條件為的不等式3 .某線性規(guī)劃問題，n個(gè)變量，m個(gè)約束方程，系數(shù)矩陣的秩為m(m<

5、;n)則下列說法正確的是 ABDE。A.基可行解的非零分量的個(gè)數(shù)不大于m B .基本解的個(gè)數(shù)不會(huì)超過 Cn個(gè)C.該問題不會(huì)出現(xiàn)退化現(xiàn)象D .基可行解的個(gè)數(shù)不超過基本解的個(gè)數(shù)E.該問題的基是一個(gè) mKm階方陣4 .若線性規(guī)劃問題的可行域是無界的，則該問題可能ABCDA .無有限最優(yōu)解B.有有限最優(yōu)解 C.有唯一最優(yōu)解 D.有無窮多個(gè)最優(yōu)解 E.有有限 多個(gè)最優(yōu)解5 .下列說法錯(cuò)誤的有_ABC_>A.基本解是大于零的解B .極點(diǎn)與基解一一對(duì)應(yīng)C.線性規(guī)劃問題的最優(yōu)解是唯一的D .滿足約束條件的解就是線性規(guī)劃的可行解6 .線性規(guī)劃問題若有最優(yōu)解，則最優(yōu)解ADA定在其可行域頂點(diǎn)達(dá)到B只有一個(gè) C

6、會(huì)有無窮多個(gè) D唯一或無窮多個(gè) E其值為0四、名詞解釋1基：在線性規(guī)劃問題中，約束方程組的系數(shù)矩陣 A的任意一個(gè) mx m階的非奇異子方陣 B , 稱為線性規(guī)劃問題的一個(gè)基。2、線性規(guī)劃問題：就是求一個(gè)線性目標(biāo)函數(shù)在一組線性約束條件下的極值問題。3 .可行解：在線性規(guī)劃問題中，凡滿足所有約束條件的解稱為線性規(guī)劃問題可行解4、可行域：線性規(guī)劃問題的可行解集合。5、基本解：在線性約束方程組中，對(duì)于選定的基B令所有的非基變量等于零，得到的解，稱為線性規(guī)劃問題的一個(gè)基本解。6.、基本可行解：在線性規(guī)劃問題中，滿足非負(fù)約束條件的基本解稱為基本可行解。線性規(guī)劃的基本方法一、填空題1 .對(duì)于目標(biāo)函數(shù)極大值型

7、的線性規(guī)劃問題，用單純型法求解時(shí)，當(dāng)基變量檢驗(yàn)數(shù)為0,非基變量檢驗(yàn)數(shù)8j w 0時(shí)，當(dāng)前解為最優(yōu)解。2 .用大M法求目標(biāo)函數(shù)為極大值的線性規(guī)劃問題時(shí)，引入的人工變量在目標(biāo)函數(shù)中的系數(shù)應(yīng)為一M。3 .在單純形迭代中，可以根據(jù)最終 表中人工變量不為零判斷線性規(guī)劃問題無解。4 .當(dāng)線性規(guī)劃問題的系數(shù)矩陣中不存在現(xiàn)成的可行基時(shí)，一般可以加入人工變量構(gòu)造可行基。5 .在單純形迭代中，選出基變量時(shí)應(yīng)遵循最小比值。法則。6 .在單純形迭代過程中， 若有某個(gè)8 k>0對(duì)應(yīng)的非基變量 xk的系數(shù)列向量Pk W0時(shí),則此 問題是無界的。7 .在大M法中，M表示充分大正數(shù)。二、單選題1 .在單純形迭代中，出基

8、變量在緊接著的下一次迭代中B立即進(jìn)入基。A.會(huì)B .不會(huì) C .有可能 D .不一定2 .在單純形法計(jì)算中，如不按最小比值原則選取換出變量，則在下一個(gè)解中BoA.不影響解的可行性 B.至少有一個(gè)基變量的值為負(fù)C.找不到出基變量 D.找不到進(jìn)基變量3 .用單純形法求解極大化線性規(guī)劃問題中，在最優(yōu)單純形表中若某非基變量檢驗(yàn)數(shù)為零，而其他非基變量檢驗(yàn)數(shù)全部 <0,則說明本問題 B。A.有惟一最優(yōu)解B .有多重最優(yōu)解 C .無界 D .無解4 .下列說法錯(cuò)誤的是 BA.圖解法與單純形法從幾何理解上是一致的B .在單純形迭代中，進(jìn)基變量可以任選C.在單純形迭代中，出基變量必須按最小比值法則選取D

9、.人工變量離開基底后，不會(huì)再進(jìn)基5 .單純形法當(dāng)中，入基變量的確定應(yīng)選擇檢驗(yàn)數(shù)CA絕對(duì)值最大 B絕對(duì)值最小C 正值最大 D負(fù)值最小6 .在線性規(guī)劃問題的典式中，基變量的系數(shù)列向量為D_A 單位陣 B 非單位陣 C單位行向量D 單位列向量7 .在約束方程中引入人工變量的目的是DA體現(xiàn)變量的多樣性 B 變不等式為等式 C 使目標(biāo)函數(shù)為最優(yōu) D 形成一個(gè)單位陣8 .求目標(biāo)函數(shù)為極大的線性規(guī)劃問題時(shí)，若全部非基變量的檢驗(yàn)數(shù)WO,且基變量中有人工變量時(shí)該問題有 BA無界解B無可行解C唯一最優(yōu)解D無窮多最優(yōu)解三、多選題1.對(duì)取值無約束的變量Xj。通常令Xj=Xj'- x " j,其中Xj

10、'> 0,xj”> 0,在用單純形法求得的最優(yōu)解中，可能出現(xiàn)的是 ABCA.ij=i'=l) 8$。工=(1，甲砌阮，由。2 .設(shè)X(1), X(2)是用單純形法求得的某一線性規(guī)劃問題的最優(yōu)解，則說明 ACDE。A.此問題有無窮多最優(yōu)解 B .該問題是退化問題C .此問題的全部最優(yōu)解可表示為入#+(1 入)X(2),其中0W入W1 D .X(1) ,X(2)是兩個(gè)基可行解E.X(1),X(2)的基變量個(gè)數(shù)相同3 .單純形法中，在進(jìn)行換基運(yùn)算時(shí)， 應(yīng)ACDE。A.先選取進(jìn)基變量， 再選取出基變量 B.先 選出基變量，再選進(jìn)基變量 C.進(jìn)基變量的系數(shù)列向量應(yīng)化為單位向量

11、D.旋轉(zhuǎn)變換時(shí)采用的矩陣的初等行變換 E.出基變量的選取是根據(jù)最小比值法則6 .從一張單純形表中可以看出的內(nèi)容有ABCE。A. 一個(gè)基可行解 B.當(dāng)前解是否為最優(yōu)解C.線性規(guī)劃問題是否出現(xiàn)退化 D.線性規(guī)劃問題的最優(yōu)解 E.線性規(guī)劃問題是否無界 四、名詞、簡答1、人造初始可行基：當(dāng)我們無法從一個(gè)標(biāo)準(zhǔn)的線性規(guī)劃問題中找到一個(gè)m階單位矩陣時(shí),通常在約束方程中引入人工變量，而在系數(shù)矩陣中湊成一個(gè)m階單位矩陣，進(jìn)而形成的一個(gè)初始可行基稱為人造初始可行基。2、單純形法解題的基本思路？可行域的一個(gè)基本可行解開始，轉(zhuǎn)移到另一個(gè)基本可行解，并且使目標(biāo)函數(shù)值逐步得到改善，直到最后球場最優(yōu)解或判定原問題無解。線性

12、規(guī)劃的對(duì)偶理論一、填空題1 .線性規(guī)劃問題具有對(duì)偶性，即對(duì)于任何一個(gè)求最大值的線性規(guī)劃問題，都有一個(gè)求最_小彳1 /極小值的線性規(guī)劃問題與之對(duì)應(yīng)，反之亦然。2 .在一對(duì)對(duì)偶問題中，原問題的約束條件的右端常數(shù)是對(duì)偶問題的目標(biāo)函數(shù)系數(shù)。3 .如果原問題的某個(gè)變量無約束，則對(duì)偶問題中對(duì)應(yīng)的約束條件應(yīng)為等式。4 .對(duì)偶問題的對(duì)偶問題是原回題 。5 .若原問題可行，但目標(biāo)函數(shù)無界，則對(duì)偶問題不可彳/6 .線性規(guī)劃問題的最優(yōu)基為 B,基變量的目標(biāo)系數(shù)為 Cb,則其對(duì)偶問題的最優(yōu)解Y* = CbB 1。7 .若X*和Y*分別是線性規(guī)劃的原問題和對(duì)偶問題的最優(yōu)解，則有CX=Y b。8 .若X、Y分別是線性規(guī)劃

13、的原問題和對(duì)偶問題的可行解，則有CX£Ybo9 .若X*和Y*分別是線性規(guī)劃的原問題和對(duì)偶問題的最優(yōu)解，則有CX =Y*卜10 .設(shè)線性規(guī)劃的原問題為maxZ=CX Ax< b, X>0,則其對(duì)偶問題為min=Yb YA AcY>0。二、單選題0,則其對(duì)偶問題約1 .線性規(guī)劃原問題的目標(biāo)函數(shù)為求極小值型，若其某個(gè)變量小于等于束條件為A形式。A.B.C ,“>" D.2 .設(shè)X、Y分別是標(biāo)準(zhǔn)形式的原問題與對(duì)偶問題的可行解，則 CCh C XCy b3 .如果z。是某標(biāo)準(zhǔn)型線性規(guī)劃問題的最優(yōu)目標(biāo)函數(shù)值，則其對(duì)偶問題的最優(yōu)目標(biāo)函數(shù)值w*AoA. W =Z*

14、 B. WwZ* C. Wwz*D. VV>Z *4 .如果某種資源的影子價(jià)格大于其市場價(jià)格，則說明 _ BA.該資源過剩B.該資源稀缺 C.企業(yè)應(yīng)盡快處理該資源 D.企業(yè)應(yīng)充分利用該資源，開僻新的生產(chǎn)途徑三、多選題1.在一對(duì)對(duì)偶問題中，可能存在的情況是ABC。A. 一個(gè)問題有可行解，另一個(gè)問題無可行解.兩個(gè)問題都有可行解C.兩個(gè)問題都無可行解. 一個(gè)問題無界，另一個(gè)問題可行5 .下列說法錯(cuò)誤的是B 。A.任何線性規(guī)劃問題都有一個(gè)與之對(duì)應(yīng)的對(duì)偶問題B.對(duì)偶問題無可行解時(shí)，其原問X>0,則對(duì)偶問題為 minW=Yb YA>C,題的目標(biāo)函數(shù)無界。C.若原問題為 maxZ=CX A

15、X& b,Y> 0。D.若原問題有可行解，但目標(biāo)函數(shù)無界，其對(duì)偶問題無可行解。3.如線性規(guī)劃的原問題為求極大值型，則下列關(guān)于原問題與對(duì)偶問題的關(guān)系中正確的是BCDE。A原問題的約束條件 7 ,對(duì)應(yīng)的對(duì)偶變量0" B原問題的約束條件為“="，對(duì) 應(yīng)的對(duì)偶變量為自由變量 C.原問題的變量0 ”，對(duì)應(yīng)的對(duì)偶約束D.原問題的 變量“& O對(duì)應(yīng)的對(duì)偶約束E.原問題的變量無符號(hào)限制，對(duì)應(yīng)的對(duì)偶約束“=” 4. 一對(duì)互為對(duì)偶的問題存在最優(yōu)解，則在其最優(yōu)點(diǎn)處有BDA.若某個(gè)變量取值為 0,則對(duì)應(yīng)的對(duì)偶約束為嚴(yán)格的不等式B.若某個(gè)變量取值為正，則相應(yīng)的對(duì)偶約束必為等式C

16、.若某個(gè)約束為等式，則相應(yīng)的對(duì)偶變?nèi)≈禐檎鼶.若某個(gè)約束為嚴(yán)格的不等式，則相應(yīng)的對(duì)偶變量取值為0 E.若某個(gè)約束為等式，則相應(yīng)的對(duì)偶變量取值為0 四、名詞、簡答題1 、.對(duì)稱的對(duì)偶問題：設(shè)原始線性規(guī)劃問題為maxZ=CX s.t AX w b X >0稱線性規(guī)劃問題 minW=Yb s.tYA>C Y>0為其對(duì)偶問題。又稱它們?yōu)橐粚?duì)對(duì)稱的對(duì)偶問題。2、影子價(jià)格：對(duì)偶變量 Yi表示與原問題的第i個(gè)約束條件相對(duì)應(yīng)的資源的影子價(jià)格，在數(shù) 量上表現(xiàn)為，當(dāng)該約束條件的右端常數(shù)增加一個(gè)單位時(shí)（假設(shè)原問題的最優(yōu)解不變），原問 題目標(biāo)函數(shù)最優(yōu)值增加的數(shù)量。3、一對(duì)對(duì)偶問題可能出現(xiàn)的情形：1.

17、原問題和對(duì)偶問題都有最優(yōu)解，且二者相等；2.一個(gè)問題具有無界解，則另一個(gè)問題具有無可行解；3.原問題和對(duì)偶問題都無可行解。線性規(guī)劃的靈敏度分析 一、填空題1、在靈敏度分析中，某個(gè)非基變量的目標(biāo)系數(shù)的改變，將引起該非基變量自身的檢驗(yàn)數(shù)的 變化。2 .如果某基變量的目標(biāo)系數(shù)的變化范圍超過其靈敏度分析容許的變化范圍，則此基變量應(yīng) 出基。3 .若某約束常數(shù)bi的變化超過其容許變動(dòng)范圍，為求得新的最優(yōu)解，需在原最優(yōu)單純形表 的基礎(chǔ)上運(yùn)用對(duì)偶單純形法求解。4 .如果線性規(guī)劃的原問題增加一個(gè)約束條件，相當(dāng)于其對(duì)偶問題增加一個(gè)變量。5 .若某線性規(guī)劃問題增加一個(gè)新的約束條件，在其最優(yōu)單純形表中將表現(xiàn)為增加一行

18、，一列。二、單選題1 .若線性規(guī)劃問題最優(yōu)基中某個(gè)基變量的目標(biāo)系數(shù)發(fā)生變化，則 CoA.該基變量的檢驗(yàn)數(shù)發(fā)生變化B.其他基變量的檢驗(yàn)數(shù)發(fā)生變化 C.所有非基變量的檢驗(yàn)數(shù)發(fā)生變化D.所有變量的檢驗(yàn)數(shù)都發(fā)生變化2 .在線性規(guī)劃的各項(xiàng)敏感性分析中，一定會(huì)引起最優(yōu)目標(biāo)函數(shù)值發(fā)生變化的是BoA.目標(biāo)系數(shù)Cj的變化B.約束常數(shù)項(xiàng)bi變化C.增加新的變量 D.增加新約束 三、多選題1.在靈敏度分析中，我們可以直接從最優(yōu)單純形表中獲得的有效信息有ABCE。A.最優(yōu)基B的逆B-1 B .最優(yōu)解與最優(yōu)目標(biāo)函數(shù)值C .各變量的檢驗(yàn)數(shù)D.對(duì)偶問題的解E .各列向量3.線性規(guī)劃問題的各項(xiàng)系數(shù)發(fā)生變化，下列不能引起最優(yōu)解

19、的可行性變化的是ABC 。A.非基變量的目標(biāo)系數(shù)變化 B.基變量的目標(biāo)系數(shù)變化 C.增加新的變量D,增加新的約 束條件 四、名詞、簡答題1 .靈敏度分析：研究線性規(guī)劃模型的原始數(shù)據(jù)變化對(duì)最優(yōu)解產(chǎn)生的影響運(yùn)輸問題一、填空題1 .物資調(diào)運(yùn)問題中，有m個(gè)供應(yīng)地，A ,A,Am,A的供應(yīng)量為a (i=1 ,2，m),nmn個(gè)需求地 B,電Bn,B的需求量為b(j=1 ,2,，n),則供需平衡條件為Z ai =Z biijj 12 .物資調(diào)運(yùn)方案的最優(yōu)性判別準(zhǔn)則是：當(dāng)全部檢驗(yàn)數(shù)非負(fù)時(shí)，前的方案一定是最優(yōu)方案。3 .可以作為表上作業(yè)法的初始調(diào)運(yùn)方案的填有數(shù)字的方格數(shù)應(yīng)為m+n1個(gè)(設(shè)問題中含有m個(gè)供應(yīng)地和

20、n個(gè)需求地)4 .若調(diào)運(yùn)方案中的某一空格的檢驗(yàn)數(shù)為1,則在該空格的閉回路上調(diào)整單位運(yùn)置而使運(yùn)費(fèi)增加1 o5 .調(diào)運(yùn)方案的調(diào)整是要在檢驗(yàn)數(shù)出現(xiàn)負(fù)值的點(diǎn)為頂點(diǎn)所對(duì)應(yīng)的閉回路內(nèi)進(jìn)行運(yùn)量的調(diào)整。6 .按照表上作業(yè)法給出的初始調(diào)運(yùn)方案，從每一空格出發(fā)可以找到且僅能找到_1條閉回路7 .在運(yùn)輸問題中，單位運(yùn)價(jià)為 Cj位勢(shì)分別用Ui, V表示，則在基變量處有 Q Cj=ui+Vj。8、供大于求的、供不應(yīng)求的不平衡運(yùn)輸問題，分別是指mai _> fbi的運(yùn)輸問題、£向_i J jdiw三為i的運(yùn)輸問題。j 1 1從某空格出發(fā)的閉回路的轉(zhuǎn)角點(diǎn)所對(duì)應(yīng)的變量必10 .在表上作業(yè)法所得到的調(diào)運(yùn)方案中,

21、為基變量。11 .在某運(yùn)輸問題的調(diào)運(yùn)方案中，點(diǎn)(2 , 2)的檢驗(yàn)數(shù)為負(fù)值，(調(diào)運(yùn)方案為表所示)則相應(yīng)的調(diào)整量應(yīng)為300 。InmIVA300100300B400C600300則這個(gè)2的含義是該檢驗(yàn)數(shù)近12 .若某運(yùn)輸問題初始方案的檢驗(yàn)數(shù)中只有一個(gè)負(fù)值：2,在格單位調(diào)整量。13 .運(yùn)輸問題的初始方案中的基變量取值為正。14在編制初始方案調(diào)運(yùn)方案及調(diào)整中，如出現(xiàn)退化，則某一個(gè)或多個(gè)點(diǎn)處應(yīng)填入數(shù)字 0二、單選題1、在表上作業(yè)法求解運(yùn)輸問題中，非基變量的檢驗(yàn)數(shù)DoA.大于0 B .小于0 C .等于0 D .以上三種都可能2 .運(yùn)輸問題的初始方案中，沒有分配運(yùn)量的格所對(duì)應(yīng)的變量為BA基變量B非基變量

22、C松弛變量D剩余變量3 .表上作業(yè)法中初始方案均為 AA可行解B非可行解C待改進(jìn)解D最優(yōu)解4 .閉回路是一條封閉折線，每一條邊都是DA 水平 B垂直 C 水平+垂直 D水平或垂直5 .運(yùn)輸問題中分配運(yùn)量的格所對(duì)應(yīng)的變量為AA基變量B 非基變量 C松弛變量D 剩余變量6 .所有物資調(diào)運(yùn)問題，應(yīng)用表上作業(yè)法最后均能找到一個(gè)DA可行解 B非可行解C 待改進(jìn)解 D 最優(yōu)解7 .一般講，在給出的初始調(diào)運(yùn)方案中，最接近最優(yōu)解的是C_A西北角法 B最小元素法C 差值法 D 位勢(shì)法8 .在運(yùn)輸問題中，調(diào)整對(duì)象的確定應(yīng)選擇CA 檢驗(yàn)數(shù)為負(fù) B檢驗(yàn)數(shù)為正 C檢驗(yàn)數(shù)為負(fù)且絕對(duì)值最大D檢驗(yàn)數(shù)為負(fù)且絕對(duì)值最小9 .運(yùn)輸

23、問題中，調(diào)運(yùn)方案的調(diào)整應(yīng)在檢驗(yàn)數(shù)為d負(fù)值的點(diǎn)所在的閉回路內(nèi)進(jìn)行。A任意值 B 最大值 C 絕對(duì)值最大 D絕對(duì)值最小10 .表上作業(yè)法的基本思想和步驟與單純形法類似，因而初始調(diào)運(yùn)方案的給出就相當(dāng)于找到一個(gè)-CA基 B可行解 C初始基本可行解 D最優(yōu)解11平衡運(yùn)輸問題即是指 m個(gè)供應(yīng)地的總供應(yīng)量 D n個(gè)需求地的總需求量。A大于 B大于等于 C 小于 D 等于三、多選題1 .下列說法正確的是 ABD。A.表上作業(yè)法也是從尋找初始基可行解開始的B.當(dāng)一個(gè)調(diào)運(yùn)方案的檢驗(yàn)數(shù)全部為正值時(shí)，當(dāng)前方案一定是最佳方案C.最小元素法所求得的運(yùn)輸?shù)倪\(yùn)量是最小的D.表上作業(yè)法中一張供需平衡表對(duì)應(yīng)一個(gè)基可行解四、名詞1

24、、平衡運(yùn)輸問題：m個(gè)供應(yīng)地的供應(yīng)量等于 n個(gè)需求地的總需求量，這樣的運(yùn)輸問題稱平衡運(yùn)輸問題。2、不平衡運(yùn)輸問題：m個(gè)供應(yīng)地的供應(yīng)量不等于 n個(gè)需求地的總需求量，這樣的運(yùn)輸問題稱不平衡運(yùn)輸問題。整數(shù)規(guī)劃一、填空題1 .用分枝定界法求極大化的整數(shù)規(guī)劃問題時(shí)，任何一個(gè)可行解的目標(biāo)函數(shù)值是該問題目 標(biāo)函數(shù)值的下界。2 .在分枝定界法中，若選 K=4/3進(jìn)行分支，則構(gòu)造白約束條件應(yīng)為X產(chǎn)1, X產(chǎn)2。3 .已知整數(shù)規(guī)劃問題 Po,其相應(yīng)的松馳問題記為 P0，若問題P0無可行解，則問題 P。 無可行解。4 .在0 - 1整數(shù)規(guī)劃中變量的取值可能是 _0或1。5 .對(duì)于一個(gè)有n項(xiàng)任務(wù)需要有n個(gè)人去完成的分配

25、問題，其解中取值為1的變量數(shù)為n個(gè)。6 .分枝定界法和割平面法的基礎(chǔ)都是用線性規(guī)劃方法求解整數(shù)規(guī)劃。7 .若在對(duì)某整數(shù)規(guī)劃問題的松馳問題進(jìn)行求解時(shí)，得到最優(yōu)單純形表中，由X。所在行得X1+1/7x3+2/7x5=13/7,則以X1行為源行的割平面方程為-X3-X5<0 。 7 - 7 - 7 -8 .求解分配問題的專門方法是匈牙利法。9 .在應(yīng)用匈牙利法求解分配問題時(shí)，最終求得的分配元應(yīng)是獨(dú)立零元素。10 .分枝定界法一般每次分枝數(shù)量為2J1.二、單選題1 .整數(shù)規(guī)劃問題中，變量的取值可能是DoA.整數(shù)B. 0或1C.大于零的非整數(shù) D.以上三種都可能2 .在下列整數(shù)規(guī)劃問題中，分枝定界

26、法和割平面法都可以采用的是從。A.純整數(shù)規(guī)劃B.混合整數(shù)規(guī)劃 C. 0-1規(guī)劃D.線性規(guī)劃3 .下列方法中用于求解分配問題的是D_oA.單純形表B.分枝定界法 C.表上彳業(yè)法 D.匈牙利法三、多項(xiàng)選擇1 .下列說明不正確的是 ABC。A.求解整數(shù)規(guī)劃可以采用求解其相應(yīng)的松馳問題，然后對(duì)其非整數(shù)值的解四舍五入的方法得到整數(shù)解。B.用分枝定界法求解一個(gè)極大化的整數(shù)規(guī)劃問題，當(dāng)?shù)玫蕉嘤谝粋€(gè)可行解時(shí)，通常任取其中一個(gè)作為下界。C.用割平面法求解整數(shù)規(guī)劃時(shí)，構(gòu)造的割平面可能割去一些不屬于最優(yōu)解的整數(shù)解。D.用割平面法求解整數(shù)規(guī)劃問題時(shí)，必須首先將原問題的非整數(shù)的約束系數(shù)及右端常數(shù)化為整數(shù)。2 .在求解整

27、數(shù)規(guī)劃問題時(shí)，可能出現(xiàn)的是ABC。A.唯一最優(yōu)解B.無可行解C .多重最佳解D.無窮多個(gè)最優(yōu)解3 .關(guān)于分配問題的下列說法正確的是 _ ABD。A.分配問題是一個(gè)高度退化的運(yùn)輸問題B.可以用表上作業(yè)法求解分配問題C .從分配問題的效益矩陣中逐行取其最小元素，可得到最優(yōu)分配方案D.匈牙利法所能求解的分配問題，要求規(guī)定一個(gè)人只能完成一件工作，同時(shí)一件工作也只給一個(gè)人做。4 .整數(shù)規(guī)劃類型包括（CDE ）A線性規(guī)劃B 非線性規(guī)劃 C 純整數(shù)規(guī)劃 D 混合整數(shù)規(guī)劃 E 0 1規(guī)劃三、名詞1、純整數(shù)規(guī)劃：如果要求所有的決策變量都取整數(shù)，這樣的問題成為純整數(shù)規(guī)劃問題。2、01規(guī)戈IJ問題：在線性規(guī)劃問題中

28、，如果要求所有的決策變量只能取0或1,這樣的問題稱為0 1規(guī)劃。3、混合整數(shù)規(guī)劃：在線性規(guī)劃問題中，如果要求部分決策變量取整數(shù)，則稱該問題為混合整數(shù)規(guī)劃。圖與網(wǎng)絡(luò)分析一、填空題1 .任一樹中的邊數(shù)必定是它的頂點(diǎn)數(shù)減1。2 .最小樹問題就是在網(wǎng)絡(luò)圖中，找出若干條邊，連接所有結(jié)點(diǎn),而且連接的總長度最小。3 . 18、求支撐樹有 破圈 法和 避圈 法兩種方法。二、單選題1、關(guān)于圖論中圖的概念，以下敘述 （旦）正確。A圖中的有向邊表示研究對(duì)象，結(jié)點(diǎn)表示銜接關(guān)系。 B圖中的點(diǎn)表示研究對(duì)象，邊表示點(diǎn)與點(diǎn)之間的關(guān)系。C圖中任意兩點(diǎn)之間必有邊。D圖的邊數(shù)必定等于點(diǎn)數(shù)減 1。2 .關(guān)于樹的概念，以下敘述 （B）

29、正確。A樹中的點(diǎn)數(shù)等于邊數(shù)減1 B 連通無圈的圖必定是樹C 含n個(gè)點(diǎn)的樹是唯一的D任一樹中，去掉一條邊仍為樹。3 . 一個(gè)連通圖中的最小樹 （B）,其權(quán)（A）。A是唯一確定的 B 可能不唯一C可能不存在D 一定有多個(gè)。4 .關(guān)于最大流量問題，以下敘述（D）正確。A一個(gè)容量網(wǎng)絡(luò)的最大流是唯一確定的B達(dá)到最大流的方案是唯一的C當(dāng)用標(biāo)號(hào)法求最大流時(shí)，可能得到不同的最大流方案D當(dāng)最大流方案不唯一時(shí)，得到的最大流量亦可能不相同。5 .圖論中的圖，以下敘述 （C）不正確。A.圖論中點(diǎn)表示研究對(duì)象，邊或有向邊表示研究對(duì)象之間的特定關(guān)系。B.圖論中的圖，用點(diǎn)與點(diǎn)的相互位置，邊的長短曲直來表示研究對(duì)象的相互關(guān)系

30、。C.圖論中的邊表示研究對(duì)象，點(diǎn)表示研究對(duì)象之間的特定關(guān)系。D .圖論中的圖，可以改變點(diǎn)與點(diǎn)的相互位置。只要不改變點(diǎn)與點(diǎn)的連接關(guān)系。6 .關(guān)于最小樹，以下敘述 （旦）正確。A.最小樹是一個(gè)網(wǎng)絡(luò)中連通所有點(diǎn)而邊數(shù)最少的圖B.最小樹是一個(gè)網(wǎng)絡(luò)中連通所有的點(diǎn)，而權(quán)數(shù)最少的圖 C. 一個(gè)網(wǎng)絡(luò)中的最大權(quán)邊必不包含在其最小樹內(nèi)D. 一個(gè)網(wǎng)絡(luò)的最小樹一般是不唯一的。7 .關(guān)于可行流，以下敘述 （A）不正確。A.可行流的流量大于零而小于容量限制條件B.在網(wǎng)絡(luò)的任一中間點(diǎn)，可行流滿足流人量=流出量。C.各條有向邊上的流量均為零的流是一個(gè)可行流D.可行流的流量小于容量限制條件而大于或等于零。三、多選題1 .關(guān)于圖

31、論中圖的概念，以下敘述（123）正確。（1）圖中的邊可以是有向邊， 也可以是無向邊（2）圖中的各條邊上可以標(biāo)注權(quán)。（3）結(jié)點(diǎn) 數(shù)等于邊數(shù)的連通圖必含圈 （4）結(jié)點(diǎn)數(shù)等于邊數(shù)的圖必連通。2 .關(guān)于樹的概念，以下敘述 （123）正確。1）樹中的邊數(shù)等于點(diǎn)數(shù)減 1（2）樹中再添一條邊后必含圈。（3）樹中刪去一條邊后必不連 通（4）樹中兩點(diǎn)之間的通路可能不唯一。3 .從連通圖中生成樹，以下敘述 （134）正確。（1）任一連通圖必有支撐樹（2）任一連通圖生成的支撐樹必唯一（3）在支撐樹中再增加一條邊后必含圈（4）任一連通圖生成的各個(gè)支撐樹其邊數(shù)必相同4 .在下圖中，（abcd）不是卞據(jù)（a）生成的支撐樹

32、。畬Q勿力白m（b）（c） M5 .從賦權(quán)連通圖中生成最小樹，以下敘述（124）不正確。（1）任一連通圖生成的各個(gè)最小樹，其總長度必相等（2）任一連通圖生成的各個(gè)最小樹，其邊數(shù)必相等。（3）任一連通圖中具有最小權(quán)的邊必包含在生成的最小樹上。（4）最小樹中可能包括連通圖中的最大權(quán)邊。6 .從起點(diǎn)到終點(diǎn)的最短路線，以下敘述（123）不正確。1）從起點(diǎn)出發(fā)的最小權(quán)有向邊必含在最短路線中。（2）整個(gè)圖中權(quán)最小的有向邊必包含在最短路線中。（3）整個(gè)圖中權(quán)最大的有向邊可能含在最短路線中（4）從起點(diǎn)到終點(diǎn)的最短路線是唯一的。7 .關(guān)于帶收發(fā)點(diǎn)的容量網(wǎng)絡(luò)中從發(fā)點(diǎn)到收點(diǎn)的一條增廣路，以下敘述（123）不正確。（

33、1）增廣路上的有向邊的方向必須是從發(fā)點(diǎn)指向收點(diǎn)的（2）增廣路上的有向邊，必須都是不飽和邊（3）增廣路上不能有零流邊（4）增廣路上與發(fā)點(diǎn)到收點(diǎn)方向一致的有向邊不能是 飽和邊，相反方向的有向邊不能是零流邊8 .關(guān)于樹，以下敘述（ABCE）正確。A.樹是連通、無圈的圖 B.任一樹，添加一條邊便含圈C.任一樹的邊數(shù)等于點(diǎn)數(shù)減1。D.任一樹的點(diǎn)數(shù)等于邊數(shù)減1E.任一樹，去掉 條邊便不連通。9 .關(guān)于最短路，以下敘述 （ACDE）不正確。A從起點(diǎn)出發(fā)到終點(diǎn)的最短路是唯一的。B.從起點(diǎn)出發(fā)到終點(diǎn)的最短路不一定是唯一的，但其最短路線的長度是確定的。C.從起點(diǎn)出發(fā)的有向邊中的最小權(quán)邊，一定包含在起點(diǎn)到終點(diǎn)的最短

34、路上 D.從起點(diǎn)出發(fā)的有向邊中的最大權(quán)邊，一定不包含在起點(diǎn)到終點(diǎn)的最 短路上。E .整個(gè)網(wǎng)絡(luò)的最大權(quán)邊的一定不包含在從起點(diǎn)到終點(diǎn)的最短路線上。10 .關(guān)于增廣路，以下敘述 （BC ）正確。A.增廣路是一條從發(fā)點(diǎn)到收點(diǎn)的有向路，這條路上各條邊的方向必一致。B.增廣路是一條從發(fā)點(diǎn)到收點(diǎn)的有向路，這條路上各條邊的方向可不一致。C.增廣路上與發(fā)點(diǎn)到收點(diǎn)方向一致的邊必須是非飽和邊，方向相反的邊必須是流量大于零的邊。D.增廣路上與發(fā)點(diǎn)到收點(diǎn)方向一致的邊必須是流量小于容量的邊，方向相反的邊必須是流量等于零的邊。E.增廣路上與發(fā)點(diǎn)到收點(diǎn)方向一致的邊必須是流量為零的邊，方向相反的邊必須是流量大于零的邊。 四、名詞解釋1、樹：在圖論中，具有連通和不含圈特點(diǎn)的圖稱為樹。2 .權(quán)：在圖中，邊旁標(biāo)注的數(shù)字稱為權(quán)。3 .網(wǎng)絡(luò)：在圖論中，給邊或有向邊賦了權(quán)的圖稱為網(wǎng)絡(luò)4 .最大流問題：最大流問題是指在網(wǎng)絡(luò)圖