北京交通大學交通運輸學院《942管理運籌學》歷年考研真題匯編（含部分答案）合集

目錄2015年北京交通大學交通運輸學院942管理運籌學考研真題2014年北京交通大學交通運輸學院942管理運籌學考研真題2013年北京交通大學交通運輸學院942管理運籌學考研真題2012年北京交通大學交通運輸學院942管理運籌學考研真題2011年北京交通大學交通運輸學院942管理運籌學考研真題2010年北京交通大學交通運輸學院942管理運籌學考研真題2010年北京交通大學交通運輸學院942管理運籌學考研真題及詳解2009年北京交通大學交通運輸學院942管理運籌學考研真題2009年北京交通大學交通運輸學院942管理運籌學考研真題及詳解2008年北京交通大學交通運輸學院942管理運籌學考研真題2008年北京交通大學交通運輸學院942管理運籌學考研真題（含部分答案）

2007年北京交通大學交通運輸學院417管理運籌學考研真題2007年北京交通大學交通運輸學院417管理運籌學考研真題及詳解2006年北京交通大學交通運輸學院417管理運籌學考研真題2006年北京交通大學交通運輸學院417管理運籌學考研真題及詳解2005年北京交通大學交通運輸學院417管理運籌學考研真題2005年北京交通大學交通運輸學院417管理運籌學考研真題及詳解

2004年北京交通大學交通運輸學院管理運籌學考研真題2004年北京交通大學交通運輸學院管理運籌學考研真題及詳解2003年北方交通大學交通運輸學院管理運籌學考研真題2003年北方交通大學交通運輸學院管理運籌學考研真題及詳解2002年北方交通大學交通運輸學院管理運籌學考研真題2002年北方交通大學交通運輸學院管理運籌學考研真題及詳解

2001年北方交通大學交通運輸學院管理運籌學考研真題2001年北方交通大學交通運輸學院管理運籌學考研真題及詳解2000年北方交通大學交通運輸學院管理運籌學考研真題

2015年北京交通大學交通運輸學院942管理運籌學考研真題

2014年北京交通大學交通運輸學院942管理運籌學考研真題

2013年北京交通大學交通運輸學院942管理運籌學考研真題

2012年北京交通大學交通運輸學院942管理運籌學考研真題

2011年北京交通大學交通運輸學院942管理運籌學考研真題

2010年北京交通大學交通運輸學院942管理運籌學考研真題

2010年北京交通大學交通運輸學院942管理運籌學考研真題及詳解北京交通大學2010年碩士研究生入學考試科目代碼：942科目名稱：管理運籌學一、判斷（正確的打“∨”，錯誤的打“×”）1．線性規(guī)劃問題的每一個基解對應可行域的一個頂點；（北京交通大學2010年研）【答案】×【解析】基解不一定是可行解，基可行解對應著可行域的頂點。2．若、分別是某一線性規(guī)劃問題的最優(yōu)解，則也是該線性規(guī)劃問題的最優(yōu)解，其中、為正的實數；（北京交通大學2010年研）【答案】×【解析】必須規(guī)定，當一線性規(guī)劃問題存在兩個最優(yōu)解時，則它一定存在無數個最優(yōu)解，3．已知為線性規(guī)劃問題的對偶問題的最優(yōu)解，若，則說明在最優(yōu)生產計劃中第種資源已經完全耗盡；（北京交通大學2010年研）【答案】∨【解析】對偶問題互補松弛性質中；當表明在最優(yōu)生產計劃中第種資源已經完全耗盡。時，有，4．整數規(guī)劃問題最優(yōu)解的目標函數值一定優(yōu)于其相應線性規(guī)劃問題最優(yōu)解的目標函數值；（北京交通大學2010年研）【答案】×【解析】因為附加了整數條件，其可行域比其相應線性規(guī)劃問題的可行域減小，故整數規(guī)劃問題最優(yōu)解的目標函數值一定不優(yōu)于其相應線性規(guī)劃問題最優(yōu)解的目標函數值。5．指派問題效率矩陣的每個元素乘以同一大于0的常數，將不影響最優(yōu)指派方案；（北京交通大學2010年研）【答案】∨【解析】效率矩陣每個元素乘以同一大于0的常數，即目標函數的系數同時增大k倍，不會影響最優(yōu)基的變化，故不影響最優(yōu)指派方案。6．如果圖T是樹，則T中一定存在兩個頂點，它們之間存在兩條不同的鏈；（北京交通大學2010年研）【答案】×【解析】連通且不含圈的無向圖稱為樹。因此任意兩點間必定只有一條鏈。7．任一圖研）都存在支撐子圖和支撐樹；（北京交通大學2010年【答案】×【解析】當圖中存在一個頂點，其次為0時，則該圖不存在支撐樹。8．網絡圖中任何一個結點都表示前一工序的結束和后一工序的開始；（北京交通大學2010年研）【答案】×【解析】網絡圖的起始點只表示一工序的開始，結束點只表示一工序的結束。9．結點最早時間同最遲時間相等的點連接的線路就是關鍵路線；（北京交通大學2010年研）【答案】∨【解析】關鍵路線是指總時差為零的工作鏈，而該工作鏈是由一系列最早時間同最遲時間相等的點連接而成的。10．假如到達排隊系統的顧客為普阿松流，則依次到達的兩名顧客之間的間隔時間服從負指數分布；（北京交通大學2010年研）【答案】∨【解析】設N（t）為時間[0，t]內到達系統的顧客數，則為參數為的普阿松流的充要條件是：相繼到達時間間隔服從相互獨立的參數為的負指數分布。11．運輸問題是一種特殊的線性規(guī)劃模型，因而其求解結果也可能出現四種情況之一：有唯一最優(yōu)解，有無窮多最優(yōu)解，無界解，無可行解；（北京交通大學2010年研）【答案】×【解析】運輸問題是一種特殊的線性規(guī)劃模型，它總存在可行解，或是存在唯一最優(yōu)解，或是有無窮最優(yōu)解。12．單純形法計算中，選取最大正檢驗數對應的變量作為換入變量，將使目標函數值得到最快的增長。【答案】∨【解析】選擇任何一個大于零的都可以，由上式可以看出，將最大正檢驗數對應的變量作為換入變量，將使目標函數值得到最快的增長。二、簡答1．試簡述求解整數規(guī)劃模型的分枝定界法剪枝的幾種情況；（北京交通大學2010年研）答：（1）某枝已經達到其范圍內的最優(yōu)解；（2）某枝域內沒有可行解時，即是不可行域；（3）某枝所得數據不優(yōu)于當前最優(yōu)解時。2．試寫出標準指派問題的線性規(guī)劃問題；（北京交通大學2010年研）答：設，則得線性規(guī)劃模型3．試寫出求解最短徑路的Dijkstra算法的步驟；（北京交通大學2010年研）答：步驟：（1）給（2）若vi點為剛得到P標號的點，考慮這樣的點vj，（vi，vj）屬于E，且vj為T標號。對vj的T標號進行如下修改：（3）比較所有具有T標號的點，把最小者改為P標號，即：當存在兩個以上最小者時，可同時改為P標號。若全部點均為P標號時停止。否則用代轉回（2）。4．試寫出M/M/1排隊系統的Little公式；（北京交通大學2010年研）答：三、（40分）某廠生產Ⅰ、Ⅱ、Ⅲ三種產品，其所需勞動力、原材料等有關數據如下：每件產品Ⅰ分別需要勞動力和原材料6個小時和3公斤，每件產品Ⅱ分別需要勞動力和原材料為3小時和4公斤，每件產品Ⅲ分別需要勞動力和原材料為5小時和5公斤；擁有的勞動力和原材料總數分別為45小時和30公斤；又知Ⅰ、Ⅱ、Ⅲ三種產品的單件利潤分別為3、1、4元。（北京交通大學2010年研）要求：1．寫出該廠獲得最大的生產計劃問題的線性規(guī)劃模型并求出最優(yōu)解；答：設三種產品的產量分別為x1、x2、x3，則得模型：將上述問題改寫為標準形式為：用單純形法計算如下：cj31400CBXBbx1x20x445630x53034x3x4x551[5]040011001310x415[3]－14x363/54/50－11/5－4/53/5－11/5003x151－1/301/3－1/34x33010－21－1/52/50－1/5－3/5得到最優(yōu)解，即生產Ⅰ、Ⅲ各5和3件。2．寫出該線性規(guī)劃問題的對偶問題，并求對偶問題的最優(yōu)解；答：對偶問題：由及上述最終單純形表可知，。3．產品Ⅰ的利潤在什么范圍內變化時，上述最優(yōu)計劃不變？答：保持最優(yōu)計劃不變，即保持各非基變量檢驗數非正，則解得。4．如果設計一種新產品Ⅳ，單件產品消耗勞動力8小時，原材料2公斤，每件可獲利3元，問該產品是否值得生產？答：新產品的產量為x6，則相對約束矩陣多一列向量單純形表中為，在最終，其檢驗數為，故值得生產。5．如果勞動力數量不變，原材料可以從市場購買，每公斤0.4元，問該廠是否購買原材料來擴大生產，以購買多少為宜？答：設購買，則①②，故可以購買原材料來擴大生產。由①②兩式得，即購買15公斤時可獲得最大效益。四、（16分）某公司有甲，乙，丙三個工廠和A，B，C三個客戶，這三個工廠在下一時期將分別生產某種產品300，500和400件，公司計劃賣給客戶A，B，C的產品數量分別為400，300，100件，客戶D想盡可能多地購買剩下的商品。工廠賣給各客戶單位產品的利潤如下表。問如何安排供應使該公司總利潤最大。答：該問題屬于平衡運輸問題，客戶D將購買300＋500＋400－（400＋300＋100）＝400（件）商品。則由沃格爾法得初始方案，并用位勢法得各空格檢驗數[]所示：ABCD供給量行差甲乙丙[－2]15[－3]13[－1]12300143002001830017[1]15[－3]1250020013[－2]1010091001040011112322需求量400300410033400223列差3234空格[乙C]檢驗數為正，故調整其所在回路，調整值為min[200，100]＝100并檢驗得：ABCD供給量甲乙丙[－2]15[－3]13[－2]1230014300100183001710015[－3]1250030013[－2]10[－1]910010400需求量400300100400所有檢驗數均小于零，即得最優(yōu)方案如下：ABCD供給量甲乙丙300300500100400100300100300需求量4003001004001200五、（20分）用動態(tài)規(guī)劃方法求解下列整數規(guī)劃問題：（北京交通大學2010年研）答：將該過程分為3個階段，決策變量為，狀態(tài)變量為，表示第k階段開始時候的狀態(tài)（k＝1，2，3），其中，最優(yōu)指標函數，表示第k階段狀態(tài)為時，第k階段至第3階段的最優(yōu)值，且逆推法。，表示每個階段的指標函數。采用k＝3時，k＝2時，k＝1時，。所以得x1*＝1，x2*＝2，x3*＝0，maxZ＝18。六、（14分）某理發(fā)店只有一個理發(fā)員，來理發(fā)的顧客到達過程為posson流，平均5人/小時；理發(fā)時間服從負指數分布，平均需要10分鐘；店內備有5把椅子供顧客等候，多余顧客將到其他理發(fā)店理發(fā)。（北京交通大學2010年研）求：（1）該理發(fā)店忙的概率；（2）該店內恰有2個顧客的概率；（3）在該店內的平均顧客數；（4）每位顧客在該店內的平均逗留時間；（5）等待服務的平均顧客數；（6）每位顧客平均等待時間；（7）顧客損失的概率。答：該問題屬于M/M/1/N模型，，，N＝5。（1）（2），∴1－P0＝0.7494，即為理發(fā)店忙的概率。∴。（3）。（4）（5）。。（6）顧客的平均等待時間是（7）。，即顧客損失的概率。2009年北京交通大學交通運輸學院942管理運籌學考研真題

