北京交通大學(xué)交通運(yùn)輸學(xué)院《942管理運(yùn)籌學(xué)》歷年考研真題匯編（含部分答案）

目錄

2015年北京交通大學(xué)交通運(yùn)輸學(xué)院942

管理運(yùn)籌學(xué)考研真題

2014年北京交通大學(xué)交通運(yùn)輸學(xué)院942

管理運(yùn)籌學(xué)考研真題

2013年北京交通大學(xué)交通運(yùn)輸學(xué)院942

管理運(yùn)籌學(xué)考研真題

2012年北京交通大學(xué)交通運(yùn)輸學(xué)院942

管理運(yùn)籌學(xué)考研真題

2011年北京交通大學(xué)交通運(yùn)輸學(xué)院942

管理運(yùn)籌學(xué)考研真題

2010年北京交通大學(xué)交通運(yùn)輸學(xué)院942

管理運(yùn)籌學(xué)考研真題

2010年北京交通大學(xué)交通運(yùn)輸學(xué)院942

管理運(yùn)籌學(xué)考研真題及詳解

2009年北京交通大學(xué)交通運(yùn)輸學(xué)院942

管理運(yùn)籌學(xué)考研真題

2009年北京交通大學(xué)交通運(yùn)輸學(xué)院942

管理運(yùn)籌學(xué)考研真題及詳解

2008年北京交通大學(xué)交通運(yùn)輸學(xué)院942

管理運(yùn)籌學(xué)考研真題

2008年北京交通大學(xué)交通運(yùn)輸學(xué)院942

管理運(yùn)籌學(xué)考研真題（含部分答案）

2007年北京交通大學(xué)交通運(yùn)輸學(xué)院417

管理運(yùn)籌學(xué)考研真題

2007年北京交通大學(xué)交通運(yùn)輸學(xué)院417

管理運(yùn)籌學(xué)考研真題及詳解

2006年北京交通大學(xué)交通運(yùn)輸學(xué)院417

管理運(yùn)籌學(xué)考研真題

2006年北京交通大學(xué)交通運(yùn)輸學(xué)院417

管理運(yùn)籌學(xué)考研真題及詳解

2005年北京交通大學(xué)交通運(yùn)輸學(xué)院417

管理運(yùn)籌學(xué)考研真題

2005年北京交通大學(xué)交通運(yùn)輸學(xué)院417

管理運(yùn)籌學(xué)考研真題及詳解

2004年北京交通大學(xué)交通運(yùn)輸學(xué)院管

理運(yùn)籌學(xué)考研真題

2004年北京交通大學(xué)交通運(yùn)輸學(xué)院管

理運(yùn)籌學(xué)考研真題及詳解

2003年北方交通大學(xué)交通運(yùn)輸學(xué)院管

理運(yùn)籌學(xué)考研真題

2003年北方交通大學(xué)交通運(yùn)輸學(xué)院管

理運(yùn)籌學(xué)考研真題及詳解

2002年北方交通大學(xué)交通運(yùn)輸學(xué)院管

理運(yùn)籌學(xué)考研真題

2002年北方交通大學(xué)交通運(yùn)輸學(xué)院管

理運(yùn)籌學(xué)考研真題及詳解

2001年北方交通大學(xué)交通運(yùn)輸學(xué)院管

理運(yùn)籌學(xué)考研真題

2001年北方交通大學(xué)交通運(yùn)輸學(xué)院管

理運(yùn)籌學(xué)考研真題及詳解

2000年北方交通大學(xué)交通運(yùn)輸學(xué)院管

理運(yùn)籌學(xué)考研真題

2015年北京交通大學(xué)交通運(yùn)輸學(xué)院942管理運(yùn)籌學(xué)考研真題

2014年北京交通大學(xué)交通運(yùn)輸學(xué)院942管理運(yùn)籌學(xué)考研真題

2013年北京交通大學(xué)交通運(yùn)輸學(xué)院942管理運(yùn)籌學(xué)考研真題

2012年北京交通大學(xué)交通運(yùn)輸學(xué)院942管理運(yùn)籌學(xué)考研真題

2011年北京交通大學(xué)交通運(yùn)輸學(xué)院942管理運(yùn)籌學(xué)考研真題

2010年北京交通大學(xué)交通運(yùn)輸學(xué)院942管理運(yùn)籌學(xué)考研真題

2010年北京交通大學(xué)交通運(yùn)輸學(xué)院942管理運(yùn)籌學(xué)考研真題及詳解

北京交通大學(xué)2010年碩士研究生入學(xué)考試

科目代碼：942科目名稱：管理運(yùn)籌學(xué)

一、判斷（正確的打“∨”，錯(cuò)誤的打“×”）

1．線性規(guī)劃問題的每一個(gè)基解對(duì)應(yīng)可行域的一個(gè)頂點(diǎn)；（北京交通大

學(xué)2010年研）

【答案】×

【解析】基解不一定是可行解，基可行解對(duì)應(yīng)著可行域的頂點(diǎn)。

2．若、分別是某一線性規(guī)劃問題的最優(yōu)解，則也是

該線性規(guī)劃問題的最優(yōu)解，其中、為正的實(shí)數(shù)；（北京交通大學(xué)

2010年研）

【答案】×

【解析】必須規(guī)定，當(dāng)一線性規(guī)劃問題存在兩個(gè)最優(yōu)

解時(shí)，則它一定存在無數(shù)個(gè)最優(yōu)解，

3．已知為線性規(guī)劃問題的對(duì)偶問題的最優(yōu)解，若，則說明在最

優(yōu)生產(chǎn)計(jì)劃中第種資源已經(jīng)完全耗盡；（北京交通大學(xué)2010年研）

【答案】∨

【解析】對(duì)偶問題互補(bǔ)松弛性質(zhì)中；當(dāng)時(shí)，有，

表明在最優(yōu)生產(chǎn)計(jì)劃中第種資源已經(jīng)完全耗盡。

4．整數(shù)規(guī)劃問題最優(yōu)解的目標(biāo)函數(shù)值一定優(yōu)于其相應(yīng)線性規(guī)劃問題最

優(yōu)解的目標(biāo)函數(shù)值；（北京交通大學(xué)2010年研）

【答案】×

【解析】因?yàn)楦郊恿苏麛?shù)條件，其可行域比其相應(yīng)線性規(guī)劃問題的可行

域減小，故整數(shù)規(guī)劃問題最優(yōu)解的目標(biāo)函數(shù)值一定不優(yōu)于其相應(yīng)線性規(guī)

劃問題最優(yōu)解的目標(biāo)函數(shù)值。

5．指派問題效率矩陣的每個(gè)元素乘以同一大于0的常數(shù)，將不影響最

優(yōu)指派方案；（北京交通大學(xué)2010年研）

【答案】∨

【解析】效率矩陣每個(gè)元素乘以同一大于0的常數(shù)，即目標(biāo)函數(shù)的系數(shù)

同時(shí)增大k倍，不會(huì)影響最優(yōu)基的變化，故不影響最優(yōu)指派方案。

6．如果圖T是樹，則T中一定存在兩個(gè)頂點(diǎn)，它們之間存在兩條不同的

鏈；（北京交通大學(xué)2010年研）

【答案】×

【解析】連通且不含圈的無向圖稱為樹。因此任意兩點(diǎn)間必定只有一條

鏈。

7．任一圖都存在支撐子圖和支撐樹；（北京交通大學(xué)2010年

研）

【答案】×

【解析】當(dāng)圖中存在一個(gè)頂點(diǎn)，其次為0時(shí)，則該圖不存在支撐樹。

