Algorithm 版 (精华区)
发信人: sino (茶水博士), 信区: Algorithm
标 题: 2000建模竞赛试题
发信站: 哈工大紫丁香 (2000年09月28日13:13:47 星期四), 站内信件
2000网易杯全国大学生数学建模竞赛题目
A题 DNA序列分类
2000年6月，人类基因组计划中DNA全序列草图完成，预计2001年可以完成精确的全序列
图，此后人类将拥有一本记录着自身生老病死及遗传进化的全部信息的"天书"。这本大
自然写成的"天书"是由4个字符A，T，C，G按一定顺序排成的长约30亿的序列，其中没有
"断句"也没有标点符号，除了这4个字符表示4种碱基以外，人们对它包含的"内容"知之
甚少，难以读懂。破译这部世界上最巨量信息的"天书"是二十一世纪最重要的任务之一
。在这个目标中，研究DNA全序列具有什么结构，由这4个字符排成的看似随机的序列中
隐藏着什么规律，又是解读这部天书的基础，是生物信息学（Bioinformatics）最重要
的课题之一。
虽然人类对这部"天书"知之甚少，但也发现了DNA序列中的一些规律性和结构。例如，在
全序列中有一些是用于编码蛋白质的序列片段，即由这4个字符组成的64种不同的3字符
串，其中大多数用于编码构成蛋白质的20种氨基酸。又例如，在不用于编码蛋白质的序
列片段中，A和T的含量特别多些，于是以某些碱基特别丰富作为特征去研究DNA序列的结
构也取得了一些结果。此外，利用统计的方法还发现序列的某些片段之间具有相关性，
等等。这些发现让人们相信，DNA序列中存在着局部的和全局性的结构，充分发掘序列的
结构对理解DNA全序列是十分有意义的。目前在这项研究中最普通的思想是省略序列的某
些细节，突出特征，然后将其表示成适当的数学对象。这种被称为粗粒化和模型化的方
法往往有助于研究规律性和结构。
作为研究DNA序列的结构的尝试，提出以下对序列集合进行分类的问题：
1）下面有20个已知类别的人工制造的序列（见反面），其中序列标号1-10 为A类，
11-20为B类。请从中提取特征，构造分类方法，并用这些已知类别的序列，衡量你的方
法是否足够好。然后用你认为满意的方法，对另外20个未标明类别的人工序列（标号21
-40）进行分类，把结果用序号（按从小到大的顺序）标明它们的类别（无法分类的不写
入）：
A类 ； B类 。
请详细描述你的方法，给出计算程序。如果你部分地使用了现成的分类方法，也要
将方法名称准确注明。
这40个序列也放在如下地址的网页上，用数据文件Art-model-data 标识，供下载：
网易网址：www.163.com 教育频道 在线试题；
教育网： www.cbi.pku.edu.cn News mcm2000
教育网： www.csiam.edu.cn/mcm
2）在同样网址的数据文件Nat-model-data 中给出了182个自然DNA序列，它们都较长。
用你的分类方法对它们进行分类，像1）一样地给出分类结果。
提示：衡量分类方法优劣的标准是分类的正确率，构造分类方法有许多途径，例如提取
序列的某些特征，给出它们的数学表示：几何空间或向量空间的元素等，然后再选择或
构造适合这种数学表示的分类方法；又例如构造概率统计模型，然后用统计方法分类等
。
Art-model-data
1.aggcacggaaaaacgggaataacggaggaggacttggcacggcattacacggaggacgaggtaaaggaggcttg
tctacggccggaagtgaagggggatatgaccgcttgg
2.cggaggacaaacgggatggcggtattggaggtggcggactgttcggggaattattcggtttaaacgggacaagg
aaggcggctggaacaaccggacggtggcagcaaagga
3.gggacggatacggattctggccacggacggaaaggaggacacggcggacatacacggcggcaacggacggaacg
gaggaaggagggcggcaatcggtacggaggcggcgga
4.atggataacggaaacaaaccagacaaacttcggtagaaatacagaagcttagatgcatatgttttttaaataaa
atttgtattattatggtatcataaaaaaaggttgcga
5.cggctggcggacaacggactggcggattccaaaaacggaggaggcggacggaggctacaccaccgtttcggcgg
aaaggcggagggctggcaggaggctcattacggggag
6.atggaaaattttcggaaaggcggcaggcaggaggcaaaggcggaaaggaaggaaacggcggatatttcggaagt
ggatattaggagggcggaataaaggaacggcggcaca
7.atgggattattgaatggcggaggaagatccggaataaaatatggcggaaagaacttgttttcggaaatggaaaa
aggactaggaatcggcggcaggaaggatatggaggcg
8.atggccgatcggcttaggctggaaggaacaaataggcggaattaaggaaggcgttctcgcttttcgacaaggag
gcggaccataggaggcggattaggaacggttatgagg
9.atggcggaaaaaggaaatgtttggcatcggcgggctccggcaactggaggttcggccatggaggcgaaaatcgt
gggcggcggcagcgctggccggagtttgaggagcgcg
10.tggccgcggaggggcccgtcgggcgcggatttctacaagggcttcctgttaaggaggtggcatccaggcgtcg
cacgctcggcgcggcaggaggcacgcgggaaaaaacg
11.gttagatttaacgttttttatggaatttatggaattataaatttaaaaatttatattttttaggtaagtaatc
caacgtttttattactttttaaaattaaatatttatt
12.gtttaattactttatcatttaatttaggttttaattttaaatttaatttaggtaagatgaatttggttttttt
taaggtagttatttaattatcgttaaggaaagttaaa
13.gtattacaggcagaccttatttaggttattattattatttggattttttttttttttttttttaagttaaccg
aattattttctttaaagacgttacttaatgtcaatgc
14.gttagtcttttttagattaaattattagattatgcagtttttttacataagaaaatttttttttcggagttca
tattctaatctgtctttattaaatcttagagatatta
15.gtattatatttttttatttttattattttagaatataatttgaggtatgtgtttaaaaaaaattttttttttt
ttttttttttttttttttttaaaatttataaatttaa
16.gttatttttaaatttaattttaattttaaaatacaaaatttttactttctaaaattggtctctggatcgataa
tgtaaacttattgaatctatagaattacattattgat
17.gtatgtctatttcacggaagaatgcaccactatatgatttgaaattatctatggctaaaaaccctcagtaaaa
tcaatccctaaacccttaaaaaacggcggcctatccc
18.gttaattatttattccttacgggcaattaattatttattacggttttatttacaattttttttttttgtccta
tagagaaattacttacaaaacgttattttacatactt
19.gttacattatttattattatccgttatcgataattttttacctcttttttcgctgagtttttattcttacttt
ttttcttctttatataggatctcatttaatatcttaa
20.gtatttaactctctttactttttttttcactctctacattttcatcttctaaaactgtttgatttaaactttt
gtttctttaaggattttttttacttatcctctgttat
21.tttagctcagtccagctagctagtttacaatttcgacaccagtttcgcaccatcttaaatttcgatccgtacc
gtaatttagcttagatttggatttaaaggatttagattga
22.tttagtacagtagctcagtccaagaacgatgtttaccgtaacgtqacgtaccgtacgctaccgttaccggatt
ccggaaagccgattaaggaccgatcgaaaggg
23.cgggcggatttaggccgacggggacccgggattcgggacccgaggaaattcccggattaaggtttagcttccc
gggatttagggcccggatggctgggaccc24.tttagctagctactttagctatttttagtagctagccagccttt
aaggctagctttagctagcattgttctttattgggacccaagttcgacttttacgatttagttttgaccgt
25.gaccaaaggtgggctttagggacccgatgctttagtcgcagctggaccagttccccagggtattaggcaaaag
ctgacgggcaattgcaatttaggcttaggcca
26.gatttactttagcatttttagctgacgttagcaagcattagctttagccaatttcgcatttgccagtttcgca
gctcagttttaacgcgggatctttagcttcaagctttttac
27.ggattcggatttacccggggattggcggaacgggacctttaggtcgggacccattaggagtaaatgccaaagg
acgctggtttagccagtccgttaaggcttag
28.tccttagatttcagttactatatttgacttacagtctttgagatttcccttacgattttgacttaaaatttag
acgttagggcttatcagttatggattaatttagcttattttcga
29.ggccaattccggtaggaaggtgatggcccgggggttcccgggaggatttaggctgacgggccggccatttcgg
tttagggagggccgggacgcgttagggc30.cgctaagcagctcaagctcagtcagtcacgtttgccaagtcagta
atttgccaaagttaaccgttagctgacgctgaacgctaaacagtattagctgatgactcgta
31.ttaaggacttaggctttagcagttactttagtttagttccaagctacgtttacgggaccagatgctagctagc
aatttattatccgtattaggcttaccgtaggtttagcgt32.gctaccgggcagtctttaacgtagctaccgttta
gtttgggcccagccttgcggtgtttcggattaaattcgttgtcagtcgctctrtgggtttagtcattcccaaaagg
33.cagttagctgaatcgtttagccatttgacgtaaacatgattttacgtacgtaaattttagccctgacgtttag
ctaggaatttatgctgacgtagcgatcgactttagcac
34.cggttagggcaaaggttggatttcgacccagggggaaagcccgggacccgaacccagggctttagcgtaggct
gacgctaggcttaggttggaacccggaaa
35.gcggaagggcgtaggtttgggatgcttagccgtaggctagctttcgacacgatcgattcgcaccacaggataa
aagttaagggaccggtaagtcgcggtagcc
36.ctagctacgaacgctttaggcgcccccgggagtagtcgttaccgttagtatagcagtcgcagtcgcaattcgc
aaaagtccccagctttagccccagagtcgacg
37.gggatgctgacgctggttagctttaggcttagcgtagctttagggccccagtctgcaggaaatgcccaaagga
ggcccaccgggtagatgccasagtgcaccgt
38.aacttttagggcatttccagttttacgggttattttcccagttaaactttgcaccattttacgtgttacgatt
tacgtataatttgaccttattttggacactttagtttgggttac
39.ttagggccaagtcccgaggcaaggaattctgatccaagtccaatcacgtacagtccaagtcaccgtttgcagc
taccgtttaccgtacgttgcaagtcaaatccat
40.ccattagggtttatttacctgtttattttttcccgagaccttaggtttaccgtactttttaacggtttacctt
tgaaatttttggactagcttaccctggatttaacggccagttt
B题 钢管订购和运输
要铺设一条 的输送天然气的主管道, 如图一所示(见反面)。经筛选后可以生产这种主
管道钢管的钢厂有 。图中粗线表示铁路，单细线表示公路，双细线表示要铺设的管道(
假设沿管道或者原来有公路，或者建有施工公路)，圆圈表示火车站，每段铁路、公路和
管道旁的阿拉伯数字表示里程(单位km)。
为方便计，1km主管道钢管称为1单位钢管。
一个钢厂如果承担制造这种钢管，至少需要生产500个单位。钢厂 在指定期限内能生产
该钢管的最大数量为 个单位，钢管出厂销价1单位钢管为 万元，如下表：
1 2 3 4 5 6 7
800 800 1000 2000 2000 2000 3000
160 155 155 160 155 150 160
1单位钢管的铁路运价如下表：
里程(km) ≤300 301～350 351～400 401～450 451～500
运价(万元) 20 23 26 29 32
里程(km) 501～600 601～700 701～800 801～900 901～1000
运价(万元) 37 44 50 55 60
1000km以上每增加1至100km运价增加5万元。
公路运输费用为1单位钢管每公里0.1万元（不足整公里部分按整公里计算）。
钢管可由铁路、公路运往铺设地点（不只是运到点 ，而是管道全线）。
（1）请制定一个主管道钢管的订购和运输计划，使总费用最小（给出总费用)。
（2）请就（1）的模型分析：哪个钢厂钢管的销价的变化对购运计划和总费用影响最大
，哪个钢厂钢管的产量的上限的变化对购运计划和总费用的影响最大，并给出相应的数
字结果。
（3）如果要铺设的管道不是一条线，而是一个树形图，铁路、公路和管道构成网络，请
就这种更一般的情形给出一种解决办法，并对图二按（1）的要求给出模型和结果。
2000网易杯全国大学生数学建模竞赛题目(大专组)
C题 飞越北极
今年6月，扬子晚报发布消息："中美航线下月可飞越北极，北京至底特律可节省4小
时"，摘要如下：
7月1日起，加拿大和俄罗斯将允许民航班机飞越北极，此改变可大幅度缩短北美与
亚洲间的飞行时间，旅客可直接从休斯敦，丹佛及明尼阿波利斯直飞北京等地。据加拿
大空中交通管制局估计，如飞越北极，底特律至北京的飞行时间可节省4个小时。由于不
需中途降落加油，实际节省的时间不止此数。
假设：飞机飞行高度约为10公里，飞行速度约为每小时980公里；从北京至底特律原来的
航线飞经以下10处：
A1 (北纬31度，东经122度)； A2 (北纬36度，东经140度)；
A3 (北纬 53度，西经165度)； A4 (北纬62度，西经150度);
A5 (北纬 59度，西经140度)； A6 (北纬 55度，西经135度)；
A7 (北纬 50度，西经130度)； A8 (北纬 47度，西经125度)；
A8 (北纬 47度，西经122度)； A10 (北纬 42度，西经87度)。
请对"北京至底特律的飞行时间可节省4小时"从数学上作出一个合理的解释，分两种情况
讨论：
（1） 设地球是半径为6371千米的球体；
（2） 设地球是一旋转椭球体，赤道半径为6378千米，子午线短半轴为6357千米。
D题 空洞探测
山体、隧洞、坝体等的某些内部结构可用弹性波测量来确定。一个简化问题可描述
为，一块均匀介质构成的矩形平板内有一些充满空气的空洞，在平板的两个邻边分别等
距地设置若干波源，在它们的对边对等地安放同样多的接收器，记录弹性波由每个波源
到达对边上每个接收器的时间，根据弹性波在介质中和在空气中不同的传播速度，来确
定板内空洞的位置。现考察如下的具体问题：
一块240（米）×240（米）的平板（如图），在 AB边等距地设置7个波源Pi (i=1,…,7
)，CD边对等地安放7个接收器Qj (j=1,…,7)，记录由Pi发出的弹性波到达Qj的时间tij
(秒); 在 AD边等距地设置7个波源Ri (i=1,…,7)，BC边对等地安放7个接收器Sj (j=1,
…,7)，记录由Ri发出的弹性波到达Sj的时间τij (秒)。已知弹性波在介质和空气中的
传播速度分别为2880（米/秒）和320（米/秒），且弹性波沿板边缘的传播速度与在介质
中的传播速度相同。
1）确定该平板内空洞的位置。
2）只根据由Pi发出的弹性波到达Qj的时间tij(i,j=1,…,7)，能确定空洞的位置吗
；讨论在同样能够确定空洞位置的前提下，减少波源和接受器的方法。
tij Q1 Q2 Q3 Q4 Q5 Q6 Q7
P1 0.0611 0.0895 0.1996 0.2032 0.4181 0.4923 0.5646
P2 0.0989 0.0592 0.4413 0.4318 0.4770 0.5242 0.3805
P3 0.3052 0.4131 0.0598 0.4153 0.4156 0.3563 0.1919
P4 0.3221 0.4453 0.4040 0.0738 0.1789 0.0740 0.2122
P5 0.3490 0.4529 0.2263 0.1917 0.0839 0.1768 0.1810
P6 0.3807 0.3177 0.2364 0.3064 0.2217 0.0939 0.1031
P7 0.4311 0.3397 0.3566 0.1954 0.0760 0.0688 0.1042
τij S1 S2 S3 S4 S5 S6 S7
R1 0.0645 0.0602 0.0813 0.3516 0.3867 0.4314 0.5721
R2 0.0753 0.0700 0.2852 0.4341 0.3491 0.4800 0.4980
R3 0.3456 0.3205 0.0974 0.4093 0.4240 0.4540 0.3112
R4 0.3655 0.3289 0.4247 0.1007 0.3249 0.2134 0.1017
R5 0.3165 0.2409 0.3214 0.3256 0.0904 0.1874 0.2130
R6 0.2749 0.3891 0.5895 0.3016 0.2058 0.0841 0.0706
R7 0.4434 0.4919 0.3904 0.0786 0.0709 0.0914 0.0583
--
撷取生活中每一朵清新的浪花,智慧的浪花..汇成音乐的海洋.
※ 来源:·哈工大紫丁香 bbs.hit.edu.cn·[FROM: 202.118.247.254]
Powered by KBS BBS 2.0 (http://dev.kcn.cn)
页面执行时间：3.308毫秒