運籌學考試資料

1、大工15秋運籌學開卷考試期末復習資料一、單項選擇題大工15秋運籌學開卷考試期末復習資料 第1頁 共16頁1、下列敘述正確的是（ ）。A線性規(guī)劃問題，若有最優(yōu)解，則必是一個基變量組的可行基解B線性規(guī)劃問題一定有可行基解C線性規(guī)劃問題的最優(yōu)解只能在最低點上達到D單純形法求解線性規(guī)劃問題時，每換基迭代一次必使目標函數(shù)值下降一次答案：A2、數(shù)學規(guī)劃的研究對象為（ ）。A數(shù)值最優(yōu)化問題 B最短路問題 C整數(shù)規(guī)劃問題 D最大流問題答案：A3、下列方法中可以用來求解部分樹的方法的為（ ）。大工運籌學課程考試試卷（A） 第3頁 共16頁A閉回路法 B破圈法 C踏石法 D匈牙利算法答案：B4、把各種備選方案、可

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

3、樂觀準則 B折中準則 C等可能準則 D最大后悔值準則答案：D9、以下說法中不正確的為（ ）。A完成各個作業(yè)需要的時間最長的路線為關鍵路線 B關鍵路線上的作業(yè)稱為關鍵作業(yè)C所有關鍵作業(yè)的總時差為0 D以上說法均不正確答案：D10、（ ）也稱小中取大準則。這是一種在不確定型決策問題中，充分考慮可能出現(xiàn)的最小收益后，在最小收益中再選取最大者的保守決策方法。A悲觀準則 B折中準則 C等可能準則 D后悔值準則答案：A11、當某個非基變量檢驗數(shù)為零，則該問題有（ ）。大工15秋運籌學開卷考試期末復習資料 第2頁 共16頁A無解B無窮多最優(yōu)解C退化解D惟一最優(yōu)解答案：B12、假設對于一個動態(tài)規(guī)劃問題，應用順

4、推法以及逆推解法得出的最優(yōu)解分別為P和D，則有（ ）。AP>DBP<DCP=DD不確定答案：C13、下列有關線性規(guī)劃問題的標準形式的敘述中錯誤的是（ ）。大工運籌學課程考試試卷（C） 第3頁 共16頁A目標函數(shù)求極大B約束條件全為等式C約束條件右端常數(shù)項全為正D變量取值全為非負答案：C14、運輸問題的基變量有（ ）個。大工運籌學課程考試試卷（A） 第3頁 共16頁Am×nBm+n-1Cm+nD不確定答案：B15、目標規(guī)劃的目標權系數(shù)是定量的概念，數(shù)值（ ），表示該目標越重要。大工運籌學課程考試試卷（C） 第3頁 共16頁A越小B越大C為0D為正答案：B16、下列敘述正確的

5、是（ ）。A線性規(guī)劃問題，若有最優(yōu)解，則必是一個基變量組的可行基解B線性規(guī)劃問題一定有可行基解C線性規(guī)劃問題的最優(yōu)解一定唯一D單純形法求解線性規(guī)劃問題時，每換基迭代一次必使目標函數(shù)值下降一次答案： A17、設M是線性規(guī)劃問題，N是其對偶問題，則（ ）不正確。AM有最優(yōu)解，N不一定有最優(yōu)解B若M和N都有最優(yōu)解，則二者最優(yōu)值肯定相等C若M無可行解，則N無有界最優(yōu)解DN的對偶問題為M答案： A18、PERT 網(wǎng)絡圖中，（ ）表示為完成某個工序所需的時間或資源等數(shù)據(jù)。大工15秋運籌學開卷考試期末復習資料 第3頁 共16頁A節(jié)點B弧C權D圓圈答案： C19、網(wǎng)絡的最大流量應（ ）它的最小割集的容量。A大

