全国数学建模竞赛

5
图 1 运输车行走路线图 使得运输路程最短。对应的运输方案如下表2： 运输路线 ① ② ③ ④ ⑤ ⑥ ⑦ ⑧ ⑨ ⑩ 先后经过的垃圾 集中点
34-17-16-6 20-31-5-2 24-18-35-7 19-14-37-4 28-26-21-25-3 30-29-27 15-13-8 12-9-1 36-23-32-11 33-22-10
n辆车的运输总时间
运输车空载的总费用 运输车重载的总费用 运输车的总费用 铲车1的空载费用 铲车2的空载费用 铲车3的空载费用 全部铲车空载的总费用
5
5.1
模型的建立与求解
问题一
确定运输车路线算法,由于最远的垃圾集中点的运输时间不超过运输车每天平均工作 时间， 所以可以先不考虑时间的约束。从而建立如下算法： 首先确定重载起点：由于每个垃圾集中点的垃圾量及其坐标是不变，重载运输的费 用是不变的， 所以为了使总运输费用最少， 只要使空载的费用最少， 即尽量安排较远的垃 圾集中点在同一路线上， 从而确定重载起点Xn 然后确定运输车路线走向： 要求运输时走最短的路线， 以及运输费用最低， 而且由于 运输车的重载费用1.8元/吨是空载费用0.4 元/吨的4.5倍，为了使运输总费用W 最少,那只 能从最远的点（i = 1）开始运载垃圾， 下一个点编号为j + 1， 走一条路线， 向垃圾处理站 （坐标原点）方向运回。顺次经过的点遵循满足条件：
X ≥X ij ij +1 Y ≥Y
ij ij 百度文库1
即其横坐标以及纵坐标均不超过前一点的横、纵坐标，并且各点横、纵坐标递减进 行搭配， 由若干个点组成一条路线。 确定集中点数，根据每个垃圾集中点的垃圾量，每条路线上的垃圾总量不超过运输 车的最大运输量：
Ci ∑ j =1
Tij ≤ 6, i = 1, 2, · · · , L 4
编 号
专
用
页
赛区评阅编号（由赛区组委会评阅前进行编号） ：
全国统一编号（由赛区组委会送交全国前编号） ：
全国评阅编号（由全国组委会评阅前进行编号） ：
碎纸片的拼接复原
摘
要
本文对于垃圾运输问题的优化，通过运用图论的TSP问题的有关知识对题目给出的 坐标数据进行了处理，根据从最远点开始运载垃圾运输费用最低的原则，以及不走回路 的前提， 在条件时间约束下， 建立了运输车和铲车的调度优化模型， 得到运输车和铲车的 安排路线和时间，在垃圾运输问题上，安排了六辆运输车，三辆铲车的最少调动车辆数 目， 达到最少运输费用。 问题一包含着垃圾量和运输费用的累积计算问题，因此，文中以运输车所花费用最 少为目标函数， 以运输车载重量的大小、 当天必须将所有垃圾清理完等为约束条件， 以运 输车是否从一个垃圾站点到达另一个垃圾站点为决策变量，建立了使得运输费用最小的 单目标的非线性规划模型。 运用求解， 得出了最优的运输路线为10条， 此时运输所花费用 为2800.8元。 问题二，建立了以运行路径最短为目标的单目标非线性规划模型。从而求出了使铲 车费用最少的3条运行路线， 且各条路线的工作时间较均衡。 因此， 处理站需投入3台铲车 才能完成所有装载任务，且求得铲车所花费用为202.0元，三辆铲车的具体运行路线见文 中表4。文中，我们假定垃圾处理站的运输工作从晚21：00开始，根据各铲车的运输路线 和所花时间的大小， 将铲车和运输车相互配合进行工作的时间做出了详细的安排见表5。 问题三，要求给出当有载重量为4吨、6吨、8吨三种运输车时的最优的调度方案。基 于第一问中的模型， 修改载重量的约束条件， 用和分别求解， 得出两种调度方案， 但总的 运输费用不变，均为2800.8元；对于10条路径，分别需要4吨的运输车1 辆；6吨的运输车1 辆；8 吨的运输车6辆， 各运输车具体的运输线路见文中图2。 关键词：哈密顿图 TSP问题 垃圾集中点 重载起点 运输路线 LINGO优化
运输路程
58 42 68 54 88 92 56 40 84 64
运输所需 时间
2小时2分 1小
空载运输 费用
14.5 10.5 17.0 13.5 22.0 23.0 14.0 10.0 21.0 16.0
重载费用
175.6 144.2 303.2 215.4 371.5 418.6 225.3 156.6 402.8 228.4
根据上面算法,建立运输车费用优化模型:
min W1 = 0.4 ∗
L ∑
i=1 Xij ≥ Xij +1
Xi1
s.t.
Ci ∑ Tij ≤ 6
j =1
Yij ≥ Yij +1
, i = 1, 2, · · · , L
依据题目给出各垃圾集中点的坐标，用Excle的绘图功能绘点得到垃圾集中点坐标系，再 根据垃圾运输车路线算法， 由此可以把垃圾集中点划分为十条最优路线如图1所示：
2
2.1
问题分析
问题一的分析
这是一个碎纸片拼接复原的问题。由于19张纸片是来自同一页印刷文字文件的碎纸 机破碎纸片，它们都是规则的纵列长条状矩形。因此我们无法利用碎片的边缘性状，只 考虑纸片内容的识别。 图片文件的数据， 简单地说， 就是一个二维数组， 这个二维数组存 储着一张图片各个像素点的颜色索引值或颜色值（由于本体提供的是白底黑字下文我们 用灰度值来替换） ， 所以我们使用Matlab中的imread函数对19 张碎纸片的图像进行灰度分 析，然后得到每条纵切纸片的左右边缘灰度值向量。将某纸片一个边缘灰度值向量通过
2
循环和其他纸片边的距离度和相似度进行匹配。 筛选出距离度最小， 且相似度最大的两张 纸片拼接在一起作为一张新纸片， 再进入算法循环进行匹配筛选。 如果复原过程中出现距 离度最小且相似度最大的纸片并不是同一张时，需要通过人工干预找出距离度小相似度 大的几组中哪一组最合适。通过18 次匹配筛选可以得出一个图片编码次序，用Matlab中 的imshow可以得到原图片。英文的识别存在更大的难度， 因为英文字母间的相似度更大， 计算机的区分更加困难优先考虑距离度。
2013 江西师范大学大学生数学建模竞赛训练题3
承 诺
书
我们仔细阅读了中国大学生数学建模竞赛的竞赛规则。 我们完全明白， 在竞赛开始后参赛队员不能以任何方式 （包括电话、 电子邮件、 网上 咨询等）与队外的任何人（包括指导教师）研究、 讨论与赛题有关的问题。 我们知道， 抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他公开的资 料 （包括网上查到的资料） ， 必须按照规定的参考文献的表述方式在正文引用处和参考文 献中明确列出。 我们郑重承诺， 严格遵守竞赛规则， 以保证竞赛的公正、 公平性。 如有违反竞赛规则 的行为， 我们将受到严肃处理。 我们参赛的题目是：
B题
我们的参赛报名号为（如果赛区设置报名号的话） ： 所属学校（请填写完整的全名） ： 参赛队员（打印并签名） ： 1、 陶雨挺
2、 孙强 3、 聂文俊
江西师范大学
指导教师或指导教师组负责人（打印并签名） ： 吴根秀 日期： 年 月 日
赛区评阅编号（由赛区组委会评阅前进行编号） ：
2013 江西师范大学大学生数学建模竞赛训练题2
2.2
问题二的分析
对于碎纸机既纵切又横切的情形，首先是在基于原有第一问的基础上增加了纵向的 分析，因为上下边缘经常出现整白条为本问加大了难度.而且每张纸片被切得更细更小， 每张纸片的边缘像素锐减了11倍， 单张所含信息量变少， 而总信息量变大。 简单的套用第 一问的方法可能出现很大误差以至于各种不匹配的情况，所以如何自动化的读取209 张 图片的灰度值并成功正确的完成匹配成为首要难题，考虑到纸片与斜向纸片的上下匹配 问题我们可以获取更多的信息来缩小误差。第一步通过Matlab中imread函数的批量读取 图片数据功能自动读取209 张纸片的灰度值， 第二步通过Matlab筛选什么什么样的成为左 边第一张的纸片，通过灰度值判断每张碎片的行间距从而找出该片所在的横行，完成横 向的匹配拼接后再进行纵列匹配排序。当复原过程中出现距离度最小且相似度最大的纸 片并不是同一张时， 需要通过人工干预找出距离度小相似度大的几组中哪一组最合适。
1
1
问题的重述
破碎文件的拼接在司法物证复原、历史文献修复以及军事情报获取等领域都有着重 要的应用。传统上， 拼接复原工作需由人工完成， 准确率较高， 但效率很低。特别是当碎 片数量巨大， 人工拼接很难在短时间内完成任务。 随着计算机技术的发展， 人们试图开发 碎纸片的自动拼接技术， 以提高拼接复原效率。请讨论以下问题： 1. 对于给定的来自同一页印刷文字文件的碎纸机破碎纸片 （仅纵切） ， 建立碎纸片拼 接复原模型和算法， 并针对附件1、 附件2给出的中、 英文各一页文件的碎片数据进行拼接 复原。如果复原过程需要人工干预，请写出干预方式及干预的时间节点。复原结果以图 片形式及表格形式表达（见【结果表达格式说明】 ） 。 2. 对于碎纸机既纵切又横切的情形，请设计碎纸片拼接复原模型和算法，并针对附 件3、 附件4给出的中、 英文各一页文件的碎片数据进行拼接复原。 如果复原过程需要人工 干预， 请写出干预方式及干预的时间节点。复原结果表达要求同上。 3. 上述所给碎片数据均为单面打印文件，从现实情形出发，还可能有双面打印文件 的碎纸片拼接复原问题需要解决。 附件5给出的是一页英文印刷文字双面打印文件的碎片 数据。 请尝试设计相应的碎纸片拼接复原模型与算法， 并就附件5的碎片数据给出拼接复 原结果， 结果表达要求同上。 【数据文件说明】 (1) 每一附件为同一页纸的碎片数据。 (2) 附件1、 附件2为纵切碎片数据， 每页纸被切为19条碎片。 (3) 附件3、 附件4为纵横切碎片数据， 每页纸被切为11×19个碎片。 (4) 附件5为纵横切碎片数据， 每页纸被切为11×19个碎片， 每个碎片有正反两面。 该 附件中每一碎片对应两个文件，共有2×11×19个文件，例如，第一个碎片的两面分别对 应文件000a、 000b。 【结果表达格式说明】 复原图片放入附录中， 表格表达格式如下： (1) 附件1、 附件2的结果：将碎片序号按复原后顺序填入1×19的表格； (2) 附件3、 附件4的结果：将碎片序号按复原后顺序填入11×19的表格； (3) 附件5的结果： 将碎片序号按复原后顺序填入两个11×19的表格； (4) 不能确定复原位置的碎片， 可不填入上述表格， 单独列表。
说明 第k个垃圾集中点的垃圾量,k = 1, 2, · · · , 36 第k个垃圾集中点的横坐标， k = 1, 2, · · · , 36 第k个垃圾集中点的纵坐标， k = 1, 2, · · · , 36 垃圾运输路线总条数 第i条路线上垃圾集中点的个数， i = 1, 2, · · · , L 安排运输车的总数量 第i条路线上的第j 个垃圾集中点的横坐标， i = 1, 2, · · · , L, j = 1, 2, · · · , Ci 第i条路线上的第j 个垃圾集中点的垃圾量， i = 1, 2, · · · , L, j = 1, 2, · · · , Ci 第i条路线所需要的总时间
2.3
问题三的分析
对于第三问，相当于原有的一张纸片变成了两张，总信息量增大的同时，单张纸片 的信息量增加也为能充分利用这些信息的人提供了便利。我们在系统自动匹配筛选出最 高匹配度碎片的同时，立刻检验这两张碎片反面的边缘灰度值匹配结果，如果匹配度都 高， 就自动拼接， 如果反面匹配度低， 那说明出现误差， 系统再筛选次最高匹配度碎片以 此循环。可以在大幅度的减小误差达到很好的效果。
时46分
2小
时29分
2小
时06分
2小
时59分
3
模型假设
(1) 纸片内图像完好无损不会出现有切割后出现污渍的纸片； (2) 每个附件中纸片都来自同一张图， 没有调换的情况； (3) 样本图片所写的文章本身具有一定的逻辑性可以进行人工干预； (4) 样本图片内的文章已经过标准格式化的处理， 不会出现行间距不一致的情况。
3
4
符号说明
符号
Tk Xk Yk L Ci N Xij Tij hi Hn W1 W2 W Q1 Q2 Q3 Q