1、北京交通大學 942 管理運籌學 2011 年真題一(每題 1分，共 15 分)判斷(1) . 線性規劃問題的基可行解和其可行域的頂點是一一對 應的；(2) 若x(1), ?梓)分別是某一線性規劃問題的 最優解，則 x=?1)+?2)也是該線性規劃問題的最優解，其中 ？，? 為正的實數；(3) 若線性規劃的對偶問題有最優解，則原線性規劃問題也 一定有最優解，反之亦然；( 4)用割平面法求整數規劃時，構造的割平面有可能切去一些不屬于最優解的整數可行解；(5) 運輸問題系數矩陣的某行元素同時加上一個任意常數k， 都不影響最優方案；(6) 如果圖T是樹，則T中一定存在至少兩個頂點，它們的 次為 1；

2、(7) 用 Dijkstra 算法只能求解非負權圖中兩點 2 之間的最 短路，而 Floyd 算法怎能求解任意賦權圖中任意兩點之間的 最短路問題；( 8)網絡圖中任何一個結點都表示前一工序的結束和后一 工序的開始；( 9)結點最早時間同最遲時間相等的點連接的線路就是關 鍵線路；10）假如到達排隊系統的顧客來自兩個方面，分別服從普阿松分布，則這兩部分顧客合起來的顧客流仍然服從同一普 阿松分布；（11）運輸問題也是線性規劃模型，因而運輸問題有可能存 在最優解，也有可能不存在最優解；（12）只要能將所研究的問題分解成多個不同階段，就一定 可以用動態規劃方法求出其最優解；（13）隱枚舉法是一種特殊的分

3、支定界法，它適用于任何 01 規劃問題；（14）指派問題效率矩陣 A的元素可分成0與非0元素兩部 分，覆蓋 0 元素的最少直線數等于位于不同行不同列 0 元素 的最大個數；（15）機器負荷分配問題中，始終固定終端自由的生產效率 要比始端固定終端也固定的生產效率低。二 . 下列每一個問題中至少有一個說法是正確的， 共有 20 個 說法正確，請把 20 個正確說法找出來，超過 20 個時按題順 序取前 20 個為準，每個 1.5 分，共 30 分）1. 當極大化LP問題單純性表的基底 B變為？時，則祁變為 岔1 b，岔1 b>0而？?孑？?1 N中存在正數，則（）說法正確。A. 基*?對應的

4、解是最優解，最優解時？?=?b;B. 基 彩寸應的解是基可行解；C. 用單純形法繼續計算一定可在有限步求得最優解；2. 在（m+n個約束條件的運輸問題中，下述（ ）回答是正 確的。A. 恰有m+n-1個是獨立的；B. 至多有m+n-1個是獨立的；C. 恰有m+n個是獨立的；D. 至多有m+n個是獨立的；3. 用分支定界法解整數規劃（LP）時，下列（）說法是正 確的。A 產生分枝問題就是將松弛問題可行域進行分割，舍去那些 不含原問題解的區域；B. 任一分支問題解的目標值都代表該分支問題所含整數解 的目標值上限，所有分支問題中最優者若是整數解，則必為 原問題最優解；C. 若所有分支問題無可行解，則

5、原問題也無可行解；D. 若多個分支問題無整數解，則原問題無最優解。4. 動態規劃求解問題時，下列（ ）說法是正確的。A. 無論初始狀態和初始決策如何，對于當前狀態和決策而言 余下的決策必須構成最優策略；B. 整體最優局部必然最優，因此所有構成策略的子策略最優 時整體也應該最優；C. 動態規劃就是把問題分成階段，根據狀態轉移方程徐兆最優指標的子策略，從終點逐步到始點優化的過程；D. 策略與決策實際上是一回事。5. 對于圖，下列（ ）說法正確。A. 任何圖，次為奇數的節點個數必為偶數；B. 任意兩個節點直接有且只有一條路相通的是樹；C. 一棵具有 p 個節點的樹有且僅有 q=p-1 條邊，任何具有

6、 p 個節點和 p-1 條邊的圖就是一棵樹D. 從圖的任何一個生成樹開始，通過有限步連續的樹基本變 換可以得到圖的每一個生成樹，其中邊數最少的生成樹就是 最小生成樹。6. 關于帶收發點的容量網絡中從出發點到收點的一條增廣 鏈，以下（ ）敘述正確。A. 增廣路上的有向邊的方向必須是從發點指向收點的；B. 增廣路上的有向邊必須都是不飽和邊；C. 增廣路上不能有零流邊；D. 增廣路上與發點到收點方向的有向邊不能是飽和邊，相反 方向的有向邊不能是零。7. 線性規劃問題最優基中某個基變量的目標系數發生變化， 則（ ）正確。A. 該基變量的檢驗數必然為零；B. 其他基變量的檢驗數可能變化；C. 所有非基變