2009年北京交通大學交通運輸學院942管理運籌學考研真題及詳解北京交通大學2009年碩士研究生入學考試科目代碼：942科目名稱：管理運籌學一、（50分）已知線性規(guī)劃問題如下：1．求該問題的最優(yōu)解；答：用對偶單純形法計算如下：ciCBXBb251/200x3x4x5x1x20x4－3－1－20x5－90－125－1/210[－3]011/2000x4－2/3－1－11/601[－1/6]0－1/30－1/6－611/2x3301/31－2－29/600x691/2x366112413010－2010得最優(yōu)解，X*＝（0，0，6）T，minz＝1/2×6＝3。2．寫出該線性規(guī)劃問題的對偶問題，并求對偶問題的最優(yōu)解；答：由上最終單純形表可得，，maxw＝33．分別確定x2、x3的目標函數系數c2、c3在什么范圍內變化，最優(yōu)解不變？答：（1）c2變化，最優(yōu)解不變，要保證，解得，即。（2）c3變化，最優(yōu)解不變，要保證，，解得，即。4．求約束條件右端值由變?yōu)闀r的最優(yōu)解；答：代入最終單純形表中，，因此不是最優(yōu)解。ci0x6－3611251/2000[－6]11/2x3424131－200100x41/2－1－11/6011/2x3401/310029/600－1/6－1/31/6得新的最優(yōu)解是X*＝[0，0，4]T，minz＝1/2×4＝2。5．求增加新的約束條件x1＋2x2＋x3≤5時的最優(yōu)解。答：加入松弛變量x6得下表cjCBXBb0x4－3－1－20x5－90－10x6－5－1－2251/200x3x4x5－1/210[－3]01－1001/2000x1x2x60012500x4－2/3－1－11/601/2x330x6－2－1－5/3029/601－1/6001/310－1/300[－1/3]1201/61000010000x41/3－1/2－10100－1/2－1－31/21/2x350x5613253/24得最優(yōu)解X*＝[0，0，5]T，minz＝1/2×5＝5/2。二、（25分）某鐵路企業(yè)承擔A、B、C三個城市之間的城際旅客列車運輸任務，列車的出發(fā)和到達時間如下表所示：設旅客列車從到達某站到出發(fā)至少需要2個小時的準備時間，試制定一個最佳的旅客列車車底接續(xù)方案，使該鐵路企業(yè)所使用的車底數量最少。答：題中，將達到某城市的列車當成是要完成工作的工作人員，而在該城市出發(fā)當成是要完成的工作，則3座城市的列車工作效率如下所示，數據是執(zhí)行任務需等待時間。A城市：到達出發(fā)T101T103T105T107T109T102T104T106T108T1102381362925158411319152214201623152521420B城市到達出發(fā)T102T104T106T101T103T1051615102322173221C城市到達出發(fā)T108T110T107T109751513則對于A城市，利用匈牙利算法指派任務如下：初次指派為：蓋所有的零元素，◎的個數少于54，故進行劃線覆；繼續(xù)求解，零元素，并最終求得最優(yōu)解，依然不符合，故繼續(xù)劃線覆蓋所有，即A城市中到達出發(fā)T101T103T105T107T109T102T104T106T108T110319243所需車底數是3；同理得B城市的指派為，所需車底數為2；C城市指派為，需要車底數為2。綜上，該企業(yè)總的車底數最少需要是7個。三、（20分）已知運輸問題的運價及產銷平衡表如下：要求：1．用最小元素法求該運輸問題的初始解，并進一步求出最優(yōu)解；2.A3→B3的單位運價C33變?yōu)槭裁粗禃r，有無窮多最優(yōu)解？并進一步給出兩個新的最優(yōu)方案。答：（1）該運輸問題的初始解是：B1B2B3B4產量A1A2310A310210122553銷量6101212利用位勢法計算個空格的檢驗數為：產量B1B2B3B4A1[1][0]10[1]10A2310[－2]1225A33[13]2銷量61012[7]512空格A2B2檢驗數小于0，故調整其所在回路，調整量為min（2，3）＝2，得新方案，并檢驗之，如表中所示：B1B2B3B4產量A1[－1][－2]10[－1]10A2A3151021225[13][2][7]51212銷量610仍不是最優(yōu)方案，故繼續(xù)調整，最后得最終方案如下：B1B2B3B4產量A110A210121225A3銷量61012121055（2）A3B3的檢驗數為C33－12＋10－6＝0時，即C33＝8時，有無窮多最優(yōu)解。新方案一：B1B2B3B4產量A1A210101.54.511.512250.55

