運籌學(xué)復(fù)習(xí)題

精選文檔運籌學(xué)復(fù)習(xí)題線性規(guī)劃的基本見解一、填空題1．線性規(guī)劃問題是求一個線性目標(biāo)函數(shù)_在一組線性拘束條件下的極值問題。2．圖解法合用于含有兩個變量的線性規(guī)劃問題。3．線性規(guī)劃問題的可行解是指知足所有拘束條件的解。4．在線性規(guī)劃問題的基本解中，所有的非基變量等于零。5．在線性規(guī)劃問題中，基可行解的非零重量所對應(yīng)的列向量線性沒關(guān)6．若線性規(guī)劃問題有最優(yōu)解，則最優(yōu)解必然可以在可行域的極點（極點）達到。7．線性規(guī)劃問題有可行解，則必有基可行解。8．假如線性規(guī)劃問題存在目標(biāo)函數(shù)為有限值的最優(yōu)解，求解時只需在其基可行解_的會合中進行找尋即可獲取最優(yōu)解。9．知足非負條件的基本解稱為基本可行解。10．在將線性規(guī)劃問題的一般形式轉(zhuǎn)變?yōu)闃?biāo)準(zhǔn)形式時，引入的松馳數(shù)目在目標(biāo)函數(shù)中的系數(shù)為零。11．將線性規(guī)劃模型化成標(biāo)準(zhǔn)形式時，“≤”的拘束條件要在不等式左_端加入廢弛變量。12．線性規(guī)劃模型包含決議（可控）變量，拘束條件，目標(biāo)函數(shù)三個因素。13．線性規(guī)劃問題可分為目標(biāo)函數(shù)求極大值和極小_值兩類。14．線性規(guī)劃問題的標(biāo)準(zhǔn)形式中，拘束條件取等式，目標(biāo)函數(shù)求極大值，而所有變量必然非負。二、單項選擇題1．假如一個線性規(guī)劃問題有n個變量，m個拘束方程(m<n)，系數(shù)矩陣的數(shù)為m，則基可行解的個數(shù)最多為_C_。A．m個B．n個mn個C．CD．Cnm2．以以下圖形中暗影部分組成的會合是凸集的是A3．在以下線性規(guī)劃問題的基本解中，屬于基可行解的是BA．(一1，0，O)TB．(1，0，3，0)TC．(一4，0，0，3)TD．(0，一1，0，5)T7．對于線性規(guī)劃模型的可行域，下邊_D_的表達正確。A．可行域內(nèi)必有無量多個點B．可行域必有界C．可行域內(nèi)必然包含原點D．可行域.精選文檔必是凸的8．以下對于可行解，基本解，基可行解的說法錯誤的選項是_B__.A．可行解中包含基可行解B．可行解與基本解之間無交集C．線性規(guī)劃問題有可行解必有基可行解D．知足非失拘束條件的基本解為基可行解9.線性規(guī)劃問題有可行解，則AA必有基可行解B必有唯一最優(yōu)解C無基可行解D無唯一最優(yōu)解10.為化為標(biāo)準(zhǔn)形式而引入的廢弛變量在目標(biāo)函數(shù)中的系數(shù)應(yīng)為AA0B1C2D311.若線性規(guī)劃問題沒有可行解，可行解集是空集，則此問題BA沒有無量多最優(yōu)解B沒有最優(yōu)解C有無界解D無有界解三、多項選擇題1．在線性規(guī)劃問題的標(biāo)準(zhǔn)形式中，不可以能存在的變量是D.A．可控變量B．松馳變量c．節(jié)余變量D．人工變量2．以下選項中符合線性規(guī)劃模型標(biāo)準(zhǔn)形式要求的有BCDA．目標(biāo)函數(shù)求極小值B．右端常數(shù)非負C．變量非負D．拘束條件為等式E．拘束條件為“≤”的不等式3．某線性規(guī)劃問題，n個變量，m個拘束方程，系數(shù)矩陣的秩為m(m<n)則以下說法正確的是ABDE。A．基可行解的非零重量的個數(shù)不大于mB．基本解的個數(shù)不會超出mCn個C．該問題不會出現(xiàn)退化現(xiàn)象D．基可行解的個數(shù)不超出基本解的個數(shù)E．該問題的基是一個m×m階方陣4．若線性規(guī)劃問題的可行域是無界的，則該問題可能ABCDA．無有限最優(yōu)解B．有有限最優(yōu)解C．有唯一最優(yōu)解D．有無量多個最優(yōu)解E．有有限多個最優(yōu)解5．以下說法錯誤的有_ABC_。A．基本解是大于零的解B．極點與基解一一對應(yīng)C．線性規(guī)劃問題的最優(yōu)解是唯一的D．知足拘束條件的解就是線性規(guī)劃的可行解6.線性規(guī)劃問題如有最優(yōu)解，則最優(yōu)解ADA定在其可行域極點達到B只有一個C會有無量多個D唯一或無量多個E.精選文檔其值為0四、名詞解說1基：在線性規(guī)劃問題中，拘束方程組的系數(shù)矩陣A的隨意一個m×m階的非奇怪子方陣B，稱為線性規(guī)劃問題的一個基。2、線性規(guī)劃問題：就是求一個線性目標(biāo)函數(shù)在一組線性拘束條件下的極值問題。.可行解：在線性規(guī)劃問題中，凡知足所有拘束條件的解稱為線性規(guī)劃問題可行解4、可行域：線性規(guī)劃問題的可行解會合。5、基本解：在線性拘束方程組中，對于選定的基B令所有的非基變量等于零，獲取的解，稱為線性規(guī)劃問題的一個基本解。6.、基本可行解：在線性規(guī)劃問題中，知足非失拘束條件的基本解稱為基本可行解。線性規(guī)劃的基本方法一、填空題1．對于目標(biāo)函數(shù)極大值型的線性規(guī)劃問題，用純真型法求解時，當(dāng)基變量查驗數(shù)為0,非基變量查驗數(shù)δj_≤_0時，目前解為最優(yōu)解。2．用大M法求目標(biāo)函數(shù)為極大值的線性規(guī)劃問題時，引入的人工變量在目標(biāo)函數(shù)中的系數(shù)應(yīng)為－M。3．在純真形迭代中，可以依據(jù)最后_表中人工變量不為零判斷線性規(guī)劃問題無解。4．當(dāng)線性規(guī)劃問題的系數(shù)矩陣中不存在現(xiàn)成的可行基時，一般可以加入人工變量結(jié)構(gòu)可行基。5．在純真形迭代中，選出基變量時應(yīng)依據(jù)最小比值θ法例。6．在純真形迭代過程中，如有某個δk>0對應(yīng)的非基變量xk的系數(shù)列向量Pk_≤0_時，則此問題是無界的。7.在大M法中，M表示充分大正數(shù)。二、單項選擇題1．在純真形迭代中，出基變量在緊接著的下一次迭代中B立刻進入基。A．會B．不會C．有可能D．不用然2．在純真形法計算中，如不按最小比值原則采納換出變量，則在下一個解中B。A．不影響解的可行性B．最罕有一個基變量的值為負C．找不到出基變量D．找不到進基變量3．用純真形法求解極大化線性規(guī)劃問題中，在最優(yōu)純真形表中若某非基變量查驗數(shù)為零，.精選文檔而其余非基變量查驗數(shù)所有<0，則說明本問題B。A．有唯一最優(yōu)解B．有多重最優(yōu)解C．無界D．無解4．以下說法錯誤的選項是BA．圖解法與純真形法從幾何理解上是一致的B．在純真形迭代中，進基變量可以任選C．在純真形迭代中，出基變量必然按最小比值法例采納D．人工變量走開基底后，不會再進基5.純真形法中間，入基變量確實定應(yīng)選擇查驗數(shù)CA絕對值最大B絕對值最小C正當(dāng)最大D負值最小6.在線性規(guī)劃問題的典式中，基變量的系數(shù)列向量為DA單位陣B非單位陣C單位行向量D單位列向量7.在拘束方程中引入人工變量的目的是DA表現(xiàn)變量的多樣性B變不等式為等式C使目標(biāo)函數(shù)為最優(yōu)D形成一個單位陣8.求目標(biāo)函數(shù)為極大的線性規(guī)劃問題時，若所有非基變量的查驗數(shù)≤O，且基變量中有人工變量時該問題有BA無界解B無可行解C唯一最優(yōu)解D無量多最優(yōu)解三、多項選擇題1．對取值無拘束的變量xj。平季節(jié)xj=xj’-x”j，此中xj’≥0，xj”≥0，在用純真形法求得的最優(yōu)解中，可能出現(xiàn)的是ABC2．設(shè)X(1)，X(2)是用純真形法求得的某一線性規(guī)劃問題的最優(yōu)解，則說明ACDE。A．此問題有無量多最優(yōu)解B．該問題是退化問題C．此問題的所有最優(yōu)解可表示為λX(1)+(1一λ)X(2)，此中0≤λ≤1D．X(1)，X(2)是兩個基可行解E．X(1)，X(2)的基變量個數(shù)同樣3．純真形法中，在進行換基運算時，應(yīng)ACDE。A．先采納進基變量，再采納出基變量B．先選出基變量，再選進基變量C．進基變量的系數(shù)列向量應(yīng)化為單位向量D．旋轉(zhuǎn)變換時采納的矩陣的初等行變換E．出基變量的采納是依據(jù)最小比值法例6．從一張純真形表中可以看出的內(nèi)容有ABCE。A．一個基可行解B．目前解能否為最優(yōu)解C．線性規(guī)劃問題能否出現(xiàn)退化D．線性規(guī)劃問題的最優(yōu)解E．線性規(guī)劃問題能否無界四、名詞、簡答1、人造初始可行基：當(dāng)我們沒法從一個標(biāo)準(zhǔn)的線性規(guī)劃問題中找到一個m階單位矩陣時，平常在拘束方程中引入人工變量，而在系數(shù)矩陣中湊成一個m階單位矩陣，從而形成的一.精選文檔個初始可行基稱為人造初始可行基。2、純真形法解題的基本思路？可行域的一個基本可行解開始，轉(zhuǎn)移到另一個基本可行解，并且使目標(biāo)函數(shù)值逐漸獲取改良，直到最后球場最優(yōu)解或判斷原問題無解。線性規(guī)劃的對偶理論一、填空題．線性規(guī)劃問題擁有對偶性，即對于任何一個求最大值的線性規(guī)劃問題，都有一個求最小值/極小值的線性規(guī)劃問題與之對應(yīng)，反之亦然。2．在一對對偶問題中，原問題的拘束條件的右端常數(shù)是對偶問題的目標(biāo)函數(shù)系數(shù)。3．假如原問題的某個變量無拘束，則對偶問題中對應(yīng)的拘束條件應(yīng)為等式_。4．對偶問題的對偶問題是原問題_。5．若原問題可行，但目標(biāo)函數(shù)無界，則對偶問題不可以行。6．線性規(guī)劃問題的最優(yōu)基為B，基變量的目標(biāo)系數(shù)為CB，則其對偶問題的最優(yōu)解Y﹡=CBB－1。7．若X﹡和Y﹡分別是線性規(guī)劃的原問題和對偶問題的最優(yōu)解，則有8．若X、Y分別是線性規(guī)劃的原問題和對偶問題的可行解，則有9．若X﹡和Y﹡分別是線性規(guī)劃的原問題和對偶問題的最優(yōu)解，則有

