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

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