A3銷量6101212新方案二：B1B2B3B4產量A1A2A310102411122515銷量6101212四、（21分）某公司生產并銷售某產品。根據市場預測，今后四個月的市場需求量如下表所示。已知生產一件產品的成本是1千元，每批產品的生產準備成本是3千元，每月僅能生產一批，每批6件。每件存儲成本為0.5千元，且第一個月初無存貨，第四個月末的存貨要求為零。求最優(yōu)生產計劃。（北京交通大學2009年研）答：采用動態(tài)規(guī)劃方法求解。設每個月生產xk件產品，xk小于等于6；sk為每個月開始的存貨量，則s1＝0，s5＝0，，表示在k月初存貨量是sk是從第表示第k個月生產xk個產品k個月開始至第4個月的最優(yōu)指標函數。時所需要的生產費用，，表示第k個月生產xk個產品時，剩余產品所需要的存儲費用，（1）k＝4時，（2）k＝3時，（3）k＝2時，（4）k＝1時，∴為最優(yōu)生產計劃。五、（20分）在下圖中，分別求v1至v6，v1至v4，v6至v2和v2至v5的最短路和最短距離。（北京交通大學2009年研）答：用Floyd方法求解：令網絡的權矩陣為k＝0，，由表示從vi到vj點或直接有邊或借v1點為中間點是的最短路長，括弧中元素為更新元素，得D（1）k＝1，；表示從vi到vj點最多經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分）某汽車加油站只有一個加油設備，汽車到達加油站的過程服從泊松分布，汽車平均到達時間間隔為5分鐘，加油站平均1個小時能加24輛車。試求：（1）加油站的空閑的概率；（2）加油站有三輛車的概率；（3）加油站有兩輛車以上的概率；（4）加油站內的平均車輛數；（5）車輛在加油站內的平均逗留時間；（6）加油站內的平均等待車數；（7）車輛的平均等待時間。答：屬于M/M/1/∞模型，。（1）加油站的空閑的概率。（2）加油站有三輛車的概率（3）加油站有兩輛車以上的概率（4）加油站內的平均車輛數即。。。（輛）。（5）車輛在加油站內的平均逗留時間（6）加油站內的平均等待車數即（7）車輛的平均等待時間（輛）。。2008年北京交通大學交通運輸學院942管理運籌學考研真題

