運籌學復習教材課件學習資料

PAGE2一、填空題1、線性規(guī)劃問題中，如果在約束條件中出現(xiàn)等式約束，我們通常用增加___的方法來產生初始可行基。2、線性規(guī)劃模型有三種參數(shù)，其名稱分別為價值系數(shù)、___和___。3、原問題的第1個約束方程是“=”型，則對偶問題相應的變量是___變量。4、求最小生成樹問題，常用的方法有：避圈法和___。5、原問題的變量取值是0，則其對偶問題對應的約束條件是。6、目標規(guī)劃單純形法的最優(yōu)性檢驗規(guī)則是。7、表上作業(yè)法包括有、、。8、目標規(guī)劃克服了線性規(guī)劃只能解個目標的問題。9、運輸問題初始方案的確定的方法有、、10、在目標規(guī)劃問題中，約束條件分為和。二、判斷題：1、在互為對偶的一對原問題與對偶問題中，不管原問題是求極大還是極小，原問題可行解的目標函數(shù)值一定超過其對偶問題可行解的目標函數(shù)值。（）2、如線性規(guī)劃問題存在可行域，則可行域一定包含坐標的原點。（）3、含n個變量m個約束的標準型線性規(guī)劃問題，基解數(shù)恰好為個。（）4、若,分別是某一線性規(guī)劃的最優(yōu)解，則也是該線性規(guī)劃問題的最優(yōu)解，其中。（）5、如果線性規(guī)劃的原問題存在可行解，則其對偶問題也一定存在可行解。（）6、任何線性規(guī)劃問題具有唯一的對偶問題。（）7、單純形法計算中選取最大正檢驗數(shù)對應的變量作為換入基的變量，將使迭代后的目標函數(shù)得到最快的增長。（）8、如果線性規(guī)劃的對偶問題無可行解，則原問題也一定無可行解。（）9、原問題求最大值，第i個約束是“≥”，則該約束條件對應的對偶變量yi=010、對取值無約束的變量，通常令，其中，在用單純形法求得的最優(yōu)解中，有可能同時出現(xiàn)（）11、線性規(guī)劃問題標準形式的數(shù)學模型的目標函數(shù)是求最小值。（）12、如線性規(guī)劃問題存在可行域，則可行域是一個凸集。（）13、對偶單純形法就是求解對偶問題的單純形法。（）14、構成運輸問題初始方案的基變量的個數(shù)是m個。（）15、如果線性規(guī)劃的原問題存在可行解，則其對偶問題也一定存在可行解。（）16、運輸問題中的非基變量的閉回路是存在而且是唯一的。（）17、在互為對偶的一對原問題與對偶問題中，如果一問題的變量取值非0，則其對偶問題的約束條件取嚴格的不等式。（）18、分配問題效率表中某一行元素分別加上（減去）一個常數(shù)，則最優(yōu)解不變。（）19、原問題求最大值，某約束是“≥”約束，則該約束條件對應的對偶變量≤（）20、目標規(guī)劃問題中的約束條件有剛性約束和柔性約束。（）21、完全圖是既連通圖，也是簡單圖。（）22、樹圖是部分圖，也是子圖。（）23、任何圖中，點的次數(shù)之和等于邊的2倍。（）24、圖中任一個點i，若j是與i相鄰點中距離最近的，則邊[i,j]一定含在該圖的最小部分樹內。（）25、自由時差是指不影響它的各項緊后作業(yè)最早開工時間條件下，該項作業(yè)可以推遲的開工的最大時間限度。（）三、單項選擇題：1、互為對偶的兩個線性規(guī)劃問題的解存在關系（）A.原問題具有無界解，則對偶問題無可行解B.對偶問題無可行解，原問題具有無界解C.若最優(yōu)解存在，則最優(yōu)解相同D.一個問題無可行解，則另一個問題也無可行解2、線性規(guī)劃具有唯一最優(yōu)解是指（）A.最優(yōu)表中存在常數(shù)項為零B.最優(yōu)表中非基變量檢驗數(shù)全部非零C.最優(yōu)表中存在非基變量的檢驗數(shù)為零D.可行解集合有界3、原問題有6個變量4個約束，其對偶問題（）A.有4個變量6個約束B.有6個變量4個約束C.有6個變量6個約束D.有4個變量4個約束4、具有n個頂點的樹的邊數(shù)恰好為（）A.(n-1)條B.n條C.(n+1)條D.(n+2)條5、有4個產地5個銷地的平衡運輸問題模型具有特征（）A.有9個變量B.有20個約束C.有8約束D.有8個基變量6、X是線性規(guī)劃的基本可行解則有（）A.X中的基變量非零，非基變量為零B.X不一定滿足約束條件C.X中的基變量非負，非基變量為零D.X是最優(yōu)解7、互為對偶的兩個線性規(guī)劃問題的變量存在關系（）A.在一個問題中是變量，則在另一問題中也是變量B.在一問題中是基變量，則在另一問題中也是基變量C.在一問題中是非基變量，則在另一問題中也是非基變量D.在一問題中是基解變量，則在另一問題中是非基解變量8、線性規(guī)劃具有多個最優(yōu)解是指（）A.可行解集合有界B.最優(yōu)表中非基變量檢驗數(shù)全部非零C.最優(yōu)表中存在常數(shù)項為零D.最優(yōu)表中存在非基變量的檢驗數(shù)為零9、原問題有5個變量4個約束，其對偶問題（）A.有4個變量4個約束B.有5個變量5個約束C.有4個變量5個約束D.有5個變量4個約束10、μ是關于可行流f的一條增廣鏈，則在μ上有（）A.對任意

B.對任意C.對任意

