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

精品文檔運籌學(xué)復(fù)習(xí)題線性規(guī)劃的基本概念一、填空題在一組線性約束條件下的極值問題。圖解法適用于含有兩個變量的線性規(guī)劃問題。線性規(guī)劃問題的可行解是指滿足所有約束條件的解。在線性規(guī)劃問題的基本解中，所有的非基變量等于零。在線性規(guī)劃問題中，基可行解的非零分量所對應(yīng)的列向量線性無關(guān)若線性規(guī)劃問題有最優(yōu)解，則最優(yōu)解一定可以在可行域的頂點（極點）達(dá)到。線性規(guī)劃問題有可行解，則必有基可行解。的集滿足非負(fù)條件的基本解稱為基本可行解。_端加入松弛變量。線性規(guī)劃模型包括決策（可控）變量，約束條件，目標(biāo)函數(shù)三個要素。值兩類。非負(fù)。二、單選題如果一個線性規(guī)劃問題有n個變量，個約束方程(m<n)，系數(shù)矩陣的數(shù)為m，則基可行解的個數(shù)最多為_C_。A．m個 個 n下列圖形中陰影部分構(gòu)成的集合是凸集的是

nmBA．

B．(1，0，3，0)T

一4，0，0，3)T D．(0，一1，0，5)T精品文檔精品文檔精品文檔精品文檔精品文檔_D_的敘述正確?？尚杏騼?nèi)必有無窮多個點B．可行域必有界C．可行域內(nèi)必然包括原點D必是凸的下列關(guān)于可行解，基本解，基可行解的說法錯誤的_B .可行解中包含基可行解 可行解與基本解之間無交集C．線性規(guī)劃問題有可行解必有基可行解 D．滿足非負(fù)約束條件的基本解為基行解線性規(guī)劃問題有可行解，則AA必有基可行解 B必有唯一最優(yōu)解 C無基可行解 D無唯一最優(yōu)解AA0 B1 C 2 D3若線性規(guī)劃問題沒有可行解，可行解集是空集，則此問題BA沒有無窮多最優(yōu)解 B 沒有最優(yōu)解C有無界解 D無有界三、多選題在線性規(guī)劃問題的標(biāo)準(zhǔn)形式中，不可能存在的變量是DA．可控變量B．松馳變量c．剩余變量D．人工變量下列選項中符合線性規(guī)劃模型標(biāo)準(zhǔn)形式要求的有BCD目標(biāo)函數(shù)求極小值個變量，個約束方程，系數(shù)矩陣的秩為m(m<nABDE。基可行解的非零分量的個數(shù)不大于m B．基本解的個數(shù)不會超過Cm個nC．該問題不會出現(xiàn)退化現(xiàn)象 D．基可行解的個數(shù)不超過基本解的個E．該問題的基是一個m×m階方陣若線性規(guī)劃問題的可行域是無界的，則該問題可能ABCD無有限最優(yōu)解B．有有限最優(yōu)解C．有唯一最優(yōu)解D．有無窮多個最優(yōu)解E多個最優(yōu)解_ABC_?；窘馐谴笥诹愕慕?極點與基解一一對應(yīng)C．線性規(guī)劃問題的最優(yōu)解是唯一的D．滿足約束條件的解就是線性規(guī)劃的可行線性規(guī)劃問題若有最優(yōu)解，則最優(yōu)解ADA定在其可行域頂點達(dá)到 B只有一個 C會有無窮多個D唯一或無窮多個其值為0四、名詞解釋1A的任意一個m×m階的非奇異子方陣稱為線性規(guī)劃問題的一個基。2、線性規(guī)劃問題：就是求一個線性目標(biāo)函數(shù)在一組線性約束條件下的極值問題。3.可行解：在線性規(guī)劃問題中，凡滿足所有約束條件的解稱為線性規(guī)劃問題可行解4、可行域：線性規(guī)劃問題的可行解集合。5、基本解：在線性約束方程組中，對于選定的基B令所有的非基變量等于零，得到的解，稱為線性規(guī)劃問題的一個基本解。6.、基本可行解：在線性規(guī)劃問題中，滿足非負(fù)約束條件的基本解稱為基本可行解。線性規(guī)劃的基本方法一、填空題0,非基變量檢驗數(shù)δ_≤_0j用大M。表中人工變量不為零判斷線性規(guī)劃問題無解?；?。在單純形迭代中，選出基變量時應(yīng)遵循最小比值θ法則。δk>0對應(yīng)的非基變量x的系數(shù)列向量P_≤0_k k問題是無界的。在大M二、單選題在單純形迭代中，出基變量在緊接著的下一次迭代中B立即進(jìn)入基A．會 不會 有可能 不一定在單純形法計算中，如不按最小比值原則選取換出變量，則在下一個解中B。精品文檔A．不影響解的可行性B．至少有一個基變量的值為負(fù)C．找不到出基變量D．找不到進(jìn)基變量3．0，則說明本問題B。A．有惟一最優(yōu)解 有多重最優(yōu)解 無界 無4．下列說法錯誤的是BA．會再進(jìn)基單純形法當(dāng)中，入基變量的確定應(yīng)選擇檢驗數(shù)CA絕對值最大 B絕對值最小 C正值最大 D負(fù)值最小DA單位陣 B非單位陣 C單位行向量 D單位列向量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)三、多選題對取值無約束的變量x。通常令x=xx”，其中x0，x”≥0，在用單純形j j j j j j法求得的最優(yōu)解中，可能出現(xiàn)的是ABC設(shè)X(1)，X(2)是用單純形法求得的某一線性規(guī)劃問題的最優(yōu)解，則說明ACDE。A．此問題有無窮多最優(yōu)解B．該問題是退化問題C．示為λX(1)+(1λ)X(2)0≤λ≤1D．X(1)，X(2)E．X(1)，X(2)的基變量個數(shù)相同ACDE先選出基變量，再選進(jìn)基變量C．進(jìn)基變量的系數(shù)列向量應(yīng)化為單位向量D．旋轉(zhuǎn)變換時采用的矩陣的初等行變換E．出基變量的選取是根據(jù)最小比值法則精品文檔精品文檔6．從一張單純形表中可以看出的內(nèi)容有ABCEA．一個基可行解B．解C．線性規(guī)劃問題是否出現(xiàn)退化D．線性規(guī)劃問題的最優(yōu)解E．線性規(guī)劃問題是否無界四、名詞、簡答1、人造初始可行基：當(dāng)我們無法從一個標(biāo)準(zhǔn)的線性規(guī)劃問題中找到一個m通常在約束方程中引入人工變量，而在系數(shù)矩陣中湊成一個m階單位矩陣，進(jìn)而形成的一個初始可行基稱為人造初始可行基。2并且使目標(biāo)函數(shù)值逐步得到改善，直到最后球場最優(yōu)解或判定原問題無解。線性規(guī)劃的對偶理論一、填空題小值/極小值的線性規(guī)劃問題與之對應(yīng)，反之亦然。在一對對偶問題中，原問題的約束條件的右端常數(shù)是對偶問題的目標(biāo)函數(shù)系數(shù)。。_。若原問題可行，但目標(biāo)函數(shù)無界，則對偶問題不可行。線性規(guī)劃問題的最優(yōu)基為B，基變量的目標(biāo)系數(shù)為CBBY﹡=CB－1。B若X﹡和Y﹡分別是線性規(guī)劃的原問題和對偶問題的最優(yōu)解，則有CX﹡=。若X、YCX≤Yb。若X﹡和Y﹡分別是線性規(guī)劃的原問題和對偶問題的最優(yōu)解，則有CX﹡=Y*b。設(shè)線性規(guī)劃的原問題為maxZ=CX，Ax≤b，X≥0，則其對偶問題為min=Yb Y≥0_。二、單選題線性規(guī)劃原問題的目標(biāo)函數(shù)為求極小值型，若其某個變量小于等于0束條件為A形式。A．“≥”B“≤” ，“>”．“=”設(shè)X、Y分別是標(biāo)準(zhǔn)形式的原問題與對偶問題的可行,則C 。精品文檔精品文檔精品文檔精品文檔精品文檔w﹡A。A．W﹡=Z﹡ B．W﹡≠Z﹡ C．W﹡≤Z﹡ 4．_BA．該資源過剩B．該資源稀缺C．企業(yè)應(yīng)盡快處理該資源D．企業(yè)應(yīng)充分利用該資源，開僻新的生產(chǎn)途徑三、多選題1．在一對對偶問題中，可能存在的情況是ABCA．一個問題有可行解，另一個問題無可行解 兩個問題都有可行解C．兩個問題都無可行解 一個問題無界，另一個問題可下列說法錯誤的是B 。A．任何線性規(guī)劃問題都有一個與之對應(yīng)的對偶問題B．對偶問題無可行解時，其原問．若原問題為，則對偶問題為Y≥0D．若原問題有可行解，但目標(biāo)函數(shù)無界，其對偶問題無可行解。3．如線性規(guī)劃的原問題為求極大值型，則下列關(guān)于原問題與對偶問題的關(guān)系中正確的是BCDE。AB應(yīng)的對偶變量為自由變量C對應(yīng)的對偶約束“≥”D．原問題的變量“≤O”對應(yīng)的對偶約束“≤”E．原問題的變量無符號限制，對應(yīng)的對偶約束“=”4．一對互為對偶的問題存在最優(yōu)解，則在其最優(yōu)點處有BDA．若某個變量取值為0，則對應(yīng)的對偶約束為嚴(yán)格的不等式B則相應(yīng)的對偶約束必為等式C．若某個約束為等式，則相應(yīng)的對偶變?nèi)≈禐檎鼶．若某個約束為嚴(yán)格的不等式，則相應(yīng)的對偶變量取值為0E．若某個約束為等式，則相應(yīng)的對偶變量0四、名詞、簡答題1、.對稱的對偶問題：設(shè)原始線性規(guī)劃問題為maxZ=CX s.tAX≤b X≥0稱線性規(guī)劃問題minW=Yb s.t Y≥0 為其對偶問題。又稱它為一對對稱的對偶問題。2、影子價格：對偶變量Yi表示與原問題的第i量上表現(xiàn)為，當(dāng)該約束條件的右端常數(shù)增加一個單位時（假設(shè)原問題的最優(yōu)解不變，原問題目標(biāo)函數(shù)最優(yōu)值增加的數(shù)量。3原問題和對偶問題都無可行解。線性規(guī)劃的靈敏度分析一、填空題1、在靈敏度分析中，某個非基變量的目標(biāo)系數(shù)的改變，將引起該非基變量自身的檢驗數(shù)的變化。2．如果某基變量的目標(biāo)系數(shù)的變化范圍超過其靈敏度分析容許的變化范圍，則此基變量應(yīng)出基。若某約束常數(shù)b的變化超過其容許變動范圍，為求得新的最優(yōu)解，需在原最優(yōu)單純形表i的基礎(chǔ)上運用對偶單純形法求解。如果線性規(guī)劃的原問題增加一個約束條件，相當(dāng)于其對偶問題增加一個變量。若某線性規(guī)劃問題增加一個新的約束條件二、單選題若線性規(guī)劃問題最優(yōu)基中某個基變量的目標(biāo)系數(shù)發(fā)生變化，則C。．該基變量的檢驗數(shù)發(fā)生變化驗數(shù)發(fā)生變化D．所有變量的檢驗數(shù)都發(fā)生變化2．在線性規(guī)劃的各項敏感性分析中，一定會引起最優(yōu)目標(biāo)函數(shù)值發(fā)生變化的是。A．目標(biāo)系數(shù)c的變化B．約束常數(shù)項b變化C．增加新的變量D．增加新約束j i三、多選題1．在靈敏度分析中，我們可以直接從最優(yōu)單純形表中獲得的有效信息有ABCEA．最優(yōu)基B的逆B-1 最優(yōu)解與最優(yōu)目標(biāo)函數(shù)值 各變量的檢驗數(shù)D．對偶問題的解 各列向量3．線性規(guī)劃問題的各項系數(shù)發(fā)生變化，下列不能引起最優(yōu)解的可行性變化的是ABC_A．非基變量的目標(biāo)系數(shù)變化B．基變量的目標(biāo)系數(shù)變化C．增加新的變量D，增加新的約束條件四、名詞、簡答題靈敏度分析：研究線性規(guī)劃模型的原始數(shù)據(jù)變化對最優(yōu)解產(chǎn)生的影響運輸問題mA…，A，A的供應(yīng)量為a(i=1，2…，m)，nl 2 m j i個需求地BB…BB的需求量為b(j=2n

=n1 2 n j

aii1

bij1案?？梢宰鳛楸砩献鳂I(yè)法的初始調(diào)運方案的填有數(shù)字的方格數(shù)應(yīng)為m+n－1mn若調(diào)運方案中的某一空格的檢驗數(shù)為1，1。調(diào)運方案的調(diào)整是要在檢驗數(shù)出現(xiàn)負(fù)值的點為頂點所對應(yīng)的閉回路內(nèi)進(jìn)行運量的調(diào)整。_1路ij i 在運輸問題中，單位運價為C位勢分別用u表示，則在基變量處有cC=u+V。ij i ij i j ij8、供大于求的、供不應(yīng)求的不平衡運輸問題，分別是指mai

＞nbi

的運輸問題、ma_i＜nbi

的運輸問題。

i1

jij1的調(diào)整量應(yīng)為300_。IⅡⅢⅣA300100300BC600400300在格單位調(diào)整量。運輸問題的初始方案中的基變量取值為正。14在編制初始方案調(diào)運方案及調(diào)整中，如出現(xiàn)退化，則某一個或多個點處應(yīng)填入數(shù)字0二、單選題1、在表上作業(yè)法求解運輸問題中，非基變量的檢驗數(shù)。A．大于0 小于0 等于0 以上三種都可運輸問題的初始方案中，沒有分配運量的格所對應(yīng)的變量為BA基變量 B非基變量 C松弛變量 D剩余變量表上作業(yè)法中初始方案均為AA可行解 B非可行解 C 待改進(jìn)解 D最優(yōu)解閉回路是一條封閉折線，每一條邊都是DA水平 B垂直 C水平＋垂直 D水平或垂直運輸問題中分配運量的格所對應(yīng)的變量為 AA基變量 B非基變量 C松弛變量 D剩余變量所有物資調(diào)運問題，應(yīng)用表上作業(yè)法最后均能找到一個DA可行解 B非可行解 C 待改進(jìn)解 D最優(yōu)解一般講，在給出的初始調(diào)運方案中，最接近最優(yōu)解的是CA西北角法 B最小元素法 C 差值法 D位勢法CA檢驗數(shù)為負(fù)B檢驗數(shù)為正C檢驗數(shù)為負(fù)且絕對值最大D檢驗數(shù)為負(fù)且絕對值最小C負(fù)值的點所在的閉回路內(nèi)進(jìn)行。A任意值 B最大值 C絕對值最大 D絕對值最小10.表上作業(yè)法的基本思想和步驟與單純形法類似，因而初始調(diào)運方案的給出就相當(dāng)于找一個CA基 B可行解 C初始基本可行解 D最優(yōu)11平衡運輸問題即是指m個供應(yīng)地的總供應(yīng)量Dn個需求地的總需求量。A大于 B大于等于 C小于 D等三、多選題下列說法正確的是ABD。A．表上作業(yè)法也是從尋找初始基可行解開始的B．當(dāng)一個調(diào)運方案的檢驗數(shù)全部為正值時，當(dāng)前方案一定是最佳方案C．最小元素法所求得的運輸?shù)倪\量是最小的D．表上作業(yè)法中一張供需平衡表對應(yīng)一個基可行解四、名詞1、平衡運輸問題：m個供應(yīng)地的供應(yīng)量等于n個需求地的總需求量，這樣的運輸問題稱平衡運輸問題。2個供應(yīng)地的供應(yīng)量不等于n稱不平衡運輸問題。整數(shù)規(guī)劃標(biāo)函數(shù)值的下界。r在分枝定界法中，若選X4／3X1≤1，X1≥2。r已知整數(shù)規(guī)劃問題PP’，若問題P。0 0 0無可行解。0-1_01。對于一個有n項任務(wù)需要有n1n個。線性規(guī)劃方法求解整數(shù)規(guī)劃。若在對某整數(shù)規(guī)劃問題的松馳問題進(jìn)行求解時，得到最優(yōu)單純形表中，由X。所在行6 1 2X1／7x+2／7x=13／7，則以X_1 3 5 1

