北京理工大學858運籌學2002~2005

一、 （15分）用大M法或兩階段法求解下列線性規(guī)劃問題：minz=2x+3x12fx>1251x+x>350S.t.s1 22x+x<60012x,x>012二、 （15分）1、 設(shè)C為目標函數(shù)中x的系數(shù)，球第一題中使其最優(yōu)解保持不變的C的變化范圍；1112、 設(shè)b為第1個約束條件的常數(shù)項，求第一題中使其最優(yōu)解保持不變的b的變化范圍;113、 請寫出第一題線性規(guī)劃問題的對偶問題，并寫出次對偶問題的解。三、（10分）用表上作業(yè)法求解以下運輸問題：ABC產(chǎn)量甲36760乙85730丙491130銷量355530四、（15分）用最短路法求解下列問題：某工廠對其未來四年定編人數(shù)和研制產(chǎn)品的期望利潤進行了估算，若假定每年增加或減少的人數(shù)不超過1人，試求隔年應(yīng)保持的最佳人員數(shù)，關(guān)于保留不同人員數(shù)在未來四年中所獲利潤估算如下表：-- 年數(shù)人員數(shù)f'-r一二四8393792122107481119264125531五、（15分）某養(yǎng)豬專業(yè)戶，現(xiàn)有100頭豬，已知豬的繁殖率為1.4（可簡化為每年年底豬的頭數(shù)是年初的1.4倍）。飼養(yǎng)一頭豬的成本約30元，它包括維持一頭豬及子豬的費用。飼養(yǎng)者可按下列價格賣出他的豬，每年一頭豬的報價為200元，但可以按購買豬的多少打折，價格為200元減去0.2元乘以購買豬的數(shù)量（例如買5頭，此時每頭豬的價格為200-0.2x5=199元）。該專業(yè)戶決定從現(xiàn)在起，飼養(yǎng)到第5年初為止，把全部豬賣掉，但在第五年初出售剩余的豬使，每只豬的單價變?yōu)椋ú淮蛘郏?50元，該專業(yè)戶該如何做出決策，每年在集市上賣掉多少頭豬，同時飼養(yǎng)多少頭豬才能使自己的總收益最大？（假定現(xiàn)在是第一年年初）。六、（15分）某超市有三個收款臺，顧客到來交款的規(guī)律服從柏松流，其平均到達率為每10分鐘9人。每個收款臺的服務(wù)的時間服從指數(shù)分布，其服務(wù)率平均取為每10分鐘完成4人，假設(shè)顧客排成一隊，然后到三個收款臺之一空閑位去交款，試求：1、服務(wù)臺全空閑的概率；2、顧客必須等待的概率（系統(tǒng)中已有3個或超過3個顧客）；3、正在排隊的平均人數(shù)；4、用于排隊等待的平均時間。七、（15分）假設(shè)在上題的超市中，顧客到達時在每個收款臺前各排一隊，且進入隊列后堅持不換隊，這樣排成三個獨立的隊列，試求一個獨立隊列的：1、服務(wù)臺的空閑概率；2、顧客必須等待的概率；3、隊列中正在排隊的平均人數(shù)；4、隊列中顧客排隊等待的平均時間；5、是比較兩種排隊方案的優(yōu)劣，并簡述該比較方法的合理性。、(20分)用二階段法或大M法求解下列線性規(guī)劃問題：maxz=x+2x+2x1235x+3x+x<9TOC\o"1-5"\h\z1 2 3一5x+6x+15x<15\o"CurrentDocument"s.t.< 1 2 32x+x+x>51 2 3x,x,x>0123、(25分)已知線性規(guī)劃問題maxz=一5x+5x+13x1 2 3一x+x+3x<201 2 3x>0(j=1,2,3)js.t.x>0(j=1,2,3)j123、3、目標函數(shù)中x的系數(shù)變?yōu)閏=6；22c.j-551300c召x召bx】x?x§x@x§5x?20一113100x§10160-2一41z10000一2一50的最有單純表如下表所示，試分別就下列情況進行靈敏度分析，并求新的最優(yōu)解。寫出該線性規(guī)劃問題的對偶規(guī)劃，并寫出這對偶規(guī)劃問題的解；1、2、第2個約束條件的右端常數(shù)變?yōu)閎=95；244、(c)6^10、a=316<a.<5丿增加一個新變量x，其系數(shù)為6三、（20分）京工大學有三個區(qū)：一區(qū)、二區(qū)和三區(qū)，每年分別需要生活用煤和取暖用煤3000噸、1000噸和2000噸，由河北保定、山西長治兩處煤礦負責供應(yīng)，這兩處的煤礦價格相同，煤的質(zhì)量也基本相同兩處煤礦能供應(yīng)京工大學所用煤的數(shù)量分別是：河北保定1500噸，山西長治4000噸，由煤礦至京工大學的單位運價（百元/噸）見下表：一區(qū)二區(qū)三區(qū)山西長治1.651.701.75河北保定1.601.651.70由于需大于供，經(jīng)京工大學研究平衡決定一區(qū)供應(yīng)量可減少0~300噸，二區(qū)需要量應(yīng)全部滿足，三區(qū)供應(yīng)量不能少于1600噸。試求總運費最小的調(diào)運方案。（做出產(chǎn)銷平衡與運價表即可，無需計算求解）四、（20分）某企業(yè)準備資金600萬元，計劃對A、B、C三個項目進行投資，每個項目至少投資100萬元,最多可投資400萬元。投資以100萬元為單位，各項目的投資效益與投入該項目的資金有關(guān)，三個項目AB、C的投資效益和投入資金的關(guān)系如下表：ABC100萬元18萬元16萬元15萬元200萬元32萬元34萬元31萬元300萬元48萬元52萬元53萬元400萬元68萬元63萬元65萬元問：如何對三個項目進行投資分配，可使總投資效益最大。五、（25分）某企業(yè)生產(chǎn)某種產(chǎn)品，每月月初按訂貨單發(fā)貨，生產(chǎn)的產(chǎn)品隨時入庫，由于空間的限制，倉庫做多能夠貯存產(chǎn)品90000件，在上半年（1至6月）其生產(chǎn)成本（萬元/千件）和產(chǎn)品訂單的需求數(shù)量情況如下表:?月份成本與需求123456生產(chǎn)成本（c）k（萬元/千件）2.12.82.32.72.02.5需求量（v）k（千件）356350326744已知上一年底庫存量為40千件，要求底6月庫存量仍能夠保持40千件。問:如何安排這6個月的生產(chǎn)量，使既能滿足各月的訂單需求，同時生產(chǎn)成本最低。六、（25分）某汽車修理站有一個修理工，已知來站修理的洗車每天（以12小時計）平均到達8輛，每輛平均修理1小時，汽車到達間隔時間和修理時間服從指數(shù)分布，試求:1、在修理站停留汽車的平均數(shù)；2、汽車列隊等待修理的平均時間；3、修理站至少有兩輛汽車的可能性。七、（15分）某重要設(shè)施是由三道防線組成的防空系統(tǒng)，第一道防線上配備兩座武器；第二道防線上配備三座武器；第三道防線上配備一座武器，所有武器的類型一樣。武器對來犯敵機的射擊時間服從卩二1（架/分鐘）的指數(shù)分布，敵機來犯服從九二2（架/分鐘）的泊松流。試估計該防空系統(tǒng)的有效率。、（25分）求解下列線性規(guī)劃問題。minz=5x+21x13x一x+6x一x=2TOC\o"1-5"\h\z1 2 3 4s.t.Qx+x+2x一x=11 2 3 5\o"CurrentDocument"x.>0,j=1,2, ,5、（25分）某公司制造三種產(chǎn)品A、B、C,需要兩種資源（勞動力和原材料）這些產(chǎn)品對兩種資源的需求、單位利潤以及該公司的資源限制如下表所示，要求確定總利潤最大的最優(yōu)生產(chǎn)計劃。產(chǎn)品A產(chǎn)品B產(chǎn)品C資源限制每單位產(chǎn)品的資源需求勞動力63545原材料34530每單位產(chǎn)品的利潤315設(shè)x、x、x分別是產(chǎn)品A、B、C的產(chǎn)量，我們可得到該問題的線性規(guī)劃模型如下:123maxz=3x+x+5xTOC\o"1-5"\h\z1 2 36x+3x+5x<451 2 3s.t.Q3x+4x+5x<301 2 3x,x,x>0123其中x,x,x是產(chǎn)品A、B、C的產(chǎn)量。123這個線性規(guī)劃問題的最終單純形表如下基變量c召x】x?x§S]S2b31500x】3110115x§5011123zj3450130c—zjj0-300一11、 求出使得最優(yōu)解不變的產(chǎn)品A的單位利潤變動范圍。問c=2時最優(yōu)解變不變？12、 從商標中判斷該規(guī)劃最優(yōu)解是否唯一，并說明理由。3、 求出使原材料對偶價格不變的b的變化范圍。24、 由于技術(shù)上的突破，每單位產(chǎn)品B對原材料的需要量減少為2個單位，這時是否需要改變生產(chǎn)計劃?為什么？5、假如這時，又試制新產(chǎn)品D,生產(chǎn)一個單位新產(chǎn)品D需要勞動力4個單位，原材料3個單位，而每單位的新產(chǎn)品D的利潤為3元。請問這時生產(chǎn)計劃是否需要進行修改？為什么？如果需要修改，怎樣修改？三、（10分）已知線性規(guī)劃問題：maxz=x一x+x123一x+x+x<21 2 3s.t.Q—2x+x一x<1123x,x,x>0123試應(yīng)用對偶理論證明上述線性規(guī)劃問題無最優(yōu)解。四、（20分）金泰公司計劃在三個不同的地區(qū)設(shè)置4個銷售店，根據(jù)市場預測部門估計，在不同的地區(qū)設(shè)置不同數(shù)量的銷售店每月利潤如下表所示。試問在各個地區(qū)設(shè)幾個銷售店才能使各月的總利潤為最大，其值為多少。請用動態(tài)規(guī)劃求解。12300001161210225171433021164322217五、（25分）向陽廠打算在今后四周內(nèi)采購某種原料，事先可以估計出未來四周原料的價格及其發(fā)生的概率如下表所示：價格（元）150170200概率0.250.350.40由于生產(chǎn)需要，該廠必須在今后的四周內(nèi)采購。如果第一周內(nèi)價格偏高，可以在后面的第二、三、四周內(nèi)采購；以此類推。但是，到第四周末無論原料價格如何都必須采購。試用動態(tài)規(guī)劃的逆序遞推法求出最優(yōu)采購策略及最低期望價格。六、（20分）某維修車間有1個維修工人，儀器故障到達流服從泊松分布，維修儀器時間服從指數(shù)分布。儀器平均每小時到達10臺，平均5分鐘修理完一臺。假設(shè)儀器故障立即送到維修車間，該維修系統(tǒng)為等待制。已知每臺儀器停工1分鐘的平均損失費為5元，試問1、儀器站平均每臺儀器損失多少元？2、在維修車間停留儀器的平均數(shù)。3、維修的儀器必須在維修車間內(nèi)消耗10分鐘以上的概率。七、（25分）某汽車加油站只有1個加油管，汽車到達為泊松流，加油時間服從指數(shù)分布。平均到達率和平均服務(wù)率分別為九和卩。已知汽車排隊等待（不含服務(wù)時間）1小時的損失費為C1元，加油站空閑1小時損失費為2c元。試求使總的說損失費（包括顧客排隊等待的損失費和服務(wù)機構(gòu)空閑時的損失費）最小1的最優(yōu)服務(wù)強度P*（P=X>）。、（20分）考慮下列線性規(guī)劃問題：maxz=x+4x+3x123x+2x+2x<151 2 32x+x+5x<20s.詁 1 2 3x+x+x=10123x,x,x>01231、求解此問題；2、寫出此問題的對偶規(guī)劃及其最優(yōu)解、（25分）考慮下列線性規(guī)劃：maxz=3x+5x+x1 2 3填寫出此線性規(guī)劃最優(yōu)單純形表中空格處的數(shù)值，并求：1、 寫出此線性規(guī)劃的最優(yōu)解、最優(yōu)值、最優(yōu)基B和它的B-1；2、 求此線性規(guī)劃的影子價格；3、 試求c在什么范圍內(nèi)，次線性規(guī)劃的最優(yōu)解不變2三、（15分）用表上作業(yè)法求解以下運輸問題：ABC產(chǎn)量甲36560乙85730丙49830銷量384529四、（20分）有一種設(shè)備最長使用3年時間，先考慮它在3年內(nèi)的更新問題。在每年年初要作出決策，是繼續(xù)使用還是更新。如果繼續(xù)使用，已知每年需要支付的維修費用如下表所示（單位：百元）：使用年數(shù)0~11~22?3每年維修費用568如果更新設(shè)備，已知在各年年初購置該種設(shè)備的價格如下表所示（殘值忽略不計）（單位：百元）年份123每年價格111213已知開始時該設(shè)備已經(jīng)使用了1年，問每年年初應(yīng)怎樣做出決策，才能使3年內(nèi)該項設(shè)備的購置和維修總費用最少？（用動態(tài)規(guī)劃方法求解）五、（25分）某廠有100臺設(shè)備，可用于加工甲、乙兩種產(chǎn)品。根據(jù)以往經(jīng)驗，這些設(shè)備都用于加工甲產(chǎn)11品時，每季度末損壞-臺；而都用于加工乙產(chǎn)品時，每季度末損壞—臺，損壞的設(shè)備當年不能修復。每310臺機器一季度用于加工甲產(chǎn)品可獲利10百元；加工乙產(chǎn)品可獲利7百元。問如何安排各季度加工甲、已產(chǎn)品的設(shè)備臺數(shù)，才能使全年獲利最大？（用動態(tài)規(guī)劃方法求解）六、 （20分）一個小型的平價自選市場只有一個收款出口，假設(shè)到達收款出口的顧客流為泊松流，平均每小時為30人。收款員的服務(wù)時間服從負指數(shù)分布，平均每小時可服務(wù)40人。1、 計算這個排隊系統(tǒng)的數(shù)量指標P,L,L;W,W；0qsqs2、 顧客對這個排隊系統(tǒng)抱怨花費時間太多，商店為了改進服務(wù)，準備對以下兩方案進行選擇：（1）在收款出口除了收款員外，專顧一名包裝員。這樣可以使每小時的服務(wù)率從40人提高到60人；（2）增加一個收款出口，使排隊系統(tǒng)變成M/M/2系統(tǒng)，每個收款出口每小時的服務(wù)率仍為40人。請對這兩個排隊系統(tǒng)進行評價，并做出選擇。七、 （25分）某機場有一條專供飛機降落的跑道。假定飛機降落占用跑