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

1、2019年春運籌學(xué)期末考試復(fù)習(xí)題 注意事項：本復(fù)習(xí)題滿分共：400分。一、單項選擇題（本大題共 28小題，每小題4分，共112分）1、下列敘述正確的是（）。A.線性規(guī)劃問題，若有最優(yōu)解，則必是一個基變量組的可行基解B.線性規(guī)劃問題一定有可行基解C.線性規(guī)劃問題的最優(yōu)解只能在最低點上達到D.單純形法求解線性規(guī)劃問題時，每換基迭代一次必使目標(biāo)函數(shù)值下降一次答案：A TOC o 1-5 h z 2、數(shù)學(xué)規(guī)劃的研究對象為（）。A.數(shù)值最優(yōu)化問題B .最短路問題C .整數(shù)規(guī)劃問題D .最大流問題答案：A3、下列方法中可以用來求解部分樹的方法的為（）。A.閉回路法B .破圈法 C .踏石法D .匈牙利算法

2、答案：B4、把各種備選方案、可能出現(xiàn)的狀態(tài)和概率以及產(chǎn)生的后果繪制在一張圖上，稱為（）。A.決策樹B .最大流 C .最小支撐樹D.連通圖答案：A5、以下說法中，不屬于無概率決策問題（不確定型決策問題）的特點的為（）。A.決策人面臨多種決策方案B.對每個決策方案對應(yīng)的幾個不同決策狀態(tài)無法估計其出現(xiàn)概率的大小C.僅憑個人的主觀傾向和偏好進行方案選擇D.未來情況和條件出現(xiàn)的概率已知答案：D6、線性規(guī)劃問題中決策變量應(yīng)為（）。A.連續(xù)變量B .離散變量C .整數(shù)變量D .隨機變量答案：A7、線性規(guī)劃問題的數(shù)學(xué)模型由目標(biāo)函數(shù)、約束條件和A.非負條件 B .頂點集合C答案：D8、典型的無概率決策準(zhǔn)則，不

3、包括（）。A.樂觀準(zhǔn)則B .折中準(zhǔn)則 C答案：D9、以下說法中不正確的為（）。A.完成各個作業(yè)需要的時間最長的路線為關(guān)鍵路線C.所有關(guān)鍵作業(yè)的總時差為 0D:）三個部分組成。最優(yōu)解 D .決策變量.等可能準(zhǔn)則 D .最大后悔值準(zhǔn)則B .關(guān)鍵路線上的作業(yè)稱為關(guān)鍵作業(yè).以上說法均不正確答案：D10、（）也稱小中取大準(zhǔn)則。這是一種在不確定型決策問題中，充分考慮可能出現(xiàn)的最小收益后，在 最小收益中再選取最大者的保守決策方法。.等可能準(zhǔn)則D .后悔值準(zhǔn)則）B.無窮多最優(yōu)解D.惟一最優(yōu)解A.悲觀準(zhǔn)則B .折中準(zhǔn)則 C答案：A11、當(dāng)某個非基變量檢驗數(shù)為零，則該問題有（A.無解C.退化解答案：BP和D,則有

4、（）。12、假設(shè)對于一個動態(tài)規(guī)劃問題，應(yīng)用順推法以及逆推解法得出的最優(yōu)解分別為B. PDC. P=DD.不確定答案：C13、下列有關(guān)線性規(guī)劃問題的標(biāo)準(zhǔn)形式的敘述中錯誤的是（）。A.目標(biāo)函數(shù)求極大B.約束條件全為等式C.約束條件右端常數(shù)項全為正D.變量取值全為非負答案：C14、運輸問題的基變量有（）個。A. mx nB. m+n-1m+nD.不確定答案：B）,表不該目標(biāo)越重要。15、目標(biāo)規(guī)劃的目標(biāo)權(quán)系數(shù)是定量的概念，數(shù)值（A.越小B.越大C.為0D.為正答案：B16、下列敘述正確的是（）。A.線性規(guī)劃問題，若有最優(yōu)解，則必是一個基變量組的可行基解B.線性規(guī)劃問題一定有可行基解C.線性規(guī)劃問題的最