6、于B等于C小于D不大于答案： B20、利用單純形法求解線性規(guī)劃問題時，判斷當前解是否為最優(yōu)解的標準為所有非基變量的檢驗數(shù)應為（ ）。大工運籌學課程考試試卷（B） 第4頁 共16頁A正B負C非正D非負答案：C21、若原問題為無界解，則對偶問題的解是（ ）。A無解B無窮多解C無界解D不能確定答案：A22、PERT 網(wǎng)絡圖中，（ ）表示一個事件，用圓圈和里面的數(shù)字表示。大工15秋運籌學開卷考試期末復習資料 第4頁 共16頁A節(jié)點B弧C權D關鍵路線答案：A23、具有 7個節(jié)點的樹 T 的邊恰好為（ ）條。A5B6C7 D8答案：B24、下列數(shù)學模型中，（ ）是線性規(guī)劃模型。MaxZ=10x1+x2-3

7、x3x21+5x215x1-8x2+3x322xj0, j=1,2,3A. MinZ=3x1+x22x3 B. 2x1+3x2-4x312 4x1+x2+2x38 3x1-x2+3x3=6 x10,x2無約束,x30Z=5x1+6x2+8x3-9x4x1+4x3-x4=19x2-5x3+4x430x1+x2-6x49xj0,j=1,2,3,4MaxZ=x1+4x2-8x3+x24 x1+4x3-x4=29x2-5x3+4x440x1+x2-6x419xj0,j=1,2,3,4 C. D. 答案：A25、若線性規(guī)劃問題的最優(yōu)解不唯一，則在最優(yōu)單純形表上（ ）。大工運籌學課程考試試卷（A） 第5頁

8、 共16頁A非基變量的檢驗數(shù)都為零B非基變量檢驗數(shù)不必有為零者C非基變量檢驗數(shù)必有為零D非基變量的檢驗數(shù)都小于零答案：C26、對于總運輸費用最小的運輸問題，若已得最優(yōu)運輸方案，則其中所有空格的檢驗數(shù)均（ ）。大工運籌學課程考試試卷（A） 第5頁 共16頁A非正B非負C大于0D小于0答案：B27、下列步驟中，不屬于目標規(guī)劃模型圖解法的為（ ）。大工運籌學課程考試試卷（A） 第5頁 共16頁A作平面直角坐標系B作出目標約束所在直線，標出偏差方向C作出目標函數(shù)的一族平行線D按優(yōu)先級次序，確定滿意解答案：C28、下列關于圖的說法中，錯誤的為（ ）。第5頁 共16頁A點表示所研究的事物對象B邊表示事物之

9、間的聯(lián)系C無向圖是由點及邊所構成的圖D無環(huán)的圖稱為簡單圖答案：D二、判斷題1、增加約束條件時，線性規(guī)劃模型的可行域不擴大。（ ）答案：對2、決策變量、目標函數(shù)和約束條件是數(shù)學規(guī)劃模型的三個要素，若目標函數(shù)和約束條件均為線性的數(shù)學規(guī)劃問題稱為非線性規(guī)劃。（ ）答案：錯3、產(chǎn)地數(shù)與銷地數(shù)相等的運輸問題是產(chǎn)銷平衡運輸問題。（ ）答案：錯4、能夠通過網(wǎng)絡的最大可行流稱最大流。（ ）答案：對5、確定主觀概率常用的方法是專家咨詢法。（ ）答案：對6、在二人有限對策中，若甲乙雙方的贏得總和不全為零，則稱為二人有限非零和對策。（ ）答案：對7、增加約束條件時，線性規(guī)劃模型的可行域不擴大。（ ）答案：對8、線性