8．網(wǎng)絡(luò)圖中任何一個(gè)結(jié)點(diǎn)都表示前一工序的結(jié)束和后一工序的開始；

（北京交通大學(xué)2010年研）

【答案】×

【解析】網(wǎng)絡(luò)圖的起始點(diǎn)只表示一工序的開始，結(jié)束點(diǎn)只表示一工序的

結(jié)束。

9．結(jié)點(diǎn)最早時(shí)間同最遲時(shí)間相等的點(diǎn)連接的線路就是關(guān)鍵路線；（北

京交通大學(xué)2010年研）

【答案】∨

【解析】關(guān)鍵路線是指總時(shí)差為零的工作鏈，而該工作鏈?zhǔn)怯梢幌盗凶?/p>

早時(shí)間同最遲時(shí)間相等的點(diǎn)連接而成的。

10．假如到達(dá)排隊(duì)系統(tǒng)的顧客為普阿松流，則依次到達(dá)的兩名顧客之間

的間隔時(shí)間服從負(fù)指數(shù)分布；（北京交通大學(xué)2010年研）

【答案】∨

【解析】設(shè)N（t）為時(shí)間[0，t]內(nèi)到達(dá)系統(tǒng)的顧客數(shù)，則為參

數(shù)為的普阿松流的充要條件是：相繼到達(dá)時(shí)間間隔服從相互獨(dú)立的參

數(shù)為的負(fù)指數(shù)分布。

11．運(yùn)輸問題是一種特殊的線性規(guī)劃模型，因而其求解結(jié)果也可能出現(xiàn)

四種情況之一：有唯一最優(yōu)解，有無窮多最優(yōu)解，無界解，無可行解；

（北京交通大學(xué)2010年研）

【答案】×

【解析】運(yùn)輸問題是一種特殊的線性規(guī)劃模型，它總存在可行解，或是

存在唯一最優(yōu)解，或是有無窮最優(yōu)解。

12．單純形法計(jì)算中，選取最大正檢驗(yàn)數(shù)對(duì)應(yīng)的變量作為換入變

量，將使目標(biāo)函數(shù)值得到最快的增長。

【答案】∨

【解析】選擇任何一個(gè)大于零的都可以，

由上式可以看出，將最大正檢驗(yàn)數(shù)對(duì)應(yīng)的變量作為換入變量，將使

目標(biāo)函數(shù)值得到最快的增長。

二、簡答

1．試簡述求解整數(shù)規(guī)劃模型的分枝定界法剪枝的幾種情況；（北京交

通大學(xué)2010年研）

答：（1）某枝已經(jīng)達(dá)到其范圍內(nèi)的最優(yōu)解；

（2）某枝域內(nèi)沒有可行解時(shí)，即是不可行域；

（3）某枝所得數(shù)據(jù)不優(yōu)于當(dāng)前最優(yōu)解時(shí)。

2．試寫出標(biāo)準(zhǔn)指派問題的線性規(guī)劃問題；（北京交通大學(xué)2010年研）

答：設(shè)，

則得線性規(guī)劃模型

3．試寫出求解最短徑路的Dijkstra算法的步驟；（北京交通大學(xué)2010年

研）

答：步驟：

（1）給

（2）若vi點(diǎn)為剛得到P標(biāo)號(hào)的點(diǎn)，考慮這樣的點(diǎn)vj，（vi，vj）屬于E，

且vj為T標(biāo)號(hào)。對(duì)vj的T標(biāo)號(hào)進(jìn)行如下修改：

（3）比較所有具有T標(biāo)號(hào)的點(diǎn)，把最小者改為P標(biāo)號(hào)，即：

當(dāng)存在兩個(gè)以上最小者時(shí)，可同時(shí)改為P標(biāo)號(hào)。若全部點(diǎn)均為P標(biāo)號(hào)時(shí)停

止。否則用代轉(zhuǎn)回（2）。

4．試寫出M/M/1排隊(duì)系統(tǒng)的Little公式；（北京交通大學(xué)2010年研）

答：

三、（40分）某廠生產(chǎn)Ⅰ、Ⅱ、Ⅲ三種產(chǎn)品，其所需勞動(dòng)力、原材料等

有關(guān)數(shù)據(jù)如下：每件產(chǎn)品Ⅰ分別需要?jiǎng)趧?dòng)力和原材料6個(gè)小時(shí)和3公斤，

每件產(chǎn)品Ⅱ分別需要?jiǎng)趧?dòng)力和原材料為3小時(shí)和4公斤，每件產(chǎn)品Ⅲ分別

需要?jiǎng)趧?dòng)力和原材料為5小時(shí)和5公斤；擁有的勞動(dòng)力和原材料總數(shù)分別

為45小時(shí)和30公斤；又知Ⅰ、Ⅱ、Ⅲ三種產(chǎn)品的單件利潤分別為3、1、

4元。（北京交通大學(xué)2010年研）

要求：

1．寫出該廠獲得最大的生產(chǎn)計(jì)劃問題的線性規(guī)劃模型并求出最優(yōu)解；

答：設(shè)三種產(chǎn)品的產(chǎn)量分別為x1、x2、x3，則得模型：

將上述問題改寫為標(biāo)準(zhǔn)形式為：

用單純形法計(jì)算如下：

cj31400

CBXBbx1x2x3x4x5

0x44563510

0x53034[5]01

31400

0x415[3]－101－1

4x363/54/5101/5

3/5－11/500－4/5

3x151－1/301/3－1/3

4x33011－1/52/5

0－20－1/5－3/5

得到最優(yōu)解，即生產(chǎn)Ⅰ、Ⅲ各5和3件。

2．寫出該線性規(guī)劃問題的對(duì)偶問題，并求對(duì)偶問題的最優(yōu)解；

答：對(duì)偶問題：

由及上述最終單純形表可知，。

3．產(chǎn)品Ⅰ的利潤在什么范圍內(nèi)變化時(shí)，上述最優(yōu)計(jì)劃不變？

答：保持最優(yōu)計(jì)劃不變，即保持各非基變量檢驗(yàn)數(shù)非正，則

解得。

4．如果設(shè)計(jì)一種新產(chǎn)品Ⅳ，單件產(chǎn)品消耗勞動(dòng)力8小時(shí)，原材料2公

斤，每件可獲利3元，問該產(chǎn)品是否值得生產(chǎn)？

答：新產(chǎn)品的產(chǎn)量為x6，則相對(duì)約束矩陣多一列向量，在最終

單純形表中為

，其檢驗(yàn)數(shù)為

，故值得生產(chǎn)。

5．如果勞動(dòng)力數(shù)量不變，原材料可以從市場(chǎng)購買，每公斤0.4元，問該

廠是否購買原材料來擴(kuò)大生產(chǎn)，以購買多少為宜？

答：設(shè)購買，則①

②，故可以購買原材料來擴(kuò)大生產(chǎn)。

由①②兩式得，即購買15公斤時(shí)可獲得最大效益。

四、（16分）某公司有甲，乙，丙三個(gè)工廠和A，B，C三個(gè)客戶，這三

個(gè)工廠在下一時(shí)期將分別生產(chǎn)某種產(chǎn)品300，500和400件，公司計(jì)劃賣

給客戶A，B，C的產(chǎn)品數(shù)量分別為400，300，100件，客戶D想盡可能

多地購買剩下的商品。工廠賣給各客戶單位產(chǎn)品的利潤如下表。問如何

安排供應(yīng)使該公司總利潤最大。

答：該問題屬于平衡運(yùn)輸問題，客戶D將購買300＋500＋400－（400＋