2008年北京交通大學交通運輸學院942管理運籌學考研真題（含部分答案）北京交通大學2008年碩士研究生入學考試試卷考試科目：942管理運籌學注意事項：答案一律寫在答題紙上，寫在試卷上的不予裝訂和評分！一、（35分）已知線性規(guī)劃問題：maxZ＝3x1＋4x2＋x3（1）求線性規(guī)劃問題的最優(yōu)解：（2）求對偶問題的最優(yōu)解：（3）求b1的靈敏度范圍；（4）求c2的靈敏度范圍；如果右端值[10，16]變?yōu)閇12，10]求新問題的最優(yōu)解。答：（1）由題意，用單純形法計算。Cj34100θiCBXBb00101[2]11016221013410058Cj－Zj40Cj－Zj51/211/21/206[1]00－1110－1－2010643Cj－Zj2011/21－1/26100－1100－1－1－1此時，所有檢驗數為負，已得最優(yōu)解XT＝（6，2，0），目標函數值為Z＝26。（2）對偶問題Minw＝10y1＋16y2s．ty1＋2y2≥3①2y1＋2y2≥4②y1＋y2≥1③y1，y2≥0由互補松弛條件YXs＝0，XYs＝0；由X＝（6，2，0），得Y1s＝0Y2s＝0，即①②③為嚴格等式，即y1＋2y2＝3，2y1＋2y2＝4；所以y1＝1，y2＝1。即最優(yōu)解y1＝1，y2＝1，minw＝26。（3）靈敏度分析當b1變化△b時，可計算B－1b＋B－1由，所以。因此8≤b1≤16。（4）記即，得，所以。（5）當右端值由[10，16]變?yōu)閇12，10]時，。將其反映到最終單純性表中，再用對偶單純性法進行迭代，如下。Cj34100CBXBb43Cj－Zj7011/21－1/2－2100[－1]100－1－1－145111/201/20Cj－Zj2－1001－10－10－1－2故新問題的最優(yōu)解為X＊＝（0，5，0，2，0），最優(yōu)值為z＊＝20。二、（20）已知LP問題為要求：（1）設其偶變量為y1，y2，y3，y4，寫出其對偶問題；（2）已知原問題最優(yōu)解（x1，x2，x3，x4，）＝（2，2，4，0），試根據對偶性質直接求出對偶問題的最優(yōu)解。（北京交通大學2008年研）答：（1）對偶問題minW＝8y1＋6y2＋6y3＋9y4s．t（2）由互補松弛條件YXs＝0，XYs＝0；（x1，x2，x3，x4，）＝（2，2，4，0），則X1s＝X2s＝X3s＝0，X4s≠0，且＝0，Y1s＝Y2s＝Y3s＝0所以，因此（y1，y2，y3，y4）＝（，1，0）。三、（20）某公司有3個工廠和3個客戶，這3個工廠在下一時期將分別制造產品300，500和200件，公司答應賣給客戶1，2，3的產品分別是300，200，100件，客戶4想盡可能多的購買剩下產品。工廠i賣給客戶j的單位產品利潤如下表所示。問如何安排生產和供應才能使總利潤最大？答：用18減去圖中各個利潤，將問題轉化為運輸問題，建立產銷平衡表。產量356430001365005898200銷量300200100400用伏格爾法求解，（）內數據為解產地銷地銷量產量行差30（300）1（200）3（0）65300564（300）300112500139（100）8（100）2003318200100400列差334323324用位勢法計算所有空格的檢驗數，計算結果如下圖所示。12104－24－112354表中有負檢驗數，選擇（1，3）為調入格，調入量為100，得新的解300200200100100100再用位勢法檢驗，得檢驗數2322103－141244此時，所有檢驗數都非負，故上表中的解為最優(yōu)解。即安排A1生產300提供給B4，A2生產200提供給B1，A2生產200提供給B2，A3生產100提供給B3，A3生產100提供給B1，A3生產100提供給B4，故總利潤為15000。四、（25）某工廠有1000臺機器，擬分四個階段使用。已知在每個階段有兩種生產任務，進行第一種生產時每臺機器可收益9千元，其機器報廢率0.3，而進行第二種生產時每臺機器可收益6千元，其機器報廢率為0.1．文怎樣分配機器，使收益最大？（要求寫出動態(tài)規(guī)劃模型的基本要素并求解）（北京交通大學2008年研）答：將此題看成一個4個階段決策問題。令為狀態(tài)變量，它表示第k階段初擁有的完好機器數量，決策變量為第k階段分配給第一種生產的機器數量，于是為該階段分配給第二種生產的機器數量。狀態(tài)轉移方程為收益，則，設為第k階段的令最優(yōu)值函數表示由機器數量出發(fā)，從第k階段開始到第4階段結束時所獲得的收益最大值，故有遞推關系式：（1）k＝4時，因f4是u4的線性單調增函數，故得最大解（2）k＝3時，，相應的。故得最大解，相應的有。（3）k＝2時，當，相應的有。（4）k＝1時，當，相應的有。因s1＝1000，所以＝23793千元。計算結果表明，第1階段將1000臺機器投入第二種生產，第2階段將900臺機器投入到第二種生產，第3階段將810臺機器投入到第一種生產，第4階段將567臺機器投入到第一種生產。可得最大收益為23793千元。五、（10）為解決污水河流的污染問題，某城市擬修建污水處理站。備選的站址有A、B、C三個，其投資等技術經濟參數見下表：按環(huán)保部門要求，每年至少要從污水中清除8萬噸污染物1和6萬噸污染物2。請構造一個整數規(guī)劃模型，在滿足環(huán)保要求的前提下使投資和運行費用最小。（北京交通大學2008年研）答：設表示處理的萬噸數，，被采用時為1，未采用時為0。建立整數規(guī)劃模型minz＝500＋500x1＋400＋800x2＋300＋1000x3六、（20）某修理店只有一個修理工，來修理的顧客到達過程為poisson流，平均5人／小時。分別計算在下列修理時間分布的情況下系統的Ls，Lq，Ws與Wq的值。（1）修理時間為常數，每次修理需10分鐘；（2）修理時間為負指數分布，平均修理需10分鐘；（3）修理時間為正態(tài)分布，μ＝9分鐘，δ＝4。答：（1）當修理時間為常數（2）當修理時間為負指數分布（3）當修理時間為正態(tài)分布2007年北京交通大學交通運輸學院417管理運籌學考研真題

2007年北京交通大學交通運輸學院417管理運籌學考研真題及詳解北京交通大學2007年碩士研究生入學考試試卷考試科目：417管理運籌學注意事項：答案一律寫在答題紙上，寫在試卷上的不予裝訂和評分！一、（20分）某工廠準備生產甲、乙、丙三種產品，它們都消耗A、B兩種原材料，有關數據如下表所示：要求：構造使該廠利潤最大的線性規(guī)劃模型，并用單純型法求解。答：設三種產品的產量分別為x1、x2、x3，則得以下線性規(guī)劃模型：用單純形法計算如下：cj3140x3x451[5]040CBXBbx1x20x445630x5303431x5010x415[3]－101－14x363/54/5101/53/5－11/500－4/53x151－1/301/3－1/34x33010－21－1/52/50－1/5－3/5得到最優(yōu)解，即生產甲和丙各5和3單位。二、（40分）已知線性規(guī)劃模型Maxz＝2x1＋x2求：（1）寫出原問題的對偶線性規(guī)劃模型；（2）用對偶單純型法求解原問題的最優(yōu)解；（3）增加約束條件3x1＋2x2≤12，最優(yōu)解會有什么變化？（4）若C1由2降至1.5，C2由1升至2，最優(yōu)解會有什么變化？（5）資源b3由現在的5變成4，最優(yōu)解是否發(fā)生變化。答：（1）（2）對原問題的對偶問題利用對偶單純形法cjCBYBb0y4－2015y124y2500y3y41y50[－6]－10y5－1－5－2－1011524150024y21/301/6－1/600y5－1/3－50[－2/3]－1/3115010104024y21/4－5/415y31/215/2015/20－1/41/41/2－3/27/23/2得最優(yōu)解，X*＝[7/2，3/2]，maxz＝8.5。（3）即對偶問題增加了一變量y6，其約束變量為a＝[3，2]T，目標函數變量為12，在最終單純形表中的，，因此不是最優(yōu)解，繼續(xù)計算如下：cjCBYBby1152450012y6y2y3y4y524y21/4－5/4105y31/215/20115/200－1/41/41/41/2－3/2[3/2]7/23/2－3/224y21/6－5/21－1/6－1/31/2012y61/351502/31/3－1101040得原問題最優(yōu)解X*＝[4，0]，maxz＝8。（4）在其對偶問題中，即資源變量變化，最終單純形表中，繼繼續(xù)利用對偶單純形法計算如下：cjCBYBb15y124y2500y3y4y524y2－1/8[－5/4]10－1/41/411/2－3/207/23/25y39/415/215/20015y11/1015y33/200－4/501/5－1/5661－10023得原問題最優(yōu)解X*＝（2，3）T，maxz＝7。（5）即對偶問題c3＝4，y3是基變量，因此檢查各非基變量的檢驗數，因此最優(yōu)解不發(fā)生變化。三、（15分）求出下面運輸問題的所有最優(yōu)解。答：本題為運輸平衡問題，用沃格爾法計算如下：（）內數據為解。產地銷地B1B2B3B4產量行差A1A2A3A49（6）8（2）13（5）14（5）181141110810912（24）1411（6）13240022611122107（12）111212360銷量列差611114135051111111112用位勢法檢驗，各空格檢驗數[]內數據，存在檢驗數小于零的空格。產地銷地B1B2B3B4產量A19（6）8（2）13（5）14（5）18A2A310[2]10[3]12（24）14[1]11（6）13[1]2468[1]9[3]A4銷量10[2]7（12）11[－1]12[－1]1261435560在相應回路調整，如空格A1B3所在回路，調整量為5，最后得新方案，并檢驗如下：不存在檢驗數小于0的空格，得最優(yōu)解，∵A3B1檢驗數為0，∴最優(yōu)解不唯一。產地銷地B1B2B3B414[1]產量18A19（6）8（12）13[1]A2A310[1]10[2]12（24）14[1]11（6）13[1]248[0]9[2]6A4銷量10[2]7（2）11（5）12（5）1261435560由A3B1所在回路，任意變化可得所有最優(yōu)解如下：產地銷地B1B2B3B4產量A16－c12＋c18A2A324246c6－cA4銷量2－c5＋c51214355606C的取值范圍是[0，2]。四、（15分）用分支定界法求整數規(guī)劃問題的最優(yōu)解

