04年研究生图论题目.doc

2004年全国首届部分高校研究生数学建模竞赛试题有关说明 2004年全国部分高校研究生数学建模竞赛组织委员会、评审委员会热烈欢迎广大研究生参加竞赛，接受挑战，真心预祝你们在竞赛中充分发挥自己的聪明才智，团结协作，顽强拼搏，赛出风格，赛出水平。衷心希望你们通过竞赛增长才干，提高能力。 本次竞赛共有A、B、C、D四道赛题，每队可任选一题参赛，只要在九月二十日十八时之前寄出参赛论文都可以参加评奖。但是由于赛题的难度不可能完全相同，差异在所难免。因此，在评奖中既要考虑四条题目之间的大致平衡，也会考虑到题目的难易程度，向选择难度较大题目的参赛队有所倾斜，特此说明。 由于各种原因，参赛队也有可能对题目有疑问，可以在的网页上贴出疑问，我们将请命题人在同一网页尽快作出回答，以提高效率。但绝对不应借此进行讨论，请各参赛队自觉遵守竞赛纪律。 竞赛仅仅是个手段，不是目的。因此，我们真诚欢迎广大研究生竞赛后对赛题继续进行深入的讨论，中国数学建模网页将为大家提供交流的平台。在评奖中可能参考这里的结果，更重要的是争取把这些真刀真枪的实际问题解决得更好，扩大数学建模活动的影响，同时也进一步提高我国数学建模活动的水平。评审委员会将选择讨论中出现的优秀成果（包括少量的竞赛优秀论文）在核心期刊上发表。 研究生和教师是数模活动的主体，我们真诚地盼望能经常听到你们的意见与建议，让我们共同努力把这一活动办得既扎实又有成效。 补充通知 各参赛队： 关于竞赛的几个具体问题通知如下： 1、 竞赛采用统一封面，请与题目一同下载。 2、 参赛队号已正式通知各校，为防止通信出现差错， 各校的参赛队号表也与题目公布在一起备查。 3、 鉴于有部分学校分几次报名，有的学校对报名表的 顺序没有足够地重视，也有参赛队的成员已发生变化，同时防止组委会登记工作中出现错误，请每个参赛队务必重填报名表，并由学校竞赛负责人分配属于本校的队号，不要发生本单位内或本单位与外单位重号现象。重填后的报名表应装订于论文的封面前。 A题发现黄球并定位 一、设在半径为50m，高为10m的圆柱体内有红、蓝、黄三种小球，若一只红球到某只黄球再到一只蓝球的距离小于等于40m,才认为该黄球有可能被这对红、蓝球发现，试问在这个圆柱体的底面至少要放置多少红球、多少蓝球，又它们分别放置在什么地方（设放置后不能移动），才能使放在圆柱体内任何位置（距离底面不足0.1m不予考虑）的黄球都有可能被红球、蓝球发现。 二、如果增加一个条件。分别以过红球或蓝球（可以将它们看成质点）的两条直线为轴，以红球、蓝球为顶点作两个圆锥，圆锥轴截面的顶角均为4度。当黄球（直径2mm）至少有一部分位于上述两个圆锥的交集中（第一问中40m的条件仍旧要满足），就认为红球、蓝球发现了黄球并知道了从红球到黄球中心再到蓝球的距离。当然这时还无法给出黄球的准确定位，但是对同一个黄球，如果存在几对符合上述条件的红球、蓝球，（甚至一个红球、三个蓝球或三个红球、一个蓝球构成的三对）就可以为黄球定位。现在要给固定在圆柱体内任意位置（距离底面不足0.1m仍不予考虑）的黄球定位，假设以红球、蓝球为顶点的每个圆锥的轴可以取任意位置，即为一只黄球定位时取某个方向，为另一只黄球定位时又可以取另外的方向。为此至少需要红球、蓝球各多少个？红球、蓝球又应如何放置在圆柱体的底面？（仍旧假设红球、蓝球放置后不能移动） 三、假设黄球从圆柱体外任意位置进入圆柱体，并且在圆柱体内可以随意移动（仍不会到达距离底面不足0.1m的地方），移动速度的范围是0.15-1.02m/s。这时给黄球定位显然更困难。现在假设以红球、蓝球为顶点的圆锥的轴也是可以随意旋转的，旋转的角速度最大为60o/s。请你们决定为了给作直线运动的黄球定位是否需要增加红球、蓝球的数量，是否需要改变红球、蓝球在圆柱底面的放置位置（仍旧假设红球、蓝球放置后不能移动），并为每个红球、蓝球所在的圆锥轴制定旋转方案。请你们为运动的黄球被定位的概率下个定义，再根据此定义计算你们方案的定位概率。 四、如果某个黄球被发现、定位的信息是共享的，即所有红球、蓝球都知道这些信息，进一步有一个计算机知道所有上述信息，并且所有红球、蓝球所在的圆锥轴都受到这个计算机的控制。请问全部红球、蓝球的圆锥轴如何协同旋转，以增加黄球被发现、被定位的概率。（如果感到困难，可以先仅在直径10m的圆柱或边长8m的正方体或更小的区域内考虑问题）。仿真、讨论增加红球、蓝球的个数到共190个或更多时对黄球定位的益处。（仍旧假设红球、蓝球放置后不能移动） 五、如果圆柱体的底面有一些起伏（位置、高度可自定），而红球、蓝球到黄球的连线穿过底面则无效，即认为不符合第二问中关于黄球被发现、被定位的条件。那么这些起伏对仍需要放置在圆柱体底面的红球、蓝球的个数有无影响？进行适当的讨论。 六、如果在第二问中红球、蓝球发现黄球时不但知道从红球到黄球中心再到蓝球的距离，而且同时知道红球、蓝球所在圆锥轴的准确的方向，这一点对黄球的定位有什么影响？如果计算机可以在一毫秒的时间内改变全部红球或蓝球中任意一只或多只球的颜色对于黄球被发现、被定位又有什么影响？ 七、一旦有一对红球、蓝球发现黄球，计算机应如何控制所有红球、蓝球所在的圆锥轴的旋转方案来跟踪移动的黄球并尽快给它定位？ 八、如果有多个黄球同时（有一定的时间差）越过圆柱体的表面，计算机如何控制所有红球、蓝球所在的圆锥轴的旋转以使全部黄球可能被及早发现，尽快定位？ 九、你们对黄球发现、定位有什么更好的建议？例如，是否可以让红球、蓝球在圆柱体底面以不超过0.15m/s速度移动，这样对黄球的及早发现，尽快定位有无好处？ B题：实用下料问题 “下料问题(cuttingstockproblem)”是把相同形状的一些原材料分割加工成若干个不同规格大小的零件的问题，此类问题在工程技术和工业生产中有着重要和广泛的应用.这里的“实用下料问题”则是在某企业的实际条件限制下的单一材料的下料问题。 现考虑单一原材料下料问题.设这种原材料呈长方形，长度为,宽度为，现在需要将一批这种长方形原料分割成种规格的零件,所有零件的厚度均与原材料一致，但长度和宽度分别为，其中wi.种零件的需求量分别为.下料时，零件的边必须分别和原材料的边平行。这类问题在工程上通常简称为二维下料问题。特别当所有零件的宽度均与原材料相等，即，则问题称为一维下料问题。 一个好的下料方案首先应该使原材料的利用率最大，从而减少损失，降低成本，提高经济效益。其次要求所采用的不同的下料方式尽可能少，即希望用最少的下料方式来完成任务。因为在生产中转换下料方式需要费用和时间，既提高成本，又降低效率。此外，每种零件有各自的交货时间，每天下料的数量受到企业生产能力的限制。因此实用下料问题的目标是在生产能力容许的条件下，以最少数量的原材料，尽可能按时完成需求任务,同时下料方式数也尽量地小.请你们为某企业考虑下面两个问题。 1 建立一维单一原材料实用下料问题的数学模型,并用此模型求解下列问题，制定出在生产能力容许的条件下满足需求的下料方案,同时求出等额完成任务所需的原材料数，所采用的下料方式数和废料总长度.单一原材料的长度为3000mm,需要完成一项有53种不同长度零件的下料任务.具体数据见表一，其中为需求零件的长度，为需求零件的数量.此外，在每个切割点处由于锯缝所产生的损耗为5mm.据估计，该企业每天最大下料能力是100块，要求在4天内完成的零件标号()为:5,7,9,12,15,18,20,25,28,36,48;要求不迟于6天完成的零件标号()为:4,11,24,29,32,38,40,46,50.(提示：可分层建模。(1).先考虑用材料既少,下料方式又少的模型,或先仅考虑所用材料最少的模型及增加一种下料方式大致相当于使原材料总损耗增加0.08%情况下的最佳方案。(2).在解决具体问题时,先制定4天的下料方案,再制定6天的下料方案,最后制定53种零件的下料方案.这一提示对第2题也部分适用.) 表一需求材料的数据单位：mm 1 2 3 4 5 6 7 8 9 10 1743 1680 1532 1477 1313 1285 1232 1217 1180 1177 4 216 104 38 4 60 4 8 6 10 11 12 13 14 15 16 17 18 19 20 1105 1055 1046 1032 1030 975 893 882 847 845 8 2 4 8 8 2 8 301 6 38 21 22 23 24 25 26 27 28 29 30 830 795 766 745 732 719 714 690 665 633 30 8 4 4 34 18 4 4 90 30 31 32 33 34 35 36 37 38 39 40 630 600 590 588 582 578 540 488 455 434 30 212 108 482 196 8 32 4 52 42 41 42 43 44 45 46 47 48 49 50 420 415 414 411 405 328 313 290 275 265 8 8 8 60 136 4 68 286 502 286 51 52 53 255 184 155 292 57 24 2 建立二维单一原材料实用下料问题的数学模型,并用此模型求解下列问题.制定出在企业生产能力容许的条件下满足需求的下料方案,同时求出等额完成任务所需的原材料 块数和所需下料方式数.这个问题的单一原材料的长度为3000mm,宽度为100mm,需要完成一项有43种不同长度和宽度零件的下料任务.具体数据见表二，其中分别为需求零件的长度、宽度和数量.切割时的锯缝可以是直的也可以是弯的，切割所引起的锯缝损耗忽略不计.据估计，该企业每天最大下料能力是20块要求在4天内完成的零件标号()为:3,7,9,12,15,18,20,25,28,36. 表二需求材料的数据单位：mm 1 2 3 4 5 6 7 8 9 10 1105 1055 1046 1032 1030 975 893 882 847 845 30 20 50 30 20 50 30 20 30 30 24 6 12 24 24 6 24 1001 20 108 11 12 13 14 15 16 17 18 19 20 830 795 766 745 732 719 714 690 665 633 30 20 35 30 30 30 50 30 20 30 90 40 12 12 68 54 10 12 270 90 21 22 23 24 25 26 27 28 29 30 630 600 590 588 582 578 540 488 455 434 30 35 20 20 30 20 50 20 20 30 90 612 508 2082 496 24 62 20 162 92 31 32 33 34 35 36 37 38 39 40 420 415 414 411 405 328 313 290 275 265 20 30 20 30 20 30 50 30 20 30 40 24 40 180 536 12 128 686 2002 686 41 42 43 255 184 155 30 20 50 692 357 52 C题售后服务数据的运用 产品质量是企业的生命线，售后服务是产品质量的观测点，如何用好售后服务的数据是现代企业管理的重要问题之一。 现以某轿车生产厂家为例考虑这个问题。假设该厂的保修期是三年,即在某轿车售出后三年中对于非人为原因损坏的轿车免费维修。在全国各地的维修站通过网络将保修记录送到统一的数据库里面，原始数据主要是这是哪个批次生产的轿车（即生产月份）、售出时间、维修时间、维修部位、损坏原因及程度、维修费用等等。通过这样的数据可以全面了解所有部件的质量情况，若从不同的需求角度出发科学整理数据库中的数据，可得到不同用途的信息，从而实现不同的管理目的。 整车或某个部件的“千车故障数”是一个很重要的指标，常用于描述轿车的质量。首先将轿车按生产批次划分成若干个不同的集合（下面表格的同一行数据就来自同一集合），再对每个集合中迄今已售出的全部轿车进行统计，由于每个集合中的轿车是陆续售出的，因此它们的统计时间的起点即售出时间是不同的。但在下面表格中，每一列数据的统计时间的长度却是相同的（例如2002年3月底售出的轿车，到2002年8月底；或2003年10月初售出的轿车，到2004年3月初都是使用了五个月，显然它们的统计时间的终点也是不同的），在相同使用时间长度（例如下表中第5列都是使用10个月的）内的整车或某个部件的保修总次数乘以1000再除以迄今已售出的轿车数量，即为下面表格中的千车故障数。 数据利用的时效性是很强的，厂方希望知道近期生产中的质量情况，但刚出厂的轿车还没有全卖出去，已售出的轿车使用几个月后的保修情况可能还没有数据反馈，因此数据显得滞后很多。当一个批次生产的轿车的三年保修期都到时，我们对这批轿车的质量情况有了最准确的信息，可惜时间是轿车出厂的四、五年后，这些信息已无法指导过去的生产，对现在的生产也没有什么作用。所以如何更科学地利用少量数据预测未来情况是售后服务数据利用的重要问题。 现有2004年4月1日从数据库中整理出来的某个部件的千车故障数，见下页的表。其中的使用月数一栏是指售出轿车使用了的月份数，使用月数0的列中是已售出的全部轿车在用户没使用前统计的千车故障数，1的列中是某一批次已售出的每一辆轿车，在它被使用到第一个月结束时统计的，对于该批次售出的全部轿车累计的千车故障数（即没使用时和第一个月中千车故障数的和），12的列中是每辆车使用到恰好一年结束时的累计千车故障数。生产月份是生产批次，如0201表示2002年1月份生产的。随着时间的推移，轿车不断地销售出去，已售出轿车使用一段时间后的千车故障数也能不断自动更新，再打印出的表中数据也将都有变化。 1.该表是工厂的真实数据，没有修改，反映的情况很多，请你分析表中是否存在不合理数据，并对制表方法提出建议； 2.利用这个表的数据预测时请注意区分水平和垂直方向。请你设计相应的模型与方法，并预测：0205批次使用月数18时的千车故障数，0306批次使用月数9时的千车故障数，0310批次使用月数12时的千车故障数； 3.如果有所有部件的千车故障数的数据表，你可以为质量管理方面提供那些决策与咨询？ 4.你还有什么想法和建议。（比如配件的生产组织、运送等等） 轿车某部件千车故障数的数据表 使用月数 12 11 10 9 8 7 6 5 4 3 2 1 0 生产月份 制表时销售量 0201 2457 4.88 4.88 4.88 4.48 4.07 4.07 3.66 2.44 2.44 1.22 1.22 0.41 0.41 0202 1670 5.99 5.99 5.39 5.39 5.39 5.39 4.19 4.19 3.59 2.99 2.4 1.8 0 0203 1580 4.43 3.8 3.8 3.8 3.8 3.8 3.16 2.53 2.53 1.27 0.63 0 0 0204 3704 13.77 12.15 11.61 9.72 9.18 7.83 6.75 5.67 4.32 2.43 1.35 0.54 0 0205 3806 36.78 34.68 31.53 29.43 27.06 25.22 23.12 21.81 18.13 16.55 13.4 8.93 3.94 0206 2910 41.58 39.18 36.08 32.99 31.62 28.87 24.74 23.02 18.9 15.46 13.4 9.28 4.47 0207 1614 72.49 69.39 62.58 54.52 47.71 43.99 40.27 34.7 30.36 26.64 22.3 13.01 3.72 0208 1985 75.57 71.54 69.02 64.48 56.93 52.9 45.34 36.78 28.21 20.65 13.6 7.56 1.51 0209 2671 112.32 110.45 108.57 104.08 95.84 84.61 74.88 65.89 52.04 42.31 27.33 11.23 1.87 0210 2107 121.97 119.6 116.28 115.33 107.74 96.35 84.48 69.29 54.11 39.39 22.78 11.39 2.85 0211 1399 95.78 95.78 94.35 92.21 85.78 82.2 72.19 61.47 47.18 40.03 25.73 12.87 3.57 0212 403 101.74 101.74 94.29 91.81 89.33 84.37 81.89 67 52.11 44.67 32.26 7.44 7.44 0301 6450 122.79 122.79 122.48 121.55 119.84 115.5 108.06 98.29 82.64 66.98 44.96 22.02 3.72 0302 2522 143.93 143.93 143.93 143.93 141.95 139.57 135.21 125.69 106.66 84.46 62.25 25.38 1.59 0303 2900 60.34 60.34 60.34 60.34 60 58.28 55.86 51.72 46.21 33.1 16.55 1.03 0304 1127 18.63 18.63 18.63 18.63 18.63 16.86 15.97 13.31 7.99 2.66 0 0305 818 14.67 14.67 14.67 14.67 13.45 13.45 13.45 11 8.56 1.22 0306 1199 5.84 5.84 5.84 5.84 5.84 5.84 5 1.67 0 0307 1831 13.65 13.65 13.65 13.65 13.11 10.38 7.1 0.55 0308 1754 5.7 5.7 5.7 5.7 4.56 1.71 0 0309 2163 0.92 0.92 0.92 0.92 0.46 0.46 0310 2389 0 0 0 0 0 0311 2434 0 0 0 0 0312 1171 0 0 0 D题研究生录取问题 根据素质教育和培养高素质合格人才的要求，目前各学校都对硕士研究生的录取方法进行改革，即在录取的过程中改变了以往根据考试成绩定终身的做法，加大了复试的作用。一般是根据初试的成绩，在达到国家和学校分数线的学生中从高分到低分排序，按1:1.5的比例选择进入复试的名单。复试一般采用由专家组面试考核的办法，主要面试考核学生的专业知识面、思维的创造性、灵活的应变能力、文字和口头的表达能力和外语水平等综合素质。专家组一般由多名专家组成，每位专家根据自己看法和偏好对所有参加复试学生的个方面都给出相应的评价，可以认为专家组的面试整体评价是客观的，最后由主管部门综合所有专家的意见和学生的初试成绩等因素确定录取名单。 某学校系计划招收10名计划内研究生，依照有关规定由初试上线的前15名学生参加复试，专家组由8位专家组成。在复试过程中，要求每位专家对每个参加复试学生的以上个方面都给出一个等级评分，从高到低共分为A,B,C,D四个等级，并将其填入面试表内。所有参加复试学生的初试成绩、各位专家对学生的个方面专长的评分如表（）表（8）所示。 该系现有10名导师拟招收研究生，分为四个研究方向。导师的研究方向、专业学术水平（发表论文数、论文检索数、编（译）著作数、科研项目数），以及对学生的期望要求见表(9)。在这里导师和学生的基本情况都是公开的。要解决的问题是： (1)首先，请你综合考虑学生的初试成绩、复试成绩等因素，帮助主管部门确定10名研究生的录取名单。然后，要求被录取的10名研究生与10名导师之间做双向选择，即学生可根据自己的专业发展意愿（依次申报个专业志愿，如表(10)所示）、导师的基本情况和导师对学生的期望要求来选择导师；导师根据学生所报专业志愿、专家组对学生专长的评价和自己对学生的期望要求等来选择学生。请你给出一种10名研究生和导师之间的最佳双向选择方案（并不要求一名导师只带一名研究生），使师生双方的满意度最大。 (2)根据上面已录取的10名研究生的专业志愿（见表（10），如果每一位导师只能带一名研究生，请你给出一种10名导师与10名研究生双向选择的最佳方案，使得师生双方尽量都满意。 (3)如果由十位导师根据初试的成绩及专家组的面试评价和他们自己对学生的要求条件录取研究生，那么，10名研究生的新录取方案是什么？为简化问题，假设没有申报专业志愿，请你给出这10名研究生各申报一名导师的策略和导师各选择一名研究生的策略。相互选中的即为确定；对于剩下的导师和学生，再按上述办法进行双向选择，直至确定出每一名导师带一名研究生的方案，使师生都尽量满意。 (4)学校在确定研究生导师的过程中，要充分考虑学生的申报志愿情况。为此，学校要求根据10名导师和15名学生的综合情况选择5名导师招收研究生，再让这5名导师在15名学生中择优录取10名研究生。请你给出一种导师和研究生的选择（录取）方案，以及每一名导师带名研究生的双向选择最佳策略。 (5)请你设计一种更能体现“双向选择”的研究生录取方案，提供给主管部门参考，并说明你的方案的优越性。 表（）：研究生复试专家面试评分表 编号：专家1 复试 学生 笔试 成绩 专家对学生专长的面试评分 灵活性 创造性 知识面 表达力 外语 学生1 416 A B A B A 学生2 410 A C A B B 学生3 405 B A C D C 学生4 397 B A B B A 学生5 392 B A B C A 学生6 389 B B A B D 学生7 385 A B C B B 学生8 382 B A A C A 学生9 380 B B A B B 学生10 378 D B A C C 学生11 377 D B C A B 学生12 372 A B A C A 学生13 360 B C B A D 学生14 358 D B A B C 学生15 356 A B C B B 表（）：研究生复试专家面试评分表 编号：专家2 复试 学生 笔试 成绩 专家对学生专长的面试评分 灵活性 创造性 知识面 表达力 外语 学生1 416 B A A B A 学生2 410 A B A C B 学生3 405 B A A C B 学生4 397 A B D B C 学生5 392 B A B C B 学生6 389 B D A B C 学生7 385 A B C B D 学生8 382 B A A C B 学生9 380 B B A B B 学生10 378 D B A C C 学生11 377 B C B A B 学生12 372 A B B A A 学生13 360 B A B C B 学生14 358 B B A A A 学生15 356 A B C B B 表（）：研究生复试专家面试评分表 编号：专家3 复试 学生 笔试 成绩 专家对学生专长的面试评分 灵活性 创造性 知识面 表达力 外语 学生1 416 A B B B B 学生2 410 A B A B A 学生3 405 B A D C B 学生4 397 A C B B B 学生5 392 B A B C B 学生6 389 A D A B A 学生7 385 A B C B B 学生8 382 B B A C B 学生9 380 A B C B B 学生10 378 C B A C D 学生11 377 D B B A B 学生12 372 A B B C B 学生13 360 B D C A C 学生14 358 D C A B C 学生15 356 A B B B A 表（）：研究生复试专家面试评分表 编号：专家4 复试 学生 笔试 成绩 专家对学生专长的面试评分 灵活性 创造性 知识面 表达力 外语 学生1 416 A B B B A 学生2 410 A B A B A 学生3 405 B A B B B 学生4 397 B B B B B 学生5 392 B B C B B 学生6 389 B C C B C 学生7 385 A C B D C 学生8 382 B B A C B 学生9 380 A C A B B 学生10 378 C A B B D 学生11 377 D B C B C 学生12 372 A B B B B 学生13 360 A B B A A 学生14 358 B B A B B 学生15 356 A C B B B 表（）：研究生复试专家面试评分表 编号：专家5 复试 学生 笔试 成绩 专家对学生专长的面试评分 灵活性 创造性 知识面 表达力 外语 学生1 416 A B A A A 学生2 410 B B A B A 学生3 405 B A B B B 学生4 397 B B B C B 学生5 392 A B B B A 学生6 389 C A B B C 学生7 385 A C B D C 学生8 382 B B A B A 学生9 380 B C A B B 学生10 378 B C A B D 学生11 377 C C B A C 学生12 372 A B B A B 学生13 360 A B B C D 学生14 358 B C B C C 学生15 356 A B B B B 表（）：研究生复试专家面试评分表 编号：专家6 复试 学生 笔试 成绩 专家对学生专长的面试评分 灵活性 创造性 知识面 表达力 外语 学生1 416 A B B B B 学生2 410 A B A B A 学生3 405 A B B B B 学生4 397 B A C D C 学生5 392 A A B B A 学生6 389 B C A B B 学生7 385 B A B C D 学生8 382 C B A B B 学生9 380 B C B B C 学生10 378 C A B C D 学生11 377 C B B A B 学生12 372 B B B B B 学生13 360 B B C B B 学生14 358 A C A B B 学生15 356 B B C A B 表（）：研究生复试专家面试评分表