10、規(guī)劃問題存在至少一個對偶問題。（ ）答案：錯9、產(chǎn)地數(shù)與銷地數(shù)相等的運輸問題是產(chǎn)銷平衡運輸問題。（ ）大工15秋運籌學開卷考試期末復習資料 第6頁 共16頁答案：錯10、在互為對偶的一對原問題與對偶問題中，不管原問題是求極大或是極小，原問題可行解的目標函數(shù)值都一定超過其對偶問題可行解的目標函數(shù)值。（ ）答案：錯11、圖的最小生成樹一定唯一。（ ）答案：錯12、動態(tài)規(guī)劃的逆推與順推解法得到不同的最優(yōu)解。（ ）答案：錯13、對于線性規(guī)劃標準型，利用單純形求解時，每做一次換基迭代，都能保證它相應的目標函數(shù)值必為不減少。（ ）答案：對14、當目標規(guī)劃問題模型中存在的約束條件，則該約束為系統(tǒng)約束。（ ）

11、答案：錯15、PERT 網(wǎng)絡圖中，事件通常用箭線表示，作業(yè)用圓圈表示。（ ）答案：錯16、無多重邊的圖稱為簡單圖。（ ）答案：錯17、運輸問題、最短路問題和求網(wǎng)絡最大流問題，都可看作是最小費用流的特例。（ ）答案：對18、目標規(guī)劃問題中，權系數(shù)是定量的概念，數(shù)值越大，表示該目標越重要。（ ）答案：對19、若線性規(guī)劃問題存在可行域，則問題的可行域是凸集。（ ）答案：對20、目標規(guī)劃模型中，應同時包含系統(tǒng)約束與目標約束。（ ）答案：錯21、PERT 網(wǎng)絡圖中，任何消耗時間或資源的行動都可稱作作業(yè)。（ ）答案：對22、任務分配問題共有m×m個約束條件。（ ）答案：錯23、樹枝總長為最短的部

12、分樹稱為圖的最小部分樹。（ ）答案：對24、目標的優(yōu)先級是一個定性的概念，不同優(yōu)先級的目標無法從數(shù)量上來衡量。（ ）答案：對25、單純形法計算中，應選取最小正檢驗數(shù)對應的變量作為換入變量。（ ）答案：錯26、當目標規(guī)劃問題模型中存在的約束條件，則該約束為目標約束。（ ）答案：錯27、PERT 網(wǎng)絡圖中，事件消耗一定的時間和資源。（ ）答案：錯28、在動態(tài)規(guī)劃模型中，問題的階段數(shù)等于問題中的子問題的數(shù)目。（ ）答案：對29、運輸問題和求網(wǎng)絡最大流問題，都可看作是最小費用流的特例。（ ）答案：對30、當網(wǎng)絡中不存在任何增廣鏈時，則網(wǎng)絡達到最大流狀態(tài)。（ ）答案：對31、在可行解的狀態(tài)下，原問題與對

13、偶問題的目標函數(shù)值是相等的。（ ）大工15秋運籌學開卷考試期末復習資料 第7頁 共16頁答案：錯32、在解決運輸問題時，采用閉回路法，可以得到運輸問題的基本可行解。（ ）大工運籌學課程考試試卷（A） 第7頁 共16頁答案：錯33、在整數(shù)規(guī)劃問題中，若變量取值為0或者1，則為01規(guī)劃問題。（ ）大工運籌學課程考試試卷（A） 第7頁 共16頁答案：對34、PERT網(wǎng)絡圖是由結點、弧及權所構成的有向圖。（ ）大工運籌學課程考試試卷（A） 第8頁 共16頁答案：對35、完成各個作業(yè)需要的時間最長的路線稱為關鍵路線。（ ）大工運籌學課程考試試卷（A） 第8頁 共16頁答案：對三、名詞解釋題1、凸集1如果

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

15、可行解。6、關鍵活動答案：為了完成整個項目的進度計劃，需要找出其中最長的路徑，即關鍵路徑。關鍵路徑上的活動稱為項目的關鍵活動。7、增廣鏈答案：由發(fā)點到收點之間的一條鏈，如果在前向弧上滿足流量小于容量，即fij<cij，后向弧上滿足流量大于0，即fij>0，則稱這樣的鏈為增廣鏈。8、局勢答案：局勢是指在一局對策中，每個局中人從其策略集中各取出一個策略參與對策，這些策略合起來稱為一個局勢。9、線性規(guī)劃的建模答：線性規(guī)劃的建模是指將用語言文字描述的應用問題轉化為用線性規(guī)劃模型描述的數(shù)學問題。10、靈敏度分析答：靈敏度分析是分析研究一個線性規(guī)劃模型中的參數(shù)A,b,C取值的變化對最優(yōu)解或最優(yōu)

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