300＋100）＝400（件）商品。則由沃格爾法得初始方案，并用位勢(shì)法

得各空格檢驗(yàn)數(shù)[]所示：

ABCD供給量行差

甲[－2]15[－3]13[－1]1230014300111

乙2001830017[1]15[－3]1250012

丙20013[－2]10100910010400322

需求量400300100400

3432

列差332

234

空格[乙C]檢驗(yàn)數(shù)為正，故調(diào)整其所在回路，調(diào)整值為min[200，100]＝

100并檢驗(yàn)得：

ABCD供給量

甲[－2]15[－3]13[－2]1230014300

乙100183001710015[－3]12500

丙30013[－2]10[－1]910010400

需求量400300100400

所有檢驗(yàn)數(shù)均小于零，即得最優(yōu)方案如下：

ABCD供給量

甲300300

乙100300100500

丙300100400

需求量4003001004001200

五、（20分）用動(dòng)態(tài)規(guī)劃方法求解下列整數(shù)規(guī)劃問題：（北京交通大學(xué)

2010年研）

答：將該過程分為3個(gè)階段，決策變量為，狀態(tài)變量為，表示第k階

段開始時(shí)候的狀態(tài)（k＝1，2，3），其中，最優(yōu)指標(biāo)函數(shù)

，表示第k階段狀態(tài)為時(shí)，第k階段至第3階段

的最優(yōu)值，且，表示每個(gè)階段的指標(biāo)函數(shù)。采用

逆推法。

k＝3時(shí)，

k＝2時(shí)，

k＝1時(shí)，。

***

所以得x1＝1，x2＝2，x3＝0，maxZ＝18。

六、（14分）某理發(fā)店只有一個(gè)理發(fā)員，來理發(fā)的顧客到達(dá)過程為

posson流，平均5人/小時(shí)；理發(fā)時(shí)間服從負(fù)指數(shù)分布，平均需要10分

鐘；店內(nèi)備有5把椅子供顧客等候，多余顧客將到其他理發(fā)店理發(fā)。

（北京交通大學(xué)2010年研）

求：

（1）該理發(fā)店忙的概率；

（2）該店內(nèi)恰有2個(gè)顧客的概率；

（3）在該店內(nèi)的平均顧客數(shù)；

（4）每位顧客在該店內(nèi)的平均逗留時(shí)間；

（5）等待服務(wù)的平均顧客數(shù)；

（6）每位顧客平均等待時(shí)間；

（7）顧客損失的概率。

答：該問題屬于M/M/1/N模型，，，N＝5。

（1），∴1－P0＝0.7494，即為理發(fā)店忙的概率。

（2）

∴。

（3）。

（4）。

（5）。

（6）顧客的平均等待時(shí)間是。

（7），即顧客損失的概率。

2009年北京交通大學(xué)交通運(yùn)輸學(xué)院942管理運(yùn)籌學(xué)考研真題

2009年北京交通大學(xué)交通運(yùn)輸學(xué)院942管理運(yùn)籌學(xué)考研真題及詳解

北京交通大學(xué)2009年碩士研究生入學(xué)考試

科目代碼：942科目名稱：管理運(yùn)籌學(xué)

一、（50分）已知線性規(guī)劃問題如下：

1．求該問題的最優(yōu)解；

答：用對(duì)偶單純形法計(jì)算如下：

ci251/200

CBXBbx1x2x3x4x5

0x4－3－1－2－1/210

0x5－90－1[－3]01

251/200

0x4－2/3－1－11/601[－1/6]

1/2x3301/310－1/3

－2－29/600－1/6

0x696110－61

1/2x36241－20

13010

得最優(yōu)解，X*＝（0，0，6）T，minz＝1/2×6＝3。

2．寫出該線性規(guī)劃問題的對(duì)偶問題，并求對(duì)偶問題的最優(yōu)解；

答：

由上最終單純形表可得，，maxw＝3

3．分別確定x2、x3的目標(biāo)函數(shù)系數(shù)c2、c3在什么范圍內(nèi)變化，最優(yōu)解不

變？

答：（1）c2變化，最優(yōu)解不變，要保證，解得，即

。

（2）c3變化，最優(yōu)解不變，要保證，，解得

，即。

4．求約束條件右端值由變?yōu)闀r(shí)的最優(yōu)解；

答：代入最終單純形表中，，因此不是最優(yōu)解。

ci251/200

0x6－36110[－6]1

1/2x34241－20

13010

0x41/2－1－11/601－1/6

1/2x3401/310－1/3

029/6001/6

得新的最優(yōu)解是X*＝[0，0，4]T，minz＝1/2×4＝2。

5．求增加新的約束條件x1＋2x2＋x3≤5時(shí)的最優(yōu)解。

答：加入松弛變量x6得下表

cj251/2000

CBXBbx1x2x3x4x5x6

0x4－3－1－2－1/2100

0x5－90－1[－3]010

0x6－5－1－2－1001

251/2000

0x4－2/3－1－11/601－1/60

1/2x3301/310－1/30

0x6－2－1－5/300[－1/3]1

229/6001/60

0x41/3－1/2－1010－1/2

1/2x3512100－1

0x5635001－3

3/240001/2

得最優(yōu)解X*＝[0，0，5]T，minz＝1/2×5＝5/2。

二、（25分）某鐵路企業(yè)承擔(dān)A、B、C三個(gè)城市之間的城際旅客列車運(yùn)

輸任務(wù)，列車的出發(fā)和到達(dá)時(shí)間如下表所示：

設(shè)旅客列車從到達(dá)某站到出發(fā)至少需要2個(gè)小時(shí)的準(zhǔn)備時(shí)間，試制定一

個(gè)最佳的旅客列車車底接續(xù)方案，使該鐵路企業(yè)所使用的車底數(shù)量最

少。

答：題中，將達(dá)到某城市的列車當(dāng)成是要完成工作的工作人員，而在該

城市出發(fā)當(dāng)成是要完成的工作，則3座城市的列車工作效率如下所示，

數(shù)據(jù)是執(zhí)行任務(wù)需等待時(shí)間。

A城市：

到達(dá)出發(fā)T101T103T105T107T109

T1022381315

T10419202568

T10615162124

T10822234911

T110141520253

B城市

到達(dá)出發(fā)T102T104T106

T10116233

T10315222

T105101721

C城市

到達(dá)出發(fā)T108T110

T107715

T109513

則對(duì)于A城市，利用匈牙利算法指派任務(wù)如下：

初次指派為：，◎的個(gè)數(shù)少于54，故進(jìn)行劃線覆

蓋所有的零元素

；

繼續(xù)求解，，依然不符合，故繼續(xù)劃線覆蓋所有

零元素，并最終求得最優(yōu)解

，即A城市中

到達(dá)出發(fā)T101T103T105T107T109

T1023

T10419

T1062

T1084

T1103

所需車底數(shù)是3；

同理得B城市的指派為，所需車底數(shù)為2；

C城市指派為，需要車底數(shù)為2。

綜上，該企業(yè)總的車底數(shù)最少需要是7個(gè)。

三、（20分）已知運(yùn)輸問題的運(yùn)價(jià)及產(chǎn)銷平衡表如下：

要求：

1．用最小元素法求該運(yùn)輸問題的初始解，并進(jìn)一步求出最優(yōu)解；

2.A3→B3的單位運(yùn)價(jià)C33變?yōu)槭裁粗禃r(shí)，有無窮多最優(yōu)解？并進(jìn)一步給

出兩個(gè)新的最優(yōu)方案。

答：（1）該運(yùn)輸問題的初始解是：

B1B2B3B4產(chǎn)量

A11010

