《運籌學》期末復習題一、單項選擇題1、下列論述對的的是（）。A．線性規劃問題，若有最優解，則必是一種基變量組的可行基解B．線性規劃問題一定有可行基解C．線性規劃問題的最優解只能在最低點上到達D．單純形法求解線性規劃問題時，每換基迭代一次必使目的函數值下降一次答案：A2、線性規劃的變量個數與其對偶問題的（）相等。A．變量目的函數C．約束條件個數答案：C3、在運用表上作業法求各非基變量的檢查數時，有閉回路法和（）兩種措施。A．西北角法C．最低費使用方法答案：B4、下列各項（）不是目的規劃的特點。A．多目的C．具有優先次序答案：B5、下列有關圖的說法中，錯誤的為（）。A．點表達所研究的事物對象C．無向圖是由點及邊所構成的圖答案：D6、運用單純形法求解線性規劃問題時，首先需要（）。A．找初始基礎可行基C．確定改善方向答案：A7、對偶問題最優解的剩余變量解值（）原問題對應變量的檢查數的絕對值。A．不小于C．等于答案：C第1頁共17頁B．變量約束條件D．不確定B．位勢法D．元素差額法B．單一目的D．不求最優B．檢查目前基礎可行解與否為最優解D．確定入變量的最大值和出變量B．不不小于D．不能確定8、當某個非基變量檢查數為零，則該問題有（）。A．無解B．無窮多最優解C．退化解D．惟一最優解答案：B9、PERT網絡圖中，（）表達一種工序。A．節點B．弧C．權D．關鍵路線答案：B10、假設對于一種動態規劃問題，應用順推法以及逆推解法得出的最優解分別為P和D，則有（A．P>DB．P答案：C11、下列有關線性規劃問題的原則形式的論述中錯誤的是（）。A．目的函數求極大B．約束條件全為等式C．約束條件右端常數項全為正D．變量取值全為非負答案：C12、線性規劃問題的數學模型由目的函數、約束條件和（）三個部分構成。A．非負條件B．頂點集合C．最優解D．決策變量答案：D13、假如原問題有最優解，則對偶問題一定具有（）。A．無窮多解B．無界解C．最優解D．不能確定答案：C14、運送問題的基變量有（）個。A．m某nB．m+n-1C．m+nD．不確定答案：B15、目的規劃的目的權系數是定量的概念，數值（），表達該目的越重要。A．越小B．越大C．為0D．為正第2頁共17頁答案：B16、下列論述對的的是（）。A．線性規劃問題，若有最優解，則必是一種基變量組的可行基解B．線性規劃問題一定有可行基解C．線性規劃問題的最優解一定唯一D．單純形法求解線性規劃問題時，每換基迭代一次必使目的函數值下降一次答案：A17、設M是線性規劃問題，N是其對偶問題，則（）不對的。A．M有最優解，N不一定有最優解B．若M和N均有最優解，則兩者最優值肯定相等C．若M無可行解，則N無有界最優解D．N的對偶問題為M答案：A18、PERT網絡圖中，（）表達為完畢某個工序所需的時間或資源等數據。A．節點C．權答案：C19、網絡的最大流量應（）它的最小割集的容量。A．不小于C．不不小于答案：B20、運用單純形法求解線性規劃問題時，判斷目前解與否為最優解的原則為所有非基變量的檢查數應為（）。A．正C．非正答案：C21、若原問題為無界解，則對偶問題的解是（）。A．無解C．無界解答案：A22、PERT網絡圖中，（）表達一種事件，用圓圈和里面的數字表達。第3頁共17頁B．弧D．圓圈B．等于D．不不小于B．負D．非負B．無窮多解D．不能確定A．節點C．權答案：A23、具有7個節點的樹T的邊恰好為（）條。A．5B．弧D．關鍵路線B．6C．7D．8答案：B24、下列數學模型中，（）是線性規劃模型。A.MinZ=3某1+某2－2某3B.Ma某Z=10某1+某2-3某322某1+3某2-4某3≤12某1+5某2≤154某1+某2+2某3≥8某1-8某2+3某3≥223某1-某2+3某3=6某j≥0,j=1,2,3某1≥0,某2無約束,某3≤02C.D.Z=5某1+6某2+8某3-9某4Ma某Z=某1+4某2-8某3+某4某1+4某3-某4=19某2-5某3+4某4≥30某1+某2-6某4≤9某j≥0,j=1,2,3,4某1+4某3-某4=29某2-5某3+4某4≥40某1+某2-6某4≤19某j≥0,j=1,2,3,4答案：A25、若線性規劃問題的最優解不唯一，則在最優單純形表上（）。A．非基變量的檢查數都為零C．非基變量檢查數必有為零答案：C26、對于總運送費用最小的運送問題，若已得最優運送方案，則其中所有空格的檢查數均（）。A．非正C．不小于0答案：B27、下列環節中，不屬于目的規劃模型圖解法的為（）。A．作平面直角坐標系C．作出目的函數的一族平行線答案：C28、下列有關圖的說法中，錯誤的為（）。第4頁共17頁B．非基變量檢查數不必有為零者D．非基變量的檢查數都不不小于零B．非負D．不不小于0B．作出目的約束所在直線，標出偏差方向D．按優先級次序，確定滿意解A．點表達所研究的事物對象C．無向圖是由點及邊所構成的圖答案：D二、判斷題1、若LP問題有最優解，則要么最優解唯一，要么有無窮多最優解。（）答案：對2、在運送問題的解的檢查數的計算時，常采用匈牙利法。（）答案：錯3、偏差變量是指實際值與目的值的差距，其中d可以用來表達實際值未到達目的值的差距。（）答案：錯4、作業的最早結束時間是它的最早開始時間加上該項作業的計劃時間。（）答案：對5、關鍵路線上的作業稱為關鍵作業。（）答案：對6、破圈法可以用來求解部分樹。（）答案：對7、增長約束條件時，線性規劃模型的可行域不擴大。（）答案：對8、線性規劃問題存在至少一種對偶問題。（）答案：錯9、產地數與銷地數相等的運送問題是產銷平衡運送問題。（）答案：錯10、在互為對偶的一對原問題與對偶問題中，不管原問題是求極大或是極小，原問題可行解的目的函數值都一定超過其對偶問題可行解的目的函數值。（）答案：錯11、圖的最小生成樹一定唯一。（）答案：錯12、動態規劃的逆推與順推解法得到不一樣的最優解。（）答案：錯13、對于線性規劃原則型，運用單純形求解時，每做一次換基迭代，都能保證它對應的目的函數值必為不第5頁共17頁+減少。（）答案：對14、當目的規劃問題模型中存在某1某2d答案：錯15、PERT網絡圖中，事件一般用箭線表達，作業用圓圈表達。（）答案：錯16、無多重邊的圖稱為簡樸圖。（）答案：錯17、運送問題、最短路問題和求網絡最大流問題，都可看作是最小費用流的特例。（）答案：對18、目的規劃問題中，權系數是定量的概念，數值越大，表達該目的越重要。（）答案：對19、若線性規劃問題存在可行域，則問題的可行域是凸集。（）答案：對20、目的規劃模型中，應同步包括系統約束與目的約束。（）答案：錯21、PERT網絡圖中，任何消耗時間或資源的行動都可稱作作業。（）答案：對22、任務分派問題共有m某m個約束條件。（）答案：錯23、樹枝總長為最短的部分樹稱為圖的最小部分樹。（）答案：對24、目的的優先級是一種定性的概念，不一樣優先級的目的無法從數量上來衡量。（）答案：對25、單純形法計算中，應選用最小正檢查數對應的變量作為換入變量。（）答案：錯26、當目的規劃問題模型中存在2某1某24的約束條件，則該約束為目的約束。（）答案：錯27、PERT網絡圖中，事件消耗一定的時間和資源。（）答案：錯第6頁共17頁5的約束條件，則該約束為系統約束。（）28、在動態規劃模型中，問題的階段數等于問題中的子問題的數目。（）答案：對29、運送問題和求網絡最大流問題，都可看作是最小費用流的特例。（）答案：對30、當網絡中不存在任何增廣鏈時，則網絡到達最大流狀態。（）答案：對31、在可行解的狀態下，原問題與對偶問題的目的函數值是相等的。（）答案：錯32、在處理運送問題時，采用閉回路法，可以得到運送問題的基本可行解。（）答案：錯33、在整數規劃問題中，若變量取值為0或者1，則為0—1規劃問題。（）答案：對34、PERT網絡圖是由結點、弧及權所構成的有向圖。（）答案：對35、完畢各個作業需要的時間最長的路線稱為關鍵路線。（）答案：對三、名詞解釋題1、規劃問題答案：生產和經營中常常提出怎樣合理安排，使人力、物力等多種資源得到充足運用，獲得最大的效益。這就是所謂的規劃問題。2、對偶問題答案：內容一致但從相反角度提出的一對問題稱為對偶問題。3、無向圖答案：無向圖是指由點及邊所構成的圖。4、割集答案：割集是指容量網絡中一組弧的集合，割斷這些弧，能使流中斷，簡稱割。5、路線答案：從PERT網絡圖中從最初事件到最終事件的一條路。6、偏差變量答案：偏差變量指實際值與目的值的差距。第7頁共17頁7、PERT網絡圖答案：PERT網絡圖是由結點、弧及權所構成的有向圖。8、增廣鏈答案：由發點到收點之間的一條鏈，假如在前向弧上滿足流量不不小于容量，即fij0，則稱這樣的鏈為增廣鏈。9、系統約束答案：系統約束指某種資源在使用上要受到嚴格的限制，決不容許超用或超負荷運行。10、簡樸圖答案：既沒有自環也沒有平行邊的圖稱為簡樸圖。11、狀態轉移律答案：狀態參數變化的規律。從第k階段的某一狀態值k出發，當決策變量某k的取值確定之后，下一階段的狀態值k+1按某種規律T(k,某k)確定。12、閉回路答案：閉回路指調運方案中由一種空格和若干個有數字格的水平和垂直連線包圍成的封閉回路。13、正偏差變量答案：正偏差變量指實際值超過目的值的差距。14、作業的最早開始時間答案：作業的最早開始時間是它的各項緊前作業最早結束時間中的最大一種值。15、連通圖答案：若一種圖中，任意兩點之間至少存在一條鏈，稱這樣的圖為連通圖。16、0-1規劃問題答案：在整數規劃問題中，若變量取值為0或者1，則為0-1規劃問題。17、負偏差變量答案：負偏差變量指實際值未到達目的值的差距。18、作業的最遲結束時間答案：作業的最遲結束時間是它的各項緊后作業最遲開始時間中的最小一種。19、最小割答案：網絡中所有割集中容量之和為最小的一種割集。20、偏差變量答案：偏差變量指實際值與目的值的差距。d表達實際值超過目的值的差距；d表達實際值未到達目的值的差距。第8頁共17頁+21、圖答案：容量網絡指對網絡上的每條弧(vi，vj)都給出一種最大的通過能力，稱為該弧的容量，記為c(vi，vj)，簡稱容量。以cij表達。23、狀態答案：狀態指某階段初始狀況。既反應前面各階段決策的結局，又是本階段作出決策的出發點和根據。是動態規劃中各階段信息的傳遞點和結合點。四、簡答題1、簡述避圈法的環節？答案：答：將圖中所有的點分為V和v兩部分，其中V——最小部分樹內點的集合；v——非最小部分樹內點的集合。（1）任取一點vi加粗，令vi∈V；（2）取V中與v相連的邊中一條最短的邊(vi,vj)，加粗(vi,vj)，令vj∈V；（3）反復（2），至所有的點均在V之內。2、簡述運用分枝定界法求解整數規劃問題時，首先需要尋找替代問題，簡述替代問題應具有的條件。答案：（1）輕易求解；（2）松弛問題的解集應所有包括原問題的解集。3、簡述圖解法的合用條件和基本環節。答案：答：對于只含兩個變量的線性規劃問題，可通過在平面上作圖的措施求解。圖解法的環節如下：（1）建立平面直角坐標系；（2）圖示約束條件，找出可行域；（3）圖示代表目的函數的直線及目的函數值增長（或減小）的方向；（4）將目的函數直線沿其法線方向在可行域內向可行域邊界平移至目的函數到達最優值為止，目的函數到達最優值的點就為最長處。4、簡述運用元素差額法確定運送問題初始方案的基本思想和環節。答：基本思想：從總體考慮，得到初始可行方案。環節：從運價表上分別找出每行與每列的最小的兩個元素之差，再從差值最大的行或列中找出最小運價確定供需關系和供應數量。5、簡述求網絡最大流的標號算法的基本環節。答：第一步：標號過程，找一條增廣鏈第9頁共17頁（1）給源點標號[,()=]，表達從點有無限流出潛力+（2）找出與已標號節點i相鄰的所有未標號節點j，若1)(i,j)是前向弧且飽和，則節點j不標號；2)(i,j)是前向弧且未飽和，則節點j標號為[i,(j)]，表達從節點i正向流出，可增廣+(j)=min[(i),cijfij]；3)(j,i)是后向弧，若fji=0，則節點j不標號；4)(j,i)是后向弧，若fji>0，則節點j標號為[i,(j)]，表達從節點j流向i，可增廣(j)=min[(i),fji]；（3）反復環節（2），也許出現兩種狀況：1)節點t尚未標號，但無法繼續標識，闡明網路中已不存在增廣鏈，目前流V(f)就是最大流；所有獲標號的節點在V中，未獲標號節點在V中，V與V間的弧即為最小割集；算法結束；2)節點t獲得標號，找到一條增廣鏈，由節點t標號回溯可找出該增廣鏈；到第二步。第二步：增廣過程。（1）對增廣鏈中的前向弧，令f=f+(