Maxz＝X1＋x2答：利用單純形法先解相應的線性規(guī)劃，得最優(yōu)解如下：cj1100CBXBbx1x2x3x41x13/2107/161x210/3017/8－9/327/1600－21/16－5/32不是整數，故用分支定界法繼續(xù)求解，z0＝29/6是問題最優(yōu)解z*的上界，z＝0是一個下界，則。將問題分成問題B1和B2問題B1問題B2z1＝10/3z1＝41/9x1＝1x1＝2x2＝7/3x2＝23/9∵z1<z2，∴先將問題B2分解成B3和B4問題B3問題B4z1＝17/6z1＝14/3x1＝5/6x1＝5/3x2＝2x2＝3接著講B4分解成問題B5和B6，問題B5問題B6z1＝17/6z1＝4x1＝2x1＝3x2＝23/9x2＝1得到一整數解z＝4，X＝[3，1]T，比較個z值，發(fā)現B6的解即為最優(yōu)解。五、（20分）某部門擬將某種新設備5臺分配給甲、乙、丙3個工廠，各工廠獲得這些設備后可盈利如下表所示，這5臺設備應如何分配，使其利潤最大？用動態(tài)規(guī)劃方法求解（要求寫出狀態(tài)轉移方程和遞推方程）。答：將該問題分成3個階段，xk（k＝1，2，3，4）為決策變量即在第K階段分給k工廠xk臺設備，sk（k＝1，2，3，4）為第k階段開始時候的狀態(tài)變量，為最優(yōu)策略的指標函數，表示第k階段狀態(tài)為sk時第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）分別表示三家工廠獲得這種設備后將能為集團提供的盈利，如上表所示，采用逆推法，計算如下：k＝3時，，即S3x3x3*000114226331144125512012345k＝2時，，即x2S2012345x2*01234504565＋410115＋610＋411125＋1110＋611＋4110510141601221、22125＋1210＋1111＋611＋41121k＝1時，，即x1s1012345x1*5213＋167＋149＋1012＋513210、2∴分配給各廠的設備分別為2、2、1或者0、2、3．獲得最大利益21。六、（20分）在下圖中，分別求v1至v6，v4至v5，v6至V2的最短路和最短距離。答：用Floyd方法求解：令網絡的權矩陣為，Dk表示至少經過vk時的距離，括號內數字即變動的距離。，，∴可得v1至v6的沒有通路，最短距離是∞。v4至v5的最短路是v4—v2—v3—v5，最短距離是－3。v6至V2的最短路是v6—v4—v2，最短距離－1。七、排隊論（20分）假設到達一個公用電話間的顧客數服從普阿松分布，有兩個公用電話間同時使用。兩個顧客相繼到達的平均間隔時間為3分鐘，通話時間服從平均數為3分鐘的普阿松分布。公用電話間內最多只能容納5人。假設到達的顧客見到電話間里已有5個人時就離開這個公用電話間去別處打電話。求：（1）一位到達的顧客只得離開這個電話間去別處打電話的概率；（2）平均隊長；（3）電話局打算只要顧客在隊伍中的平均等待時間不超過1分鐘，就搬走一臺電話。但如果因為減少一臺電話會使顧客排隊等待時間超過5分鐘，那么電話局就會放棄原來的打算。問這個公用電話間的服務設施是否需要改變？答：（1）即去別處打電話的概率是0.3276。（2）。（3）當撤走一臺電話時，此問題變成M/M/1/5排隊模型?！嚯娫捲O施不會改變。2006年北京交通大學交通運輸學院417管理運籌學考研真題

