運籌學(xué)考研試題.ppt

運籌學(xué)考研試題匯編,運籌學(xué),Operational Research,1,一、線性規(guī)劃（每題20分） 設(shè)線性規(guī)劃問題為：,北京工商大學(xué)2004年攻讀碩士學(xué)位研究生入學(xué)考試試題,考試科目：物流管理與運籌學(xué),第一部分 運籌學(xué)（60分）,（1）利用兩階段法求解上述線性規(guī)劃問題； （2）寫出相應(yīng)的對偶線性規(guī)劃問題數(shù)學(xué)模型。,2,3,二、動態(tài)規(guī)劃（10分） 某商店在未來4個月里，準備利用它的一個倉庫來專門經(jīng)銷某種 商品。倉庫最大容量能儲存這種商品1000單位。假定該倉庫每 月只能出賣倉庫現(xiàn)有的貨。當商店在某月購貨時，下月初才能到 貨。預(yù)測該商品未來四個月的買賣價格如下表所示，假定商品在 1月開始經(jīng)銷時，倉庫儲有該商品500單位。試問若不計庫存費 用，該商店應(yīng)如何制定1月至4月的訂購與銷售計劃，使預(yù)期獲 利最大。試用動態(tài)規(guī)劃建立相應(yīng)的數(shù)學(xué)模型。,3,三、對策論（每題15分） 用圖解法求解矩陣對策G=S1,S2,A,其中,四、存儲論（15分） 某廠按合同每年需提供D個產(chǎn)品，不允許缺貨。假設(shè)每一周期工廠需裝配費b元，存儲費每年每單位產(chǎn)品為a元，問全年應(yīng)分幾批訂貨才能使裝配費、存儲費兩者之和為最少。,4,一、（40分）已知線性規(guī)劃問題,北京交通大學(xué)2005年碩士研究生入學(xué)考試試卷,考試科目：管理運籌學(xué),（1）求線性規(guī)劃問題的最優(yōu)解（20分）,（2）求對偶問題的最優(yōu)解（5分）,（3）當b3=150時最優(yōu)基是否發(fā)生變化？為什么？（5分）,（4）求c2的靈敏度范圍（5分）,(5)如果x3的系數(shù)由1,3,5變?yōu)?,3,2，最優(yōu)基是否改變？若改變求最優(yōu)解。（5分）,5,二、已知某運輸問題其供銷關(guān)系及單位運價表如下表所示：,要求：用表上作業(yè)法求出最優(yōu)調(diào)運方案。,6,三、（20分） 某市共有6個區(qū)，每個區(qū)都可以設(shè)消防站，市政 府希望設(shè)置消防站最少以便節(jié)省費用，但必須保 證在城區(qū)任何地方發(fā)生火災(zāi)時消防車能在15分鐘 內(nèi)趕到現(xiàn)場。據(jù)實地測定，各區(qū)之間消防車行駛 時間如下表所示。建立該問題的規(guī)劃模型。,各區(qū)之間的行駛時間,7,四、（30分） 某公司有資金10萬元，若投資于各項目（i=1，2，3）的投資額為xi時，收益分別為,問如何分配投資數(shù)額才能使總投資最大？,8,五、（20分） 求下圖所示的網(wǎng)絡(luò)的最小費用最大流。（每條弧旁邊的數(shù)字(bij, cij)）,9,六、（20分） 某廠擬用1名修理工人，已知平均送修的設(shè)備數(shù) 臺/h,現(xiàn)有兩種級別的工人可聘：A級工，其工作能力 為 臺/小時，工資每小時20元。因設(shè)備送修，平 均每臺每小時造成停工損失為40元。問應(yīng)聘用哪一種 工人，可使工廠的經(jīng)濟效益較高。,10,杭州商學(xué)院2003年碩士研究生入學(xué)考試試卷（A卷） 招生專業(yè)：管理科學(xué)與工程 考試科目：運籌學(xué) 考試時間：3小時 一、填空題（每小題4分，共28分） 1、線性規(guī)劃行問題的可行域為 ，特殊情況下為 或 。 2、用單純形法解線性規(guī)劃問題時，目標函數(shù)中人工變量的 系數(shù)為 ，附加變量的系數(shù)數(shù)為 。 3、單純形法與對偶單純形法的主要區(qū)別在于：迭代過程中，前者始終保持 的可行性，后者始終保持 的可行性。 4、分支定界法和割平面法的基本思路都是通過在原線性規(guī)劃問題中不斷 來縮小 ，最終得到原問題的整數(shù)最優(yōu)解。,11,7、動態(tài)規(guī)劃的兩種遞推方法是 和 。 對于給定的問題，如果有固定的 ，則 這兩種方法會得到相同的最優(yōu)結(jié)果。,6、序貫式算法的核心是序貫地 ，即 根據(jù)優(yōu)先級別，將線性目標規(guī)劃依次求解。,5、目標規(guī)劃中，,和,對于第i個目標約束,，如果希望,，則目標函數(shù)為 。,分別表示 變量；,12,二、計算題（共60分） 1、已知線性規(guī)劃的數(shù)學(xué)模型為：（30分） （1）用兩階段法求該模型的最優(yōu)解； （2）用對偶單純形法求該模型的最優(yōu)解； （3）寫出對偶問題的數(shù)學(xué)模型，并求其最優(yōu)解； （4）價值系數(shù)C3在什么范圍內(nèi)變化可保持最優(yōu)解不變？,13,2、求解01規(guī)劃問題：（15分）,14,3、用動態(tài)規(guī)劃方法求解整數(shù)規(guī)劃問題：（15分）,15,三、應(yīng)用題（共50分） 1、某公司計劃新開4家連鎖店B1、B2、B3、B4，并通知了4家建筑公司A1、A2、A3、A4，以便每家商店都分別由一個建筑公司來承建；設(shè)建筑公司Ai對商店Bj投標的建造費用為Cij萬元（見表）。試求解：對這4家建筑公司如何分配建造任務(wù)，才能使總建造費用最少？所需的建造費用是多少？（15分）,16,2、某公司有三個服裝加工廠甲、乙、丙，每天的服裝產(chǎn)量分別為1000件、1200件、1100件，供應(yīng)A、B、C三個銷售點，各銷售點的需求量分別為900件、1300件、1000件。從服裝廠到各個銷售點的運費和銷售利潤見下表（單位：元/件）：,該公司按以下目標調(diào)運產(chǎn)品： 第一目標：滿足各銷售點的需求； 第二目標：因路況原因，C銷售點的服裝最好由乙廠供應(yīng)； 第三目標：甲廠因倉庫限制，其產(chǎn)品應(yīng)盡量全部調(diào)出； 第四目標：利潤不少于60000元； 第五目標：調(diào)運總費用最省； 試建立該目標規(guī)劃問題的數(shù)學(xué)模型（不要求求解）。（15分）,17,3、某公司出售中央空調(diào)，空調(diào)每年的熱銷季節(jié)是69月，銷售部門對這段時間的需求時預(yù)測分別為30、20、30、40臺。每月的訂貨量只能是10、20、30、40臺這四種情況之一，所需費用相適應(yīng)為48、86、118、138萬元。每月末的存貨不應(yīng)超過40臺，儲存費按月末存貨量計算，每月每臺為100元。由于空調(diào)是季節(jié)性產(chǎn)品，因而希望熱銷前后存貨為零。問如何合理安排各個月的訂貨，才能使熱銷季節(jié)的總費用最??？（20分）,18,四、證明題（12分） 證明：如果線性規(guī)劃問題有限最優(yōu)解，則其目標函數(shù)最優(yōu)值一定可以在可行域的頂點上達到,19,杭州商學(xué)院2004年碩士研究生入學(xué)考試試卷（A卷） 招生專業(yè)：管理科學(xué)與工程 考試科目：運籌學(xué) 考試時間：3小時,2單純形法中，要把數(shù)學(xué)模型化為標準型，須引入 ；若約束條件中附加變量的系數(shù)是 或原約束為 ，則必須引入 ，以構(gòu)成初始可行基。 30-1規(guī)劃的隱枚舉法的基本思想是從所有變量等于 出發(fā)，依次指定一些變量為 ，直到得到一個可行解。,一、填空題（每空格2分，共28分） 1線性規(guī)劃問題的可行解X=（x1,x2,xn)T為基本可行解的充要條件是X的正分量對應(yīng)的系數(shù)列向量是 。,20,4.目標規(guī)劃中，,和,對于第i個目標約束,，如果希望,，則目標函數(shù)為 。,分別表示 變量；,5建立目標規(guī)劃的數(shù)學(xué)模型時，需要排定各目標 的 ，確定各目標值bi,各權(quán)系數(shù)wj。,6動態(tài)規(guī)劃模型中，狀態(tài)變量的選擇要能滿足兩個條 件： 和 。 7動態(tài)規(guī)劃中，對于一個給定的問題，如果有固定的 和 ，則順序遞推和逆序遞推會得到相同的最優(yōu)結(jié)果。,21,已知線性規(guī)劃的數(shù)學(xué)模型如下，請用圖解法求該模型的最優(yōu)解。（10分）,22,采用隱枚舉法求解0-1規(guī)劃問題（15分）,23,3已知線性規(guī)劃的數(shù)學(xué)模型如下，請寫出對偶問題的數(shù)學(xué)模型，并求其對偶問題的最優(yōu)解。（15分）,24,三、應(yīng)用題（共70分） 1某農(nóng)場有3萬畝農(nóng)田，欲種植玉米、大豆和小麥三種農(nóng)作物。各種作物每畝需施肥料分別為0.12噸、0.2噸、0.15噸。預(yù)計秋后玉米每畝可收獲500千克，售價為0.24元/千克，大豆每畝可收獲200千克，售價為1.20元/千克，小麥每畝可收獲300千克，售價為0.70元/千克。農(nóng)場年初規(guī)劃時依次考慮以下的幾個方面： P1：年終收益不低于350萬元； P2：總產(chǎn)量不低于1.25萬噸； P3：小麥產(chǎn)量以0.5萬噸為宜； P4：大豆產(chǎn)量不少于0.2萬噸； P5；玉米產(chǎn)量不超過0.6萬噸； P6：農(nóng)場現(xiàn)能提供5000噸化肥，若不夠，可在市場高價購買，但希望高價采購量愈少愈好。試建立該目標規(guī)劃問題的數(shù)學(xué)模型（不需要求解）。（16分）,25,2現(xiàn)指派五位員工去完成五項不同的工作，每人做各項工作所需費用（元）如下表所示。問應(yīng)該如何指派，才能使總的費用最小？相應(yīng)的總費用為多少？（16分）,26,3某農(nóng)場生產(chǎn)四種農(nóng)作物，每種農(nóng)作物的成本和利潤如下：,目前農(nóng)場有400公斤肥料和500公斤殺蟲劑，問每種農(nóng)作物種植多少畝才使利潤最大？（20分）,27,4已知四個城市間的距離如下表所示，求從A城市出發(fā)，經(jīng)其余城市一次且僅一次，最后返回到A城市的最短路徑與距離。（18分）,28,四、證明題（12分） 證明：若線性規(guī)劃問題存在可行域，則問題的可行域是凸集。,29,華南理工大學(xué)2005年攻讀碩士學(xué)位研究生入學(xué)考試試卷,一、設(shè)某種動物每天至少需700克蛋白質(zhì)、30克礦物質(zhì)、100毫克維生素?，F(xiàn)有5種飼料可供選用，各種飼料每公斤營養(yǎng)成分的含量及單價如下表所示：,科目：運籌學(xué) 適用專業(yè)：數(shù)量經(jīng)濟學(xué),試建立既滿足動物生長的營養(yǎng)需要，又使費用最省的選用飼料方案的線性規(guī)劃模型。（25分）,30,二、給定線性規(guī)劃：,已知,試確定該基本解是否為最優(yōu)解？如果是，給出相應(yīng)結(jié)果；否則確定進入變量和退出變量。,31,三、給定整數(shù)線性規(guī)劃：,已知其對應(yīng)線性規(guī)劃問題的最優(yōu)單純形表為：,試以x2為源行，寫出其分量切割方程和約束條件的表示形式。（20分）,32,四、某地區(qū)有三個化肥廠，設(shè)為A、B、C，其年產(chǎn)量分別為7萬噸，8萬噸和3萬噸。有四個產(chǎn)糧區(qū)需要該種化肥，設(shè)為甲、乙、丙、丁，其化肥需求量分別為6萬噸，6萬噸，3萬噸，3萬噸。已知從各化肥廠到各產(chǎn)糧區(qū)的每噸化肥的運價如下標所示（表中單位：元/噸） 試制定一個使總的運費為最少的化肥調(diào)撥方案。（25分）,33,五求解下面網(wǎng)絡(luò)中的最大流，并在圖上用切割線標記出網(wǎng)絡(luò)的最小截集。(20分),34,六. 指出下面網(wǎng)絡(luò)圖中的錯誤并予以改進：(15分),35,七. 已知某項工程的網(wǎng)絡(luò)圖如下，試確定圖中的關(guān)鍵路線并計算工程的預(yù)計完工時間與時間方差。(20分),36,北京交通大學(xué)2006年碩士研究生入學(xué)考試試卷,考試科目：管理運籌學(xué),一、（25分）設(shè)有如下線性規(guī)劃問題：,37,二、（25分）標準型線性規(guī)劃問題（max z=CX, AX=b, X0）的最優(yōu)單純形表為：,其中：x4, x5是對應(yīng)于初始單位矩陣的松弛變量。試求： 求該標準型線性規(guī)劃目標函數(shù)的系數(shù)c1-c5; 設(shè)該標準型線性規(guī)劃的右端常數(shù)項為b, b1和b2分別為b的兩個分量的增量，試分別對這兩個增量進行靈敏度分析，即求出b1和b2分別變化時的取值范圍。 要使現(xiàn)行的最優(yōu)基不變，求目標函數(shù)系數(shù)c1的變化范圍。 求兩個約束的影子價格。,38,三、某工廠安排某種生活必需品在以后四個月的生產(chǎn)計劃。該產(chǎn)品可以在以后四個月的任一個月生產(chǎn)，不過受用工和原料價格的影響，不同的月份其生產(chǎn)成本不同，該產(chǎn)品在以后四個月的生產(chǎn)成本分別是12，10，15，18元/件。該產(chǎn)品在以后四個月需要量分別是400，700，900和800件。考慮到生活必需品的需要，產(chǎn)品需要量必須加以滿足。該廠平常每月最多能生產(chǎn)700件，但在第二個月農(nóng)閑時期工廠可以聘用臨時工加班，加班后可增產(chǎn)300件，但生產(chǎn)成本每件增加3元。過剩產(chǎn)品每件儲存費用是每月3元。試完成： （1）仿照運輸問題建立使總成本最小的生產(chǎn)計劃線性規(guī)劃數(shù)學(xué)模型；（10分） （2）用運輸問題表上作業(yè)法求解。（10分） （3）理論上將該問題有幾個最優(yōu)基本可行解？（5分）,39,四、（25分）某城市公共交通公司共有公交客車1000輛，可投入超負荷和正常負荷兩種狀態(tài)運營，如果當年投入高負荷狀態(tài)運營，年運量為20萬人/臺，且第一年投入高負荷運營時汽車年完好率為0.8，以后每年投入高負荷運營時每年完好率隨車齡每年以0.1遞減，如果投入正常負荷狀態(tài)運營，年運量為15萬人/臺，第一年汽車年完好率為0.95，以后各年投入正常負荷狀態(tài)運營時每年年完好率以0.05遞減，試安排5年運量最大的運營方案。,40,五、（15分）用割平面法求解下列IP問題：,41,六、（15分）試證明定理：可行流f *是最大流的充分必要條件是不存在關(guān)于f *的增廣鏈。,42,七、（20分）某理發(fā)店只有一個理發(fā)師，來理發(fā)的顧客到達過程為possion流，平均到達間隔為20分鐘。理發(fā)時間服從負指數(shù)分布，平均需要15分鐘。試求： （1）理發(fā)店空閑的概率； （2）店內(nèi)恰有3個顧客的概率； （3）店內(nèi)至少有一個顧客的概率； （4）在店內(nèi)的平均顧客數(shù)； （5）每位顧客在店內(nèi)的平均逗留時間； （6）等待服務(wù)的平均顧客數(shù)； （7）每位顧客的平均等待時間； （8）顧客在店內(nèi)逗留超過10分鐘的概率。,43,北京交通大學(xué)2004年碩士研究生入學(xué)考試試卷,考試科目：管理運籌學(xué),一、（30分）回答下列問題： 1.什么是線性規(guī)劃問題的基可行解？ 2.什么是可行流？ 3.什么是關(guān)于可行流f 的增廣鏈？ 4.線性規(guī)劃問題最優(yōu)解共有幾種可能？并寫出各自相應(yīng)的判別準則。 5.非標準指派問題：某大型工程有5個工程項目，決定向社會公開招標。建設(shè)公司A1，A2，A3參加招標承建，根據(jù)實際情況，可允許每家公司承建一或兩項工程。報價表如右，單位萬元。如何將其化成標準的指派問題（只轉(zhuǎn)化成標準的 指派問題即可，不要求求解）,44,二、（30分）某工廠生產(chǎn)甲、乙兩種產(chǎn)品，需要A，B兩種資源，有關(guān)資料如下：,45,（1）求使工廠獲利最大的生產(chǎn)計劃（列出模型并求解） （2）確定原最優(yōu)基不變條件下，產(chǎn)品甲的單位利潤的允許可變范圍。 （3）若該廠準備出讓資源給另一個工廠，構(gòu)成原問題的對偶問題，列出對偶問題的數(shù)學(xué)模型。 （4）資源A，B的影子價格。 （5）試用此例的計算結(jié)果，驗證和解釋對偶理論中的互補松弛性定理的正確性。,46,三、（20分）設(shè)有產(chǎn)量分別為30，50，60的三個原料產(chǎn)地A1，A2，A3，欲將原料運往需求量分別為15，10，40，45的四個銷地，運價表如下。試求運費最省的調(diào)運方案。,47,四、（25分）某工廠現(xiàn)有100臺機器，擬分四期使用，在每一期都有兩種生產(chǎn)任務(wù)。根據(jù)經(jīng)驗，若把x1臺投入第一種任務(wù)，則在本期結(jié)束時將有1/3x1臺機器損壞報廢，剩下的機器全部投入第二種任務(wù)，則有1/10的機器在期末損壞報廢。如果干第一種任務(wù)時每臺機器可獲利潤10，干第二種任務(wù)時每臺機器可獲利潤7，問應(yīng)如何分配使用機器以使四期的總利潤最大（期末剩下的完好機器數(shù)量不限）,48,五、求下圖所示網(wǎng)絡(luò)的最大流（弧旁的數(shù)字是容量，流量），并指出截集。(25分),49,七、（20分）某修理店只有一個修理工人，來修理的顧客到達次數(shù)服從普阿松分布，平均每小時4人。修理時間服從負指數(shù)分布，平均需6分鐘。求： （1）修理店空閑的概率； （2）店內(nèi)有3個顧客的概率； （3）店內(nèi)至少有一個顧客的概率； （4）在店內(nèi)顧客的平均數(shù)； （5）在店內(nèi)的平均逗留時間； （6）等待服務(wù)的顧客平均數(shù)； （7）平均等待修理時間； （8）如果店內(nèi)已有3個顧客，那么后來的顧客即不再排隊，其他條件相同，求店內(nèi)空閑的概率和店內(nèi)顧客平均數(shù)。,50,2019/10/26,51,物流工程與管理方向考試運籌學(xué)的學(xué)習(xí)與方向,1 西南交大 物流工程 專業(yè)課 管理運籌學(xué) 2 北京交大 交通運輸規(guī)劃與管理 運輸與物流 專業(yè)課 管理運籌學(xué) 3 大連海事 交通運輸規(guī)劃與管理 專業(yè)課 運籌學(xué) 4 哈工大 土地資源管理 專業(yè)課 運籌學(xué),52,7.西安建筑科技大學(xué) 管理學(xué)院工程管理專業(yè) 101統(tǒng)考政治201統(tǒng)考英語303數(shù)學(xué)三416技術(shù)經(jīng)濟學(xué)或417運籌學(xué) 4.東南大學(xué) 土木學(xué)院建設(shè)與房地產(chǎn)系 120100管理科學(xué)與工程 南開 120100管理科學(xué)與工程 101政治201英語303數(shù)學(xué)三885管理信息系統(tǒng)或886（商學(xué)院）運籌學(xué) _ 01信息系統(tǒng)與電子商務(wù) _ 02物流與供應(yīng)鏈管理 _ 03管理科學(xué) 側(cè)重數(shù)學(xué)建模和計算機應(yīng)用，這兩科難度較大。,復(fù)試筆試科目：項目管理與工程造價或施工技術(shù)與組織設(shè)計或運籌學(xué),53,上海交大： 120100管理科學(xué)與工程 研究方向： _ 01系統(tǒng)科學(xué)與系統(tǒng)工程 _ 02管理科學(xué)與決策科學(xué) _ 03管理信息系統(tǒng) _ 04技術(shù)創(chuàng)新與管理 _ 05工程管理與項目管理 _ 06交通運輸管理 考試科目： 101政治201英語301數(shù)學(xué)一816自動控制理論或840運籌學(xué)與概率統(tǒng)計或842信息系統(tǒng)分析與設(shè)計或845管理學(xué) 840運籌學(xué)與概率統(tǒng)計 （線性規(guī)劃、圖論與網(wǎng)絡(luò)、排隊論、庫存論、決策論）運籌學(xué)清華大學(xué)編寫組編清華大學(xué)出版社1990概率論與數(shù)理統(tǒng)計（第二版）浙大編高等教育出版社1989,54,120100 管理科學(xué)與工程101政治理論201英語301數(shù)學(xué)一863運籌學(xué)或893管理經(jīng)濟學(xué) 意思就是說 你可以從這兩門中任選一門 參加考試 你可以選擇考運籌學(xué)也可以選擇管理經(jīng)濟學(xué) 一般都會選擇一門難度較低的或是自己學(xué)的比較好的參加初試,55,東南大學(xué)120100 管理科學(xué)與工程 01 國際工程管理 02 工程項目管理 03 房地產(chǎn)投資與管理 04 建筑業(yè)與建筑企業(yè)管理 05 建設(shè)項目環(huán)境管理與可持續(xù)發(fā)展 101 政治理論201 英語301 數(shù)學(xué)一926 工程經(jīng)濟 或 972 運籌學(xué) 復(fù)試科目:539 工程項目管理,北大028)光華管理學(xué)院 (120100)管理科學(xué)與工程 (101)政治 (201)英語 (301)數(shù)學(xué)一 (487)運籌學(xué)與管理信息系統(tǒng),56,北京交通大學(xué)2001年碩士研究生入學(xué)考試試卷,考試科目：管理運籌學(xué),一、（30分）某廠下一個計劃期準備利用設(shè)備甲、乙、丙生產(chǎn)A，B，C三種產(chǎn)品，生產(chǎn)單位產(chǎn)品所需的設(shè)備臺時有關(guān)數(shù)據(jù)如下：,（1）如何安排生產(chǎn)，使該廠生產(chǎn)利潤最大？最大利潤是多少？ （2）如果可利用其它廠的設(shè)備來擴大生產(chǎn)，每月可租用300臺設(shè)備甲，租金為8.4萬，問是否要租借？ （3）如果A產(chǎn)品對各種設(shè)備的生產(chǎn)消耗變?yōu)椋?，2，5）T，是否要生產(chǎn)A產(chǎn)品？,57,二、（13分）由A、B兩煤礦供應(yīng)甲、乙、丙三個城市煤炭，各煤炭可供應(yīng)量、各城市需要量及各煤礦到各城市間運價（元/噸）如下表：,由于供不應(yīng)求，經(jīng)研究平衡決定，甲城市供應(yīng)量可減少030萬噸，乙城市需求量需全部滿足，試求將甲乙兩礦煤炭全部分配出去，滿足上述條件又使總費用為最低的調(diào)運方案。,58,三、（15分）（1）對整數(shù)規(guī)劃問題,去掉變量為整數(shù)的約束，引入松弛變量x3,x4，并用單純形法求解，可得最終單純形表如下：,則下面哪個式子是這個問題的割平面方程。,59,（2）某公司有可利用資金M萬元，擬在S1，S2，S10處增建5個分店。經(jīng)市場調(diào)研和預(yù)測，增建分店時要考慮以下幾點：第i處建分店的投資為Ci萬元；S1，S2，S3三處至多建兩個分店；S4，S5兩處至少建一個分店；S6，S7，S8三處中應(yīng)建一個分店；試建立滿足上述條件且總投資額為最小的整數(shù)規(guī)劃模型。,四、（12分）某工廠為職工設(shè)立了晝夜24小時都能看病的醫(yī)療室（按單服務(wù)臺處理）。醫(yī)療室有兩個供病人等候看病的椅子，病人到達醫(yī)療室如沒有座位就依次站立等候。病人按泊松流到達，平均每小時到達3人，醫(yī)生給病人看病時間服從負指數(shù)分布，平均給每個病人看病時間為12分鐘。因病人看病給工廠造成的損失為20元。 （1）求病人到達醫(yī)療室需要站立等候的概率。 （2）平均每個病人在醫(yī)療室要等待多長時間。 （3）工廠每天損失的期望值。,60,五、（15分）從兩口油井v1，v2經(jīng)管道將原油輸至脫水處理廠v5，中間經(jīng)過v3,v4兩個泵站。下圖中弧旁的數(shù)字為各管道的最大通過能力（噸/小時）。求從油井每小時能輸送到處理廠的最大流量。（寫出求解的過程和結(jié)果）,20,10,10,30,40,20,61,六、（15分）某公司總部有一部貨車沿著公路給4個零售店卸下5箱貨物，如果各零售店出售該貨物所得利潤如下表所示。,（1）求使總利潤最大的動態(tài)規(guī)劃遞推方程。,62,（2）如果用逆推法，階段k表示第k個零售店，pk(xk)表示給零售店k得到xk箱貨物的利潤，f k(sk)表示第k店到第n(n=4)店的總利潤,則k=4，k=3時動態(tài)規(guī)劃求解過程如下表給出，試完成后面各階段的動態(tài)規(guī)劃求解過程。,63,64,北京交通大學(xué)2000年碩士研究生入學(xué)考試試卷,考試科目：管理運籌學(xué),一、是非選擇題（回答是與否，每題1.5分，共15分） 1.線性規(guī)劃問題的基本類型是“max”類型。 2.線性規(guī)劃問題的每一個基可行解對應(yīng)可行域的一個頂點。 3.已知y1*為線性規(guī)劃對偶最優(yōu)解的一個分量，說明在原最優(yōu)生產(chǎn)計劃中第一種資源已完全耗盡。 4.因為資源的影子價格不是市場價格，所以它們兩者不可能相等。 5.當一個運輸問題的調(diào)運方案存在負檢驗數(shù)時，它不可能是最優(yōu)方案。 6.整數(shù)規(guī)劃解的目標值一般不優(yōu)于其相應(yīng)線性規(guī)劃問題的最優(yōu)值。,65,7.存儲論研究的中心問題是供應(yīng)和需求問題。 8.經(jīng)濟訂貨批量是數(shù)量最低的訂貨批量。 9.任何圖中，次為奇數(shù)的頂點必為2的倍數(shù)。 10.圖G=（V，E），其邊數(shù)等于頂點數(shù)減1，則G是樹。,66,二、已知某生產(chǎn)計劃問題的線性規(guī)劃模型及求解的最終單純形表：,1.用圖解法求原問題的最優(yōu)解。 2.寫出其對偶問題，并用對偶單純形法求對偶問題的最優(yōu)解。 3.對目標函數(shù)c1=3進行靈敏度分析。 4.若約束常數(shù)b2=8減少1個單位，求新的最優(yōu)解。（25分）,67,三、某公司計劃從bi(i=1,2,8)等8個可供選擇的城市中決策籌建4個分公司，相應(yīng)的建設(shè)費為Ci(i=1,2,8) 并規(guī)定：b1，b2，b8最多選一個； b3，b4，b5最少選一個； b6，b7，b8 最多只能選擇兩個。 試建立該問題的數(shù)學(xué)模型。（10分）,68,四、現(xiàn)有四個水泥產(chǎn)地發(fā)運15（萬噸）水泥供三個工地使用，需要量是19（萬噸），各產(chǎn)地及工地供銷量以及運送1噸水泥運價（元）如表所示：設(shè) 1.B1工地需要供給3萬噸優(yōu)質(zhì)水泥； 2.B2工地可取得當?shù)?萬噸水泥補 充使用； 3.B3工地可使用低標號水泥； 4.A3水泥廠可生產(chǎn)3萬噸優(yōu)質(zhì)水泥， 剩余生產(chǎn)的是一般水泥，A4生產(chǎn)低 標號水泥，其他產(chǎn)地生產(chǎn)一般水泥。 試求在滿足以上條件下，使運費達 到最少的運輸方案。（20分）,69,五、用Dijkstra算法求v1到各點的最短路。（15分）,70,六、某廠可同時采購I，II，III三種元件，年需要量分別為DI=2000，DII=4000，DIII=5000，每個年存儲費分別為C1I=0.1，C1II=0.08，C1III=0.15，每次采購訂貨費C2=150元，求共同的訂購周期和各自的經(jīng)濟訂購批量，并計算三種元件聯(lián)合采購比分別單獨采購全年節(jié)省的費用。（15分）,71,北京交通大學(xué)2003年碩士研究生入學(xué)考試試卷,考試科目：管理運籌學(xué),一、已知線性規(guī)劃問題（35分）,試用單純形法求最優(yōu)解。 寫出原問題的對偶問題，并根據(jù)對偶理論，直接求出對偶問題的最優(yōu)解。 如果增加一個新的變量x6(x60)， ，c6=7，原問題的最優(yōu)解有何變化。 如果添加一個新的約束x1+2x2+x34，原問題的最優(yōu)解有何變化。,72,二、有三家企業(yè)A1，A2，A3生產(chǎn)同一種產(chǎn)品供應(yīng)三個用戶B1，B2，B3，A1企業(yè)至少要發(fā)出60個單位的產(chǎn)品，它最多能生產(chǎn)110個單位產(chǎn)品；A2企業(yè)必須發(fā)出70個單位產(chǎn)品；A3企業(yè)至少發(fā)出40個單位產(chǎn)品。各用戶的需求量分別為100，40和60個單位，生產(chǎn)企業(yè)到用戶的單位運價見下表。用表上作業(yè)法求該運輸問題的最優(yōu)解。（20分）,73,三、甲、乙、丙、丁和戊五條生產(chǎn)線去生產(chǎn)A、B、C、D和E五種產(chǎn)品。已知每條生產(chǎn)線生產(chǎn)各種產(chǎn)品所產(chǎn)生的效益如下表所示。試確定總效益為最大的指派方案。（20分）,74,四、求下圖從vs到vt的最小費用最大流。圖中弧旁的數(shù)字為（費用，容量）（20分）,（5，6）,（3，4）,（1，1）,（2，3）,（9，2）,（4，1）,（3，2）,（4，10）,vs,vt,v1,v2,v3,75,五、某市為方便居民就醫(yī)，擬在新建的居民小區(qū)建設(shè)若干所醫(yī)院。已知備選地址代碼及其所能覆蓋的居民小區(qū)編號如下標，試問，為覆蓋所有小區(qū)，至少應(yīng)建多少所學(xué)校。列出模型，不用求解。 （15分）,76,六、某汽車檢測站有一條檢測線，要求做檢測的車輛按普阿松流到達，平均每小時6輛。每輛車的檢測時間服從負指數(shù)分布，平均每輛10分鐘。用于等待檢測的停車泊位有5個，當無停車泊位時，來檢測的車輛自動離去，到其他檢測站檢測。試計算： 1.某車輛一到達就可以進行檢測的概率； 2.等待檢測的平均車數(shù)； 3.每輛車在檢測線上逗留的期望時間； 4.在可能到來的車輛中，有百分之幾不等待離開； 5.如果車輛因停車泊位被占用而離去，每輛車損失a元，求每小時因車輛離去而造成的損失。（20分）,77,七、設(shè)某臺新設(shè)備的年效益及年均維修費、更新凈費用如下表。試確定今后4年內(nèi)的更新策略，使總收益最大。（要求寫出狀態(tài)轉(zhuǎn)移方程和遞推公式）。設(shè)折扣因子為1，單位萬元。（20分）,78,79,北京交通大學(xué)2000年碩士研究生入學(xué)考試試卷,考試科目：管理運籌學(xué),一、是非選擇題（回答是與否，每題1.5分，共15分） 1.線性規(guī)劃問題的基本類型是“max”類型。 2.線性規(guī)劃問題的每一個基可行解對應(yīng)可行域的一個頂點。 3.已知y1*為線性規(guī)劃對偶最優(yōu)解的一個分量，說明在原最優(yōu)生產(chǎn)計劃中第一種資源已完全耗盡。 4.因為資源的影子價格不是市場價格，所以它們兩者不可能相等。 5.當一個運輸問題的調(diào)運方案存在負檢驗數(shù)時，它不可能是最優(yōu)方案。 6.整數(shù)規(guī)劃解的目標值一般不優(yōu)于其相應(yīng)線性規(guī)劃問題的最優(yōu)值。,80,7.存儲論研究的中心問題是供應(yīng)和需求問題。 8.經(jīng)濟訂貨批量是數(shù)量最低的訂貨批量。 9.任何圖中，次為奇數(shù)的頂點必為2的倍數(shù)。 10.圖G=（V，E），其邊數(shù)等于頂點數(shù)減1，則G是樹。,81,二、已知某生產(chǎn)計劃問題的線性規(guī)劃模型及求解的最終單純形表：,1.用圖解法求原問題的最優(yōu)解。 2.寫出其對偶問題，并用對偶單純形法求對偶問題的最優(yōu)解。 3.對目標函數(shù)c1=3進行靈敏度分析。 4.若約束常數(shù)b2=8減少1個單位，求新的最優(yōu)解。（25分）,82,三、某公司計劃從bi(i=1,2,8)等8個可供選擇的城市中決策籌建4個分公司，相應(yīng)的建設(shè)費為Ci(i=1,2,8) 并規(guī)定：b1，b2，b8最多選一個； b3，b4，b5最少選一個； b6，b7，b8 最多只能選擇兩個。 試建立該問題的數(shù)學(xué)模型。（10分）,83,四、現(xiàn)有四個水泥產(chǎn)地發(fā)運15（萬噸）水泥供三個工地使用，需要量是19（萬噸），各產(chǎn)地及工地供銷量以及運送1噸水泥運價（元）如表所示：設(shè) 1.B1工地需要供給3萬噸優(yōu)質(zhì)水泥； 2.B2工地可取得當?shù)?萬噸水泥補 充使用； 3.B3工地可使用低標號水泥； 4.A3水泥廠可生產(chǎn)3萬噸優(yōu)質(zhì)水泥， 剩余生產(chǎn)的是一般水泥，A4生產(chǎn)低 標號水泥，其他產(chǎn)地生產(chǎn)一般水泥。 試求在滿足以上條件下，使運費達 到最少的運輸方案。（20分）,84,五、用Dijkstra算法求v1到各點的最短路。（15分）,85,六、某廠可同時采購I，II，III三種元件，年需要量分別為DI=2000，DII=4000，DIII=5000，每個年存儲費分別為C1I=0.1，C1II=0.08，C1III=0.15，每次采購訂貨費C2=150元，求共同的訂購周期和各自的經(jīng)濟訂購批量，并計算三種元件聯(lián)合采購比分別單獨采購全年節(jié)省的費用。（15分）,86,華中科技大學(xué)2007年考研運籌學(xué)試題,適用專業(yè):管理科學(xué)與工程、工商管理等,一、（20分）已知一個線性規(guī)劃問題的靈敏度分析報告如下：,變動單元格,87,約束條件,（1）當x1的目標系數(shù)增加2單位，同時x2的目標系數(shù)減少5單位時最優(yōu)解是否改變？ （2）當?shù)谝患s束的右端項減少2單位，同時第二約束的右端增加3單位，第三約束的右端項增加2單位時目標值改變多少？ （3）第三約束是起作用約束？第二約束的影子價格為-2表示什么意義？,88,二、（20分）已知線性規(guī)劃,（1）填空完成上面單純形表，并求其對偶問題的最優(yōu)解。 （2）求出C2和C3的值，并確定C3增加多少時，線性規(guī)劃有無窮多個最優(yōu)解。,的最優(yōu)單純形表,89,三、求解線性規(guī)劃,90,四、（10分）某人求解某平衡運輸問題，得到該問題的最優(yōu)運輸方案和最優(yōu)運費，然后將某一產(chǎn)地的產(chǎn)量增加20單位，同時將另一銷地的銷量增加20單位，其他數(shù)據(jù)不變，結(jié)果最優(yōu)運費在運量增加后反而下降，請解釋為什么會發(fā)生這種現(xiàn)象？,91,西北工業(yè)大學(xué)復(fù)試大綱,運籌學(xué)考試大綱 一、考試內(nèi)容 1.線性規(guī)劃與單純形方法：線性規(guī)劃的基本概念；線性規(guī)劃的基本理論；單純形方法；線性規(guī)劃應(yīng)用舉例。 2.線性規(guī)劃的對偶理論及其應(yīng)用：線性規(guī)劃的對偶問題；線性規(guī)劃的對偶理論；對偶解的經(jīng)濟解釋；對偶單純形方法；靈敏度分析。 3.運輸問題：運輸問題的數(shù)學(xué)模型；表上作業(yè)法；產(chǎn)銷不平衡的運輸問題。 4.目標規(guī)劃：多目標線性規(guī)劃問題；目標規(guī)劃模型及其求解方法；目標規(guī)劃的靈敏度分析；應(yīng)用舉例。 5.整數(shù)規(guī)劃：整數(shù)規(guī)劃問題的提出；求解整