北京理工大學運籌學

北京理工大學運籌學（2002）、（15分）用大M法或兩階段法求解下列線性規(guī)劃問題：minz-2氣+3x2^xi>125x+x>350s.t.\122X]+x2<600X],x2>0二、（15分）1、設q為目標函數中氣的系數，球第一題中使其最優(yōu)解保持不變的氣的變化范圍；2、設4為第1個約束條件的常數項，求第一題中使其最優(yōu)解保持不變的九的變化范圍;3、請寫出第一題線性規(guī)劃問題的對偶問題，并寫出次對偶問題的解。三、（10分）用表上作業(yè)法求解以下運輸問題:ABC產量甲36760乙85730丙491130銷量355530四、（15分）用最短路法求解下列問題：某工廠對其未來四年定編人數和研制產品的期望利潤進行了估算，若假定每年增加或減少的人數不超過1人，試求隔年應保持的最佳人員數，關于保留不同人員數在未來四年中所獲利潤估算如下表：人員數年數一四8393792122107481119264125531五、（15分）某養(yǎng)豬專業(yè)戶，現有100頭豬，已知豬的繁殖率為1.4（可簡化為每年年底豬的頭數是年初的1.4倍）。飼養(yǎng)一頭豬的成本約30元，它包括維持一頭豬及子豬的費用。飼養(yǎng)者可按下列價格賣出他的豬，每年一頭豬的報價為200元，但可以按購買豬的多少打折，價格為200元減去0.2元乘以購買豬的數量（例如買5頭，此時每頭豬的價格為200-0.2x5=199元）。該專業(yè)戶決定從現在起，飼養(yǎng)到第5年初為止，把全部豬賣掉，但在第五年初出售剩余的豬使，每只豬的單價變?yōu)椋ú淮蛘郏?50元，該專業(yè)戶該如何做出決策，每年在集市上賣掉多少頭豬，同時飼養(yǎng)多少頭豬才能使自己的總收益最大？（假定現在是第一年年初）。六、（15分）某超市有三個收款臺，顧客到來交款的規(guī)律服從柏松流，其平均到達率為每10分鐘9人。每個收款臺的服務的時間服從指數分布，其服務率平均取為每10分鐘完成4人，假設顧客排成一隊，然后到三個收款臺之一空閑位去交款，試求：1、服務臺全空閑的概率；2、顧客必須等待的概率（系統(tǒng)中已有3個或超過3個顧客）；3、正在排隊的平均人數；4、用于排隊等待的平均時間。七、（15分）假設在上題的超市中，顧客到達時在每個收款臺前各排一隊，且進入隊列后堅持不換隊，這樣排成三個獨立的隊列，試求一個獨立隊列的：1、服務臺的空閑概率；2、顧客必須等待的概率；3、隊列中正在排隊的平均人數；4、隊列中顧客排隊等待的平均時間；5、是比較兩種排隊方案的優(yōu)劣，并簡述該比較方法的合理性。北京理工大學運籌學（2003）、（20分）用二階段法或大M法求解下列線性規(guī)劃問題：maxz-x1+2x2+2x35x1+3x2+x3<9-5x+6x+15x<15S."1232X]+x2+x3>5X],x2,x3>0、（25分）已知線性規(guī)劃問題maxz--5x]+5x2+13x3—x+x+3x<20s.t.<12x1+4x2+10x3<90、x.>0。-1,2,3）的最有單純表如下表所示，試分別就下列情況進行靈敏度分析，并求新的最優(yōu)解。c?J—551300c^x^bx】x?x3x4x55工220—113100x310160—2—41z10000—2—501、寫出該線性規(guī)劃問題的對偶規(guī)劃，并寫出這對偶規(guī)劃問題的解;目標函數中x2的系數變?yōu)椋?6；3、4、2、第目標函數中x2的系數變?yōu)椋?6；3、4、rc〕"10、6其系數為a16-3頂,X26’:5>增加一個新變量x6，三、（20分）京工大學有三個區(qū)：一區(qū)、二區(qū)和三區(qū)，每年分別需要生活用煤和取暖用煤3000噸、1000噸和2000噸，由河北保定、山西長治兩處煤礦負責供應，這兩處的煤礦價格相同，煤的質量也基本相同，兩處煤礦能供應京工大學所用煤的數量分別是：河北保定1500噸，山西長治4000噸，由煤礦至京工大學的單位運價（百元/噸）見下表：一區(qū)二區(qū)三區(qū)山西長治1.651.701.75河北保定1.601.651.70

