(完整版)北京交通大學(xué)942真題2011

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

2、(7) 用 Dijkstra 算法只能求解非負(fù)權(quán)圖中兩點(diǎn) 2 之間的最 短路，而 Floyd 算法怎能求解任意賦權(quán)圖中任意兩點(diǎn)之間的 最短路問(wèn)題；( 8)網(wǎng)絡(luò)圖中任何一個(gè)結(jié)點(diǎn)都表示前一工序的結(jié)束和后一 工序的開(kāi)始；( 9)結(jié)點(diǎn)最早時(shí)間同最遲時(shí)間相等的點(diǎn)連接的線(xiàn)路就是關(guān) 鍵線(xiàn)路；10）假如到達(dá)排隊(duì)系統(tǒng)的顧客來(lái)自?xún)蓚€(gè)方面，分別服從普阿松分布，則這兩部分顧客合起來(lái)的顧客流仍然服從同一普 阿松分布；（11）運(yùn)輸問(wèn)題也是線(xiàn)性規(guī)劃模型，因而運(yùn)輸問(wèn)題有可能存 在最優(yōu)解，也有可能不存在最優(yōu)解；（12）只要能將所研究的問(wèn)題分解成多個(gè)不同階段，就一定 可以用動(dòng)態(tài)規(guī)劃方法求出其最優(yōu)解；（13）隱枚舉法是一種特殊的分

3、支定界法，它適用于任何 01 規(guī)劃問(wèn)題；（14）指派問(wèn)題效率矩陣 A的元素可分成0與非0元素兩部 分，覆蓋 0 元素的最少直線(xiàn)數(shù)等于位于不同行不同列 0 元素 的最大個(gè)數(shù)；（15）機(jī)器負(fù)荷分配問(wèn)題中，始終固定終端自由的生產(chǎn)效率 要比始端固定終端也固定的生產(chǎn)效率低。二 . 下列每一個(gè)問(wèn)題中至少有一個(gè)說(shuō)法是正確的， 共有 20 個(gè) 說(shuō)法正確，請(qǐng)把 20 個(gè)正確說(shuō)法找出來(lái)，超過(guò) 20 個(gè)時(shí)按題順 序取前 20 個(gè)為準(zhǔn)，每個(gè) 1.5 分，共 30 分）1. 當(dāng)極大化LP問(wèn)題單純性表的基底 B變?yōu)?？時(shí)，則祁變?yōu)?岔1 b，岔1 b>0而？?孑？?1 N中存在正數(shù)，則（）說(shuō)法正確。A. 基*?對(duì)應(yīng)的

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

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

6、 p 個(gè)節(jié)點(diǎn)和 p-1 條邊的圖就是一棵樹(shù)D. 從圖的任何一個(gè)生成樹(shù)開(kāi)始，通過(guò)有限步連續(xù)的樹(shù)基本變 換可以得到圖的每一個(gè)生成樹(shù)，其中邊數(shù)最少的生成樹(shù)就是 最小生成樹(shù)。6. 關(guān)于帶收發(fā)點(diǎn)的容量網(wǎng)絡(luò)中從出發(fā)點(diǎn)到收點(diǎn)的一條增廣 鏈，以下（ ）敘述正確。A. 增廣路上的有向邊的方向必須是從發(fā)點(diǎn)指向收點(diǎn)的；B. 增廣路上的有向邊必須都是不飽和邊；C. 增廣路上不能有零流邊；D. 增廣路上與發(fā)點(diǎn)到收點(diǎn)方向的有向邊不能是飽和邊，相反 方向的有向邊不能是零。7. 線(xiàn)性規(guī)劃問(wèn)題最優(yōu)基中某個(gè)基變量的目標(biāo)系數(shù)發(fā)生變化， 則（ ）正確。A. 該基變量的檢驗(yàn)數(shù)必然為零；B. 其他基變量的檢驗(yàn)數(shù)可能變化；C. 所有非基變

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

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

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

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

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