17、取值為0或者1，則為0-1規(guī)劃問題。17、負偏差變量答案：負偏差變量指實際值未達到目標值的差距。18、作業(yè)的最遲結束時間答案：作業(yè)的最遲結束時間是它的各項緊后作業(yè)最遲開始時間中的最小一個。19、最小割答案：網(wǎng)絡中所有割集中容量之和為最小的一個割集。20、偏差變量答案：偏差變量指實際值與目標值的差距。d+表示實際值超出目標值的差距；d-表示實際值未達到目標值的差距。21、圖答案：圖是指點V和邊E的集合，用以表示對某種現(xiàn)實事物的抽象。其中點表示所研究的事物對象；邊表示事物之間的聯(lián)系。22、容量網(wǎng)絡答案：容量網(wǎng)絡指對網(wǎng)絡上的每條弧(vi，vj)都給出一個最大的通過能力，稱為該弧的容量，記為c(vi，

18、vj)，簡稱容量。以cij表示。23、狀態(tài)答案：狀態(tài)指某階段初始狀況。既反映前面各階段決策的結局，又是本階段作出決策的出發(fā)點和依據(jù)。是動態(tài)規(guī)劃中各階段信息的傳遞點和結合點。四、簡答題1、簡述線性規(guī)劃四條基本假設的內(nèi)容。答：(1)比例性：要求每個決策變量在目標函數(shù)和約束函數(shù)中，其貢獻與決策變量的值存在直接比例性。 (2)連續(xù)性：指所有的決策變量取值為連續(xù)的數(shù)。 (3)確定性：指線性規(guī)劃中所有目標函數(shù)和約束函數(shù)中的系數(shù)都是確定的常數(shù)，不含隨機因素。 (4)可加性：指所有決策變量對目標函數(shù)和約束函數(shù)的貢獻是相互獨立的（包括正向貢獻和負向貢獻），目標函數(shù)值等于每個決策變量各自對目標函數(shù)貢獻的總和。 2

19、、簡述網(wǎng)絡計劃優(yōu)化的思路與注意事項。答：（1）優(yōu)先關注單位時間緊縮成本最小的關鍵活動進行緊縮。（2）注重關鍵路徑可能的變化。（3）充分利用非關鍵活動的松弛變量，合理調配資源。3、簡述線性規(guī)劃的建模包括哪些內(nèi)容。答：（1）決策變量的識別與描述；（2）目標函數(shù)的識別與描述；（3）約束條件的識別與描述。4、簡述決策樹方法的具體步驟。答：具體步驟:（1）畫一個方框作為出發(fā)點，稱為決策點。從決策點畫出若干條直線或折線，每條線代表一個行動方案，這樣的直（折）線，稱為方案枝。（2）在各方案枝的末端畫一個圓圈，稱為狀態(tài)點，從狀態(tài)點引出若干條直線或折線，每條線表示一種狀態(tài)，在線旁邊標出每一狀態(tài)的概率，稱為概率枝

20、。（3）把各方案在各種狀態(tài)下的損益值標記在概率枝的末端。（4）把計算得到的每個方案的損益期望值標在狀態(tài)點上，然后，通過比較，選出收益期望值最大（或損失期望值最?。┑姆桨缸鳛樽顑?yōu)方案。5、簡述單純形法的基本思路。答：基本思路：確定可行域中的一個極點作為初始點（初始基本可行解），判斷此極點是否為最優(yōu)解，如不是則再找另一個使得其目標函數(shù)值更優(yōu)的極點（稱之為迭代），再判斷此極點是否為最優(yōu)解，直到找到一個極點為其最優(yōu)解，或能判斷出LP問題無最優(yōu)解為止。 6、簡述何謂最小支撐樹問題，最小支撐樹問題的常用方法有哪些。答：如何找出網(wǎng)絡的最小樹就是最小支撐樹問題。 最小支撐樹問題可以采用避圈法和破圈法等方法進行

