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