2004 年浙江大学第二届数学建模竞赛题目
（A 题、B 题）
1. 各参赛队可在组委会公布的 A、B 两题中任选一题作答，在规定时间内完成
论文。论文应包括模型的假设、建立和求解、计算方法的设计和计算机实现、
结果的分析和检验、模型的改进等方面，并附主要程序代码。
2. 答卷用白色A4 纸。各参赛队需从 浙江大学数学建模实践基地 网站
http://www.css.zju.edu.cn/mmb上下载答卷封面，如实填写后作为封面与论文全文
装订成册， 于5月27日上午8： 00－11：00 期间交到以下地点之一（1）玉
泉校区教 11－406（2）紫金港校区紫云学园学生会（紫云学园 1-2 舍连廊
129 室）。
3. 论文中不能有任何可能显示答题人身份的标志。
4. 各参赛队应严格遵守竞赛规则，比赛开始后不得更换队员，不得与队外任何
人（包括在网上）讨论。
5. 引用别人的成果或其他公开的资料(包括网上 查到的资料) 必须按照规定的
参考文献的表述方式在正文引用处和参考文献中均明确列出。正文引用处用
方括号标示参考文献的编号，如[1][3]等；引用书籍还必须指出页码。参考
文献按正文中的引用次序列出，其中书籍的表述方式为：
[编号] 作者，书名，出版地：出版社，出版年。
参考文献中期刊杂志论文的表述方式为：
[编号] 作者，论文名，杂志名，卷期号：起止页码，出版年。
参考文献中网上资源的表述方式为：
[编号] 作者，资源标题，网址，访问时间（年月日）。
6. 请各参赛队妥善保管有关参赛资料（包括源程序等） ，以便答辩及异议期质
询所用。
A 题：DNA 限制性图谱的绘制
绘制 DNA 限制性图谱（ restriction mapping）是遗传生物学中的重要问题。由于 DNA
分子很长，目前的实验技术无法对其进行直接测量，所以生物学家们需要把 DNA 分子
切开，一段一段的来测量。在切开的过程中， DNA 片段在原先 DNA 分子上的排列顺序
丢失了，如何找回这些片段的排列顺序是一个关键问题。
为了构造一张限制性图谱，生物学家用不同的生化技术获得关于图谱的间接的信
息， 然后采用组合方法用这些数据重构图谱。一种方法是用限制性酶（ restriction enzyme）
来消化 DNA 分子。这些酶在限制性位点 (restriction sites)把 DNA 链切开，每种酶对应的
限制性位点不一样。对于每一种酶，每个 DNA 分子可能有多个限制性位点，此时可以
按照需要来选择切开某几个位点（不一定连续）。 DNA 分子被切开后，得到的每个片段
的长度就是重构这些片段的原始顺序的基本信息。在多种获取这种信息的实验方法中，
有一种广泛采用的方法：部分消化（ the partial digest, PDP）方法。
在 PDP 中，采用一种酶，通过实验得到任意两个限制性位点之间片段的长度。假
设与使用的酶对应的限制性位点有 n 个， 通过大量实验，可得到 n+2 个点（n 个位点
加上两个端点）中任意两点之间的距离，共 个值。然后用这 个距离来重构 n
个限制性位点的位置( 解不一定唯一，两个端点对应于最长的距离) 。若 是线段上的
点集 中所有点之间距离的集合，PDP 就是给定
2
2+n
C
2
2+n
C
ΔΧ
Χ ΔΧ求 Χ。下图给出了一个例子。
2 3 4 5 2
A a b c d B
图 1. A,B 是 DNA 分子的两个端点。 a ， b，c 和 d 是限制性位点。 通过实验可以
得到 ={2,3,4,5,2,5,9,14,16,7,12,14,9,11,7}. 再通过ΔΧ ΔΧ 来求 Χ ，对应于上图的
={0,2,5,9,14,16}是一种解。 Χ
上述方法要把 DNA 分子在任意的两个限制性位点处切开，这对于当前的实验技术
来说有相当难度，而且，还要对实验数据进行处理，也很复杂。最近研究人员提出了一
种新的方法，称为简化的部分消化方法（ SPDP）。这个方法与 PDP 的不同就在于它避免
了在任意两个位点切开 DNA 分子的难题和处理重复数据的困难。仍假设与使用的酶对
应的限制性位点有 n 个。首先 DNA 分子被复制成 n+1 份，前 n 个复制品中的每一个在
一个限制性位点处被切开，最后一个复制品在所有的限制性位点处被切开。这样我们分
别得到 2n 个片段长度（称为第一组数据）和 n+1 个片段长度（称为第二组数据） 。在没
有误差的前提下，第一组数据中 2n 个长度可以分成 n 对，每对的和都等于 DNA 分子的
总长度；第二组数据中 n+1 个长度的和也等于 DNA 分子的总长度。 SPDP 问题是如何
利用这两组数据重构出这 n+1 个片段在 DNA 分子上的排列，使得这个排列在 n 个位点
切开后得到的 2n 个片段长度与实验得到的 2n 个长度相等。下图给出了一个例子。
(a)
2 6 1 4 3
(b)
2 14
8 8
9 7
13 3
2 1 4 3 6
图 2. 这个例子对应的位点有 4 个。 (a) 就是我们希望重构的顺序。 (b) 中的前 4 对为 第一
组数据， 它通过切开一个位点得到，每对长度的和都是 16，剩下的为 第二组数据，含 5 个
片段长度，它通过切开所有位点得到，它们的长度总和也是 16， 但实验结果只告知每段的
长度，不知道它们在 DNA 分子上的排列顺序。
现对上述 SPDP 问题，建立数学模型，并研究以下问题：
（ 1） 设计求解该问题的算法， 并评估该算法的效率和效果。对下述 2 个实例给出答
案：
实例 1： 第一组数据：2 ， 14， 8， 8， 9， 7， 13， 3
第二组数据：2 ， 1， 4， 3， 6
实例 2: 第一组数据：1 ， 14， 12， 3， 7， 8， 9， 6， 11， 4， 12， 3， 13， 2， 5， 10
第二组数据：1 ， 1， 2， 1， 2， 2， 1， 2， 3
（2） 讨论在实验中测量片段长度时的误差，将在多大程度上影响算法的效果，当误
差到多大程度时，限制性图谱的重构将无法进行。
B 题：通讯卫星上的开关设置
考虑下述卫星通信中的优化设计问题。地面上有 n个接收站与 n个发送站，通讯卫星
上则设置了若干种开关模式。每个开关模式可用矩阵P =(p
ij
)来表示，若卫星可接收发送
站 i发出的信息并将信息传送回接收站 j时 ， 矩阵中的元素 p
ij
=1， 否则 p
ij
=0。 通讯卫星上
的接收发送任务也可以用一个矩阵T =（ t
ij
） 来表示，元素 t
ij
为信息由发送站i 到接收站 j
的传送时间长度。由于技术上的原因，当发送站 i与接收站j 传递信息时，它不能同时发
送信息给别的接收站；同样，当接收站j 在接收发送站 i的信息时，也不能同时接收其他
发送站发送的信息。你的任务是：
（ 1） 设计一组开关模式 ，k =1,…, r， r 应当尽可能小，使得对任意给定的任务
矩阵 T，卫星开关设置{ } 均能完成要求的发送接收任务。
k
P
k
P
（2 ） 设计一个算法，在发送接收任务 T给出后，可根据你设计的开关模式
（ k=1, … ,r） 求出 的使用时间 λ
k
P
k
P
k
， 使得在完成预定任务前提下各开关模
式使用的总时间最短。
（3 ） 由于技术上的原因，开关模式的总数 r 有一个上限。因此当需要传送的任务
数量较大时，可能仍无法分派任务。请你想一些办法来解决这一困难，例如
增加传送时间等。