A23101225

A3325

銷量6101212

利用位勢(shì)法計(jì)算個(gè)空格的檢驗(yàn)數(shù)為：

產(chǎn)量

B1B2B3B4

A1[1][0]10[1]10

A2310[－2]1225

A33[13]2[7]5

銷量6101212

空格A2B2檢驗(yàn)數(shù)小于0，故調(diào)整其所在回路，調(diào)整量為min（2，3）＝

2，得新方案，并檢驗(yàn)之，如表中所示：

B1B2B3B4產(chǎn)量

A1[－1][－2]10[－1]10

A211021225

A35[13][2][7]5

銷量6101212

仍不是最優(yōu)方案，故繼續(xù)調(diào)整，最后得最終方案如下：

B1B2B3B4產(chǎn)量

A11010

A210121225

A355

銷量6101212

（2）A3B3的檢驗(yàn)數(shù)為C33－12＋10－6＝0時(shí)，即C33＝8時(shí)，有無窮多最

優(yōu)解。

新方案一：

B1B2B3B4產(chǎn)量

A11010

A21.511.51225

4.50.55

A3

銷量6101212

新方案二：

B1B2B3B4產(chǎn)量

A11010

A22111225

A3415

銷量6101212

四、（21分）某公司生產(chǎn)并銷售某產(chǎn)品。根據(jù)市場(chǎng)預(yù)測(cè)，今后四個(gè)月的

市場(chǎng)需求量如下表所示。已知生產(chǎn)一件產(chǎn)品的成本是1千元，每批產(chǎn)品

的生產(chǎn)準(zhǔn)備成本是3千元，每月僅能生產(chǎn)一批，每批6件。每件存儲(chǔ)成本

為0.5千元，且第一個(gè)月初無存貨，第四個(gè)月末的存貨要求為零。求最

優(yōu)生產(chǎn)計(jì)劃。（北京交通大學(xué)2009年研）

答：采用動(dòng)態(tài)規(guī)劃方法求解。設(shè)每個(gè)月生產(chǎn)xk件產(chǎn)品，xk小于等于6；sk

為每個(gè)月開始的存貨量，則s1＝0，s5＝0，

，表示在k月初存貨量是sk是從第

k個(gè)月開始至第4個(gè)月的最優(yōu)指標(biāo)函數(shù)。表示第k個(gè)月生產(chǎn)xk個(gè)產(chǎn)品

時(shí)所需要的生產(chǎn)費(fèi)用，，表示第k個(gè)月生產(chǎn)xk個(gè)產(chǎn)

品時(shí)，剩余產(chǎn)品所需要的存儲(chǔ)費(fèi)用，

（1）k＝4時(shí)，

（2）k＝3時(shí)，

（3）k＝2時(shí)，

（4）k＝1時(shí)，

∴為最優(yōu)生產(chǎn)計(jì)劃。

五、（20分）在下圖中，分別求v1至v6，v1至v4，v6至v2和v2至v5的最短

路和最短距離。（北京交通大學(xué)2009年研）

答：用Floyd方法求解：

令網(wǎng)絡(luò)的權(quán)矩陣為

k＝0，，由表示從vi到vj點(diǎn)

或直接有邊或借v1點(diǎn)為中間點(diǎn)是的最短路長，括弧中元素為更新元素，

得D（1）

k＝1，；表示從vi到vj點(diǎn)最多經(jīng)v1，v2的

最短路長，得D（2）

k＝2，，依次類推，

k＝3，；k＝4，；

k＝5，；k＝6，

。

∴v1至v6的最短路是v1－v3－v5－v6，最短距離是－1。

v1至v4的最短路是v1－v3－v5－v4，最短距離是0。

v6至v2的最短路是v6－v4－v2，最短距離是3。

v2至v5的最短路是v2－v3－v5，最短距離1。

六、（14分）某汽車加油站只有一個(gè)加油設(shè)備，汽車到達(dá)加油站的過程

服從泊松分布，汽車平均到達(dá)時(shí)間間隔為5分鐘，加油站平均1個(gè)小時(shí)能

加24輛車。

試求：

（1）加油站的空閑的概率；

（2）加油站有三輛車的概率；

（3）加油站有兩輛車以上的概率；

（4）加油站內(nèi)的平均車輛數(shù)；

（5）車輛在加油站內(nèi)的平均逗留時(shí)間；

（6）加油站內(nèi)的平均等待車數(shù)；

（7）車輛的平均等待時(shí)間。

答：屬于M/M/1/∞模型，。

（1）加油站的空閑的概率。

（2）加油站有三輛車的概率。

（3）加油站有兩輛車以上的概率。

（4）加油站內(nèi)的平均車輛數(shù)即（輛）。

（5）車輛在加油站內(nèi)的平均逗留時(shí)間。

（6）加油站內(nèi)的平均等待車數(shù)即（輛）。

（7）車輛的平均等待時(shí)間。

2008年北京交通大學(xué)交通運(yùn)輸學(xué)院942管理運(yùn)籌學(xué)考研真題

2008年北京交通大學(xué)交通運(yùn)輸學(xué)院942管理運(yùn)籌學(xué)考研真題（含部分答

案）

北京交通大學(xué)2008年碩士研究生入學(xué)考試試卷

考試科目：942管理運(yùn)籌學(xué)

注意事項(xiàng)：答案一律寫在答題紙上，寫在試卷上的不予裝訂和評(píng)分！

一、（35分）已知線性規(guī)劃問題：

maxZ＝3x1＋4x2＋x3

（1）求線性規(guī)劃問題的最優(yōu)解：

（2）求對(duì)偶問題的最優(yōu)解：

（3）求b1的靈敏度范圍；

（4）求c2的靈敏度范圍；

如果右端值[10，16]變?yōu)閇12，10]求新問題的最優(yōu)解。

答：

（1）由題意，用單純形法計(jì)算。

Cj34100θi

CBXBb

0101[2]1105

016221018

34100

Cj－Zj

451/211/21/2010

06[1]00－116

Cj－Zj10－1－20

42011/21－1/2

36100－11

Cj－Zj00－1－1－1

此時(shí)，所有檢驗(yàn)數(shù)為負(fù)，已得最優(yōu)解XT＝（6，2，0），目標(biāo)函數(shù)值為

Z＝26。

（2）對(duì)偶問題

Minw＝10y1＋16y2

s．ty1＋2y2≥3①

2y1＋2y2≥4②

y1＋y2≥1③

y1，y2≥0

由互補(bǔ)松弛條件YXs＝0，XYs＝0；

由X＝（6，2，0），得Y1s＝0Y2s＝0，即①②③為嚴(yán)格等式，

即y1＋2y2＝3，2y1＋2y2＝4；所以y1＝1，y2＝1。

即最優(yōu)解y1＝1，y2＝1，minw＝26。

（3）靈敏度分析

當(dāng)b1變化△b時(shí)，可計(jì)算

B－1b＋B－1

由，所以。

因此8≤b1≤16。

（4）記

即，得，所以。

（5）當(dāng)右端值由[10，16]變?yōu)閇12，10]時(shí)，

。

將其反映到最終單純性表中，再用對(duì)偶單純性法進(jìn)行迭代，如下。

Cj34100

CBXBb

47011/21－1/2

3－2100[－1]1

Cj－Zj00－1－1－1

45111/201/2

02－1001－1

Cj－Zj－10－10－2

故新問題的最優(yōu)解為X＊＝（0，5，0，2，0），最優(yōu)值為z＊＝20。

二、（20）已知LP問題為

要求：

（1）設(shè)其偶變量為y1，y2，y3，y4，寫出其對(duì)偶問題；

