《上海大学历年运筹学考研真题及答案、考研大纲.docx》由会员分享,可在线阅读,更多相关《上海大学历年运筹学考研真题及答案、考研大纲.docx(53页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、考试科目:运筹学适用专业:管理科学与工程一、复习要求:要求考生熟悉模型的构建及应用,掌握定量化决策和模型化的基本思想和方 法,能灵活运用运筹学的方法求解各类问题。二、主要复习内容:、线性规划线性规划问题与数学模型、图解法、线性规划单纯形算法、单纯形法的进一 步讨论、线性规划的对偶问题、对偶问题的基本性质、影子价格、对偶单纯形法、 灵敏度分析、参数线性规划。重点:构建线性规划的数学模型,单纯形算法的掌握,对偶问题的建立,影 子价格的理解,灵敏度分析。2、运输问题运输问题及其数学模型,用表上作业法求解运输问题,运输问题的进一步讨 论,应用问题举例。重点:运输问题的数学模型,运输问题的求解。3、整数
2、规划整数规划的数学模型及其解的特点,01规划的数学模型,整数规划求解的 方法(分枝定界法、割平面法、纯01规划的求解方法),指派问题。重点:含0-1变量的混合整数规划模型的构建,整数规划的求解方法。4、动态规划多阶段决策问题的最优化,动态规划的基本概念和基本原理,动态规划模型 的建立与求解,动态规划在经济管理中的运用。重点:动态规划模型的建立与求解,动态规划在经济管理中的运用。5、排队论基本概念,到达间隔的分布和服务时间的分布,M/M/s等待制排队模型,M/M/s 混合制排队模型。重点:随机服务系统的分析以及各量值的计算。一、参考书目:运筹学教程第3版,胡运权主编,清华大学出版社2007年上海
3、大学2000年攻读硕士学位研究生入学考试试题招生专业:国际贸胤管理科学与工,考试科目;在学(理论.算法与一、(12分)某一最大化线性裁划问题在他纯形法计算时得到下面表格摹受量苞与%2cI0e0/-1,501-102aJ00-413_bd00-30其中瓦c, 4%/是未知数,原问期中要求看变量均葬负.何a, b,c, 4 %/应满足什么条 件,育下面各解成立?(1)是非可行基解.(2)是唯一优解,最优解是什么?。)有无穷多量优解.(4)是退化君可行解.(3)无界解.(6)是可行解但非量优解,只有马可以进基且出基变量必为第3个基变量,迭代后目标函 数值将靖加多少?二、(16分)求解下面运费最小的运
4、输问题:2地 位运MB,B,-I供应量A146293295A】7144需求量468(D用西北角法求初始解:(2)若已知下面可行解B,B,Al18%41A,4问它是否为量优的?若不是,求出优运方案和量小总运费.三, (16分)某卡车或重能力为10吨,现要装三种产品,已知每件产品的重量和利润如下表: .产品*类重量(电件)利润(元/件)118023.14032 .二100又规定产品3至多装2件.问如何安排运输可使总利润最大?四、分)假设某高速公路收费口只有一个,汽车按Poisson分布到达收费口,平均 每小时60辆,悔辆车递过收费口平均需时间40秒,服从负指数分布.(1)求收费口空闲的断率:(2)
5、求收费口有2辆以上(包括2辆)汽车的概率;。)求收费口排队等待的平均汽车数:(4)求汽车在收费口的平均逗留时尚;(3)若希叟汽车在收费口的平均逗留时间减少一半,则每辆车通过收费口的平均时间应为 多少?(6)汽车从到达收费口和寸费后离开的时间大于3分钟的概率为多少?.五、(16分)某厂生产三种产品,已知收益最大化模型如下:maxZXxi +% 4-lQx,s.L 5+3+ 3k)C60 (第一)3勒+5+5%W45 (第二种资源)朴 x:、xO;第,页(共千页,r一设司、内、马是产品A, B. C的计划生产量,与、x,表示两种费源f;束的不足变量,得下;面单钝忐衰为:篇X%入b3-101-115
6、均3/54/5101/59X2-1002-90(1)指出上面给出的解是否景优?求出最优解和优目标的数值.(2)写出本规划的对偶规划,它的最优解是什么,并给予一个经济学上的解算.(3)写出最优基变量,优基矩降和其逆矩阵Ar-L(4)在其他条件不变的情况下,当第二约束中右螭常数b,在什么范围内变化,原最优性是 不变的?(5)在其他条件不变的情况下,产品I的收支系数C,从8变为7,原最优性是否改变7求出 C1-7时的最优解和优目标函数值.六、(12分)某厂生产四种产品A. B. C, D,都需要经过三道工序的加工,有关数据如下:序消耗1 (工附/件)2(工时/他3 (工时附)利润(元/件). .A1
7、05112B510115C2- -4410D36314可用工时3000200C1000: :(I)销售部门要求C. D产品中至少I种产量在100以上,另外产品A是批量生产,加 要么不生产,要么生产产量不少于200,湾制定餐优生产计划(只需建立含0-1变J 量的混合独数规划模型)2)在(I逸基础上,增加一个条件:产品A的生产仅在产品B生产的条件下才考虑是否 生产.请制定量优生产计划.(只需建立含变量的混合整敷或划模型)命M纸使用说明字迹外须端正,以果色碳囊水书写在解绒内,文字与图均不得剪贴,以及七、 (10分)已知线性跳划问题(IP)如下:wunZ CTX(LPX st. AXibXiQ:愎设S
8、 问题和它的对得问题均有可行解,且设3 问题的优解为X*,最优目标 :函数值为z*,)问题的对偈问题的优解为y.证明:,以保球“扫描”赛像.上海大学23年年攻读硕士学位研究生入学考试试题招生专业:管理科学与工程考试科目:运等狗理论、算法与应用)max Z CX1、20分)设线性短划(LP) . 4r4人已知它的初始单线形裳为XWOC,211000G居bX|勘必x当A0瓦3111000必占1-120100乂显11】00I-Z2-11000其中4,勺,勺为它的作贝松弛变量现已如它的最优单纯形表如下C.b的Jtj14均010-1-22“1151/21/2-145a1/2Z(I)请填写上面或优表中空自
9、处的数字.(2)写出原线性规划问通(LP).(3)写出此向的对斜煤划,并求对儡燃划的优解.)当5变为b + 2 6 * ,其中问4在什么范圉内变化,K量优性不变?(5)目标函数中町的系敷6从/变为2,版优性是否改殳?求出g2时的优M和优目标的数值.2(20分)某产品由产地人夏往第地比的每吨运费如卜表:Bib2B,供应量(吨)A|504060ISOAj453065200A)201050250需求量150220180为潴;各峭地需要,应如何定运,方案可使总运费小?(1)建立此运问及的数学模型.(2)将此问题化为产销平衡的运,问题,并求出一个初始基本可行解.3、20分)某厂在某一段时间内准善助制三种
10、新产品AB,C,估计在该时间段内三料断产 品的研制不成功机率分别为0.3。4,0.5工厂决定再增加20万元研制般费.当不同的产品得 到不同的增加时,不成功偃率分别如下:7品 研制费增赢71加、ABC0030.4- 0.510J0.30.420.180.250.35问如何分配,可使这三种新产品都没有研制成功的横率,小?4、(16分)某理发店一次只能为一位胃客理发.每天营业时间为8g23:00,平均每天杳 20人前来理发,理发速度为每小时2人,假设顾客到达的时间匈隔和股务时间均收从负指数分布.求(I) 理发店忙的概率;(2)理发店内的平均*客数,(3)在理发店等待理发的平均喉客敷:(4)顾客在理发
11、店内平均逗团时间;(5)通客在理发店内平均等恃时间: 3/( sj. Xj + x2 + x, = 82xB -4x: +x, 10 马,七/120(I)(2)(3)用睢纯形法求最优解: 建立此问题的对偶规划;求对偶问题的最优解.玉、(20分)某公司打算向它的三个营业区增设六个销他店.辟个营业区至少增设一个。从备区赚取的利润。增设的错倚店个数有关,箕数据如下:销曾店增加数A区利润(万元)B区利润(万元)C区利润(万元)(1100200150120021016022802201703310225190_4340230“试同察区应分配几个增班的鬲伐启,才蔽3个营业区麻蕊用的总利疝质总其值点多少?六
12、、(15分,某修理店只有一个修理人,来修理的嫁客到达次数服从泊松分布,平均到iA 时间间隔30分钟,修理时间服从负指数分布,平均时间为20分髀.求(1)蜥客来修理不必等待的概率;.(2)修理店内顾客的平均数:(3)修理店内至少有2个顾客的概率;.(4) 豌客在修理店内的平均逗留时间超过2小时的概束:(5) 若顾客在修理店内平均逗用时间超过2小时,蝴店主将考虑增加修理工人.问 平均到达率为名少时店主才做这样的考虑?,3寅共3页第厂 _七、(10分)证明,已知线性规划问题max z = Zc;-j, X。内=4(i = Lg0)内工(J =工E) (2)盯之0U = L,同)式中丐为大于事的常数,
13、对应第(1)(2组约束条件的对偶变量分别为乂和町.如果令 i弓”,一工”,则问目的谖优性条件等价于当吃工0时.弓40.当0 v与 %时,弓=0当X,工%时.丐之0命JS版使用说明:字迹必维正,以黑色磁索水书写在集线内,文字与用均不得剪贴,以保正“上海大学200 3年攻谀士学位研究生入学考试诚题招生.产业经济学号目,运算学理论、算法、应用)I、(23分)某厂生产两种产品,已知收益大化模组如下:max Zxhi +61x1+12x3s.t x,+2x2+3xj2xiX)、x2i0,凡20、x*无符号限制3、(24分)有Al, A2, A3三个工厂,每天要把生产的产品运往Bl, B2. B3.B4四
14、个箱售点.各厂的供应量、各点的需求量以及运价如F表.问及如何组线 调运才能使电运费少?7售点B1B2B3B4供应A179379A213426A324256需求量3846(1)写出运输问遢的数学模型,它是属于哪一种模型?(2)用小元素法求它的可行解和所对应的目林值.(3)用位势法判断(2)中所求得的解是否优.4、(20分)某公司打算在3个不同的地区设置5个情辔点,根据市场预测部门 的估计,在不同地区设置不同数量的倒售站,每年可得利润如下表.问应如何设 置,可使每年总利润大?(要求用动态规划方法计算)、产售站 利渝012345101625303233201217202224301014161718
15、5、(21分)设有一单人打字室,顾客的到达服从Poisson分布,平均到达时间间 隔为20分钟,打字时间版从负指数分布.为每位顾客服务的平均时间为15分钟. 求(1)顾客来打字不必等待的概率;(2)打字室内顾客的平均数;(3)顾客在打字室的平均逗留时间;(4)顺客在打字室的平均等待时间;(5)打字室内至少有两位顾客的概率,(6)顾客在打字室湿留时间超过30分钟的概率;(7)若顾客在打字室内的平均逗留时间超过2小时,则主人将考虑塔加设备和 打字员.问做客的平均到达率为多少时,主人才会考虑这样做? 6、(20分)某厂用原料A, B. C生产三种不同的产品甲、乙、丙.己知各科产、 |品中A, B.
16、C的含量、原料成本、各种原料的每月跟制用量、三科产品的加工! 费用以及售价如卜表.另外,甲产品要么不生产,要么产不少f 1000kg.问; 如何安排生产,可使该厂利润大?请建立敷学模型., j甲乙丙原料成本(元3照月限制用量(kQA260%20%3.002000B2.503000CW20%40%4 50%2.001000加工费(元/kg) 售价(元/kg)1J4.51.43.41.333:7、(12分)已知线性规划:min Z=2xi -xi+2xjs.L T1F+X3XT|+xHbf3W6X|W0, X2 0 X3 无约束其最忧解为止(-5, 0, -1).(1)求大值;(2)求对偶问题的最
17、优解,8、(20分)(1)已知线性规划问题max Z=CXs.t. AXbXO其中:A=(%)01G,(瓦,力证明当用对偶单纯形法求解读线性坟划问题时, 若存在儿p若需求向量b变为另一向Jtd.求证I如果改变后的问题是可行的,则读向题一 定有量优解.不痴记而I1元总而三%痴书写在据或内,:室JllWPFIMr* 82004 掌r矮;X花.我同; 产乂延济竽与工程I产安单位或不(元,步0-506元17004T4. cc,海士畜处正若一小天务qn.普天国务时闾n时空启每天百96个织W工:;学 沙个K3H5分件.耳,刘先用从沟吩力点.看分rti,版也,喏劲升冉与N为条m_.弓;, 片的士用中可认为充
18、粼二q0圈外M口M6右磔奉是多少,:)企总务9口至少过河位氏方的我搴是多少?九千个肥牙左朕美?口平均3口对高最少少,4)七史芬夕二军虎柞队等内的蹙茎有多少为5)强方在鬟谷窗口重面时面哥五30分侨樊信总是多少。$. (20分,1产4二户维A,发三期WB)(仁,=3) -W 下表:,蕾|I|供百费,喔,二求才耳“近K三三,22 B3-雷丁玄逞.艮 .-. 三.三二三裒前狂窜.一一,季三次? .2:量女忌二“燮毛之为)鱼.壬之编方克.6. 20分,三通:工总:tnax: ,,2x. . x,x x. 一 x S 2X -,+ X, 1, 一工一N.二|x Z4x0.均无约更利用药俱翎论正争兴言力目榇
19、,。1NS37. 7r2xt +30 4x, 4 9-3勺 12“朴x,ZO,且为整数max Z = 6%- % 7Ms.t.2xt 3x 4 4x, M 94X+7x: -3x、 2的最优学更形我由下X.片 1*b |13C21/209/2必0n I%亦0-5一0-27送来淳整数理制的tt3五.C6分)茶至院内科门诒有三个医生,设雷人来就诊的射达时间同。圈从负指权分布, 平均15 10分仲来一位庸人,医生为每也筑人篇的时间也服从负指JS分布,需支间平均 需要20分”.耨奈就诒的篇人排队有两脖方式;(a)摔成一队,依次当空闲的限生处段诊: 排成三队.每位医生处各一队,井且进入队列后不再更换.问
20、:1)这沟一队方式多队于什么属队横手?(6分)2)在Q)撵队方式工分别计算在号位先生处位圈务疑的中的下面量值:服务利用 事,攵闲的概率,平均队长.平均排队长,平均遨曹时阍,平均等恃时间病人在 学旗遭雪时网超过对分钟范微, C4分)(3) 清现明哪肿挣队方式更好?为什么? (6分)六.(24分)某公司弯甲.乙、为三个主要市址.现有5名促华员,其下场利制与同C员配 事商关.关系加下表.由工作需要.暮求在乙市场至少期心促司马a在冬用*交二只分1E促销员,可使公司总利科最大.博用坊春规划方法戒鲫)、人数0115甲4055?5100 1 130150乙40507085| 95103丙506590110
21、j 125140七,(X分)证唠0:msxZ CX(1) (U: sJ.XX=b己H;在杓京条件.4X = b = ,爻需x“与小的*20系数向量成比例.若(IPH?在量优1 证明空量优基本犯行蹲中x“与x,1的谟不f同时为正.(10分)(2) 已性统创max:=/-工 *3x0SJ. 占一七N 8 ,+jr,+2x,2 6 x( 20,占40,勺之0 利用与偈理没证明:起或性炫划问履元景优解.10分)上海大学2006年攻读硕士学位研究生入学考试试题招生专业:管理科学与工程考试科目:运筹学一、判断(2分*10=20分)1、单纯刑法计算中,如果不按最小比值法选取换出变量,则在下一个解中至少有一
22、个基变量的值为负。2、线性规划问题可行域的某一顶点若其目标函数值优于相邻的所有顶点的目标函数 值,则该顶点处的目标函数值达到最优。3、在解运输问题时,其基本可行解中解变量的个数为行数+列数- 1.4、一个排队系统中,不管顾客到达和服务时间的情况如何,只要运行足够长的时间 后,系统将进入稳定状态。5、若某种资源的影子价格等于K,在其他条件不变的情况下,该中资源增加5个单 位时,相应的目标函数值将增大5K。6、在排队系统中,顾客到来的时间间隔是一个随机变量。二、建立数学模型。(12分*2=24分)某服装厂制造大、中、小三种尺寸的防寒服,所用资源有尼龙绸、尼龙棉、劳动力和缝纫设 备。缝制一件防寒服所
23、需各种资源的数量如表(单位已适当给定)。不考虑固定费用,则每 种防寒服售出一件所得利润分别为10、12、13元,可用资源分别为:尼龙绸1500米,尼龙 棉1000米,劳动力4000,设备3000小时。此外,每种防寒服不管缝制多少件,只要做都 要支付一定的固定费用:小号为100元,中号为150元,大号为200元。现欲制定一生产计 划使获得的利润为最大,请写出其数学模型(不解)。号 资源小中大尼龙绸1. 61. 81. 9尼龙棉1. 31. 51. 6劳动力44. 55缝纫设备2. 83. 84. 2三、(1)某地区有三个化肥厂,除了供应外地区需要外,估计每年可供应本地区的数字为: 化肥厂A-7万
24、t,B-8万t, C-3万t。有四个产粮区需要这种化肥,需要量为:甲地区-6万, 乙地区-6万t,丙地区-3万t, 丁地区-3万t。已知从各化肥厂到各产粮区的每t化肥的运 价表如下所示(表中单位:元t)甲乙丙A5873B49107C84239根据以上资料制定一个运费最少的方案(2)某修理店只有一个修理工人,来修理的顾客到达次数服从普阿松分布,平均每小时4 人,修理时间服从负指数分布,平均需65分钟(24分)1、修理店空闲时间概率2、店内有3个顾客的概率3、店内至少有一个顾客的概率4、在店内顾客平均数四、1.下面给出某线性规划问题的单纯形初表和终表(Min型)BS0Xl1-3& x30沟2有Or
25、的CbXb0Xl7d13-102Op012/0-24100“0沏10/0-43081*。jpCB XbXl 为 X3 x 有 沏1X2d2/50 1/10O/1/51 3/1004-10 -1/2W0(1泡表的出基变量为,进基变量为.(2)最优基逆8-=卜(3)填完终表.(4)最优解2 =,(5)对偶问题最优解/ =,(6)若原问题噌加一个新的非负变量,则对偶问题的最优目标值将(变大、不变、变 小).,五、1)请简述影子价格的定义。(2)在使用单纯型表求解型线性规划时,资源的影子价格在单纯型表的什么位置上?(3)写出影子价格的数学表达式并用其定义加以验证(4)试述运输问题中检验数的经济意义六、
26、某公司近期向市场推出了一种新产品,多功能爱印打印机。该产品的多功能很受顾客欢 迎,但一旦需停下来维修则要同时耽误多项工作,因此,顾客要求尽量缩短维修等待时间。为此,公司的技术服务部在每个销售区域设置了一位技术服务代表专门负责该产品维修 服务。假设顾客要求维修的电话是完全随机到达,平均每天到达3个。而技术服务代表连续 工作时,平均每天完成4项维修任务。(1)该服务系统能否看作一个MM / 1排队系统?为什么?(2)假设该系统可看作一个标准的MM / 1排队系统,求出系统的服务强度(技术服务代 表的繁忙率)和顾客的平均等待(不包括维修)时间。(3)现公司希望将顾客的平均等待时间降为不超过0.25天
27、。为此需将每个技术服务代表 的服务区域缩小为达到率不超过多少?这时每个技术服务代表的服务强度降为多少?max z = 2玉 + 3x22X1+2x212七、线性规划问题X1+2%284X 164x20已知其最优解X” X2 0,而第1, 4两种资源(相应于第1, 4两约束)均有余量,应用互 补松弛定理求出原问题和对偶问题的最优解上海大学2007年攻读硕士学位研究生入学考试试题招生专业:管理科学与工程考试科目:运筹学-(26分)某厂生产三种产品,设生产量分别为芭,声,七,已知收益最大化模型如下: max Z = 3x, + 2x2 + 4x3s-t-2xt+x2+3x340 (第一种资源)2玉+
28、2+3七W48 (第二种资源)x0(1)以七,尤5,4表示三个约束的不足变量,写出标准型。(4分)(2)若用单纯形法计算到卜面表格XBxx2七x4%bX4003/21-1/2-16x2013/201/2-114再10000110q-Zj0010-1-1-58指出所表达的基本可行解,目标函数值。(4分)(3)指出上面给出的解是否最优。若不是,求出最优解和最优目标函数值。(6分)(4)写出本规划的对偶规划,并求出它的最优解。(4分)(5)分)(6)若产品1的单位利润从3变为4,问最优方案是什么?此时的最大收益是多少? (4若资源常数列向量匕20、=48变为b=46、60问原最优性是否改变?求出此时
29、的最优方案和最大收益。(4分)二(24分)有442,三个工厂,要把生产的产品运往四,82,83三个需求点。若用,当,员三个需求点需求量没有得到满足,则单位罚款费用为6, 3, 4o各厂的供应量、各点的需求 量以及单位运价如F表。问应如何组织调运才能使总费用(运输费用和罚款费用之和)最小?单位运单 需求 点 工厂B,b2B3供应量Ai64715A?57830A、25625需求量204030(1)请将此问题化为供需平衡的运输问题;(2)用最小元素法求(1)的一个初始调运方案;(3)判断(2)中的方案是否最优,并说明原因。H (22分)设货车按泊松流到达车站,卸货后马上离开。已知平均每天到达4辆车。
30、该货 站有2位工人,同时为货车卸货,假设卸货时间服从负指数分布,平均每天可服务6辆车。 求:(1)该货站没有货车卸货的概率。(4分)(2)在货站排队等候卸货的平均货车数。(4分)(3)每辆车在货站的平均逗留时间。(4分)(4)若希望货车在货站的逗留时间减少一半,则这2位工人应服务了多少辆车? (4分)(5)假设2位工人分别货车卸货,此时每位工人平均每天可服务3辆车,问货站的工作效 率是否得到提高?说明原因。(6分)四、(16分)现8项任务可供选择,预期完成时间为4 (i = l,8),设计报酬为0 =1,8)(万元),设计任务只能一项一项进行,总期限为A周。要求:(1)至少完成3项设计任务;(
31、2)若选择任务1,必须同时选择任务2;(3)任务3,任务4和任务8不能同时选择:(4)或者选择项目5,或者选择项目6和7;问应当如何选择设计任务,可使总的设计报酬最大。(建立数学模型,不需要求解)第3页(共3页)五(25分)某复合系统由A、B、C三个部分串联而成,已知:A、B、C相互独立各 部分的单位故障分别为:=0.4,6=0.3,匕=0.2:每个部分单件价格为:A部分单价C=1万元;8部分单价为。2= 2万元;C部分单价为。3=3万元;共投资购置部分的金额为10万元。求A、B、C三部分应购置多少部件才能使系统的总可靠率最高?(请用 动态规划方法求解)六(15分)已知某实际问题的线性规划模型
32、为: nmax Z = fcjXjE1a“Kj= 1,, j=iXj 2 0(/= 1,)设第i项资源的影子价格为y。(1)若第一个约束条件两端乘以2,变42伪,1是对应这个新约束条件的影 j=i子价格,求1与y的关系。(2)令x; = 3M,用替代模型中所有的再,问影子价格其是否变化?若再不可能在最优基出现,问X:是否可能在最优基中出现。(3)如目标函数变为maxZ = 2j/j ,问影子价格有何变化?/=!f max Z = CX七、(10分)对整数规划(/P): s-t-AX=b ,若对其放松问题(LP): xno,且为整数max Z = CXs-t AX=b ,求得最优解,但最优解不满
33、足整数解的要求。假设变量与不是整数解, X 0其在(LP)问题的最终表中对应的约束方程为:xio + Z4。,jXj =瓦0 (N为非基变量的下标集)。请用约束:XjO + Zai,jXj = % , jeNjgN构造一个割平面约束。八(12分)简答题:(1)简述对偶单纯法的优点和应用上的局限性。(2)动态规划是基于什么原理?并简述这个原理。上海大学2008年攻读硕士学位研究生入学考试试题招生专业:管理科学与工程考试科目:运筹学一、判断(2分*10=20分)7,如线性规划问题存在最优解,则最优解一定对应可行域边界的一个点。8、任何线性规划问题存在并且具有唯一的对偶问题。9、运输问题是一种特殊的线性规划模型,因而求解结果也可能出现下列四种情况之 一:有唯最优解,有无穷最优解,无界解,无可行解.10、 任何线性规划问题都有一个对偶问题。11、 整数规划解的H标函数值般优于其相应的线性规划问题的解的目标函数值。12、 在排队系统中,顾客等待时间的分布不受排队服务规则的影响。二、建立数学模型。(12分*2=24分)某厂使用A、B两种原料生产甲、乙、丙三种产品,有关数据见下表
限制150内