5、優(yōu)解一定唯一D.單純形法求解線性規(guī)劃問題時，每換基迭代一次必使目標(biāo)函數(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)解N的對偶問題為M答案：A18、PERT網(wǎng)絡(luò)圖中，（）表示為完成某個工序所需的時間或資源等數(shù)據(jù)。A.節(jié)點B.弧C.權(quán)D.圓圈答案：C19、網(wǎng)絡(luò)的最大流量應(yīng)（）它的最小割集的容量。A.大于B.等于C.小于D.不大于答案：B20、利用單純形法求解線性規(guī)劃問題時，判斷當(dāng)前解是否為最優(yōu)解的標(biāo)準(zhǔn)為所有非基變量的檢驗數(shù)應(yīng)為（ ）。A.正B.負C.非正D.非

6、負答案：C21、若原問題為無界解，則對偶問題的解是（）。A.無解B,無窮多解C.無界解D.不能確定答案：A22、PERT網(wǎng)絡(luò)圖中，（）表示一個事件，用圓圈和里面的數(shù)字表示。A.節(jié)點C.權(quán)答案：A23、具有7個節(jié)點的樹T的邊恰好為（）條。A. 5C. 7D答案：B24、下列數(shù)學(xué)模型中，（）是線性規(guī)劃模型。MinZ=3xi+X22x3B.2x1+3x2-4x312401+x2+2x3 83xi-x 2+3x3=6xi0,x 2 無約束，x 3W 0B.弧D.關(guān)鍵路線68MaxZ=10 x+x2-3x 3x2i+5x222xj 0, j=1,2,3C.Z=5xi +6x2+8x3-9x 4 D. x

7、i+4x3-x 4=19 x2-5x 3+4x4 30 xi+x2-6x 40,j=1,2,3,4MaxZ=x+4x2-8x 3+x24 x x i+4x3-x 4=29 x2-5x 3+4x4 40 4 xi+x2-6x 40,j=1,2,3,4答案：A25、若線性規(guī)劃問題的最優(yōu)解不唯一，則在最優(yōu)單純形表上A.非基變量的檢驗數(shù)都為零B.非基變量檢驗數(shù)不必有為零者C.非基變量檢驗數(shù)必有為零D.非基變量的檢驗數(shù)都小于零答案：C26、對于總運輸費用最小的運輸問題，若已得最優(yōu)運輸方案，則其中所有空格的檢驗數(shù)均（）。A.非正B.非負C.大于0D.小于0答案：B27、下列步驟中，不屬于目標(biāo)規(guī)劃模型圖解法

8、的為（）。A.作平面直角坐標(biāo)系B.作出目標(biāo)約束所在直線，標(biāo)出偏差方向C.作出目標(biāo)函數(shù)的一族平行線D.按優(yōu)先級次序，確定滿意解答案：C28、下列關(guān)于圖的說法中，錯誤的為（）。A點表示所研究的事物對象B.邊表示事物之間的聯(lián)系C.無向圖是由點及邊所構(gòu)成的圖D.無環(huán)的圖稱為簡單圖答案：D二、判斷題（本大題共34小題，每小題2分，共68分） TOC o 1-5 h z 1、增加約束條件時，線性規(guī)劃模型的可行域不擴大。（）答案：對2、決策變量、目標(biāo)函數(shù)和約束條件是數(shù)學(xué)規(guī)劃模型的三個要素，若目標(biāo)函數(shù)和約束條件均為線性的數(shù)學(xué)規(guī)劃問題稱為非線性規(guī)劃。（）答案：錯3、產(chǎn)地數(shù)與銷地數(shù)相等的運輸問題是產(chǎn)銷平衡運輸問題