（2）已知原問題最優(yōu)解（x1，x2，x3，x4，）＝（2，2，4，0），試根

據(jù)對(duì)偶性質(zhì)直接求出對(duì)偶問題的最優(yōu)解。（北京交通大學(xué)2008年研）

答：

（1）對(duì)偶問題

minW＝8y1＋6y2＋6y3＋9y4

s．t

（2）由互補(bǔ)松弛條件YXs＝0，XYs＝0；

（x1，x2，x3，x4，）＝（2，2，4，0），則X1s＝X2s＝X3s＝0，

X4s≠0，且＝0，Y1s＝Y(jié)2s＝Y(jié)3s＝0

所以，因此（y1，y2，y3，y4）＝（，1，0）。

三、（20）某公司有3個(gè)工廠和3個(gè)客戶，這3個(gè)工廠在下一時(shí)期將分別

制造產(chǎn)品300，500和200件，公司答應(yīng)賣給客戶1，2，3的產(chǎn)品分別是

300，200，100件，客戶4想盡可能多的購買剩下產(chǎn)品。工廠i賣給客戶j

的單位產(chǎn)品利潤如下表所示。問如何安排生產(chǎn)和供應(yīng)才能使總利潤最

大？

答：用18減去圖中各個(gè)利潤，將問題轉(zhuǎn)化為運(yùn)輸問題，建立產(chǎn)銷平衡

表。

產(chǎn)量

3564300

0136500

5898200

銷量300200100400

用伏格爾法求解，（）內(nèi)數(shù)據(jù)為解

產(chǎn)地銷地產(chǎn)量行差

3564（300）300112

0（300）1（200）3（0）650013

589（100）8（100）200331

銷量300200100400

列差3432

332

34

用位勢(shì)法計(jì)算所有空格的檢驗(yàn)數(shù)，計(jì)算結(jié)果如下圖所示。

1210

4－2

－114

2354

表中有負(fù)檢驗(yàn)數(shù)，選擇（1，3）為調(diào)入格，調(diào)入量為100，得新的解

300

200200100

100100

再用位勢(shì)法檢驗(yàn)，得檢驗(yàn)數(shù)

2320

3－1

214

1244

此時(shí)，所有檢驗(yàn)數(shù)都非負(fù)，故上表中的解為最優(yōu)解。

即安排A1生產(chǎn)300提供給B4，A2生產(chǎn)200提供給B1，A2生產(chǎn)200提供給

B2，A3生產(chǎn)100提供給B3，A3生產(chǎn)100提供給B1，A3生產(chǎn)100提供給

B4，故總利潤為15000。

四、（25）某工廠有1000臺(tái)機(jī)器，擬分四個(gè)階段使用。已知在每個(gè)階段

有兩種生產(chǎn)任務(wù)，進(jìn)行第一種生產(chǎn)時(shí)每臺(tái)機(jī)器可收益9千元，其機(jī)器報(bào)

廢率0.3，而進(jìn)行第二種生產(chǎn)時(shí)每臺(tái)機(jī)器可收益6千元，其機(jī)器報(bào)廢率為

0.1．文怎樣分配機(jī)器，使收益最大？（要求寫出動(dòng)態(tài)規(guī)劃模型的基本

要素并求解）（北京交通大學(xué)2008年研）

答：將此題看成一個(gè)4個(gè)階段決策問題。令為狀態(tài)變量，它表示第k階

段初擁有的完好機(jī)器數(shù)量，決策變量為第k階段分配給第一種生產(chǎn)的

機(jī)器數(shù)量，于是為該階段分配給第二種生產(chǎn)的機(jī)器數(shù)量。

狀態(tài)轉(zhuǎn)移方程為，設(shè)為第k階段的

收益，則

令最優(yōu)值函數(shù)表示由機(jī)器數(shù)量出發(fā)，從第k階段開始到第4階段結(jié)

束時(shí)所獲得的收益最大值，故有遞推關(guān)系式：

（1）k＝4時(shí)，

因f4是u4的線性單調(diào)增函數(shù)，故得最大解，相應(yīng)的。

（2）k＝3時(shí)，

故得最大解，相應(yīng)的有。

（3）k＝2時(shí)，

當(dāng)

，相應(yīng)的有。

（4）k＝1時(shí)，

當(dāng)

，相應(yīng)的有。

因s1＝1000，所以＝23793千元。

計(jì)算結(jié)果表明，第1階段將1000臺(tái)機(jī)器投入第二種生產(chǎn)，第2階段將900

臺(tái)機(jī)器投入到第二種生產(chǎn)，第3階段將810臺(tái)機(jī)器投入到第一種生產(chǎn)，第

4階段將567臺(tái)機(jī)器投入到第一種生產(chǎn)。可得最大收益為23793千元。

五、（10）為解決污水河流的污染問題，某城市擬修建污水處理站。備

選的站址有A、B、C三個(gè)，其投資等技術(shù)經(jīng)濟(jì)參數(shù)見下表：

按環(huán)保部門要求，每年至少要從污水中清除8萬噸污染物1和6萬噸污染

物2。

請(qǐng)構(gòu)造一個(gè)整數(shù)規(guī)劃模型，在滿足環(huán)保要求的前提下使投資和運(yùn)行費(fèi)用

最小。（北京交通大學(xué)2008年研）

答：

設(shè)表示處理的萬噸數(shù)，，被采用時(shí)為1，未采用時(shí)為0。

建立整數(shù)規(guī)劃模型minz＝500＋500x1＋400＋800x2＋300＋1000x3

六、（20）某修理店只有一個(gè)修理工，來修理的顧客到達(dá)過程為poisson

流，平均5人／小時(shí)。分別計(jì)算在下列修理時(shí)間分布的情況下系統(tǒng)的

Ls，Lq，Ws與Wq的值。

（1）修理時(shí)間為常數(shù)，每次修理需10分鐘；

（2）修理時(shí)間為負(fù)指數(shù)分布，平均修理需10分鐘；

（3）修理時(shí)間為正態(tài)分布，μ＝9分鐘，δ＝4。

答：（1）當(dāng)修理時(shí)間為常數(shù)

（2）當(dāng)修理時(shí)間為負(fù)指數(shù)分布

（3）當(dāng)修理時(shí)間為正態(tài)分布

2007年北京交通大學(xué)交通運(yùn)輸學(xué)院417管理運(yùn)籌學(xué)考研真題

2007年北京交通大學(xué)交通運(yùn)輸學(xué)院417管理運(yùn)籌學(xué)考研真題及詳解

北京交通大學(xué)2007年碩士研究生入學(xué)考試試卷

考試科目：417管理運(yùn)籌學(xué)

注意事項(xiàng)：答案一律寫在答題紙上，寫在試卷上的不予裝訂和評(píng)分！

一、（20分）某工廠準(zhǔn)備生產(chǎn)甲、乙、丙三種產(chǎn)品，它們都消耗A、B

兩種原材料，有關(guān)數(shù)據(jù)如下表所示：

要求：構(gòu)造使該廠利潤最大的線性規(guī)劃模型，并用單純型法求解。

答：設(shè)三種產(chǎn)品的產(chǎn)量分別為x1、x2、x3，則得以下線性規(guī)劃模型：

用單純形法計(jì)算如下：

cj31400

CBXBbx1x2x3x4x5

0x44563510

0x53034[5]01

314

0x415[3]－101－1

4x363/54/5101/5

3/5－11/500－4/5

3x151－1/301/3－1/3

4x33011－1/52/5

0－20－1/5－3/5

得到最優(yōu)解，即生產(chǎn)甲和丙各5和3單位。