7、量檢驗數均可能變化；D. 所有變量檢驗數都可能變化。8. 排隊論中，下列（）說法正確。A. 系統容量有限制時有效到達率心和 洽義不同，卩（1-?）B. M/M/C系統與C個M/M/1系統比較，一般來說后者服務效率略好且更有靈活性；C. （p-k ）公式適用于 M/G/1模型，正確寫法為?= p+?+?T2（1-?）D. k個串聯服務站服務時間？?相互獨立且服從相同的指數分一一?=T則布?服從k階愛爾朗分布9. 設線性規劃問題 max Z=CX AX=b, X>0，則其對偶問題為min W=Yb YA>C, 丫 （- , +）,下列說法正確的是（）。A. 若X和丫是原問題和對偶問題的

8、可行解，則必有CX>Yb;B. 問題的第k個約束乘以常數 入（入工0），則對偶問題的解 ?=入?丫=入?1 ;C. 將目標函數改變為 max Z=2CX （入工0）,則對偶問題的解 ?=入?丫二入?1 ;D. 模型中全部？?用3?代替，則對偶問題解中必然 ?=3?10. 對線性規劃而言，下列說法正確的是（）A. 若R有界凸集，則任意一點 x?R可表示為R的定點的凸組 合；B. 線性規劃可行域是凸集，則頂點的個數是有限的，因而總可以在有限步內找到全部基本最優解；?C. 線性規劃可行解 x= (?,?,?)為基本可行解的充 要條件是 X 正分量所對應的系數列向量是線性獨立的；D. 如果線性規

9、劃的最優解不唯一，則最優解集合是凸集。三( 30 分)已知線性規劃模型為：Max Z=10x1+5x23? + 4? < 9 5? + 2? < 8?, ? > 0( 1) 用單純形法求該線性規劃模型的最優解；( 2) 寫出該線性規劃問題的對偶問題， 并求對偶問題的最 優解；(3) 試問 ?1?， ?2?分別在什么范圍內變化時，上述最優解不 變；(4) 試問 ?1?在什么范圍變化時，上述最優解不變；(5) 如果目標函數變為 Max Z=12x1 +4x2，試討論最優解 的變化情況；(6) 如果約束條件右端資源由 9變為11，試討論最819優解的變化情況。四. (20分)鐵路部

10、門計劃在市內 A B、C三個區設立售票處，每個區至少一家，所得收入如下表所示：-票處數區1234A200280330340B210220225230C180230260280問：售票處如何分配，是總收入最大？（要求寫出動態規劃模型的基本要素并求解）五. （15分）下圖為路網示意圖，圖中數字為距離（km），假設從天津、豐臺、鄭州、徐州調運某種物資到石家莊、 德州、邯鄲、濟南、青島等地，天津、豐臺、鄭州、徐州 可調出這種物資的數量分別為 9、10、7、9,（萬噸），石家 莊、德州、邯鄲、濟南、青島的需求量分別為6、15、3、3、8 （萬噸）試求最優調運方案。六. （20分）有三個工廠？?，？，？，

11、它們生產同一種設 備，供應？?，？?，？?地，設工廠？?，?, ?的生產能力分別 是40臺、20臺和10臺。？?，?, ?的需求分別是15臺、 25臺和10臺，運輸網絡如下圖所示，弧旁邊數字為容量。 試確定？?，？，？?各生產設備多少臺，能通過這個網絡運達 ?, ?，?并問有哪幾種生產和調運方案？?520101050610102010*62030?七. (10分)某公司要從？,？,？?0十個可供選擇的投資項目中確定五個投資對象，使總投資額最少。假設十個 項目的投資額，分別為 ? ?,？命且在項目的選擇上要 滿足下列限制條件：(1) 選擇了 ？,？就不能選擇?，反之亦然；(2) 在?,?,?,?中最多只能選擇 3個。八. (10分)考慮一個鐵路列車編組站，設待編列車到達時 間間隔服從負指數分布，平均 2列/小時，服務臺是編組 站，服務時間服從負指數分布，平均每 20分鐘可服