2006年北京交通大學交通運輸學院417管理運籌學考研真題及詳解北京交通大學2006年碩士研究生入學考試試卷考試科目：417管理運籌學注意事項：答案一律寫在答題紙上，寫在試卷上的不予裝訂和評分！一、（25分）設有如下的線性規(guī)劃問題：（1）寫出該線性規(guī)劃的標準型；（10分）答：（2）求原規(guī)劃的最優(yōu)解和最優(yōu)目標函數值。（15分）答：加入一個人工變量x7，利用單純形法計算如下：cj－123－30000CBXBbx1’x2’x3’x3’’x4x5x7x60x4720x56－30x7440x640－111－11000－1－2[2]01002123－300100000013－300000x410[1/2]1/20011/200－3x3’’3－3/2－1/2－1101/2000x7131/20x6401/20003/2101000001－11/21/20003/200－1x1’201－3x3’’13011016002100－11320000－111000000100117000x7300x6400∴x1＝－x1’＝－20，x2＝x2’＋2＝2，x3＝x3’－x3’’＝－13；得到最優(yōu)解X*＝[－20，2，－13]T，minz＝－55。二、（25分）標準型線性規(guī)劃問題（minZ＝CX，AX＝b，X≥0）的最優(yōu)單純型表為：其中：x4，x5是對應于初始單位矩陣的松弛變量。試求：（1）求該標準型線性規(guī)劃目標函數的系數c1－c5；答：松弛變量x4，x5的目標函數為0，，且由最終單純形表可知：解得。（2）設該標準型線性規(guī)劃的右端常數項為b，△b1，△b2分別為b的兩個分量的增量，試分別對兩個增量進行靈敏度分析，即求出△b1，△b2分別變化時的取值范圍；答：當當，解得，解得；。（3）假定用b＋λ△b代替b，其中△b＝的最優(yōu)基B*不變，求λ的變化范圍，并求當，－∞＜λ＜＋∞，要使現行時的最優(yōu)解；答：保持最優(yōu)基B*不變，則要求解得，當時，最優(yōu)解不發(fā)生變化，。所以X*＝[3，1]T，minz＝－9。（4）要使現行的最優(yōu)基不變，求目標函數系數c1變化范圍；答：保持最優(yōu)基不變，各非基變量檢驗數認識非負，則：解得，。∴c1變化范圍是[－3，－1]。（5）求兩個約束的影子價格。答：由最終單純形表可知，兩個影子價格即兩個松弛變量的檢驗數，即分別為3和1。三、（25分）某工廠安排某種生活必需品在以后四個月的生產計劃。該產品可以在以后四個月的任一個月生產，不過受用工和原料價格的影響，不同的月份其生產成本不同，該產品在以后四個月的生產成本分別是12，10，15，18元，件。該產品以后四個月需要量分別是400，700，900和800件，考慮到生活必需品的要求，產品需要量必須加以滿足。該工廠平常每月最多能生產700件，但在第二個月農閑時期工廠可以聘用臨時工加班，加班后可增產300件，但生產成本每件增加3元。過剩產品每件存儲費用是每月3元。試完成：（1）仿照運輸問題建立使總成本最小的生產計劃線性規(guī)劃數學模型；（10分）答：設xij是第i個月生產供第j個月消費的產品數量，i＝1，2，2‘，3，4，j＝1，2，3，4，其中x2’表示第2個月加班完成的產品數量。z表示總成本。則由題意得線性規(guī)劃數學模型：（2）用運輸問題表上作業(yè)法求解。（10分）答：總供給量為700×4＋300＝3100；總需求量是400＋700＋900＋800＝2800，故設一虛擬消費月份5，需求量是300，成本是0，其他如xij（i<j），成本是∞。則化成產銷平衡問題，利用沃格爾法得初始解如下：（括號內為分配量，[]內為檢驗數）消費月份1生產月份2345產量1（400）12[5]15[2]18[2]21（300）070022‘[∞][∞][∞][∞]400∞（700）10[0]0700∞（0）13（200）16（100）19（0）030013[0]16[3]34需求量∞[∞]∞[∞]700∞（700）15[0]18[1]070007003100∞[∞]900∞（700）18[1]800300所有空格檢驗數均為非負，故得最優(yōu)解。即4個月份分別生產400件、1000件、700件和700件。（3）理論上講該問題有幾個最優(yōu)基本可行解？（5分）答：因為存在檢驗數為0，故有無數個最優(yōu)基本可行解。四、（25分）某城市公共交通公司共有公交客車1000輛，可投入超負荷和正常負荷兩種狀態(tài)運營，如果當年投入高負荷狀態(tài)運營，年運量為20萬人／臺，且第一年投入高負荷運營時汽車年完好率為0.8，以后各年投入高負荷運營時每年完好率隨車齡每年以0.1遞減，如果投入正常負荷狀態(tài)運營，年運量為15萬人／臺，第一年汽車年完好率為0.95，以后各年投入正常負荷運營時每年完好率隨車齡以O．O5遞減，試安排5年運量最大的運營方案。答：設第k年有xk（k＝1，2，3，4，5）輛車超負荷狀運營，年初有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)指標函數表示k年初狀態(tài)為sk時，從第k年至第5年末的最大運量，K＝5時，。采用逆推方法計算如下：K＝4時，k＝3時，K＝2時，K＝1時，∴可知，第1年全部車輛正常運行，從第2年開始至第5年，所有車輛超負荷運營，可獲得最大運營量為80341萬人次。五、（15分）用割平面法求解下列IP問題：MaxZ＝8x1十5x2st．2x1＋3x2≤12x1－x2≤6x1，x2≥0且為整數答：首先用單純形法計算其相應的線性規(guī)劃問題cj8500CBXBbx1x20x312[2]30x461－1085x31x40616008x1613/21/200x400－5/2－1/210－7－40從上表中可以看出，已求得整數解XT＝[6，0]T，，maxz＝48。無需在用割平面法進行求解。六、（15分）試證明定理：可行流f*是最大流的充分必要條件是不存在關于f*的增廣鏈。答：（1）充分性不存在關于f*的增廣鏈，則對f*的任意一條弧都不能再進行調整，故現在的可行流流量已達到最大值，故可行流f*是最大流。（2）必要性（用反證法）可行流f*是最大流，假設存在關于f*的增廣鏈，則總可以對f進行調整，調整量。則增廣鏈上，正向弧，則整個可行流流量都增加，得到的新的可行流大于原可行流，則可知原可行流f*不是最大流，與題意相悖。七、（20分）某理發(fā)店只有一個理發(fā)師，來理發(fā)的顧客到達過程為Poisson流，平均到達間隔為20分鐘。理發(fā)時間服從負指數分布，平均需要15分鐘。試求：（1）理發(fā)店空閑的概率答：該問題屬于M/M/1模型，理發(fā)店空閑的概率。（2）店內恰有3個顧客的概率答：店內恰有3個顧客的概率。（3）店內至少有1個顧客的概率答：店內至少有1個顧客的概率（4）在店內的平均顧客數。答：在店內的平均顧客數。（5）每位顧客在店內的平均逗留時間答：每位顧客在店內的平均逗留時間。（6）等待服務的平均顧客數答：等待服務的平均顧客數。（7）每位顧客平均等待時間答：每位顧客平均等待時間。（8）顧客在店內逗留超過10分鐘的概率答：顧客在店內逗留超過10分鐘的概率。2005年北京交通大學交通運輸學院417管理運籌學考研真題

2005年北京交通大學交通運輸學院417管理運籌學考研真題及詳解北京交通大學2005年碩士研究生入學考試試卷考試科目：417管理運籌學注意事項：答案一律寫在答題紙上，寫在試卷上的不予裝訂和評分！一、（40分）已知線性規(guī)劃問題（1）求線性規(guī)劃問題的最優(yōu)解（20分）：答：Cj1534000θiCBb000Cj－Zj8002120051000313143[4]5532434100100000010800/3300250050－1/40－1/4－1/410－3/4020020－2[1]011/420052503/415/43/40001000/3Cj－Zj04－11/40－13/41/4001001/40－13/4020020－2－5/411/4－1－11015Cj－Zj100－3/4111/40－13/40－11/400－3/410－1/4－1所以最優(yōu)解，最優(yōu)值＝800＋500＝1300。（2）求對偶問題的最優(yōu)解（5分）；答：由最終單純性表可得y1＝0，y2＝1/4，y3＝1。（3）當△b3＝－150時最優(yōu)基是否發(fā)生變化？為什么？（5分）；答：出現了負值，所以最優(yōu)解會發(fā)生變化。（4）求c2的靈敏度范圍（5分）；答：Cj134000CBb041001/42002100－3/40－13/40－2111/4011/410100－3/4－1－11Cj－Zj3/4－7011－11/4003/4－44－所以，得。（5）如果x3的系數由[1，3，5]變?yōu)閇1，3，2]最優(yōu)基是否改變？若改變求新的最優(yōu)解（5分）。答：Cj1534000CBb041001/420020－1/400[1]111/4－101－15Cj－Zj100－3/41－1/40－13/401/400－3/410－1/4－1031503/4200200011/411/2－5/4101－15Cj－Zj150－1/410－15/4001/40－1/23/4－1/40－1/2－3/4所以最優(yōu)解，最優(yōu)值＝600＋750＝1350。二、（20分）已知某運輸問題其供需關系及單位運價表如下表所示：要求：用表上作業(yè)法找出最優(yōu)調運方案。答：由于產銷不平衡，虛擬一個銷地B4，運費為O。即B1B2B3B4產量A142508A235307A313204銷量4852首先，用伏格爾法求初始解，如下所示：（）內數據為解產地銷地B1B22（8）5B3B40產量行差A1A2A34382233021153（5）0（2）71（4）3（0）2（0）04銷量列差4228113511220其次，用位勢法進行檢驗，得空格的檢驗數。B1B2B3B4uiA14A211A3170231vj021－2所有檢驗數均為正數，說明此時已得最優(yōu)解。即最優(yōu)調運方案為A1提供B1數量為8，A2提供給B3的量為5，提供給B4的量為2，A3提供給B1的量為4?？傻米钚∵\費16＋15＋0＋4＝35。三、（20分）某市共有6個區(qū)，每個區(qū)都可以設消防站，市政府希望設置消防站最少以便節(jié)省費用，但必須保證在城區(qū)任何地方發(fā)生火警時，消防車能在15分鐘內趕到現場。據實地測定，各區(qū)之間消防車行駛時間如下表所示。建立該問題的規(guī)劃模型。各區(qū)之間的行駛時間答：根據題中給定的約束條件，可建立如下的規(guī)劃模型四、（30分）某公司有資金10萬元，若投資于各項目（i＝1，2，3）的投資額為Xi時，效益分別為g1（x1）＝4x1，g2（x2）＝9x2，g3（x3）＝2x23問：如何分配投資數額才能使總效益最大？答：設為第k階段初剩余的投資額。令最優(yōu)指數函數表示第k階段初狀態(tài)為時，第k階段到第3階段的后部最優(yōu)收益，則該問題的基本方程為（1）k＝3時，，這是一個簡單的函數求極值問題，易知：當時，取得極大值，即。（2）k＝2時，這是一個非線性規(guī)劃問題。令極小點，根據微積分知識可得。，極大值只可能在[0，s2]端點取得，當當時，時，，此時，此時；。（3）當k＝1時，當時，但此時當小點。比較[0，10]兩個端點，＝0，時，，由微積分知識，可得200；＝10，是極40。所以。再由轉移方程順推，，所以。由于，因此，，最優(yōu)目標函數值五、（20分）求下圖所示的網絡的最小費用最大流（每條弧旁邊的數字是（bij，Cij））答：取為初始可行流。構造賦權有向圖，并求出從到的最短路，如圖（a）所示。在原網絡圖中，與這條最短路相應的增廣鏈為。在上進行調整，，得。按照上述算法依次得到，流量依次為5，7，10，11，13。注意到中已無從到的最短路，所以為最小費用最大流。六、（20分）某廠擬用1名修理工人，已知平均送修的設備數λ＝0.2臺／h，現有2種級別的工人可聘：A級工，其工作能力為μ1＝0.25臺／h，工資每小時10元；B級工，其工作能力為μ2＝0.28臺/h，工資每小時20元。因設備送修，平均每臺每小時造成停工損失為40元。問應聘那一種工人，可使工廠的經濟效益較高。答：用A級工，平均損失為0.2×20×40＋10＝170（元）。用B級工，平均損失為0.2×12.5×40＋20＝120（元）。所以應聘B級工，可使工廠的經濟效益較高。