21、求解，也可借助相關的運籌學軟件包進行求解。7、簡述產(chǎn)銷平衡運輸問題的數(shù)學模型？答：具有個產(chǎn)地（）和個銷地（）的運輸問題的數(shù)學模型為對于產(chǎn)銷平衡問題有運輸問題有個決策變量，個約束條件。由于產(chǎn)銷平衡條件，只有個相互獨立，因此，運輸問題的基變量只有個。8、簡述樹的性質？答：（1）任何樹必存在次數(shù)為 1 的點；（2）具有個節(jié)點的樹 T 的邊恰好為 -1 條；（3）任何有個節(jié)點，-1 條邊的連通圖必是一棵樹。9、簡述整數(shù)規(guī)劃的求解方法有哪些？答：整數(shù)規(guī)劃的求解方法包括：（1）圖解法；（2）分枝定（限）界法；（3）割平面法；（4）匈牙利法；（5）隱枚舉法。10、簡述網(wǎng)絡圖的繪制原則和注意事項？答：（1）節(jié)

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

23、300-4100-30（1）是非可行解；（2）是唯一最優(yōu)解；（3）有無窮多最優(yōu)解；（4）是退化基可行解；（5）是可行解但非最優(yōu)解，只有可以為換入變量且換出變量必為。解：（1）當所有基變量取值均非負時的基解才是可行基解，故當時，表中是非可行解。（2）當現(xiàn)行解為可行解，且對應的非基變量的檢驗數(shù)均小于0時，線性規(guī)劃問題才有唯一最優(yōu)解，即。（3）當所有非基變量檢驗數(shù)都小于等于0且其中存在一個非基變量檢驗數(shù)等于0，而在的系數(shù)列向量中有大于0的分量時有無窮多最優(yōu)解。所以或。（4）現(xiàn)行解為退化基可行解的條件是基變量中含有零分量且所有的檢驗數(shù)均非正。所以。（5）因是可行解，所以有；非最優(yōu)解且只有可以為換入變量

24、，所以有；只有可以為換出變量，所以有，故參數(shù)應滿足：，。2、已知：（1）運輸問題的供需關系與單位運價表（見表1）； （2）用最小元素法求得表1的初始調運方案（見表2）；試用閉回路法求其檢驗數(shù)，并判斷此初始調運方案是否最優(yōu)。表1 供需關系與單位運價表 銷地產(chǎn)地甲乙丙丁產(chǎn)量132765027523603254525銷量60402015表2 初始調運方案 銷地產(chǎn)地甲乙丙丁產(chǎn)量110405022520156032525銷量60402015 解：先找出各非基變量的閉回路，即從表2的某一空格（非基變量）為起點，用水平或垂直線，只有碰到數(shù)字格（基變量）后才旋轉，繼續(xù)向前劃，直到回到起始空格為止。檢驗數(shù)的計算

25、，就是從空格對應的單位運價開始，對閉回路所對應的單位運價交替地賦予“+”和“-”號，并計算它們的代數(shù)和，如表3所示。 表3空格閉回路檢驗數(shù)（1丙）（1丙）（2丙）（2甲）（1甲）（1丙）7-2+7-3=9（1?。??。??。?甲）（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?。?甲）（2甲）（2丁）（3?。?-2+7-3=7 選出檢驗數(shù)最小的為（-1），小于0，所以該初始調運方案不是最優(yōu)調運方案。 3、試用單純形法解下列線性規(guī)劃問題。解：化標準形，找一個單位矩陣作為基，列出初始單純形表 建立初始單純形表表11200082210040201如表1所示，其中為目標函數(shù)中決策變量的系數(shù)（），由系數(shù)矩陣選