04年研究生图论题目

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题：实用下料问题

 “下料问题(cutting stock problem)”是把相同形状的一些原材料分割加工成若干个不同规格大小的零件的问题，此类问题在工程技术和工业生产中有着重要和广泛的应用. 这里的“实用下料问题”则是在某企业的实际条件限制下的单一材料的下料问题。

 现考虑单一原材料下料问题. 设这种原材料呈长方形，长度为 ,宽度为 ，现在需要将一批这种长方形原料分割成 种规格的零件, 所有零件的厚度均与原材料一致，但长度和宽度分别为 ，其中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． 建立二维单一原材料实用下料问题的数学模型, 并用此模型求解下列问题.制定出在企

本文来源：https://www.bwwdw.com/article/3dot.html