《运筹学试题》word版.doc

精品资料.为你而备兰州大学管理学院试卷运筹学（C）卷管理学院2008级用 2010年1月18日用大班号： 年级： 姓 名： 学号：（学号后6位）题 号一二三四五六七八总计得 分说 明：1 本试卷满分为100分。考试时间为120分钟。2 所有答案都必须答到试卷上，若试卷上写不完的答案可以另附纸张，但必须在试卷上注明。直接写在试卷以外的纸张上的答案不计分。3 答完卷后将考卷和草纸一起交上。一、名词解释（每题分，共10分） 1. 初始基本可行解 多个基本可行解中一个，一般情况下在求最大时取最小的基本可行解，求最小时取最大的基本可行解。1. 线性规划问题的可行域在线性规划规划问题中，符合所有约束条件约束的解（可行解）的集合，在有解的情况下，它是一个多维的区域。3确定性决策 在决策问题中，其自然状况完全决定的的决策。4剩余量 在线性规划问题中，资源限制量大于资源实际利用量的部分。 4松驰量对于一般规划问题约束条件中实际值小于常数项的部分。二、单项选择题（从下列各题四个备选答案中选出一个正确答案，答案选错或未选者，该题不得分。）（每题2分，共10分）3用图解法求解下列问题：max Z=2x-3y s.t. -x+2y2 x+2y6 x-y3 x+3y3 x,y=0 其最优解为（ C ） A(2，2) B(4，1) C(3，0) D(2，5) 4若运输问题在有条件的总供应量大于总需要量时，( D )。1 A不能求解 B不存在可行解2 C虚设一个需求点再求解 D虚设一个供应点再求解3以下叙述中，不正确的是（ C ）A树的点数为线数加1 B树的任意两点间只有一条路C图的点数大于线数 D任何不连通图都不是树4在产销平衡运输问题的数学模型中，约束条件的关系是（ A ）。A= BC D，=，都有1线性规划的约束条件为 2x1+x2+x3=5 2x1+2x2+x4=6x1, x2, x3, x40 1 则基本可行解为( A )1 A(0, 2, 3, 2) B(3, 1, 1, 0) 1 C(0, 0, 6, 5) D(2, 0, 1, 4)三、判断题（你认为下列命题是否正确，对正确的打“”；错误的打“”。）（每题分，共10分）1. 若线性规划模型的可行域非空有界，则其顶点中必存在最优解。( ) 2在目标规划中，若正偏差变量大于等于零，负偏差变量必小于等于零。( ) 1线性规划的最优解是基本可行解。( ) 4线性规划的灵敏度分析中，相差值是指变量的值与最优解的相差部分。( )5线性规划问题的图解法只能解决两个变量的问题。( )四、填空题（每题2分，共10分）1. 目标规划问题的目标函数只能求最（ 小 ），只能由（ 偏差变量 ）变量组成。2一般线性规划问题的可行域是连续的，整数规划问题的可行域是（ 离散 ）的。4一般线性规划问题中，约束条件的实际值与限制值的差决定了（ 松弛量或剩余量 ）。5最短路问题也可以用线性规划问题来求解，此时的变量数与（ 网络的弧 ）数相同。1在多目标决策问题中，当目标中规定了x=b 。为达到了目标，则必须同时满足( 下偏差和负偏差 )都为零才算达到了目标。五、转换题（只用将转换后的结果写在空白处）：（每题4分，共20分）1、将一般线性规划模型转换为标准型；min f=3x1+2x2+4x3+x4 x1-x2+2x3+x49 x1-x2+2x3-x45-2x1+x2-3x3+x4=-1x10, x20, x30, x4无约束解：min f=3x1+2x2-4 x3+ x4- x5+0 x6+0 x7 x1-x2-2 x3+ x4- x5- x6=9x1-x2-2 x3+ x4- x5+ x7=52x1-2x2-3 x3- x4+ x5=1xi0, i=1,2,72、将产销不平衡问题转换为产销平衡问题； 有三个化肥厂供应四个地区的农用化肥。假定等量的化肥在这些地区使用效果相同。各化肥厂年产量、各地区年需要量及从各化肥厂到各地运送单位化肥的运价（单位：万元/万吨）如下表。试将该的产销不平衡的运输问题化为产销平衡的问题（即设虚拟的产地或虚拟的销地，写出产销平衡运价表）。 从各化肥厂到各地蔚蓝色运送化肥的相关数据需求地区1需求地区2需求地区3需求地区4产量（万吨）化肥厂A1613221750化肥厂B1413191560化肥厂C192023-50最低需求（万吨）3070010最高需求（万吨）507030不限解：地区1地区1地区2地区3地区3地区4地区4产量（万吨）化肥厂A1616132222171750化肥厂B1414131919151560化肥厂C1919202323MM50M0MM0M030需求（万吨）30207020101030地区1地区1地区2地区3地区4地区4产量（万吨）化肥厂A16161322171750化肥厂B14141319151560化肥厂C19192023MM50M0M0M030需求（万吨）3020703010303、将指派问题转换为线性规划问题； 某公司的营销部经理将要主持召开一年一度的由营销区域经理以及销售人员参加的销售协商会议。为了更好地安排这次会议，他安排小张、小王、小李、小刘等四个人，每个人负责完成下面的一项工作：A、B、C和D。由于每人完成每项任务的时间不同，可得以下求解化费总时间最少的指派模型。请将该指派模型转化为线性规划问题。工作A工作B工作C工作D可做工作数小张354127401小王474532511小李395636431小刘305524461需要人数1111 解： Min f=35x1+41x2+27x3+40x4+47x5+45x6+32x7+51x8+39x9+56x10+36x11+43x12+30x13+55x14+24x15+46x16x1+x2+x3+x4=1x5+x6+x7+x8=1x9+x10+x11+x12=1x13+x14+x15+x16=1x1+x5+x9+x13=1x2+x6+x10+x14=1x3+x7+x11+x15=1x4+x8+x12+x16=1xi0 i=1164、将简单有优先权目标规划模型转换为分级的有优先权目标规划模型； min z=p1(d1+)+p2(d2+d3-)+p3(d4-) x14 2x2123x1+2x218x1-2x2- d1+ d1-=0x1+x2- d2+ d2-=03x1+2x2- d3+ d3-=0300x1+500x2- d4+ d4-=0x1，x2，di+，di-0 i=1,2,3,4第一级： min d1+ x14 2x2123x1+2x218x1-2x2- d1+ d1-=0x1，x2，d1+，d1-0第二级： min d2+d3- x14 2x2123x1+2x218x1-2x2- d1+ d1-=0x1+x2- d2+ d2-=03x1+2x2- d3+ d3-=0d1+=第一级的解x1，x2，di+，di-0 i=1,2,3第三级： min d4- x14 2x2123x1+2x218x1-2x2- d1+ d1-=0x1+x2- d2+ d2-=03x1+2x2- d3+ d3-=0300x1+500x2- d4+ d4-=0d1+=第一级的解d2+d3-=第二级的解x1，x2，di+，di-0 i=1,2,3,45、用图形将一线性规划问题的可行域转换为纯整数问题的可行域(在图上用“”标出)。 max z= x1+2x2 8x1+4x232 6x1+8x248 x1，x20解：max z= x1+2x2 8x1+4x232 6x1+8x248 x1，x20x1，x2为整数六、结果分析题（每题10分，共20分）(一) 某厂利用原料A、B生产甲、乙、丙3种产品，已知生产单位产品所需原料数（单位）、单件利润（元/单位）及有关数据如下表。甲乙丙原料拥有量A63545B34530单位利润415 此问题的线性规划数学模型： max z= 4x1+x2+5x3 6x1+3x2+5x345 3x1+4x2+5x330 x1，x20(1) 对于这个数学模型，需要用计算机求解，“Excel运筹学求解模板”、“规划求解参数”对话框及“规划求解结果”如下图。请详细描述求解这个数学模型的操作过程。 a、分别描述在哪些单元格输入什么数据；在C5、D5、E5分别输入目标函数就是系数：4、1、5C11、D11、E11分别输入第一个约束条件的变量系数：6、3、5C12、D12、E12分别输入第二个约束条件的变量系数：3、4、5在T11、T12分别输入常数项：45、30b、怎么操作进行求解；在主菜单中点“工具”、“规划求解”得上面的“规划求解参数”对话框，直接点“求解”。就在主菜单上得到最优解和最优值，同时得到上面的“规划求解结果”对话框。c、怎么获得灵敏度分析报告； 在“规划求解结果”对话框中，选“敏感性报告”、“确定”，就得到一个新的工作薄“敏感性报告1”，打开该工作薄就可看到该问题的灵敏度分析报告 (2) 本模型的求解结果如下：最优值35可变单元格单元格名字终值递减成本目标式系数允许的增量允许的减量$C$34最优解50421$D$34x20-2.66712.66671E+30$E$34x33051.66671.6667约束单元格名字终值阴影价格约束限制值允许的增量允许的减量$R$11实际值450.3333451515$R$12实际值300.666730157.5请回答下列问题：A、最优解和最优值是多少，递减成本一栏的数据是什么意思？最优解：（5，0，3）最优值：35B、若产品乙、丙的单件利润不变，产品甲的利润在什么范围变化，上述最优解不变？3-6元/件C、若原料A市场紧缺，除拥有量外一时无法购进，而若原料B数量不足可以去市场购买，单价为0.5，问该厂是否购买，以购进多少为宜？可以购买，因为对偶价格是0.667,用0.5购进每单位可获0.167元的差价。D、对于产品乙，其利润再增加2.5元/单位。问应该怎么安排生产。因为产品乙的相关值是2.667所以，利润再增加2.5元/单位，原方案不变。E、两个约束条件的实际值各是多少？（二） 用图解法求解下列线性规划问题：Max Z=11x1+8x2S.T. 10x1+2x2 20 3x1+3x2 18 4x1+9x2 36 x1,x20并求三个约束条件的松驰量（剩余量）和对偶价格七、计算题（每题5分，共10分）（一） 某公司铺设光导纤维网络问题。公司的管理层已经决定铺设最先进的光导纤维网络，为公司的主要部门之间提供高速通信（数据、声音和图像）。下图中的节点显示了该公司主要部门（包括公司的总部、巨型计算机、研究区、生产和配送中心等）的分布图。虚线是铺设纤维光缆的可能位置。每条虚线旁边的数字表示了如果选择在这个位置铺设光缆需要花费的成本（单位：万元）。公司主要部门的分布图 求该公司铺设光导纤维网络的最小支撑树。 最小支撑树：11 （二） 某工厂有一种新产品，其推销策略由A1、A2、A33种可供选择的方案，但各方案所需资金、时间都不同，加上市场情况的差别，获利和亏损的情况也不同。而市场状态也有3种：S1（需求量大），S2（需求量一般），S3（需求量小），但未来市场将出现哪种情况并不知道。各种状态的收益情况如下表： 新产品各种状态的收益情况表 单位：万元市场状况S1S2S3A15010-5A230250A3105-10试分别用乐观准则、悲观准则、等可能性准则和后悔值准则进行决策。晴天多云小雨悲观准则乐观准则等可能性准则甲地5010-5-550(max)18.332(max)乙地302500(max)3018.332(max)丙地105-10-10101.6665最优值05018.332 后悔表晴天多云小雨后悔值准则甲地015515(min)乙地200020丙地40201040最优值15八、建模题（每题10分，共10分）7.5某公司在三个地方有三个分厂，生产同一种产品，其产量分别为300箱、400箱和500箱。需要供应给四个地方销售，这四地的产品需求分别 为400箱、250箱、550箱和200箱。三个分厂到四个销售地的单位运价如下表： 销地产地甲乙丙丁1分厂211723252分厂101530193分厂23212022（1） 应如何安排运输方案，使得总的运输费用最小？（2） 如果2分厂的产量从400箱增加到600箱，应如何安排运输方案，使得总的运输费用最小？（3） 如果甲销地的需求量从400箱增加到500箱，其它情况都与（1）完全相同，应如何安排运输方案，使得总的运输费用最小？解：（1） 本问题的运输模型： 销地产地甲乙丙丁产量1分厂211723253002分厂101530194003分厂23212022500销量400250550200 本问题总产量：1200箱；总销量：1400箱。所以是一个销大于产的产销不平衡运输问题。代入销大于产的产销不平衡运输问题求解模板就可得结果。 （2） 如果2分厂的产量从400箱增加到600箱，可得以下的运输模型： 销地产地甲乙丙丁产量