9、。（）答案：錯4、能夠通過網(wǎng)絡(luò)的最大可行流稱最大流。（）答案：對5、確定主觀概率常用的方法是專家咨詢法。（）答案：對6、在二人有限對策中，若甲乙雙方的贏得總和不全為零，則稱為二人有限非零和對策。（）答案：對7、完成各個作業(yè)需要的時間最長的路線稱為關(guān)鍵路線。（）答案：對8、線性規(guī)劃問題存在至少一個對偶問題。（）答案：錯9、目標(biāo)函數(shù)和約束函數(shù)都是非線性的數(shù)學(xué)規(guī)劃問題稱為線性規(guī)劃問題。（）答案：錯10、在互為對偶的一對原問題與對偶問題中，不管原問題是求極大或是極小，原問題可行解的目標(biāo)函數(shù)值都一定超過其對偶問題可行解的目標(biāo)函數(shù)值。（）答案：錯11、圖的最小生成樹一定唯一。（） 答案：錯12、動態(tài)規(guī)劃的

10、逆推與順推解法得到不同的最優(yōu)解。答案：錯13、對于線性規(guī)劃標(biāo)準(zhǔn)型，利用單純形求解時，每做一次換基迭代，都能保證它相應(yīng)的目標(biāo)函數(shù)值必為不 TOC o 1-5 h z 減少。（）答案：對14、當(dāng)目標(biāo)規(guī)劃問題模型中存在 X1 +x2 +d= 5的約束條件，則該約束為系統(tǒng)約束。（）答案：錯15、PER刖絡(luò)圖中，事件通常用箭線表示，作業(yè)用圓圈表示。（）答案：錯16、無多重邊的圖稱為簡單圖。（）答案：錯17、運輸問題、最短路問題和求網(wǎng)絡(luò)最大流問題，都可看作是最小費用流的特例。（）答案：對18、目標(biāo)規(guī)劃問題中，權(quán)系數(shù)是定量的概念，數(shù)值越大，表示該目標(biāo)越重要。（）答案：對19、若線性規(guī)劃問題存在可行域，則問題

11、的可行域是凸集。（）答案：對20、目標(biāo)規(guī)劃模型中，應(yīng)同時包含系統(tǒng)約束與目標(biāo)約束。（）答案：錯21、PERT網(wǎng)絡(luò)圖中，任何消耗時間或資源的行動都可稱作作業(yè)。（）答案：對22、任務(wù)分配問題共有 mx m個約束條件。（）答案：錯23、樹枝總長為最短的部分樹稱為圖的最小部分樹。（）答案：對24、目標(biāo)的優(yōu)先級是一個定性的概念，不同優(yōu)先級的目標(biāo)無法從數(shù)量上來衡量。（）答案：對25、單純形法計算中，應(yīng)選取最小正檢驗數(shù)對應(yīng)的變量作為換入變量。（）答案：錯26、當(dāng)目標(biāo)規(guī)劃問題模型中存在 2x1 +x2 4的約束條件，則該約束為目標(biāo)約束。（） 答案：錯27、PERT網(wǎng)絡(luò)圖中，事件消耗一定的時間和資源。（）答案：錯

12、28、在動態(tài)規(guī)劃模型中，問題的階段數(shù)等于問題中的子問題的數(shù)目。（）答案：對29、運輸問題和求網(wǎng)絡(luò)最大流問題，都可看作是最小費用流的特例。（）答案：對30、當(dāng)網(wǎng)絡(luò)中不存在任何增廣鏈時，則網(wǎng)絡(luò)達到最大流狀態(tài)。（）答案：對31、在可行解的狀態(tài)下，原問題與對偶問題的目標(biāo)函數(shù)值是相等的。（）答案：錯32、在解決運輸問題時，采用閉回路法，可以得到運輸問題的基本可行解。（）答案：錯33、在整數(shù)規(guī)劃問題中，若變量取值為0或者1,則為01規(guī)劃問題。（）答案：對34、PER刖絡(luò)圖是由結(jié)點、弧及權(quán)所構(gòu)成的有向圖。（）答案：對三、名詞解釋（本大題共22小題，每小題5分，共110分）1、凸集1.如果n維空間的一個子集