D.對任意11、關于樹的性質，不正確的有（）A.樹圖是連通圖B.具有n個頂點的樹圖的邊數(shù)恰好為（n-1）條C.具有n個頂點的樹圖的邊數(shù)恰好為n條D.任何樹圖中必存在次為1的點12、有4個產地4個銷地的平衡運輸問題模型具有特征（）A.有8個變量B.有16個約束C.有4個約束D.有7個基變量13、互為對偶的兩個線性規(guī)劃若存在最優(yōu)解，則存在關系（）A.Z>W

B.Z=WC.Z≥WD.Z≤W14、線性規(guī)劃的約束條件為則初始基可行解為（）A.(0,2,3,2)B.(3,0,-1,0)C.(0,0,5,6)

D.(2,0,1,2)15、（）A.無可行解B.有唯一最優(yōu)解C.有多重最優(yōu)解D.有無界解16、X是線性規(guī)劃的基本可行解則有（）A.X中的基變量非零，非基變量為零B.X不一定滿足約束條件C.X中的基變量非負，非基變量為零D.X是最優(yōu)解17、使用人工變量法求解極大化線性規(guī)劃問題時，當所有的檢驗數(shù)在基變量中仍含有非零的人工變量，表明該線性規(guī)劃問題（）A.有唯一的最優(yōu)解B.有無窮多最優(yōu)解C.為無界解D.無可行解18、對偶單純形法解最大化線性規(guī)劃問題時，每次迭代要求單純形表中（）A.b列元素不小于零B.檢驗數(shù)都大于零C.檢驗數(shù)都不小于零D.檢驗數(shù)都不大于零19、已知某個含10個結點的樹圖，其中9個結點的次為1，1，3，1，1，1，3，1，3，則另一個結點的次為（）A.3B.2C.1D.以上三種情況均有可能20、如果要使目標規(guī)劃實際實現(xiàn)值不超過目標值，則相應的偏離變量應滿足（）A.d+?0B.d+=0C.d-=0D.d-?0,d+?021、在運輸方案中出現(xiàn)退化現(xiàn)象，是指數(shù)字格的數(shù)目（）A.等于m+nB.等于m+n-1C.小于m+n-1D.大于m+n-122、關于線性規(guī)劃的原問題和對偶問題，下列說法正確的是（）A.若原問題為元界解，則對偶問題也為無界解B.若原問題無可行解，其對偶問題具有無界解或無可行解C.若原問題存在可行解，其對偶問題必存在可行解D.若原問題存在可行解，其對偶問題無可行解23、下列說法正確的是（）A.線性規(guī)劃問題的基本解對應可行域的頂點B.若是某線性規(guī)劃問題的可行解，則（其中）也必是該問題的可行解C.單純形法解標準的線性規(guī)劃問題時，當所有檢驗時，即可判定表中解為最優(yōu)解D.單純形法解標準的線性規(guī)劃問題時，按最小比值原則確定換出基變量是為了保證迭代計算后的解仍為基本可行解四、簡答題：1、簡述單純形法的基本思路。2、簡述對偶單純形法的基本思路。3、簡述運輸問題求解的基本思路。4、寫出下列線性規(guī)劃問題的對偶問題。5、將下列線性規(guī)劃問題化為標準形式五、計算題：1、有份說明書，要分別譯成英、日、德、俄四種文字，交給甲、乙、丙、丁四個人去完成，應如何分配，使四個人分別完成這四項任務總的時間為最小？人甲乙丙丁工作譯英21097譯日154148譯德13141611譯俄4151392、請用破圈法或避圈法求下圖的最小部分樹。基變量X1X2X3X4X5X33/2001-1/8-1/4X25/20103/8-1/4X11100-1/41/2σj000-3/4-1/2已知線性規(guī)劃MaxZ=3X1+4X2X1+X2≤52X1+4X2≤12其最優(yōu)解為：3X1+2X2≤8X1,X2≥0寫出該線性規(guī)劃的對偶問題。若C2從4變成5，最優(yōu)解是否會發(fā)生改變，為什么？若b2的量從12上升到15，最優(yōu)解是否會發(fā)生變化，為什么？如果增加一種產品X6，其P6=(2,3,1)T，C6=4該產品是否應該投產？為什么？4、已知運輸問題的調運和運價表如下，求最優(yōu)調運方案和最小總費用。銷地產地B1B2B3產量A159215A231711A362820銷量1812165、某公司要把4個有關能源工程項目承包給4個互不相關的外商投標者，規(guī)定每個承包商只能且必須承包一個項目，試在總費用最小的條件下確定各個項目的承包者，總費用為多少？各承包商對工程的報價如表2所示：項目投標者ABCD甲15182124乙19232218丙26171619丁19212317求解下列線性規(guī)劃問題。7、用匈牙利法求解下列分配問題。8、用標號法算法求下圖中s至t的最大流量，并找出該網絡的最小割。（每弧旁的數(shù)字是（cij,（fij））。9、請用破圈法或避圈法求下圖的最小部分樹。10、已知運輸問題的產銷地的供需量與單位運價表（如表所示），試用表上作業(yè)法求出其最優(yōu)解。BjAiB1B2B3B4B5產量A1572415A2913567A3248136需量225451811、用圖解法求解下列線性規(guī)劃問題。12、將下列線性規(guī)劃模型的一般形式轉化為標準形式。13、用普通單純形法求解下列線性規(guī)劃問題。14、已知下列線性規(guī)劃問題，已知其對偶問題的最優(yōu)解為。試用對偶性質求解原問題。15、已知下列線性規(guī)劃問題，求出其最優(yōu)解，并求的變化范圍，使得最優(yōu)解不變。已知線性規(guī)劃問題利用對偶理論證明其目標函數(shù)值無界。用圖解法求解下列線性規(guī)劃問題，并指出問題具有唯一最