－7X3－

X5≤0_。求解分配問題的專門方法是匈牙利法。。分枝定界法一般每次分枝數(shù)量為2二、單選題整數(shù)規(guī)劃問題中，變量的取值可能是D。A．整數(shù)B．0或1C．大于零的非整數(shù)D．以上三種都可能2．在下列整數(shù)規(guī)劃問題中，分枝定界法和割平面法都可以采用的是AA．純整數(shù)規(guī)劃B．混合整數(shù)規(guī)劃C．0—1規(guī)劃D．線性規(guī)劃3．下列方法中用于求解分配問題的是D_。A．單純形表B．分枝定界法C．表上作業(yè)法D．匈牙利法三、多項選擇下列說明不正確的是ABC。A．BC．D非整數(shù)的約束系數(shù)及右端常數(shù)化為整數(shù)。在求解整數(shù)規(guī)劃問題時，可能出現(xiàn)的是ABC。A．唯一最優(yōu)解B．無可行解C．多重最佳解D3．_。D．配問題，要求規(guī)定一個人只能完成一件工作，同時一件工作也只給一個人做。整數(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ī)劃問題中，如果要求所有的決策變量只能取010—1規(guī)劃。3整數(shù)規(guī)劃。一、填空題任一樹中的邊數(shù)必定是它的頂點數(shù)減。3．18、求支撐樹有破圈 法和 避圈 法兩種方法二、單選題1、關(guān)于圖論中圖的概念，以下敘述(B)正確。ABC圖中任意兩點之間必有邊。D圖的邊數(shù)必定等于點數(shù)減1。2．(B)正確。A樹中的點數(shù)等于邊數(shù)減1 B連通無圈的圖必定是樹 C含n個點的樹是唯一的D任一樹中，去掉一條邊仍為樹。3．一個連通圖中的最小樹(B)，其權(quán)(A)。A是唯一確定的 B可能不唯一 C可能不存在 D一定有多個4．關(guān)于最大流量問題，以下敘(D)正確。ABCD當(dāng)最大流方案不唯一時5．C)不正確。A．圖論中點表示研究對象，邊或有向邊表示研究對象之間的特定關(guān)系B．圖論中的圖，用點與點的相互位置，邊的長短曲直來表示研究對象的相互關(guān)系C．圖論中的邊表示研究對象點表示研究對象之間的特定關(guān)系。 圖論中的圖可以改變點與點的相互位置只要不改變點與點的連接關(guān)系。B)正確。最小樹是一個網(wǎng)絡(luò)中連通所有點而邊數(shù)最少的圖B點，而權(quán)數(shù)最少的圖C．一個網(wǎng)絡(luò)中的最大權(quán)邊必不包含在其最小樹內(nèi)D．一個網(wǎng)絡(luò)的最小樹一般是不唯一的。A)不正確?？尚辛鞯牧髁看笥诹愣∮谌萘肯拗茥l件B．在網(wǎng)絡(luò)的任一中間點，可行流滿足流人C．各條有向邊上的流量均為零的流是一個可行流D．制條件而大于或等于零。三、多選題123)正確。(2(3)(4)結(jié)點數(shù)等于邊數(shù)的圖必連通。123)正確。1)樹中的邊數(shù)等于點數(shù)減1(2)樹中再添一條邊后必含圈。(3)樹中刪去一條邊后必不連通(4)樹中兩點之間的通路可能不唯一。134)正確。任一連通圖必有支撐樹(2)任一連通圖生成的支撐樹必唯一(3(4)任一連通圖生成的各個支撐樹其邊數(shù)必相同(a)生成的支撐樹。精品文檔124)不正確。(2(3(4)最小樹中可能包括連通圖中的最大權(quán)邊。123)不正確。1)從起點出發(fā)的最小權(quán)有向邊必含在最短路線中。(2)整個圖中權(quán)最小的有向邊必包含在最短路線中。(3)整個圖中權(quán)最大的有向邊可能含在最短路線中(4)從起點到終點的最短路線是唯一的。123)不正確。(2)增廣路上的有向邊，必須都是不飽和邊(3(4飽和邊，相反方向的有向邊不能是零流邊ABCE)正確。A．樹是連通、無圈的圖B．任一樹，添加一條邊便含圈C．任一樹的邊數(shù)等于點數(shù)減1。D．任一樹的點數(shù)等于邊數(shù)減1E．任一樹，去掉_條邊便不連通。ACDE)不正確。A從起點出發(fā)到終點的最短路是唯一的B．從起點出發(fā)到終點的最短路不一定是唯一的，但其最短路線的長度是確定的C．從起點出發(fā)的有向邊中的最小權(quán)邊，一定包含在起點到終點的最短路上D．從起點出發(fā)的有向邊中的最大權(quán)邊，一定不包含在起點到終點的短路上。E．整個網(wǎng)絡(luò)的最大權(quán)邊的一定不包含在從起點到終點的最短路線上。10．關(guān)于增廣路，以下敘(BC 正確。A．C．增廣路上與發(fā)點到收點D．增廣路上與發(fā)點邊。四、名詞解釋精品文檔精品文檔精品文檔精品文檔精品文檔1、樹:在圖論中，具有連通和不含圈特點的圖稱為樹。權(quán)：在圖中，邊旁標(biāo)注的數(shù)字稱為權(quán)。網(wǎng)絡(luò)：在圖論中，給邊或有向邊賦了權(quán)的圖稱為網(wǎng)絡(luò)最大流問題：最大流問題是指在網(wǎng)絡(luò)圖中，在單位時間內(nèi)，從發(fā)點到收點的最大流量最大流問題中流量：最大流問題中流量是指單位時間的發(fā)點的流出量或收點的流入量。容量：最大流問題中，每條有向邊單位時間的最大通過能力稱為容量飽合邊：容量與流量相等的有向邊稱為飽合邊。8零流邊：流量為零的有向邊稱為零流邊9.生成樹：若樹T是無向圖G的生成樹，則稱T是G.。計算題（答案參考課件）圖解法求線性規(guī)劃問題。maxZ2x1

3x22