二、（40分）已知線性規(guī)劃模型

Maxz＝2x1＋x2

求：

（1）寫出原問題的對(duì)偶線性規(guī)劃模型；

（2）用對(duì)偶單純型法求解原問題的最優(yōu)解；

（3）增加約束條件3x1＋2x2≤12，最優(yōu)解會(huì)有什么變化？

（4）若C1由2降至1.5，C2由1升至2，最優(yōu)解會(huì)有什么變化？

（5）資源b3由現(xiàn)在的5變成4，最優(yōu)解是否發(fā)生變化。

答：（1）

（2）對(duì)原問題的對(duì)偶問題利用對(duì)偶單純形法

cj1524500

CBYBby1y2y3y4y5

0y4－20[－6]－110

0y5－1－5－2－101

1524500

24y21/3011/6－1/60

0y5－1/3－50[－2/3]－1/31

150140

24y21/4－5/410－1/41/4

5y31/215/2011/2－3/2

15/2007/23/2

得最優(yōu)解，X*＝[7/2，3/2]，maxz＝8.5。

T

（3）即對(duì)偶問題增加了一變量y6，其約束變量為a＝[3，2]，目標(biāo)函數(shù)

變量為12，在最終單純形表中的

，，因此不是最優(yōu)解，

繼續(xù)計(jì)算如下：

cj152450012

CBYBby1y2y3y4y5y6

24y21/4－5/410－1/41/41/4

5y31/215/2011/2－3/2[3/2]

15/2007/23/2－3/2

24y21/6－5/21－1/6－1/31/20

12y61/3502/31/3－11

1501400

得原問題最優(yōu)解X*＝[4，0]，maxz＝8。

（4）在其對(duì)偶問題中，即資源變量變化，最終單純形表中

，繼繼續(xù)利用對(duì)偶單純形法計(jì)算如下：

cj1524500

CBYBby1y2y3y4y5

24y2－1/8[－5/4]10－1/41/4

5y39/415/2011/2－3/2

15/2007/23/2

15y11/101－4/501/5－1/5

5y33/2061－10

06023

得原問題最優(yōu)解X*＝（2，3）T，maxz＝7。

（5）即對(duì)偶問題c3＝4，y3是基變量，因此檢查各非基變量的檢驗(yàn)數(shù)

，因此最優(yōu)解不發(fā)生變化。

三、（15分）求出下面運(yùn)輸問題的所有最優(yōu)解。

答：本題為運(yùn)輸平衡問題，用沃格爾法計(jì)算如下：（）內(nèi)數(shù)據(jù)為解。

產(chǎn)地銷地B1B2B3B4產(chǎn)量行差

A19（6）8（2）13（5）14（5）1811411

A2101012（24）14240022

A38911（6）13611122

A4107（12）1112123

銷量61435560

列差1101

1111

111

11

21

用位勢(shì)法檢驗(yàn)，各空格檢驗(yàn)數(shù)[]內(nèi)數(shù)據(jù)，存在檢驗(yàn)數(shù)小于零的空格。

產(chǎn)地銷地B1B2B3B4產(chǎn)量

A19（6）8（2）13（5）14（5）18

A210[2]10[3]12（24）14[1]24

A38[1]9[3]11（6）13[1]6

A410[2]7（12）11[－1]12[－1]12

銷量61435560

在相應(yīng)回路調(diào)整，如空格A1B3所在回路，調(diào)整量為5，最后得新方案，

并檢驗(yàn)如下：

不存在檢驗(yàn)數(shù)小于0的空格，得最優(yōu)解，∵A3B1檢驗(yàn)數(shù)為0，∴最優(yōu)解不

唯一。

產(chǎn)地銷地B1B2B3B4產(chǎn)量

A19（6）8（12）13[1]14[1]18

A210[1]10[2]12（24）14[1]24

A38[0]9[2]11（6）13[1]6

A410[2]7（2）11（5）12（5）12

銷量61435560

由A3B1所在回路，任意變化可得所有最優(yōu)解如下：

產(chǎn)地銷地B1B2B3B4產(chǎn)量

A16－c12＋c18

A22424

A3c6－c6

A42－c5＋c512

銷量61435560

C的取值范圍是[0，2]。

四、（15分）用分支定界法求整數(shù)規(guī)劃問題的最優(yōu)解

Maxz＝X1＋x2

答：利用單純形法先解相應(yīng)的線性規(guī)劃，得最優(yōu)解如下：

cj1100

CBXBbx1x2x3x4

1x13/2107/16－9/32

1x210/3017/87/16

00－21/16－5/32

*

不是整數(shù)，故用分支定界法繼續(xù)求解，z0＝29/6是問題最優(yōu)解z的上

界，z＝0是一個(gè)下界，則。

將問題分成問題B1和B2

問題B1問題B2

z1＝10/3z1＝41/9

x1＝1x1＝2

x2＝7/3x2＝23/9

∵z1<z2，∴先將問題B2分解成B3和B4

問題B3問題B4

z1＝17/6z1＝14/3

x1＝5/6x1＝5/3

x2＝2x2＝3

接著講B4分解成問題B5和B6，

問題B5問題B6

z1＝17/6z1＝4

x1＝2x1＝3

x2＝23/9x2＝1

T

得到一整數(shù)解z＝4，X＝[3，1]，比較個(gè)z值，發(fā)現(xiàn)B6的解即為最優(yōu)

解。

五、（20分）某部門擬將某種新設(shè)備5臺(tái)分配給甲、乙、丙3個(gè)工廠，各

工廠獲得這些設(shè)備后可盈利如下表所示，這5臺(tái)設(shè)備應(yīng)如何分配，使其

利潤最大？用動(dòng)態(tài)規(guī)劃方法求解（要求寫出狀態(tài)轉(zhuǎn)移方程和遞推方

程）。

答：將該問題分成3個(gè)階段，xk（k＝1，2，3，4）為決策變量即在第K

階段分給k工廠xk臺(tái)設(shè)備，sk（k＝1，2，3，4）為第k階段開始時(shí)候的狀

態(tài)變量，為最優(yōu)策略的指標(biāo)函數(shù)，表示第k階段狀態(tài)為sk時(shí)第k階段

至第三階段的最優(yōu)值，且，用加法方式。s1＝5，s2＝s1－x1，s3

＝s2－x2＝x3。

模型為：

∴0≤x1≤5，0≤x2≤s2，0≤x3＝s3

其中，a（x1），b（x2），c（x3）分別表示三家工廠獲得這種設(shè)備后將

能為集團(tuán)提供的盈利，如上表所示，采用逆推法，計(jì)算如下：

k＝3時(shí)，

，即

*

S3x3x3

0000

1141

2262

33113

44124

55125

k＝2時(shí)，

，即

*

x2S2012345x2

0000

14551

265＋410102

3115＋610＋411142

4125＋1110＋611＋411161、2

5125＋1210＋1111＋611＋411212

k＝1時(shí)，

，即

*

x1s1012345x1

5213＋167＋149＋1012＋513210、2

∴分配給各廠的設(shè)備分別為2、2、1或者0、2、3．獲得最大利益21。

六、（20分）在下圖中，分別求v1至v6，v4至v5，v6至V2的最短路和最

短距離。

答：用Floyd方法求解：

k

令網(wǎng)絡(luò)的權(quán)矩陣為，D表示至少經(jīng)過vk時(shí)的距

離，括號(hào)內(nèi)數(shù)字即變動(dòng)的距離。

，

，

∴可得v1至v6的沒有通路，最短距離是∞。

v4至v5的最短路是v4—v2—v3—v5，最短距離是－3。

