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

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