13、S中任意兩點X1、X2連線上的點都在 S中，則稱為凸集。2、存儲策略答案：存儲策略是指決定多長時間補充一次貨物以及每次補充多少數(shù)量的策略。3、無概率決策問題答案：無概率決策問題是指決策人面臨多種決策方案，對每個決策方案對應(yīng)的幾個不同決策狀態(tài)無法估計其出現(xiàn)概率的大小，僅憑個人的主觀傾向和偏好進行方案選擇。4、對策論答案：對策論又被稱為博弈論，它是運籌學(xué)的一個重要分支，主要研究具有競爭或者對抗性質(zhì)的現(xiàn)象和規(guī)律，在經(jīng)濟學(xué)、政治科學(xué)、軍事科學(xué)、進化生物學(xué)以及當(dāng)代的計算機科學(xué)等領(lǐng)域中有廣泛的應(yīng)用。5、可行解答案：求線性目標(biāo)函數(shù)在線性約束條件下的最大值或最小值的問題，統(tǒng)稱為線性約束條件的解叫做可行解。6、

14、關(guān)鍵活動答案：為了完成整個項目的進度計劃，需要找出其中最長的路徑，即關(guān)鍵路徑。關(guān)鍵路徑上的活動稱為項 目的關(guān)鍵活動。7、增廣鏈答案：由發(fā)點到收點之間的一條鏈，如果在前向弧上滿足流量小于容量，即fij0,則稱這樣的鏈為增廣鏈。8、局勢答案：局勢是指在一局對策中，每個局中人從其策略集中各取出一個策略參與對策，這些策略合起來稱為一個局勢。9、線性規(guī)劃的建模答：線性規(guī)劃的建模是指將用語言文字描述的應(yīng)用問題轉(zhuǎn)化為用線性規(guī)劃模型描述的數(shù)學(xué)問題。10、靈敏度分析答：靈敏度分析是分析研究一個線性規(guī)劃模型中的參數(shù)A,b,C取值的變化對最優(yōu)解或最優(yōu)基的影響。11、基礎(chǔ)圖答：若把一個有向圖 D中所有弧的方向去掉，即

15、每一條弧都有相應(yīng)的無向邊替代，所得到一個無向圖稱為該有向圖D的基礎(chǔ)圖。12、納什均衡答：在一局二人有限非零和對策中，無論對方的策略如何選擇，本方都會選擇某個確定的策略，則該策略被稱為支配性策略。而由雙方各自的支配性策略所構(gòu)成的這個局勢，就被定義為納什均衡。13、正偏差變量答案：正偏差變量指實際值超出目標(biāo)值的差距。14、作業(yè)的最早開始時間答案：作業(yè)的最早開始時間是它的各項緊前作業(yè)最早結(jié)束時間中的最大一個值。15、連通圖答案：若一個圖中，任意兩點之間至少存在一條鏈，稱這樣的圖為連通圖。16、0-1規(guī)劃問題答案：在整數(shù)規(guī)劃問題中，若變量取值為0或者1,則為0-1規(guī)劃問題。17、負偏差變量答案：負偏差