v6至V2的最短路是v6—v4—v2，最短距離－1。

七、排隊(duì)論（20分）

假設(shè)到達(dá)一個(gè)公用電話間的顧客數(shù)服從普阿松分布，有兩個(gè)公用電話間

同時(shí)使用。兩個(gè)顧客相繼到達(dá)的平均間隔時(shí)間為3分鐘，通話時(shí)間服從

平均數(shù)為3分鐘的普阿松分布。公用電話間內(nèi)最多只能容納5人。假設(shè)到

達(dá)的顧客見到電話間里已有5個(gè)人時(shí)就離開這個(gè)公用電話間去別處打電

話。

求：

（1）一位到達(dá)的顧客只得離開這個(gè)電話間去別處打電話的概率；

（2）平均隊(duì)長；

（3）電話局打算只要顧客在隊(duì)伍中的平均等待時(shí)間不超過1分鐘，就搬

走一臺(tái)電話。但如果因?yàn)闇p少一臺(tái)電話會(huì)使顧客排隊(duì)等待時(shí)間超過5分

鐘，那么電話局就會(huì)放棄原來的打算。問這個(gè)公用電話間的服務(wù)設(shè)施是

否需要改變？

答：（1）

即去別處打電話的概率是0.3276。

（2）。

（3）當(dāng)撤走一臺(tái)電話時(shí)，此問題變成M/M/1/5排隊(duì)模型。

∴電話設(shè)施不會(huì)改變。

2006年北京交通大學(xué)交通運(yùn)輸學(xué)院417管理運(yùn)籌學(xué)考研真題

2006年北京交通大學(xué)交通運(yùn)輸學(xué)院417管理運(yùn)籌學(xué)考研真題及詳解

北京交通大學(xué)2006年碩士研究生入學(xué)考試試卷

考試科目：417管理運(yùn)籌學(xué)

注意事項(xiàng)：答案一律寫在答題紙上，寫在試卷上的不予裝訂和評(píng)分！

一、（25分）設(shè)有如下的線性規(guī)劃問題：

（1）寫出該線性規(guī)劃的標(biāo)準(zhǔn)型；（10分）

答：

（2）求原規(guī)劃的最優(yōu)解和最優(yōu)目標(biāo)函數(shù)值。（15分）

答：加入一個(gè)人工變量x7，利用單純形法計(jì)算如下：

cj－123－30000

’’’’’

CBXBbx1x2x3x3x4x5x7x6

0x47211－11000

0x56－3－1－2[2]0100

0x74423－30010

0x6401000001

－123－30000

0x410[1/2]1/20011/200

’’

－3x33－3/2－1/2－1101/200

0x7131/21/20003/210

0x6401000001

－11/21/20003/200

’

－1x12011002100

’’

－3x31301－113200

0x730000－1110

0x6401000001

060011700

’’’’’

∴x1＝－x1＝－20，x2＝x2＋2＝2，x3＝x3－x3＝－13；

得到最優(yōu)解X*＝[－20，2，－13]T，minz＝－55。

二、（25分）標(biāo)準(zhǔn)型線性規(guī)劃問題（minZ＝CX，AX＝b，X≥0）的最

優(yōu)單純型表為：

其中：x4，x5是對(duì)應(yīng)于初始單位矩陣的松弛變量。

試求：

（1）求該標(biāo)準(zhǔn)型線性規(guī)劃目標(biāo)函數(shù)的系數(shù)c1－c5；

答：松弛變量x4，x5的目標(biāo)函數(shù)為0，，且由最終單純形表可知：

解得

。

（2）設(shè)該標(biāo)準(zhǔn)型線性規(guī)劃的右端常數(shù)項(xiàng)為b，△b1，△b2分別為b的兩

個(gè)分量的增量，試分別對(duì)兩個(gè)增量進(jìn)行靈敏度分析，即求出△b1，△b2

分別變化時(shí)的取值范圍；

答：

當(dāng)，解得；

當(dāng)，解得。

（3）假定用b＋λ△b代替b，其中△b＝，－∞＜λ＜＋∞，要使現(xiàn)行

的最優(yōu)基B*不變，求λ的變化范圍，并求當(dāng)時(shí)的最優(yōu)解；

答：保持最優(yōu)基B*不變，則要求

解得，當(dāng)時(shí)，最優(yōu)解不發(fā)生變化，。

所以X*＝[3，1]T，minz＝－9。

（4）要使現(xiàn)行的最優(yōu)基不變，求目標(biāo)函數(shù)系數(shù)c1變化范圍；

答：保持最優(yōu)基不變，各非基變量檢驗(yàn)數(shù)認(rèn)識(shí)非負(fù)，則：

解得，。

∴c1變化范圍是[－3，－1]。

（5）求兩個(gè)約束的影子價(jià)格。

答：由最終單純形表可知，兩個(gè)影子價(jià)格即兩個(gè)松弛變量的檢驗(yàn)數(shù)，即

分別為3和1。

三、（25分）某工廠安排某種生活必需品在以后四個(gè)月的生產(chǎn)計(jì)劃。該

產(chǎn)品可以在以后四個(gè)月的任一個(gè)月生產(chǎn)，不過受用工和原料價(jià)格的影

響，不同的月份其生產(chǎn)成本不同，該產(chǎn)品在以后四個(gè)月的生產(chǎn)成本分別

是12，10，15，18元，件。該產(chǎn)品以后四個(gè)月需要量分別是400，700，

900和800件，考慮到生活必需品的要求，產(chǎn)品需要量必須加以滿足。該

工廠平常每月最多能生產(chǎn)700件，但在第二個(gè)月農(nóng)閑時(shí)期工廠可以聘用

臨時(shí)工加班，加班后可增產(chǎn)300件，但生產(chǎn)成本每件增加3元。過剩產(chǎn)品

每件存儲(chǔ)費(fèi)用是每月3元。試完成：

（1）仿照運(yùn)輸問題建立使總成本最小的生產(chǎn)計(jì)劃線性規(guī)劃數(shù)學(xué)模型；

（10分）

‘

答：設(shè)xij是第i個(gè)月生產(chǎn)供第j個(gè)月消費(fèi)的產(chǎn)品數(shù)量，i＝1，2，2，3，

4，j＝1，2，3，4，其中x2’表示第2個(gè)月加班完成的產(chǎn)品數(shù)量。z表示總

成本。則由題意得線性規(guī)劃數(shù)學(xué)模型：

（2）用運(yùn)輸問題表上作業(yè)法求解。（10分）

答：總供給量為700×4＋300＝3100；總需求量是400＋700＋900＋800＝

2800，故設(shè)一虛擬消費(fèi)月份5，需求量是300，成本是0，其他如

xij（i<j），成本是∞。則化成產(chǎn)銷平衡問題，利用沃格爾法得初始解如

下：（括號(hào)內(nèi)為分配量，[]內(nèi)為檢驗(yàn)數(shù)）

消費(fèi)月份12345產(chǎn)量

生產(chǎn)月份

1（400）12[5]15[2]18[2]21（300）0700

2[∞]∞（700）10[0]13[0]16[3]0700

2‘[∞]∞（0）13（200）16（100）19（0）0300

3[∞]∞[∞]∞（700）15[0]18[1]0700

4[∞]∞[∞]∞[∞]∞（700）18[1]0700

需求量4007009008003003100

所有空格檢驗(yàn)數(shù)均為非負(fù)，故得最優(yōu)解。

即4個(gè)月份分別生產(chǎn)400件、1000件、700件和700件。

（3）理論上講該問題有幾個(gè)最優(yōu)基本可行解？（5分）