由于需大于供，經京工大學研究平衡決定一區(qū)供應量可減少0?300噸，二區(qū)需要量應全部滿足，三區(qū)供應量不能少于1600噸。試求總運費最小的調運方案。（做出產銷平衡與運價表即可，無需計算求解）四、（20分）某企業(yè)準備資金600萬元，計劃對A、B、C三個項目進行投資，每個項目至少投資100萬元，最多可投資400萬元。投資以100萬元為單位，各項目的投資效益與投入該項目的資金有關，三個項目A、B、C的投資效益和投入資金的關系如下表：ABC100萬元18萬元16萬元15萬元200萬元32萬元34萬元31萬元300萬元48萬元52萬元53萬元400萬元68萬元63萬元65萬元問：如何對三個項目進行投資分配，可使總投資效益最大。五、（25分）某企業(yè)生產某種產品，每月月初按訂貨單發(fā)貨，生產的產品隨時入庫，由于空間的限制，倉庫做多能夠貯存產品90000件，在上半年（1至6月）其生產成本（萬元/千件）和產品訂單的需求數量情況如下表:'一一、月份成本與需求123456生產成本（匕）（萬元/千件）2.12.82.32.72.02.5需求量（七）（千件）356350326744已知上一年底庫存量為40千件，要求底6月庫存量仍能夠保持40千件。問：如何安排這6個月的生產量，使既能滿足各月的訂單需求，同時生產成本最低。六、（25分）某汽車修理站有一個修理工，已知來站修理的洗車每天（以12小時計）平均到達8輛，每輛平均修理1小時，汽車到達間隔時間和修理時間服從指數分布，試求：1、在修理站停留汽車的平均數；2、汽車列隊等待修理的平均時間；3、修理站至少有兩輛汽車的可能性。七、（15分）某重要設施是由三道防線組成的防空系統(tǒng)，第一道防線上配備兩座武器；第二道防線上配備三座武器；第三道防線上配備一座武器，所有武器的類型一樣。武器對來犯敵機的射擊時間服從R=1（架/分鐘）的指數分布，敵機來犯服從人=2（架/分鐘）的泊松流。試估計該防空系統(tǒng)的有效率。北京理工大學運籌學（2004）、（25分）求解下列線性規(guī)劃問題。minz=5x1+21x3x1-x2+6x3-x4=2s.t.<x+x+2x一x=113>0,j=1,2,,5ij二、（25分）某公司制造三種產品A、B、C,需要兩種資源（勞動力和原材料），這些產品對兩種資源的需求、單位利潤以及該公司的資源限制如下表所示，要求確定總利潤最大的最優(yōu)生產計劃。產品A產品B產品C資源限制每單位產品的勞動力63545資源需求原材料34530每單位產品的利潤315設x、x、x分別是產品A、B、C的產量，我們可得到該問題的線性規(guī)劃模型如下:123maxz=3x1+x2+5x36x1+3x2+5x3<45s.t.<3x1+4x2+5x3<30x”x2,x3>0其中x,x,x是產品A、B、C的產量。123這個線性規(guī)劃問題的最終單純形表如下：基變量cBx]x?x3$1s2b31500x】31_101_15x35011_123zj3450130c,-z.0-300-11、求出使得最優(yōu)解不變的產品A的單位利潤變動范圍。問匕=2時最優(yōu)解變不變？2、從商標中判斷該規(guī)劃最優(yōu)解是否唯一，并說明理由。3、求出使原材料對偶價格不變的?的變化范圍。4、由于技術上的突破，每單位產品B對原材料的需要量減少為2個單位，這時是否需要改變生產計劃？為什么？5、假如這時，又試制新產品D，生產一個單位新產品D需要勞動力4個單位，原材料3個單位，而每單位的新產品D的利潤為3元。請問這時生產計劃是否需要進行修改？為什么？如果需要修改，怎樣修改？三、（10分）已知線性規(guī)劃問題：maxz-%-x2+x3—x+x+x<2s.t.<一2xi+x2一x3<1xi,x2,x3>0試應用對偶理論證明上述線性規(guī)劃問題無最優(yōu)解。四、（20分）金泰公司計劃在三個不同的地區(qū)設置4個銷售店，根據市場預測部門估計，在不同的地區(qū)設置不同數量的銷售店每月利潤如下表所示。試問在各個地區(qū)設幾個銷售店才能使各月的總利潤為最大，其值為多少。請用動態(tài)規(guī)劃求解。12300001161210225171433021164322217五、（25分）向陽廠打算在今后四周內采購某種原料，事先可以估計出未來四周原料的價格及其發(fā)生的概率如下表所示：價格（元）150170200概率0.250.350.40由于生產需要，該廠必須在今后的四周內采購。如果第一周內價格偏高，可以在后面的第二、三、四周內采購；以此類推。但是，到第四周末無論原料價格如何都必須采購。試用動態(tài)規(guī)劃的逆序遞推法求出最優(yōu)采購策略及最低期望價格。六、（20分）某維修車間有1個維修工人，儀器故障到達流服從泊松分布，維修儀器時間服從指數分布。儀器平均每小時到達10臺，平均5分鐘修理完一臺。假設儀器故障立即送到維修車間，該維修系統(tǒng)為等待制。已知每臺儀器停工1分鐘的平均損失費為5元，試問1、儀器站平均每臺儀器損失多少元？2、在維修車間停留儀器的平均數。3、維修的儀器必須在維修車間內消耗10分鐘以上的概率。七、（25分）某汽車加油站只有1個加油管，汽車到達為泊松流，加油時間服從指數分布。平均到達率和平均服務率分別為人和R。已知汽車排隊等待（不含服務時間）1小時的損失費為匕元，加油站空閑1小時損失費為2匕元。試求使總的說損失費（包括顧客排隊等待的損失費和服務機構空閑時的損失費）最小的最優(yōu)服務強度P*（P=V^）。北京理工大學運籌學（2005）一、（20分）考慮下列線性規(guī)劃問題：maxz-x1+4x2+3x3x+2x+2x<152x+x+5x<20s."123xi+x2+x3=10