16、變量指實際值未達到目標(biāo)值的差距。18、作業(yè)的最遲結(jié)束時間答案：作業(yè)的最遲結(jié)束時間是它的各項緊后作業(yè)最遲開始時間中的最小一個。19、最小割答案：網(wǎng)絡(luò)中所有割集中容量之和為最小的一個割集。20、偏差變量答案：偏差變量指實際值與目標(biāo)值的差距。d+表示實際值超出目標(biāo)值的差距；d-表示實際值未達到目標(biāo)值的差距。21、圖答案：圖是指點 V和邊E的集合，用以表示對某種現(xiàn)實事物的抽象。其中點表示所研究的事物對象；邊表 示事物之間的聯(lián)系。22、容量網(wǎng)絡(luò)答案：容量網(wǎng)絡(luò)指對網(wǎng)絡(luò)上的每條?。╒i, Vj）都給出一個最大的通過能力，稱為該弧的容量，記為C（Vi,Vj ）,簡稱容量。以 Cij表不。四、簡答題（本大題共5

17、小題，每小題10分，共50分）1、簡述何謂最小支撐樹問題，最小支撐樹問題的常用方法有哪些。答：如何找出網(wǎng)絡(luò)的最小樹就是最小支撐樹問題。最小支撐樹問題可以采用避圈法和破圈法等方法進行求解，也可借助相關(guān)的運籌學(xué)軟件包進行求解。2、簡述產(chǎn)銷平衡運輸問題的數(shù)學(xué)模型？答：具有m個產(chǎn)地ai （ i =1,2,，m）和n個銷地bj（ j =1,2,，n）的運輸問題的數(shù)學(xué)模型為m nmin z 二:二 Wij Xiji m j Tl mZ Xij = bj ,（j = 1,2, n）iT ns.t. Z Xij =ai, （i =1,2 m） jmXj之0對于產(chǎn)銷平衡問題有 nm bj = ai j 1i 1

18、運輸問題有mn個決策變量， m + n個約束條件。由于產(chǎn)銷平衡條件，只有m+n-1個相互獨立，因此，運輸問題的基變量只有m - n -1個。3、簡述樹的性質(zhì)？答：（1）任何樹必存在次數(shù)為 1的點；（2）具有n個節(jié)點的樹T的邊恰好為 n -1條；（3）任何有n個節(jié)點，n ,1條邊的連通圖必是一棵樹。4、簡述整數(shù)規(guī)劃的求解方法有哪些？答：整數(shù)規(guī)劃的求解方法包括：（1）圖解法；（2）分枝定（限）界法；（3）割平面法；（4）匈牙利法；（5）隱枚舉法。5、簡述網(wǎng)絡(luò)圖的繪制原則和注意事項？答：（1）節(jié)點標(biāo)號原則：箭頭節(jié)點的標(biāo)號要大于箭尾節(jié)點的標(biāo)號。（2）兩個節(jié)點之間只能表示一道工序，只能劃一條箭線。作業(yè)和

19、箭線是一對一的關(guān)系。（3）全圖只有一個起點、一個終點。（4）不能出現(xiàn)缺口與回路。（5）各項作業(yè)之間的關(guān)系：1）作業(yè)a結(jié)束后可以開始 b和c2）作業(yè)c在a和b均結(jié)束后才能開始RYCr3） ab兩項作業(yè)結(jié)束后才可以開始 c和d4)作業(yè)c在a結(jié)束后即可進行，但作業(yè) d必須同時在a和b結(jié)束后才能開始(6)從左到有，從上到下，盡量避免交叉。五、計算題(本大題共3小題，每小題20分，共60分)1、某一最大化線性規(guī)劃問題在利用單純形法計算時得到表1。其中a,b,c,d,e, f為未知數(shù)，原問題中要求各變量均非負。問a,b,c,d,e, f應(yīng)滿足什么條件下，有下面各解成立？表1CBX BbX1X2X3X4X5

20、X6X3f7c10e0X42-1-501-10X66a-300-41cj -zjbd00-30(1)是非可行解；(2)是唯一最優(yōu)解；(3)有無窮多最優(yōu)解；(4)是退化基可行解；(5)是可行解但非最優(yōu)解，只有人可以為換入變量且換出變量必為X6。解：(1)當(dāng)所有基變量取值均非負時的基解才是可行基解，故當(dāng) f 0,b 0,d 0,d =0,b0o（4）現(xiàn)行解為退化基可行解的條件是基變量中含有零分量且所有的檢驗數(shù)均非正。所以 b 0,d 0,d 0 ；只有x6f6f6可以為換出變量，所以有故參數(shù)應(yīng)滿足：f之0,b A0,d M0 , o7a7a2、已知：（1）運輸問題的供需關(guān)系與單位運價表（見表 1）