2004年北京交通大學交通運輸學院管理運籌學考研真題

2004年北京交通大學交通運輸學院管理運籌學考研真題及詳解北京交通大學2004年碩士研究生入學考試試卷考試科目：管理運籌學注意事項：答案一律寫在答題紙上，寫在試卷上的不予裝訂和評分！一、（30分）回答下列問題：1．什么是線性規(guī)劃問題的基可行解？答：滿足線性規(guī)劃數學模型中的非負條件的基解為基可行解。2．什么是可行流？答：滿足下列條件的網絡流f稱為可行流。（1）容量限制條件對每一?。╲i，vj）∈A，（2）平衡條件對于中間點，流出量＝流入量，即對每個i（i≠s，t），有。對于起點，記對于終點，記。式中，入量）。稱為這個可行流f的流量，即發(fā)點的凈輸出量（或收點的凈輸3．什么是關于可行流f的增廣鏈？答：設f是一個可行流，是網絡的起點，是網絡的終點，是從到的一條鏈，若滿足下列條件：（1）在?。?）在弧上，上，，即中每一前向弧是非飽和弧。，即中每一后向弧是非零流弧。稱是關于可行流f的一條增廣鏈。4．線性規(guī)劃問題最優(yōu)解共有幾種可能？并寫出各自相應的判別準則。答：（1）唯一最優(yōu)解：當x≥0，且非基變量的檢驗數＜0；（2）無窮最優(yōu)解：當x≥0，且非基變量的檢驗數≤0，且有為0。5．非標準指派問題：某大型工程有五個工程項目，決定向社會公開招標，建設公司A1，A2，A3參加招標承建，根據實際情況，可允許每家建設公司承建一項或二項工程。報價表如右，單位萬元。如何將其化成標準的指派問題（只轉化成標準指派問題即可，不要求求解）答：為將非標準指派問題轉化為標準指派問題，需要使公司數目和工程數目一致，所以此題可虛擬一個工程項目B6，這個虛擬的項目由各公司承建的費用為0。又每件公司可承建一項或二項工程，所以將同一個公司虛擬成2個。即建立如下的報價表。487151204871512079171410079171410069128706912870二、（30分）某廠生產甲、乙兩種產品，需要A、B兩種資源，有關資料如下：（1）求使工廠獲利潤最大的生產計劃（列出模型并求解）；答：設生產甲，乙則用單純形法進行求解。Cj3400CBXBb00Cj－Zj61813110[2]014006402[1/2]01－1/24441/2101/28Cj－Zj100－234412002－11－11Cj－Zj00－2－1所以最優(yōu)解，最優(yōu)值＝12＋8＝20。（2）確定原最優(yōu)基不變條件下，產品甲的單位利潤的允許可變范圍；答：若變?yōu)?，則，所以。（3）若該廠準各出讓資源給另一個工廠，構成原問題的對偶問題，列出對偶問題的數學模型。答：（4）資源A、B的影子價格是多少？答：將對偶問題化為標準形式，用對偶單純形法求解。Cj－6－800CBXBb00Cj－Zj－3－1－4－1－6－110[－2]01－8000－8－1[－1/2]01－1/20－1/221/21Cj－Zj－200－4－6－8Cj－Zj21100010－211－1－4－2所以最優(yōu)解，最優(yōu)值＝12＋8＝20。所以A的影子價格為2，B的影子價格為1。（5）試用此例的計算結果，驗證和解釋對偶理論中的互補松弛定理的正確性。答：由互補松弛條件YXs＝0，XYs＝0。由于，所以y1s＝y2s＝0，即對偶問題中的約束條件為嚴格的等。與上題中用對偶單純形法所求的解相同，證明式，所以可得互補松弛定理的正確。對松弛定理的解釋見教材。三、（20分）設有產量分別30，50，60的三個原料產地A1，A2，A3，欲將原料運往需求量分別為15，10，40，45的四個銷地，運價表如下，試求運費最省的調運方案。答：由于產銷不平衡，虛擬一個銷地B5，構成產銷平衡表，用伏格爾法求初始解。（）內數據為解產地銷地B1B2B3B4B5產量行差A1A23（15）584（15）0303111174（10）86（10）0（30）5042222A31035（40）2（20）0602111銷量列差15410140345230041321321212用位勢法進行檢驗。B1B2B3B4B5uiA131202A22－1A3934－2vj3274－2由于存在負檢驗數，用閉回路法進行調整。（2，3）為調入格，調整量為min（10，40）＝10。得到如下新的分配。（）內數據為解產地銷地B1B2B38B44（15）00（30）5（30）2（30）0B5A1A2A33（15）574（10）8（10）6103繼續(xù)用位勢法進行檢驗。B1B2B3B4B5uiA121A231011