x「x2,x3>01、求解此問題；2、寫出此問題的對偶規(guī)劃及其最優(yōu)解。、（25分）考慮下列線性規(guī)劃:maxz=3x1+5x2+x34x1+2x2+x3<14s.t.<x1+x2+x3<4x”x2,x3>0?。?，x，分別為第L2個約束的松弛變量，則最優(yōu)單純形表為:45Xrb，35100X]x?x3x4x50x462-25x?411-z填寫出此線性規(guī)劃最優(yōu)單純形表中空格處的數值，并求:1、寫出此線性規(guī)劃的最優(yōu)解、最優(yōu)值、最優(yōu)基B和它的B-1；2、求此線性規(guī)劃的影子價格；3、試求勺在什么范圍內，次線性規(guī)劃的最優(yōu)解不變三、（15分）用表上作業(yè)法求解以下運輸問題:ABC產量甲36560乙85730丙49830銷量384529四、（20分）有一種設備最長使用3年時間，先考慮它在3年內的更新問題。在每年年初要作出決策，是繼續(xù)使用還是更新。如果繼續(xù)使用，已知每年需要支付的維修費用如下表所示（單位：百元）：使用年數0~11~22~3每年維修費用568如果更新設備，已知在各年年初購置該種設備的價格如下表所示（殘值忽略不計）（單位：百元）年份123每年價格111213已知開始時該設備已經使用了1年，問每年年初應怎樣做出決策，才能使3年內該項設備的購置和維修總費用最少？（用動態(tài)規(guī)劃方法求解）五、（25分）某廠有100臺設備，可用于加工甲、乙兩種產品。根據以往經驗，這些設備都用于加工甲產品時，每季度末損壞1臺；而都用于加工乙產品時，每季度末損壞土臺，損壞的設備當年不能修復。每310臺機器一季度用于加工甲產品可獲利10百元；加工乙產品可獲利7百元。問如何安排各季度加工甲、已產品的設備臺數，才能使全年獲利最大？（用動態(tài)規(guī)劃方法求解）六、（20分）一個小型的平價自選市場只有一個收款出口，假設到達收款出口的顧客流為泊松流，平均每小時為30人。收款員的服務時間服從負指數分布，平均每小時可服務40人。1、計算這個排隊系統(tǒng)的數量指標P,L,L;W,W；0qsqs2、顧客對這個排隊系統(tǒng)抱怨花費時間太多，商店為了改進服務，準備對以下兩方案進行選擇：（1）在收款出口除了收款員外，專顧一名包裝員。這樣可以使每小時的服務率從40人提高到60人；（2）增加一個收款出口，使排隊系統(tǒng)變成M/M/2系統(tǒng)，每個收款出口每小時的服務率仍為40人。請對這兩個排隊系統(tǒng)進行評價，并做出選擇。七、（25分）某機場有一條專供飛機降落的跑道。假定飛機降落占用跑道的平均時間為2分鐘（這里“占用”指不準其他飛機使用）。使飛機在空中的平均耽誤時間（Wq）不得超過10分鐘，飛機的到達為泊松分布。1、如果飛機占用跑到時間服從負指數分布，機場的最大允許載荷量（以每小時能到達的飛機平均數表示）是多少？2、如果飛機占用跑到時間服從任意獨立分布，并已知一架飛機占用跑道的標準差為1分鐘，那么機場的最大允許載荷量是多少？3、如果飛機占用跑到時間如從負指數分布，并另外規(guī)定：要求一架飛機從到達到降落時間大于20分鐘的概率小于0.05這是機場的最大允許載荷量是多少？（計算過程中如有對數，不必求出，結果可用含對數的式子表示）北京理工大學運籌學（2006）一、（20分）考慮下列線性規(guī)劃問題：minf=20x1+90x2—X]+12x2Z—5X+4X>5s.t.\123x]+10x2>13X],x2>01、不通過計算，直接討論此問題是否存在最優(yōu)解；2、用較簡單的方法求出此問題的最優(yōu)解及最優(yōu)基，并解釋為什么說這是較簡單的方法。二、（25分）考慮下列線性規(guī)劃:maxz(x)=—3x1+8x2+13x3TOC\o"1-5"\h\zax+ax+ax<b1111221331s.t.<ax+ax+ax<b2112222332ax+ax+ax<b3113223333x「x2,x3>0s.t.<xbxxxxxxx200111/703/7x510—32/70-1/7x5003-2/711/7—z—14500—4-2/70-27/71、計算此線性規(guī)劃原問題的各參數；2、寫出此線性規(guī)劃的最優(yōu)解、最優(yōu)基8、它的逆B-1和影子價格;3、試求％在什么范圍內，此線性規(guī)劃的最優(yōu)解不變；4、若b1變?yōu)?5，最優(yōu)解及最優(yōu)值是什么？三、（15分）甲、乙、丙三個企業(yè)生產同一種產品，價格、質量都相同。現需供應4、B、C、D四個地區(qū)。單位運輸費用、各企業(yè)的產量、各地區(qū)的需求如下表:4BCD產量甲7981130乙10891270丙1413101560銷量45303540由于某種原因，企業(yè)甲必須滿額生產。試用表上作業(yè)法求解以上使總運輸費用最低的運輸問題。四、（23分）某公司擬在甲、乙、丙三個地區(qū)設置5個銷售點，各地區(qū)設置銷售點數目的盈利情況如下表，問這應如何設置這5個銷售點，使公司利潤最大?甲乙丙000013542710439111141211125131112五、（22分）某公司承擔一種新產品研制任務，合同要求三個月內交出一件合格的樣品，否則將索賠2000元。根據有經驗的技術人員估計，試制品合格的概率為0.4,每次試制一批的裝配費為200元，每件產品的制造成本為100元。每次試制的周期為1個月。問該如何安排試制，每次生產多少件，才能使得期望費用最?。苛?、（20分）某單服務臺的服務系統(tǒng)，顧客按平均每小時40人的泊松流到達，服務時間服從指數分布，平均每小時服務率為H。已知顧客因排隊耽誤造成的損失為每小時平均50元，服務系統(tǒng)每小時的費用為20R元。假設這是某公司內部的一個服務系統(tǒng)，試確定使公司總支出最少的服務率。并依據求出的最優(yōu)服務率，計算此服務系統(tǒng)的空閑概率，平均系統(tǒng)隊長和平均系統(tǒng)逗留時間三項數量指標。七、（25分）某兩個服務臺的排隊系統(tǒng)，最多容納4名顧客。已知系統(tǒng)的穩(wěn)態(tài)概率為:14641P=,P=一，P=,P=—,P=—0161162163164161、系統(tǒng)中的平均顧客數L；s2、系統(tǒng)中的平均排隊顧客數L；q3、某一時刻正在被服務的顧客平均數；4、若顧客的平均到達率為每小時2人，求顧客在系統(tǒng)中的平均逗留時間W；s5、若2名服務員具有相同的服務率，利用前面得出的結果，求服務員為一名顧客服務的平均時間（1）。R北京理工大學運籌學（2007）一、（20分）考慮下列線性規(guī)劃問題minz-%+x2一4x3X]+x2+2x3-9s.t.<x+x一x<2s.t.<123x一x一xZ-4x],x2,x3>01、用單純形法計算此問題，并寫出最優(yōu)解、最優(yōu)值與最優(yōu)基;2、寫出此線性規(guī)劃問題的對偶問題，并求出對偶問題的解。二、（25分）某工廠生產甲、乙、丙三種產品，各種產品每件所需原料A分別為2、4、2kg；每件所需原料B為4、6、5kg；消耗工時為6、3、8小時；各產品的利潤分別為每件160、180、120元。每周企業(yè)可用于這些產品的工時為900小時，可提供的原料A、B分別為480kg和800kg。以總利潤最大為目標考慮各產品的生產計劃。通過計算，得到下列最優(yōu)單純形表:160180120000cxRHSxxxxxx180x5001_1160x1250_110x301_31-z-290000―25—10請解答下列問題：1、寫出此問題的線性規(guī)劃模型及其最優(yōu)解、最優(yōu)基和最優(yōu)基的逆；2、把最優(yōu)單純形表中的空白補充完整；3、若產品乙的利潤從180變?yōu)?50而其它參數均不變時，問題的最優(yōu)解和最優(yōu)值是什么？三、（15分）甲、乙兩個企業(yè)生產同一種產品，價格、質量都相同。現需供應A、B、C、D四個地區(qū)。單位運輸費用、各企業(yè)的產量、各地區(qū)的需求如下表:ABCD產量甲347550乙865970銷量20352530由于某種原因，企業(yè)乙必須滿額生產。試用表上作業(yè)法求解以上使總運輸費用最低的運輸問題。四、（25分）某企業(yè)根據市場需求預測今后3個月月底的交貨任務分別是2千件、3千件、3千件。該廠的生產能力為每月6千件，該廠倉庫的存貨能力為3千件，每生產1千件產品的費用為1千元。在進行生產的月份，工廠要固定支出3千元開工費。倉庫保管費用每1千件0.5千元。假定開始時和計劃期末庫存量都是零。試問應在各個月生產多少件產品，才能既滿足交貨任務又使總費用最少？五、（20分）考慮一種由4種不同部件A1.A2.A3、A4組成的系統(tǒng)，各部件都運行時系統(tǒng)才能運行。系統(tǒng)的可靠性可以通過在一個或幾個部件中并聯若干個單元而得到提高。并聯〃個單元后部件的可靠性（概率）R和費用C（單位：千元）見下表：NA1A2A3A4RCRCRCRC10.740.620.930.8320.7550.84——0.82530.857——————現有資金15千元，在4個部件中各并聯多少個單元才使系統(tǒng)運行的可靠性最高?六、（25分）高速公路某出口只有一個收費通道，假設到達該出口的汽車流為泊松流，平均每小時為30輛，收費員的服務時間服從負指數分布，平均每小時可服務40輛汽車。1、計算這個排隊系統(tǒng)的數量指標P0、Lq、L、氣、W，；2、考慮到車主的抱怨，該出口考慮在該出口多安排一外員工，這樣，每小時可服務50輛汽車，計算這個排隊系統(tǒng)的數量指標p、L「L、Wq、W^；3、另外，該出口也可以考慮多安排一個收費通道，每個收費通道的服務率仍為40輛汽車。4、請對2與3這兩個方案進行評價。七、（20分）某航空公司售票處開展電話訂票業(yè)務。據統(tǒng)計分析，電話到達過程服從泊松分布，平均到達率為每小時20個，平均每個業(yè)務員每小時可以處理10個電話訂票業(yè)務。請問該公司應該安裝多少臺電話，才能使因電話占線而損失的概率小于10%？北京理工大學運籌學（2008）一、（10分）現有一求最大值的線性規(guī)劃問題，對應下列含有未知變量的表，試討論下表書，a,c,c,d1212為何范圍值時，表現為下列情況：1、表中的解唯一最優(yōu)解；2、表中解為無窮多最優(yōu)解之一；3、表中解為退化的可行解；4、下一步迭代將以氣代替基變量％；5、該線性規(guī)劃問題具有無界解；6、該線性規(guī)劃問題無可行解。XbbXXXXXxd401a20x22—110—50X53a^00—31—z%00。20二、（35分）某企業(yè)用甲、乙、丙三種原料生產A、B、C、D四種產品，每種產品消耗原料定額以及三種原料的數量如下表所示：產品ABCD原料數量（噸）對原料甲的消耗（噸/萬件）32142400對原料乙的消耗（噸/萬件）20233200對原料丙的消耗（噸/萬件）13021800單位產品的利潤（萬兀/萬件）25121415求使總利潤最大的生產計劃。先求得最優(yōu)單純形表為:CbXbb，25121415000X]乂2X3X4X5X&X712乂240011051_1014X3160010130100X7600—200_7_331—z—27200—100—21—6—40請解答下列問題：1、寫出此問題的線性規(guī)劃模型及其對偶問題，并寫出問題最優(yōu)解、最優(yōu)基、最優(yōu)基的逆和對偶問題的解;2、解釋最有生產計劃中有的產品不安排生產的原因；3、對產品B的利潤進行靈敏度分析；4、若原料甲增加420噸，影子價格是否變化，求原料甲增加后的最