21、;（2）用最小元素法求得表 1的初始調(diào)運方案（見表 2）;試用閉回路法求其檢驗數(shù)，并判斷此初始調(diào)運方案是否最優(yōu)。表1供需關(guān)系與單位運價表肖地產(chǎn)地甲乙丙丁132765027523603254525銷量60402015表2初始調(diào)運方案產(chǎn)地甲乙丙丁110405022520156032525銷量60402015解：先找出各非基變量的閉回路，即從表2的某一空格（非基變量）為起點，用水平或垂直線，只有碰到數(shù)字格（基變量）后才旋轉(zhuǎn) 90：繼續(xù)向前劃，直到回到起始空格為止。檢驗數(shù)的計算，就是從空格對應(yīng)的單位運價開始，對閉回路所對應(yīng)的單位運價交替地賦予“+”和“-”號，并計算它們的代數(shù)和，如表 3所示。表3空格

22、閉回路檢驗數(shù)（1丙）（1 丙）一（2 丙）一（2 甲）一（1 甲）一（1 丙）7-2+7-3=9（1 丁）（1 ?。┮唬?2丁）一（ 2 甲）一（1 甲）一（1 ?。?-3+7-3=7（2乙）（2 乙）一（2 甲）一（1 甲）一（1 乙）一（2 乙）5-7+3-2=-1（3乙）（3 乙）-（3 甲）-（1 甲）-（1 乙）-（3 乙）5-2+3-2=4（3丙）（3 丙）-（3 甲）-（2 甲）-（2 丙）-（3 丙）4-2+7-2=7（3 丁）（3 ?。?（3 甲）-（2 甲）-（2 丁）-（3 ?。?-2+7-3=7選出檢驗數(shù)最小的為（-1 ）,小于0,所以該初始調(diào)運方案不是最優(yōu)調(diào)運方案。3

23、、試用單純形法解下列線性規(guī)劃問題max z = x1 2x22x1 2x2 . 8s.t. J0 x1 + 2x2 0解：化標(biāo)準(zhǔn)形，找一個單位矩陣作為基，列出初始單純形表max z = x1 2x2 0 x3 0 x42x1 2x2 x3=8st. 0 x1 十 2x2+ x4 = 4x1, x2, x3,刈2 0建立初始單純形表o 11 o2 22 o_-A如表1所示，其中Cj為目標(biāo)函數(shù)中決策變量 Xj的系數(shù)（j =1,2,3,4）,由系數(shù)矩陣選擇單位矩陣B1= 1 0 作為初始可行基，則對應(yīng)的基變量為XB =（x3, x4）T ,基變量的系數(shù)CB=（0,：0 1 一0）,常數(shù)向量（資源向量

24、）b =（8,4）T ,列出約束方程組的增光矩陣 bA.（注：XB所對應(yīng)的列的變量（x3,X4）為基變量，其余的變量都為非基變量）計算初始單純形表中的檢驗數(shù)Cj1200b/ =6./ aik1CbX BbXiX2X3X40X3822108/2=40X440【2】014/2=2 tCj -Zj1200表2進行迭代運算，得出下一個單純形表，對增廣矩陣進行線性變換，將主元素變?yōu)镃j -Zj =Cj -CBB-Pj=Cj CbR，如非基變量 刈*2的檢驗數(shù):C14=0 CBP(1)=1- (0 0)L- (0*2+0*2) =10C2_Z2=C2 CbP2=2- (0 0)1=2- (0*2+0*2)