答：因?yàn)榇嬖跈z驗(yàn)數(shù)為0，故有無數(shù)個(gè)最優(yōu)基本可行解。

四、（25分）某城市公共交通公司共有公交客車1000輛，可投入超負(fù)荷

和正常負(fù)荷兩種狀態(tài)運(yùn)營，如果當(dāng)年投入高負(fù)荷狀態(tài)運(yùn)營，年運(yùn)量為20

萬人／臺(tái)，且第一年投入高負(fù)荷運(yùn)營時(shí)汽車年完好率為0.8，以后各年

投入高負(fù)荷運(yùn)營時(shí)每年完好率隨車齡每年以0.1遞減，如果投入正常負(fù)

荷狀態(tài)運(yùn)營，年運(yùn)量為15萬人／臺(tái)，第一年汽車年完好率為0.95，以后

各年投入正常負(fù)荷運(yùn)營時(shí)每年完好率隨車齡以O(shè)．O5遞減，試安排5年

運(yùn)量最大的運(yùn)營方案。

答：設(shè)第k年有xk（k＝1，2，3，4，5）輛車超負(fù)荷狀運(yùn)營，年初有sk輛

完好車，則，s1＝1000輛，s2＝0.8x1

＋0.9（s1－x1），sk＋1＝sk－xk*0.01－（sk－xk）*0.05（k＝2，3，

4）。最優(yōu)指標(biāo)函數(shù)

表示k年初狀態(tài)為sk時(shí)，從第k

年至第5年末的最大運(yùn)量，。采用逆推方法計(jì)算如下：

K＝5時(shí)，

K＝4時(shí)，

k＝3時(shí)，

K＝2時(shí)，

K＝1時(shí)，

∴可知，第1年全部車輛正常運(yùn)行，從第2年開始至第5年，所有車輛超

負(fù)荷運(yùn)營，可獲得最大運(yùn)營量為80341萬人次。

五、（15分）用割平面法求解下列IP問題：

MaxZ＝8x1十5x2

st．2x1＋3x2≤12

x1－x2≤6

x1，x2≥0且為整數(shù)

答：首先用單純形法計(jì)算其相應(yīng)的線性規(guī)劃問題

cj8500

CBXBbx1x2x3x4

0x312[2]3106

0x461－1016

8500

8x1613/21/20

0x400－5/2－1/21

0－7－40

從上表中可以看出，已求得整數(shù)解XT＝[6，0]T，，maxz＝48。無需在

用割平面法進(jìn)行求解。

六、（15分）試證明定理：可行流f*是最大流的充分必要條件是不存在

關(guān)于f*的增廣鏈。

答：（1）充分性

不存在關(guān)于f*的增廣鏈，則對(duì)f*的任意一條弧都不能再進(jìn)行調(diào)整，故現(xiàn)

在的可行流流量已達(dá)到最大值，故可行流f*是最大流。

（2）必要性（用反證法）

可行流f*是最大流，假設(shè)存在關(guān)于f*的增廣鏈，則總可以對(duì)f進(jìn)行調(diào)整，

調(diào)整量。則增廣鏈上，正向弧，則整個(gè)可行流

流量都增加，得到的新的可行流大于原可行流，則可知原可行流f*不

是最大流，與題意相悖。

七、（20分）某理發(fā)店只有一個(gè)理發(fā)師，來理發(fā)的顧客到達(dá)過程為

Poisson流，平均到達(dá)間隔為20分鐘。理發(fā)時(shí)間服從負(fù)指數(shù)分布，平均需

要15分鐘。試求：

（1）理發(fā)店空閑的概率

答：該問題屬于M/M/1模型，

理發(fā)店空閑的概率。

（2）店內(nèi)恰有3個(gè)顧客的概率

答：店內(nèi)恰有3個(gè)顧客的概率。

（3）店內(nèi)至少有1個(gè)顧客的概率

答：店內(nèi)至少有1個(gè)顧客的概率。

（4）在店內(nèi)的平均顧客數(shù)

答：在店內(nèi)的平均顧客數(shù)。

（5）每位顧客在店內(nèi)的平均逗留時(shí)間

答：每位顧客在店內(nèi)的平均逗留時(shí)間。

（6）等待服務(wù)的平均顧客數(shù)

答：等待服務(wù)的平均顧客數(shù)。

（7）每位顧客平均等待時(shí)間

答：每位顧客平均等待時(shí)間。

（8）顧客在店內(nèi)逗留超過10分鐘的概率

答：顧客在店內(nèi)逗留超過10分鐘的概率。

2005年北京交通大學(xué)交通運(yùn)輸學(xué)院417管理運(yùn)籌學(xué)考研真題

2005年北京交通大學(xué)交通運(yùn)輸學(xué)院417管理運(yùn)籌學(xué)考研真題及詳解

北京交通大學(xué)2005年碩士研究生入學(xué)考試試卷

考試科目：417管理運(yùn)籌學(xué)

注意事項(xiàng)：答案一律寫在答題紙上，寫在試卷上的不予裝訂和評(píng)分！

一、（40分）已知線性規(guī)劃問題

（1）求線性規(guī)劃問題的最優(yōu)解（20分）：

答：

Cj1534000θi

CBb

08002312100800/3

012005434010300

010003[4]53001250

Cj－Zj1534000

050－1/40－1/4－1/410－3/4

020020－2[1]011/4200

52503/415/43/40001000/3

Cj－Zj－11/40－13/41/400－5/4

01001/40－13/4011/4－1

420020－2101－1

5100－3/4111/400－3/41

Cj－Zj－13/40－11/400－1/4－1

所以最優(yōu)解，最優(yōu)值＝800＋500＝1300。

（2）求對(duì)偶問題的最優(yōu)解（5分）；

答：由最終單純性表可得y1＝0，y2＝1/4，y3＝1。

（3）當(dāng)△b3＝－150時(shí)最優(yōu)基是否發(fā)生變化？為什么？（5分）；

答：

出現(xiàn)了負(fù)值，所以最優(yōu)解會(huì)發(fā)生變化。

（4）求c2的靈敏度范圍（5分）；

答：

Cj134000

CBb

01001/40－13/4011/4－1

420020－2101－1

100－3/4111/400－3/41

Cj－Zj3/4－7011－11/4003/4－44－

所以，得。

（5）如果x3的系數(shù)由[1，3，5]變?yōu)閇1，3，2]最優(yōu)基是否改變？若改變

求新的最優(yōu)解（5分）。

答：

Cj1534000

CBb

01001/40－1/4011/4－1

420020[1]101－1

5100－3/41－1/400－3/41

Cj－Zj－13/401/400－1/4－1

01503/4001/411/2－5/4

3200201101－1

5150－1/4101/40－1/23/4

Cj－Zj－15/400－1/40－1/2－3/4

所以最優(yōu)解，最優(yōu)值＝600＋750＝1350。

二、（20分）

已知某運(yùn)輸問題其供需關(guān)系及單位運(yùn)價(jià)表如下表所示：

要求：用表上作業(yè)法找出最優(yōu)調(diào)運(yùn)方案。

答：由于產(chǎn)銷不平衡，虛擬一個(gè)銷地B4，運(yùn)費(fèi)為O。

即

B1B2B3B4產(chǎn)量

A142508

A235307

A313204

銷量4852

首先，用伏格爾法求初始解，如下所示：

（）內(nèi)數(shù)據(jù)為解

產(chǎn)地銷地B1B2B3B4產(chǎn)量行差

A142（8）508223

A2353（5）0（2）7302

A31（4）3（0）2（0）0411

銷量4852