A3923－2vj3374－1此時，所有檢驗數為非負，所以此為最優(yōu)解，即A1運往銷地B115，運往B415；A2運往銷地B210，B310；A3運往銷地B330，B430。最小費用為15×3＋15×4＋4×10＋8×10＋5×30＋2×30＝435。四、（25分）某工廠有100臺機器，擬分四期使用，在每一期都有兩種生產任務。根據經驗，若把x1臺機器投入第一種任務，則在本期結束時將有1／3x1臺機器損壞報廢。剩下的機器全都投入第二種生產任務，則有1／10的機器在期束損壞報廢。如果干第一種任務時每臺機器可獲利潤10，干第二種任務時每臺機器可獲利潤7，問應如何分配使用機器以使四期的總利潤最大（期末剩下的完好機器數量不限）？答：將此題看成一個4個階段決策問題。令為狀態(tài)變量，它表示第k階段初擁有的完好機器數量；決策變量為第k階段分配給第一種生產的機器數量，于是段分配給第二種生產的機器數量。為該階狀態(tài)轉移方程為；設為第k階段的收益，則令最優(yōu)值函數表示由機器數量出發(fā)，從第k階段開始到第4階段結束時所獲得的收益最大值，故有遞推關系式：（1）k＝4時，因f4是x4的線性單調增函數，故得最大解（2）k＝3時，，相應的。故得最大解，相應的有。（3）k＝2時，當，相應的有。（4）k＝1時，當，相應的有。因s1＝100，所以＝2680（千元）。計算結果表明，第1階段將100臺機器投入第二種生產，第2階段將90臺機器投入到第二種生產，第3階段將81臺機器投入到第一種生產，第4階段將54臺機器投入到第一種生產?？傻米畲笫找鏋?680千元。五、（25分）求如下圖所示網絡的最大流（弧旁的數字表示的是（容量，流量）），并指出截集。答：（1）標號過程①首先給標上②檢查，在?、蹤z查，在弧④檢查，在弧⑤檢查，在弧；上，的標號為上，的標號為上，的標號為上，的標號為；；；。因有了標號，故轉入調整過程。（2）調整過程按點的第一個標號找到一條增廣鏈，按圖的可行流：在上調整f．調整后得如下（3）對得到的可行流進行標號：①首先給標上②檢查，在弧③檢查，在?、軝z查，在??；上，的標號為上，的標號為上，的標號為；；。因有了標號，故轉入調整過程。（4）調整過程按點的第一個標號找到一條增廣鏈，按圖的可行流：在上調整.調整后得如下（5）對得到的可行流進行標號：①首先給標上②檢查，在?、蹤z查，在?。簧?，的標號為上，的標號為；；④檢查，找不到可以標號的點，故標號無法再繼續(xù)，算法結束。最大流量為：7＋4＝11。割集為可行流圖中的虛線所示。六、（20分）某修理店只有一個修理工人，來修理的顧客到達次數服從普阿松分布，平均每小時4人，修理時間服從負指數分布，平均需6分鐘，求（1）修理店空閑的概率；答：（2）店內有3個顧客的概率；答：。（3）店內至少有一個顧客的概率；答：。（4）在店內顧客的平均數；答：。（5）在店內平均逗留時間；答：。（6）等待服務的顧客平均數；答：。（7）平均等待修理（服務）時間。答：。（8）如果店內已有3個顧客，那么后來的顧客即不在排隊，其他條件相同，求店內空閑的概率和店內顧客平均數。答：即系統的容量限制為N＝32003年北方交通大學交通運輸學院管理運籌學考研真題

2003年北方交通大學交通運輸學院管理運籌學考研真題及詳解北方交通大學2003年碩士研究生入學考試試卷考試科目：管理運籌學注意事項；答案一律寫在答題紙上，寫在試卷上的不予裝訂和評分。一、已知線性規(guī)劃問題（35分）1．試用單純形法求最優(yōu)解；答：加入松弛變量之后利用單純形法求解如下：cj23100CBXBbx1x2x3x41x500x4310x591211[4]73101000x43/4[3/4]0－3/413x29/41/417/45/40－17/40－1/41/4－3/402x1113x22000－14/3－1/3－1/31/313/20－3/2－5/3－1/3得到最優(yōu)解，X*＝[1，2，0]T，maxz＝8。2．寫出原問題的對偶問題，并根據對偶理論，直接求出對偶問題的最優(yōu)解；答：，根據對偶理論，得其最優(yōu)解Y*＝[5/3，1/3]。3．如果增加一個新的變量x6（x6≥0），P6＝C6＝7，原問題的最優(yōu)解有何變化；答：在最終單純形表中，，xk的約束變量為，檢驗數。所以最優(yōu)解發(fā)生變化，繼續(xù)計算如下：cj2310072x11103x220100－14/3－1/3[1]3/2－1/31/30－3/2－5/3－1/357xk1103x2201－50－14/3－1/31[3/2]－1/31/307/2－25/34/307xk7/312/3010/9－1/911x34/302/31－2/9[2/9]0－68/95/90－5－7/307xk3110x56031/219/2－1010100－5－4－5/2－7得最優(yōu)解，X*＝[0，0，0，3]，maxz＝21。4．如果添加一個新的約束X1＋2X2＋X3≤4，原問題的最優(yōu)解有何變化。答：加入一個松弛變量x6，重新計算如下：cjCBXBbx1x2x30x4310x5910x6412231000x4x5x61000100010001147[2]1310x41[1/2]01/210－1/20x51－10501－23x221/211/2001/21/20－1/200－3/22x1210x5303x210001061020－121－3－1010－1－10－1得到最優(yōu)解X*＝[2，1，0]T，maxz＝7。二、有三家企業(yè)A1、A2和A3生產同一種產品供應三個用戶Bl，B2和B3，Al企業(yè)至少要發(fā)出60個單位的產品，它最多能生產ll0個單位產品：A2企業(yè)必須發(fā)出70個單位產品：A3企業(yè)至少發(fā)出40個單位的產品。各用戶的需求量分別為100、40和60個單位。生產企業(yè)到用戶的單位運價見下表。用表上作業(yè)法求該運輸問題的最優(yōu)解。（20分）答：由題意設生產企業(yè)A1‘產量是30，其到個用戶的運價與A1相同；A3’產量是30，其到各用戶運價與A3相同。此時產量是230單位，故再增加一虛擬用戶B4，需求量是30，A1、A2、A3到它的運價皆是∞，兩虛擬企業(yè)到它的運價是0，則可得運輸平衡問題。用位勢法得初始方案（括號內數據）并檢驗（[]內數據）如下：用戶生產企業(yè)B1B3B3B4產量A1A1’302[2]4303[∞]∞60[0]2[2]43030030A2A3A3’需求量701[4]5[4]6[∞]∞70[1]3402[1]4[∞]∞40[1]302[1]430030100406030可以得此即為最優(yōu)解。最優(yōu)方案即用戶生產企業(yè)B1B3B3產量A1A23070609070A3需求量40401004060三、甲、乙、丙、丁和戊五條生產線去生產A、B、C、D和E五種產品。已知每條生產線生產各種產品所產生的效益如下表所示，試確定總效益為最大的指派方案。（20分）答：用表中最大元素10減去每一個元素，得到標準形式的最小化指派問題：指派任務得，顯然◎的個數小于5個，劃線覆蓋0元素。未被覆蓋區(qū)域數據減去1，同時劃線列加上1，并重新指派任務得，繼續(xù)劃線，未被覆蓋區(qū)域數據減去1，同時劃線列加上1，并重新指派個，指派成功。則◎的個數等于5即：甲生產線生產產品D；乙生產線生產產品B；丙生產線生產產品C；丁生產線生產產品A，戊生產線生產產品E，總效益最大為37。四、求下圖從Vs至Vt的最小費用最大流。圖中弧旁數字為（費用，容量）。（20分）答：（1）取f（0）＝0為初始可行流。（2）構造賦權圖W（f（0）），用Dijkstr