﹡﹡CX=Yb。CX≤Yb。﹡CX=Y*b。10．設(shè)線性規(guī)劃的原問題為maxZ=CX，Ax≤b，X≥0，則其對偶問題為min=YbYA≥c≥0_。二、單項選擇題1．線性規(guī)劃原問題的目標(biāo)函數(shù)為求極小值型，若其某個變量小于等于0，則其對偶問題約束條件為A形式。A．“≥”B．“≤”C，“>”D．“=”2．設(shè)X、Y分別是標(biāo)準(zhǔn)形式的原問題與對偶問題的可行解,則C。3．假如z。是某標(biāo)準(zhǔn)型線性規(guī)劃問題的最優(yōu)目標(biāo)函數(shù)值，則其對偶問題的最優(yōu)目標(biāo)函數(shù)值w﹡A。﹡﹡﹡﹡﹡﹡﹡﹡A．W=ZB．W≠ZC．W≤ZD．W≥Z4．假如某種資源的影子價錢大于其市場價錢，則說明_BA．該資源節(jié)余B．該資源稀缺C．公司應(yīng)趕快辦理該資源D．公司應(yīng)充分利用該資源，開僻新的生產(chǎn)門路三、多項選擇題.精選文檔1．在一對對偶問題中，可能存在的情況是ABC。A．一個問題有可行解，另一個問題無可行解B．兩個問題都有可行解C．兩個問題都無可行解D．一個問題無界，另一個問題可行2．以下說法錯誤的選項是B。A．任何線性規(guī)劃問題都有一個與之對應(yīng)的對偶問題B．對偶問題無可行解時，其原問題的目標(biāo)函數(shù)無界。C．若原問題為maxZ=CX，AX≤b，X≥0，則對偶問題為minW=Yb，YA≥C，Y≥0。D．若原問題有可行解，但目標(biāo)函數(shù)無界，其對偶問題無可行解。3．如線性規(guī)劃的原問題為求極大值型，則以下對于原問題與對偶問題的關(guān)系中正確的選項是BCDE。A原問題的拘束條件“≥”，對應(yīng)的對偶變量“≥0”B原問題的拘束條件為“=”，對應(yīng)的對偶變量為自由變量C．原問題的變量“≥0”，對應(yīng)的對偶拘束“≥”D．原問題的變量“≤O”對應(yīng)的對偶拘束“≤”E．原問題的變量無符號限制，對應(yīng)的對偶拘束“=”4．一對互為對偶的問題存在最優(yōu)解，則在其最長處處有BDA．若某個變量取值為0，則對應(yīng)的對偶拘束為嚴格的不等式B．若某個變量取值為正，則相應(yīng)的對偶拘束必為等式C．若某個拘束為等式，則相應(yīng)的對偶變?nèi)≈禐檎鼶．若某個約束為嚴格的不等式，則相應(yīng)的對偶變量取值為0E．若某個拘束為等式，則相應(yīng)的對偶變量取值為0四、名詞、簡答題1、.對稱的對偶問題：設(shè)原始線性規(guī)劃問題為maxZ=CXs.tAX≤bX≥0稱線性規(guī)劃問題minW=Ybs.tYA≥CY≥0為其對偶問題。又稱它們?yōu)橐粚ΨQ的對偶問題。2、影子價錢：對偶變量Yi表示與原問題的第i個拘束條件相對應(yīng)的資源的影子價錢，在數(shù)量上表現(xiàn)為，當(dāng)該拘束條件的右端常數(shù)增添一個單位時（假定原問題的最優(yōu)解不變），原問題目標(biāo)函數(shù)最優(yōu)值增添的數(shù)目。3、一對對偶問題可能出現(xiàn)的情況：1.原問題和對偶問題都有最優(yōu)解，且兩者相等；2.一個問題擁有無界解，則另一個問題擁有無可行解；3.原問題和對偶問題都無可行解。線性規(guī)劃的敏捷度分析一、填空題1、在敏捷度分析中，某個非基變量的目標(biāo)系數(shù)的改變，將惹起該非基變量自己的查驗數(shù)的變化。.精選文檔2．假如某基變量的目標(biāo)系數(shù)的變化范圍超出其敏捷度分析贊同的變化范圍，則此基變量應(yīng)出基。3．若某拘束常數(shù)bi的變化超出其贊同改動范圍，為求得新的最優(yōu)解，需在原最優(yōu)純真形表的基礎(chǔ)上運用對偶純真形法求解。假如線性規(guī)劃的原問題增添一個拘束條件，相當(dāng)于其對偶問題增添一個變量。若某線性規(guī)劃問題增添一個新的拘束條件，在其最優(yōu)純真形表中將表現(xiàn)為增添一行，一列。二、單項選擇題1．若線性規(guī)劃問題最優(yōu)基中某個基變量的目標(biāo)系數(shù)發(fā)生變化，則C。A．該基變量的查驗數(shù)發(fā)生變化B．其余基變量的查驗數(shù)發(fā)生變化C．所有非基變量的檢驗數(shù)發(fā)生變化D．所有變量的查驗數(shù)都發(fā)生變化2．在線性規(guī)劃的各項敏感性分析中，必然會惹起最優(yōu)目標(biāo)函數(shù)值發(fā)生變化的是B。A．目標(biāo)系數(shù)cj的變化B．拘束常數(shù)項bi變化C．增添新的變量D．增添新拘束三、多項選擇題1．在敏捷度分析中，我們可以直接從最優(yōu)純真形表中獲取的有效信息有ABCE。A．最優(yōu)基B的逆B-1B．最優(yōu)解與最優(yōu)目標(biāo)函數(shù)值C．各變量的查驗數(shù)D．對偶問題的解E．各列向量3．線性規(guī)劃問題的各項系數(shù)發(fā)生變化，以下不可以惹起最優(yōu)解的可行性變化的是ABC_。A．非基變量的目標(biāo)系數(shù)變化B．基變量的目標(biāo)系數(shù)變化C．增添新的變量D，增添新的約束條件四、名詞、簡答題1.敏捷度分析：研究線性規(guī)劃模型的原始數(shù)據(jù)變化對最優(yōu)解產(chǎn)生的影響運輸問題一、填空題1．物質(zhì)調(diào)運問題中，有m個供給地，A，A，A，A的供給量為a(i=1，2，m)，nl2mjimn個需求地B1，B2，Bn，B的需求量為bj(j=1，2，，n)，則供需均衡條件為ai=bii1j12．物質(zhì)調(diào)運方案的最優(yōu)性鑒別準(zhǔn)則是：當(dāng)所有查驗數(shù)非負時，目前的方案必然是最優(yōu)方案。3．可以作為表上作業(yè)法的初始調(diào)運方案的填有數(shù)字的方格數(shù)應(yīng)為m+n－1個(設(shè)問題中含有m個供給地和n個需求地).精選文檔4．若調(diào)運方案中的某一空格的查驗數(shù)為1，則在該空格的閉回路上浮整單位運置而使運費增添1。5．調(diào)運方案的調(diào)整是要在查驗數(shù)出現(xiàn)負值的點為極點所對應(yīng)的閉回路內(nèi)進行運量的調(diào)整。6．依據(jù)表上作業(yè)法給出的初始調(diào)運方案，從每一空格出發(fā)可以找到且僅能找到_1條閉回路7．在運輸問題中，單位運價為C位勢分別用u，V表示，則在基變量處有cCij=ui+Vj。ijijij8、供大于求的、求過于供的不均衡運輸問題，分別是指ma_＞n的運輸問題、mbia_ijii11i1＜nbi的運輸問題。j110．在表上作業(yè)法所獲取的調(diào)運方案中，從某空格出發(fā)的閉回路的轉(zhuǎn)角點所對應(yīng)的變量必為基變量。11．在某運輸問題的調(diào)運方案中，點(2，2)的查驗數(shù)為負值，(調(diào)運方案為表所示)則相應(yīng)的調(diào)整量應(yīng)為300_。IⅡⅢⅣA300100300B400C60030012.若某運輸問題初始方案的查驗數(shù)中只有一個負值：－2，則這個－2的含義是該查驗數(shù)所在格單位調(diào)整量。13.運輸問題的初始方案中的基變量取值為正。14在編制初始方案調(diào)運方案及調(diào)整中，如出現(xiàn)退化，則某一個或多個點處應(yīng)填入數(shù)字0二、單項選擇題1、在表上作業(yè)法求解運輸問題中，非基變量的查驗數(shù)D。A．大于0B．小于0C．等于0D．以上三種都可能2.運輸問題的初始方案中，沒有分派運量的格所對應(yīng)的變量為BA基變量B非基變量C廢弛變量D節(jié)余變量3.表上作業(yè)法中初始方案均為AA可行解B非可行解C待改良解D最優(yōu)解4.閉回路是一條關(guān)閉折線，每一條邊都是DA水平B垂直C水平＋垂直D水平或垂直5.運輸問題中分派運量的格所對應(yīng)的變量為A.精選文檔A基變量B非基變量C廢弛變量D節(jié)余變量6.所有物質(zhì)調(diào)運問題，應(yīng)用表上作業(yè)法最后均能找到一個DA可行解B非可行解C待改良解D最優(yōu)解7.一般講，在給出的初始調(diào)運方案中，最湊近最優(yōu)解的是CA西北角法B最小元素法C差值法D位勢法8.在運輸問題中，調(diào)整對象確實定應(yīng)選擇CA查驗數(shù)為負B查驗數(shù)為正C查驗數(shù)為負且絕對值最大D查驗數(shù)為負且絕對值最小9.運輸問題中，調(diào)運方案的調(diào)整應(yīng)在查驗數(shù)為C負值的點所在的閉回路內(nèi)進行。A隨意值B最大值C絕對值最大D絕對值最小10.表上作業(yè)法的基本思想和步驟與純真形法近似，因此初始調(diào)運方案的給出就相當(dāng)于找到一個CA基B可行解C初始基本可行解D最優(yōu)解11均衡運輸問題即是指m個供給地的總供給量Dn個需求地的總需求量。A大于B大于等于C小于D等于三、多項選擇題1．以下說法正確的選項是ABD。A．表上作業(yè)法也是從找尋初始基可行解開始的B．當(dāng)一個調(diào)運方案的查驗數(shù)所有為正值時，目前面案必然是最正確方案C．最小元素法所求得的運輸?shù)倪\量是最小的D．表上作業(yè)法中一張供需均衡表對應(yīng)一個基可行解四、名詞1、均衡運輸問題：m個供給地的供給量等于n個需求地的總需求量，這樣的運輸問題稱均衡運輸問題。2、不均衡運輸問題：m個供給地的供給量不等于n個需求地的總需求量，這樣的運輸問題稱不均衡運輸問題。整數(shù)規(guī)劃一、填空題1．用分枝定界法求極大化的整數(shù)規(guī)劃問題時，任何一個可行解的目標(biāo)函數(shù)值是該問題目標(biāo)函數(shù)值的下界。2．在分枝定界法中，若選X=4／3進行分支，則結(jié)構(gòu)的拘束條件應(yīng)為X1≤1，X1≥2。r3．已知整數(shù)規(guī)劃問題P0，其相應(yīng)的松馳問題記為P0’，若問題P0’無可行解，則問題P。.精選文檔無可行解。4．在0-1整數(shù)規(guī)劃中變量的取值可能是_0或1。5．對于一個有n項任務(wù)需要有n個人去達成的分派問題，其解中取值為1的變量數(shù)為n個。6．分枝定界法和割平面法的基礎(chǔ)都是用_線性規(guī)劃方法求解整數(shù)規(guī)劃。7．若在對某整數(shù)規(guī)劃問題的松馳問題進行求解時，獲取最優(yōu)純真形表中，由X。所專家得X+1／7x+2／7x=13／7，則以X行為源行的割平面方程為6－12_35≤0_。1351求解分派問題的專門方法是匈牙利法。9．在應(yīng)用匈牙利法求解分派問題時，最后求得的分派元應(yīng)是獨立零元素_。10.分枝定界法一般每次分枝數(shù)目為2個.二、單項選擇題1．整數(shù)規(guī)劃問題中，變量的取值可能是D。A．整數(shù)B．0或1C．大于零的非整數(shù)D．以上三種都可能2．在以下整數(shù)規(guī)劃問題中，分枝定界法和割平面法都可以采納的是A。A．純整數(shù)規(guī)劃B．混淆整數(shù)規(guī)劃C．0—1規(guī)劃D．線性規(guī)劃3．以下方法頂用于求解分派問題的是D_。A．純真形表B．分枝定界法C．表上作業(yè)法D．匈牙利法三、多項選擇1．以下說明不正確的選項是ABC。A．求解整數(shù)規(guī)劃可以采納求解其相應(yīng)的松馳問題，此后對其非整數(shù)值的解四舍五入的方法獲取整數(shù)解。B．用分枝定界法求解一個極大化的整數(shù)規(guī)劃問題，當(dāng)獲取多于一個可行解時，平常任取此中一個作為下界。C．用割平面法求解整數(shù)規(guī)劃時，結(jié)構(gòu)的割平面可能割去一些不屬于最優(yōu)解的整數(shù)解。D．用割平面法求解整數(shù)規(guī)劃問題時，必然第一將原問題的非整數(shù)的拘束系數(shù)及右端常數(shù)化為整數(shù)。2．在求解整數(shù)規(guī)劃問題時，可能出現(xiàn)的是ABC。A．唯一最優(yōu)解B．無可行解C．多重最正確解D．無量多個最優(yōu)解3．對于分派問題的以下說法正確的選項是_ABD。A．分派問題是一個高度退化的運輸問題B．可以用表上作業(yè)法求解分派問題C．從分派問題的效益矩陣中逐行取其最小元素，可獲取最優(yōu)分派方案D．匈牙利法所能求解的分.精選文檔配問題，要求規(guī)定一個人只好達成一件工作，同時一件工作也只給一個人做。4.整數(shù)規(guī)劃種類包含（CDE）A線性規(guī)劃B非線性規(guī)劃C純整數(shù)規(guī)劃D混淆整數(shù)規(guī)劃E0—1規(guī)劃三、名詞1、純整數(shù)規(guī)劃：假如要求所有的決議變量都取整數(shù)，這樣的問題成為純整數(shù)規(guī)劃問題。2、0—1規(guī)劃問題：在線性規(guī)劃問題中，假如要求所有的決議變量只好取0或1，這樣的問題稱為0—1規(guī)劃。3、混淆整數(shù)規(guī)劃：在線性規(guī)劃問題中，假如要求部分決議變量取整數(shù)，則稱該問題為混淆整數(shù)規(guī)劃。圖與網(wǎng)絡(luò)分析一、填空題1．任一樹中的邊數(shù)必然是它的極點數(shù)減1。2．最小樹問題就是在網(wǎng)絡(luò)圖中，找出若干條邊，連接所有結(jié)點，并且連接的總長度最小。3．18、求支撐樹有破圈法和避圈法兩種方法。二、單項選擇題1、對于圖論中圖的見解，以下表達(B)正確。A圖中的有向邊表示研究對象，結(jié)點表示連接關(guān)系。B圖中的點表示研究對象，邊表示點與點之間的關(guān)系。C圖中隨意兩點之間必有邊。D圖的邊數(shù)必然等于點數(shù)減1。2．對于樹的見解，以下表達(B)正確。A樹中的點數(shù)等于邊數(shù)減1B連通無圈的圖必然是樹C含n個點的樹是唯一的D任一樹中，去掉一條邊仍為樹。3．一個連通圖中的最小樹(B)，其權(quán)(A)。A是唯一確立的B可能不唯一C可能不存在D必然有多個。4．對于最大流量問題，以下表達(D)正確。A一個容量網(wǎng)絡(luò)的最大流是唯一確立的B達到最大流的方案是唯一的C當(dāng)用標(biāo)號法求最大流時，可能獲取不同樣的最大流方案D當(dāng)最大流方案不唯一時，獲取的最大流量亦可能不同樣。5．圖論中的圖，以下表達(C)不正確。A．圖論中點表示研究對象，邊或有向邊表示研究對象之間的特定關(guān)系。B．圖論中的圖，用點與點的互相地點，邊的長短曲直來表示研究對象的互相關(guān)系。C．圖論中的邊表示研究對象，點表示研究對象之間的特定關(guān)系。D．圖論中的圖，可以改變點與點的互相地點。.精選文檔只需不改變點與點的連接關(guān)系。6．對于最小樹，以下表達(B)正確。A．最小樹是一個網(wǎng)絡(luò)中連通所有點而邊數(shù)最少的圖B．最小樹是一個網(wǎng)絡(luò)中連通所有的點，而權(quán)數(shù)最少的圖C．一個網(wǎng)絡(luò)中的最大權(quán)邊必不包含在其最小樹內(nèi)D．一個網(wǎng)絡(luò)的最小樹一般是不唯一的。7．對于可行流，以下表達(A)不正確。A．可行流的流量大于零而小于容量限制條件B．在網(wǎng)絡(luò)的任一中間點，可行流知足流人量=流出量。C．各條有向邊上的流量均為零的流是一個可行流D．可行流的流量小于容量限制條件而大于或等于零。三、多項選擇題1．對于圖論中圖的見解，以下表達(123)正確。(1)圖中的邊可以是有向邊，也可以是無向邊(2)圖中的各條邊上可以注明權(quán)。(3)結(jié)點數(shù)等于邊數(shù)的連通圖必含圈(4)結(jié)點數(shù)等于邊數(shù)的圖必連通。2．對于樹的見解，以下表達(123)正確。樹中的邊數(shù)等于點數(shù)減1(2)樹中再添一條邊后必含圈。(3)樹中刪去一條邊后必不連通(4)樹中兩點之間的通路可能不唯一。3．從連通圖中生成樹，以下表達(134)正確。(1)任一連通圖必有支撐樹(2)任一連通圖生成的支撐樹必唯一(3)在支撐樹中再增添一條邊后必含圈(4)任一連通圖生成的各個支撐樹其邊數(shù)必同樣4．在以以下圖中，(abcd)不是依據(jù)(a)生成的支撐樹。5．從賦權(quán)連通圖中生成最小樹，以下表達(124)不正確。(1)任一連通圖生成的各個最小樹，其總長度必相等(2)任一連通圖生成的各個最小樹，其邊數(shù)必相等。(3)任一連通圖中擁有最小權(quán)的邊必包含在生成的最小樹上。(4)最小樹中可能包含連通圖中的最大權(quán)邊。6．從起點到終點的最短路線，以下表達(123)不正確。1)從起點出發(fā)的最小權(quán)有向邊必含在最短路線中。(2)整個圖中權(quán)最小的有向邊必包含在最短路線中。(3)整個圖中權(quán)最大的有向邊可能含在最短路線中(4)從起點到終點的最短路線是唯一的。7．對于帶收發(fā)點的容量網(wǎng)絡(luò)中從發(fā)點到收點的一條增廣路，以下表達(123)不正確。(1)增廣路上的有向邊的方向必然是從發(fā)點指向收點的(2)增廣路上的有向邊，必然都是.精選文檔不飽和邊(3)增廣路上不可以有零流邊(4)增廣路上與發(fā)點到收點方向一致的有向邊不可以是飽和邊，相反方向的有向邊不可以是零流邊8．對于樹，以下表達(ABCE)正確。A．樹是連通、無圈的圖B．任一樹，增添一條邊便含圈C．任一樹的邊數(shù)等于點數(shù)減1。D．任一樹的點數(shù)等于邊數(shù)減1E．任一樹，去掉_條邊便不連通。9．對于最短路，以下表達(ACDE)不正確。A從起點出發(fā)到終點的最短路是唯一的。B．從起點出發(fā)到終點的最短路不用然是唯一的，但其最短路線的長度是確立的。C．從起點出發(fā)的有向邊中的最小權(quán)邊，必然包含在起點到終點的最短路上D．從起點出發(fā)的有向邊中的最大權(quán)邊，必然不包含在起點到終點的最短路上。E．整個網(wǎng)絡(luò)的最大權(quán)邊的必然不包含在從起點到終點的最短路線上。10．對于增廣路，以下表達(BC)正確。A．增廣路是一條從發(fā)點到收點的有向路，這條路上各條邊的方向必一致。B．增廣路是一條從發(fā)點到收點的有向路，這條路上各條邊的方向可不一致。C．增廣路上與發(fā)點到收點方向一致的邊必然是非飽和邊，方向相反的邊必然是流量大于零的邊。D．增廣路上與發(fā)點到