上海大学历年运筹学考研真题及答案、考研大纲

考试科目：运筹学适用专业：管理科学与工程一、复习要求：要求考生熟悉模型的构建及应用，掌握定量化决策和模型化的基本思想和方法，能灵活运用运筹学的方法求解各类问题。二、主要复习内容：1、线性规划线性规划问题与数学模型、图解法、线性规划单纯形算法、单纯形法的进一步讨论、线性规划的对偶问题、对偶问题的基本性质、影子价格、对偶单纯形法、灵敏度分析、参数线性规划。重点：构建线性规划的数学模型，单纯形算法的掌握，对偶问题的建立，影子价格的理解，灵敏度分析。2、运输问题运输问题及其数学模型，用表上作业法求解运输问题，运输问题的进一步讨论，应用问题举例。重点：运输问题的数学模型，运输问题的求解。3、整数规划整数规划的数学模型及其解的特点，0－1规划的数学模型，整数规划求解的方法（分枝定界法、割平面法、纯0－1规划的求解方法），指派问题。重点：含0-1变量的混合整数规划模型的构建，整数规划的求解方法。4、动态规划多阶段决策问题的最优化，动态规划的基本概念和基本原理，动态规划模型的建立与求解，动态规划在经济管理中的运用。重点：动态规划模型的建立与求解，动态规划在经济管理中的运用。5、排队论基本概念，到达间隔的分布和服务时间的分布，M/M/s等待制排队模型，M/M/s混合制排队模型。重点：随机服务系统的分析以及各量值的计算。一、参考书目：《运筹学教程》（第3版），胡运权主编，清华大学出版社2007年上海大学2006年攻读硕士学位研究生入学考试试题招生专业：管理科学与工程考试科目：运筹学一、判断（2分*10=20分）1、单纯刑法计算中，如果不按最小比值法选取换出变量，则在下一个解中至少有一个基变量的值为负。2、线性规划问题可行域的某一顶点若其目标函数值优于相邻的所有顶点的目标函数值，则该顶点处的目标函数值达到最优。3、在解运输问题时，其基本可行解中解变量的个数为行数+列数—1.4、一个排队系统中，不管顾客到达和服务时间的情况如何，只要运行足够长的时间后，系统将进入稳定状态。5、若某种资源的影子价格等于K，在其他条件不变的情况下，该中资源增加5个单位时，相应的目标函数值将增大5K。6、在排队系统中，顾客到来的时间间隔是一个随机变量。二、建立数学模型。（12分*2=24分）某服装厂制造大、中、小三种尺寸的防寒服，所用资源有尼龙绸、尼龙棉、劳动力和缝纫设备。缝制一件防寒服所需各种资源的数量如表（单位已适当给定）。不考虑固定费用，则每种防寒服售出一件所得利润分别为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万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）请简述影子价格的定义。（2）在使用单纯型表求解型线性规划时，资源的影子价格在单纯型表的什么位置上？（3）写出影子价格的数学表达式并用其定义加以验证（4）试述运输问题中检验数的经济意义六、某公司近期向市场推出了一种新产品，多功能复印打印机。该产品的多功能很受顾客欢迎，但一旦需停下来维修则要同时耽误多项工作，因此，顾客要求尽量缩短维修等待时间。为此，公司的技术服务部在每个销售区域设置了一位技术服务代表专门负责该产品维修服务。假设顾客要求维修的电话是完全随机到达，平均每天到达3个。而技术服务代表连续工作时，平均每天完成4项维修任务。(1)该服务系统能否看作一个MM／1排队系统？为什么？(2)假设该系统可看作一个标准的MM／1排队系统，求出系统的服务强度（技术服务代表的繁忙率）和顾客的平均等待（不包括维修）时间。(3)现公司希望将顾客的平均等待时间降为不超过0.25天。为此需将每个技术服务代表的服务区域缩小为达到率不超过多少？这时每个技术服务代表的服务强度降为多少？七、线性规划问题1212121212max23221228416412,0zxxxxxxxxxx已知其最优解x1，x20，而第1，4两种资源（相应于第1，4两约束）均有余量，应用互补松弛定理求出原问题和对偶问题的最优解第1页（共3页）上海大学2007年攻读硕士学位研究生入学考试试题招生专业：管理科学与工程考试科目：运筹学一、（26分）某厂生产三种产品，设生产量分别为123,,xxx，已知收益最大化模型如下：123max324Zxxxst1232340xxx（第一种资源）12322348xxx（第二种资源）10x（产品1的生产能力限制）1230xxx，，（1）以456,,xxx表示三个约束的不足变量，写出标准型。（4分）（2）若用单纯形法计算到下面表格Bx1x2x3x4x5x6xb4x003/21-1/2-162x013/201/2-1141x10000110jjcz0010-1-1-58指出所表达的基本可行解，目标函数值。（4分）（3）指出上面给出的解是否最优。若不是，求出最优解和最优目标函数值。（6分）（4）写出本规划的对偶规划，并求出它的最优解。（4分）（5）若产品1的单位利润从3变为4，问最优方案是什么？此时的最大收益是多少？（4分）（6）若资源常数列向量404810b变为466010b，问原最优性是否改变？求出此时的最优方案和最大收益。（4分）第2页（共3页）二、（24分）有123,,AAA三个工厂，要把生产的产品运往123,,BBB三个需求点。若123,,BBB三个需求点需求量没有得到满足，则单位罚款费用为6，3，4。各厂的供应量、各点的需求量以及单位运价如下表。问应如何组织调运才能使总费用（运输费用和罚款费用之和）最小？单位运单需求点工厂B1B2B3供应量A164715A257830A325625需求量204030（1）请将此问题化为供需平衡的运输问题；（2）用最小元素法求（1）的一个初始调运方案；（3）判断（2）中的方案是否最优，并说明原因。三、（22分）设货车按泊松流到达车站，卸货后马上离开。已知平均每天到达4辆车。该货站有2位工人，同时为货车卸货，假设卸货时间服从负指数分布，平均每天可服务6辆车。求：（1）该货站没有货车卸货的概率。（4分）（2）在货站排队等候卸货的平均货车数。（4分）（3）每辆车在货站的平均逗留时间。（4分）（4）若希望货车在货站的逗留时间减少一半，则这2位工人应服务了多少辆车？（4分）（5）假设2位工人分别货车卸货，此时每位工人平均每天可服务3辆车，问货站的工作效率是否得到提高？说明原因。（6分）四、（16分）现8项任务可供选择，预期完成时间为ia(1,,8)i，设计报酬为ib(1,,8)i（万元），设计任务只能一项一项进行，总期限为A周。要求：（1）至少完成3项设计任务；（2）若选择任务1，必须同时选择任务2；（3）任务3，任务4和任务8不能同时选择；（4）或者选择项目5，或者选择项目6和7；问应当如何选择设计任务，可使总的设计报酬最大。（建立数学模型，不需要求解）第3页（共3页）五、（25分）某复合系统由A、B、C三个部分串联而成，已知：①A、B、C相互独立②各部分的单位故障分别为：1230.4,0.3,0.2PPP；③每个部分单件价格为：A部分单价11C万元；B部分单价为22C万元；C部分单价为33C万元；④共投资购置部分的金额为10万元。求A、B、C三部分应购置多少部件才能使系统的总可靠率最高？（请用动态规划方法求解）六、（15分）已知某实际问题的线性规划模型为：maxnjjZcx1(1,,)0(1,,)nijjijjaxbimxjn设第i项资源的影子价格为iy。（1）若第一个约束条件两端乘以2，变111(2)2njjjaxb，1y是对应这个新约束条件的影子价格，求1y与1y的关系。（2）令113xx，用13x替代模型中所有的1x，问影子价格iy是否变化？若1x不可能在最优基出现，问1x是否可能在最优基中出现。（3）如目标函数变为1max2njjjZcx，问影子价格有何变化？七、（10分）对整数规划()IP：max0ZCXstAXbX，且为整数，若对其放松问题（LP）：max0ZCXstAXbX,求得最优解，但最优解不满足整数解的要求。假设变量iox不是整数解，其在（LP）问题的最终表中对应的约束方程为：ioijNxao，jijxbo（N为非基变量的下标集）。请用约束：iijNXoao，jijxbo，构造一个割平面约束。八、（12分）简答题：（1）简述对偶单纯法的优点和应用上的局限性。（2）动态规划是基于什么原理？并简述这个原理。上海大学2008年攻读硕士学位研究生入学考试试题招生专业：管理科学与工程考试科目：运筹学一、判断（2分*10=20分）7、如线性规划问题存在最优解，则最优解一定对应可行域边界的一个点。8、任何线性规划问题存在并且具有唯一的对偶问题。9、运输问题是一种特殊的线性规划模型，因而求解结果也可能出现下列四种情况之一：有唯一最优解，有无穷最优解，无界解，无可行解.10、任何线性规划问题都有一个对偶问题。11、整数规划解的目标函数值一般优于其相应的线性规划问题的解的目标函数值。12、在排队系统中，顾客等待时间的分布不受排队服务规则的影响。二、建立数学模型。（12分*2=24分）某厂使用A、B两种原料生产甲、乙、丙三种产品，有关数据见下表：AB生产成本（万元/吨）销售价格（万元/吨）甲乙丙1.00.50.40.60.60.58518302035原料成本（万元/吨）57原料可用数量（吨）350460（1）请写出使总销售利润最大的线性规划模型（其中甲、乙、丙产产量分别记为x1,x2,x3,约束依A,B原料次序）:(2)写出此问题的对偶规划模型三、已知某运输问题的产销平衡表与单位运价表如下图所示。ABCDE产量产地1101520204050产地22040153030100产地33035405525150销量251156030701、求最优方案。2、如果产地3的产量变为130，又B地区需要的115单位必须满足，试重新确定最优调拨方案四、在某单位单人理发店顾客到达为普阿松分布，平均到达间隔为20分钟，理发时间服从负指数分布，平均时间为15分钟。问：（24分）5、顾客来理发不必等待的概率。6、理发店内的顾客平均数。7、顾客在理发店内平均逗留时间。五、派公司是一个生产高尔夫器材的小型公司，近期推出了高、中价位的高尔夫袋新产品（标准袋和高档袋），经销商对此产品十分感兴趣，并订购了派公司下3个月的全部产品。该高尔夫袋的生产过程主要包括4道工序：切割并印染原材料、缝合、成型（插入支撑架和球棒分离装置等）、检验和包装。有关数据如表1。派公司须决定标准袋和高档袋各生产多少可使公司的总利润最大。表1时间单耗产品（小时）工序标准袋高档袋3个月内最大生产能力（小时）切割印染7/101630缝合1/25/6600成型12/3708检验包装1/101/4135产品单位利润（美元）109(1)写出