2011山东科技大学数学建模竞赛

1、2012山东科技大学数学建模竞赛承 诺 书我们仔细阅读了山东科技大学数学建模竞赛说明。我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。我们知道，抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们将受到严肃处理。我们参赛选择的题号是（从A/B/C/D/E中选择一项填写）： D 我们的参赛报名号为： 2005 所属学

2、院（请填写完整的全名）： 理学院 参赛队员 (打印并签名) ：1. 孙旭 2. 宋宾宾 3. 柴利云 日期： 2011 年 5 月 5日142012山东科技大学数学建模竞赛编 号 专 用 页评阅记录（可供评阅人评阅时使用）：评阅人评分备注最终成绩：打孔机生产效能的提高摘要 过孔是印刷线路板（也称为印刷电路板）的重要组成部分之一，本问题旨在提高某类打孔机的生产效能。打孔机的生产效能主要取决于以下几方面：（1）单个过孔的钻孔作业时间（2）打孔机在加工作业时，钻头的行进时间；（3）针对不同孔型加工作业时，刀具的转换时间。本文将求最少工作时间转化为最小总工作量，建立数学模型。一、问题重述：印刷电路板的

3、制板费用的30%到40%是用在过孔上，合理的过孔方案可以提高效率，节约成本。打孔机生产效能提高可从钻头行进时间、钻头转换时间考虑。钻头有8种刀具a，b，c， , h，依次排列呈圆环状，只能顺时针或者逆时针转换。题目给出了10种孔型所需加工刀具及加工次序，对于须用两种或两种以上刀具加工的过孔，只要保证所需刀具加工次序正确即可。问题一：附件1提供了某块印刷线路板过孔中心坐标的数据，单位是密尔（mil）（也称为毫英寸，1 inch=1000 mil），请给出单钻头作业的最优作业线路（包括刀具转换方案）、行进时间和作业成本。问题二：为提高打孔机效能，现在设计一种双钻头的打孔机（每个钻头的形状与单钻头相

4、同），两钻头可以同时作业，且作业是独立的，即可以两个钻头同时进行打孔，也可以一个钻头打孔，另一个钻头行进或转换刀具。为避免钻头间的触碰和干扰，在过孔加工的任何时刻必须保持两钻头间距不小于3cm（称为两钻头合作间距）。为使问题简化，可以将钻头看作质点。（1） 针对附件1的数据，给出双钻头作业时的最优作业线路、行进时间和作业成本，并与传统单钻头打孔机进行比较，其生产效能提高多少？（2） 研究打孔机的两钻头合作间距对作业路线和生产效能产生的影响。2、 问题分析：本题是一个求打孔机完成目标任务所需费用最小的多目标优化问题。打孔机的生产效能取决于单个过孔的钻孔作业时间、打孔机在加工作业时钻头的行进时间和

5、针对不同孔型加工作业时，刀具的转换时间。根据题意，打所有孔时间是不变的，提高打孔机的生产效能即要求打孔机钻头行进时间尽可能短，同时钻头转换次数尽量少。而打孔机钻头行进时间与行进路程有关，即转换为求最短路径的问题。第一问中最优路线是打孔机钻头行进最短距离与钻头转换次数最少结合的多目标优化问题。将题目所给各孔型坐标导入MATLAB，绘制出了所有孔的分布图。再根据分布规律建立模型求出打孔机钻头行进最短距离和路线。然后考虑刀具转换次数最少的情况，由题意，可以用一种刀具把需要打的孔全部打完再换刀，建立模型得到此情况下的最优转换顺序。最后列出两个目标的目标函数和约束条件，用LINGO求解，得到最优解，进而

6、找到单钻头作业的最优作业线路（包括刀具转换方案）、行进时间和作业成本。第二问三、模型假设1、假定对于同一孔型钻孔作业时间都是相同的，作业时间不影响问题的分析，则求解时只分析钻头行进最短距离与钻头转换次数。2、假定打孔机连续工作，行进期间无停留时间。3、假定打孔机钻头行进时只在任意两点间做直线运动。4、四、符号说明Pi 第i个垃圾中转站(i=1,238)P(xi，yi) 第i个垃圾中转站的坐标Qi 第i个垃圾中转站的垃圾量 t（吨）M 大型垃圾中心的个数P(xlj,ylj) 大型垃圾中心坐标(j=1,2M )N 小型垃圾中心的个数P(xsk,ysk) 小型垃圾中心坐标(k=1,2N )Silj

7、第i个垃圾中转站到大型垃圾中心的路程 百公里Sisk 第i个垃圾中转站到小型垃圾中心的路程 百公里Ol 大型拖车的均吨公里耗油量 L百公里Os 小型收集车的均吨公里耗油量 L百公里a 大型拖车的数量 辆b 小型收集车的数量 辆Zab 拖车总运输费用 元Za 大型拖车的运费 元Zb 小型收集车的运费 元Zm 大型垃圾中心的费用 元Zn 小型垃圾中心的费用 元 Z 垃圾处理总费用 元m 垃圾总质量 吨mi i站垃圾的质量 吨v 大型拖车的行驶速度 公里时ni 拖车每天去i站的次数 次r 大型设备的使用年限 年五、模型建立5.1 问题一5.1.1打孔机行进最短路程此种情况单考虑打孔机钻头行进完所有点

8、的最短路程，不考虑刀具转换次数，即打孔机行进到哪点即打完这点。打孔机所要打的全部孔的相对位置和孔型见图1。图1 （二）名词定义：定点距离最小法：在某片区域中，若存在c个点，两点间路程可用x+y表示时，有以下结论：当c为奇数时，在x轴上，在第（c+1）/2个点处，到各点的距离和最小；同理在y轴上，在第（c+1）/2个点处，到各点的距离和最小。当c为偶数时，在x轴上，在第c/2c/2+1区域处，到各点的距离和最小；同理在y轴上，在第c/2c/2+1区域处，到各点的距离和最小。证明：已知A,B,C三点，求在x上取一点p使得p点到三点的距离和最小。从图上可知，当P点位于A点与C点之间，则AP+PC=A

9、C为固定最小距离。BP取最小值0时，AP+PC+BP最小，即P点位于B点（第（c+1）/2个点）时, p点到三点的距离和最小。根据之前的分析，P应位于A，C点之间，进一步应在B，E之间，进一步，接近于D点。当已知点的数量c变大，P点要进一步缩小范围取c值较大时，即可推断出一下结论：当c为偶数时，P位于中间两点之间的任意位置是等效的。当c为奇数时，P应位于第（c+1）/2个点处。同理，在y轴上，也可以确定出所求目标的y轴坐标。由所给信息新型垃圾转运站垃圾转运量等情况统计表得知：每日经转运站需要运送到垃圾处理中心的垃圾数量为804吨。一个大型厨余垃圾处理设备的运行能力为200吨/日。厨余垃圾占总垃

10、圾数量的40%，即一个垃圾处理中心每日容纳垃圾总量最多为500吨。因此，至少需要两个大型厨余垃圾处理设备。不配置小型厨余垃圾处理设备处理设备，证明如下：证明：假设离大型处理设备较远的一个中转站Pi ，它到垃圾中心的距离为Si=5公里，垃圾数为5吨，用大型设备拖车要运一次，考虑到可能会浪费（拖车每次运10吨），用小型设备要5/0.2=25个，每天每台机器费用280000/(10*365)=76元，设能用10年，则每天处理5吨的费用为Zmi=（76+200*0.2）*25=2900元。若用大型设备，费用为Zni=运费+机器每天成本+处理成本运费Zai=(5/100)*25*7.51*5=47元机器

11、每天成本+处理成本=(48000000/(365*10)/200+150)*5=1078元Zni=47+1078=1025元2900元，故不用小型设备。证毕。因此，设置两个大型处理设备，设置的两个垃圾处理中心，应符合以下条件。要求：每个区域中垃圾总量不得多于500吨。垃圾处理中心的选址应符合环境要求，不得位于市中心或小区内，不得在水资源附近。交通便利，周围有交通路线，便于穿梭于各小区之间。车辆在各转运站到垃圾处理中心运行的总路程，应取得较小路程。司机个数的确定：a=总路程/（工作时间*速度）（三）垃圾处理中心位置的确定：确定保证总路程最小的位置P(xlj,ylj) 所分割的两区域如图所示 域一

12、 含有的点为11,31,32,33,34, 5,25,38,3,4,19,26,37,7,13,29,20,8,28, 35,40,这些点运到垃圾中心1 ，坐标为P(xl1,yl1) 。各个转运站运输次数为 i点可以看做有i个坐标相同的点，总的点数为=33（i=11,31,32,33,34,5,25,38,3,4,19,26,37,7,13,29,20,8,28,35,40，）将这个点的横坐标xi，纵坐标yi列出后通过“定点距离最小法”求得垃圾中心1的坐标为。其中横坐标为第/2+1=16个点即地图上第6个中转站的横坐标，纵坐标为第26个点的纵坐标。同理求出垃圾中心2的坐标。利用MATLAB对南

13、山地图进行取点，得到各回收站的坐标，再对这些坐标进行绘图，画出点阵图。MATLAB程序如下：a=imread(nanshan.jpg)；imshow(a)xy=ginput得出各转运站的坐标。（表1）初步划分后，两个垃圾中心的各转运站数据如下表所示： （比例尺100:3公里）垃圾中心1垃圾中心2转运站iXY转运站iXY3307.5286520.3856223208.4387157.055934310.5313494.862433698.8392164.562745197.9292590.9496124212.9428178.074937178.4114434.8079110137.874725

14、7.647138230.9591404.7807122167.9019277.1649211236.9646643.497316196.4278277.1649213310.5313424.2984221256.4823289.1757219263.9891503.8706214166.4005293.6798220266.9918406.282330185.9183301.1866325412.624527.8924116321.0409316.2003326282.0054490.3583215167.9019319.203228333.0518359.7398318238.4659325

15、.2084229355.5722418.292929157.3924335.718331282.0054657.0095135411.1226338.7207732242.97620.9768127283.5068347.7289433357.0736602.960531170.9046352.233234456.1635532.3965117140.8774361.2411237265.4905452.824322218.9482368.748338417.1281515.8815112146.8828371.75074将这个点的横坐标xi，纵坐标yi列出后通过“定点距离最小法”求得垃圾中心

16、1的坐标为（307.5286,490.3583）。其中横坐标为第/2+1=16个点即地图上第6中转站的横坐标，纵坐标为第26个点的纵坐标。同理求出垃圾中心2的坐标（196.4278,319.203）Matlab程序：x=282.0054 236.9646 242.97 197.9292 357.0736 307.5286 412.624 456.1635 417.1281 263.9891 282.0054 310.5313 265.4905 178.4114 230.9591 266.9918 310.5313 355.5722 146.8828 140.8774 170.9046 157.

17、3924 218.9482 283.5068 333.0518 411.1226 238.4659 321.0409 408.1199 185.9183 166.4005 167.9019 196.4278 256.4823 137.8747 212.9428 208.4387 98.8392 44.7902 167.9019;y=657.0095 643.4973 620.9768 590.9496 602.9605 520.3856 527.8924 532.3965 515.8815 503.8706 490.3583 494.8624 452.8243 434.8079 404.780

18、7 406.282 424.2984 418.2929 371.7507 361.2411 352.233 335.718 368.748 347.7289 359.7398 338.7207 325.2084 316.2003 310.1948 301.1866 293.6798 277.1649 277.1649 289.1757 257.6471 178.0749 157.0559 164.5627 163.0613 319.2030;plot(x,y,*k);hold;a=307.5286 196.4278;b=490.3583 319.203;plot(a,b,ok);垃圾处理中心（

19、图中“”）计算位置图 优化后垃圾处理中心的位置图根据地理位置，对两个点选址进行修正。按要求，垃圾处理中心应远离小区，附近无水资源，交通便利。在已求出的两点附近分别找到最合适点，求出其坐标（重复找坐标的程序）：P1（305.5 ,443.75） 留仙大道南沙河西路东的红花岭林地P2（233.5 ,268.25） 学府路与科园路交汇处东北空地 垃圾处理中心1 垃圾处理中心2找出两个垃圾处理中心的中垂线，定位处理中心管理范围的交界线。运送至垃圾处理中心1的转运站有（每个序号对应一转运站）：3,4,5,7,8,11,13,19,20,25,26,28,29,31,32,33,34,35,37,38运送

20、至垃圾处理中心2的转运站有：1,2,6,9,10,12,14,15,16,17,18,21,22,23,24,27,30,36。（四）验证：计算各垃圾处理中心所收集的垃圾总重量：Q1=356吨Q2=448吨在垃圾处理中心的处理容量范围（500吨）之内。计算两区域大型拖车总路程：通过分析地图发现，拖车所走路线几乎都为如图水平竖直折现，故拖车在两点间所走的路程可表示为 =x+y 其中 x为两点间水平距离，y为两点间竖直距离。往返垃圾中心1的拖车总路程S1=2=2=2往返垃圾中心2的拖车总路程S2=2=2=2S1=11000.7828S2=17177.4548S=S1+S2=28178.2376每日

21、耗油总费用ZS=S*（3/100）*0.25L/km*7.51元/L=1587元设备每日运行费用Zd=150元/吨*804吨*0.4=48240元设备每日折损费用Zb=4.5*107/(r年*365)*2若r取10年，Zb= 24657元 Z=ZS+Zd+Zb=74484元一个大型设备的每日折损费用为12329元，远大于耗油费用。说明，若以增加大型设备的量来减少耗油总费用是不可取的，假设中设立两个大型垃圾处理设备是比较合适的。（五）结论：在现有转运站规模与位置不变的条件下，选用两个大型设备，分别分布在上图中所示位置，即留仙大道南沙河西路东的红花岭林地（1）、学府路与科园路交汇处东北空地（2）。

22、运送至垃圾处理中心1的转运站有：动物园站，平山村站，牛城村站，同乐村站，松坪山（二）站，阳光(白芒关外)站，光前站，官龙村站，松坪山站，福光站，新围村站，沙河市场站，龙井，麻勘站，白芒站，大石磡站，长源村站，华侨城站。运送至垃圾处理中心2的转运站有：九街站，玉泉站，科技园站，大新小学站，南山村站，月亮湾大道站，北头站，涌下村站，白石洲南站，前海公园站，深圳大学站，南光站，南园站，望海路站，花果路站，大冲站，南山市场，疏港小区站，西丽路站，塘朗站。问题二：（一）转运站重新设计规划经分析地图上的各转运站，分布有其合理性，但有很多分布欠妥，如在垃圾较少的地区分布较多，有些地区转运站分布较密，肯定给附

23、近小区运往转运站造成不便。于是经分析将部分不合理的转运站进行拆除、合并、新建，并调整转运站的大型厢配备，形成更合理的转运站分布。具体改变情况如图所示：25、34、38三个垃圾站合并为一个新的，记为P41（438.1471，524.8896），P12移动到P42（202.4332，385.2629），P14与P30合并到P30，P22与P21合并为P21，在（227.9564，229.1213）出新建P43。（二）确定垃圾处理中心的位置如第一步，先暂时将地图分为如图两部分，用“定点距离最小法”求出两垃圾中心的坐标。得出区域一的新垃圾中心的坐标为Pl1(282.0054,490.3583),区域二

24、的新垃圾中心的坐标为Pl2(212.9428,316.2003)。连接两点画出中垂线作为两区域的边界线，发现P42，P2，P27，P7，P8离垃圾中心二较近，应运往二，则对新的分布求垃圾中心。得到新的垃圾中心坐标Pl1(310.5313,494.8624)Pl2(208.4387,325.2084)经查看地图发现新的垃圾中心处理站和上题中确定的垃圾中心处理站地点大致相同，考虑到具体地形及选址要求最终确定垃圾中心处理站与上题结果一致。P1（305.5 ,443.75） 留仙大道南沙河西路东的红花岭林地P2（233.5 ,268.25） 学府路与科园路交汇处东北空地运送至垃圾处理中心1的转运站有：

25、28,20,29,13,37,26,4,19,3,41,5,33,32,11,31,运送至垃圾处理中心2的转运站有：36,10,17,9,15,1,7,30,6,42,23,24,2,43,8,18,21,27,16,35,（三）验证并矫正：计算各垃圾处理中心所收集的垃圾总重量：Q1=274吨Q2=530吨因Q2不在垃圾处理中心的处理容量范围（500吨）之内。故将在分界处的本属于垃圾站2的P8，P27划到垃圾中心站1。（由于该两点位于中垂线附近，故移动后对垃圾中心站几乎没有影响）Q1=319吨Q2=485吨其容量在垃圾处理中心处理的容量范围之内。运送至垃圾处理中心1的转运站有：28,20,29

26、,13,37,26,4,19,3,41,5,33,32,11,31,8,27,运送至垃圾处理中心2的转运站有：36,10,17,9,15,1,7,30,6,42,23,24,2,43,18,21,16,35,往返垃圾中心1的拖车总路程S1=2=2=2往返垃圾中心2的拖车总路程S2=2=2=2S1=8542.7522S2=12638.4684S=S1+S2=21181.2206每日耗油总费用ZS=S*（3/100）*0.25L/km*7.51元/L=1193.元设备每日运行费用Zd=150元/吨*804吨*0.4=48240元设备每日折损费用Zb=4.5*107/(r年*365)*2若r取10年

27、，Zb= 24657元Z=ZS+Zd+Zb=74090元（较1题中省394元）（四）结论： 经过对25、34、38三个垃圾站合并为一个新的，记为P41（438.1471，524.8896），P12移动到P42（202.4332，385.2629），P14与P30合并到P30，P22与P21合并为P21，在（227.9564，229.1213）出新建P43后，同题1中的过程，求解出两个垃圾处理中心的位置与其结果相同：选用两个大型设备，分别分布在上图中所示位置，即留仙大道南沙河西路东的红花岭林地（1）、学府路与科园路交汇处东北空地（2）。运送至垃圾处理中心1的转运站有：松坪山站,沙河市场站,龙井,

28、光前站,新围村站,西丽路站,动物园站,平山村站,官龙村站,牛城村站,大石磡站,41站,白芒站,麻勘站,阳光(白芒关外)站,松坪山（二）站,大冲站。运送至垃圾处理中心2的转运站有：南山村站,前海公园站,疏港小区站,九街站,大新小学站,涌下村站,科技园站,同乐村站,南山市场,望海路站,花果路站,玉泉站,42站,深圳大学站,南光站,43站,白石洲南站,华侨城站。6、 优化改进：1、司机个数优化开车走完总路程所需时间：S*（3/100）km/(40km/h)=21h假设司机每天开车和装运时间分别为3h和3h大型拖车需要的司机数量为a=21h/3h=7每日司机工资支出费用3500/30*a=817元假如

29、16辆大型拖车都用上，会多出9个司机的工资，共1050元/天。2、 小型设备用来处理大量垃圾很不合适，建议将小型设备安置在厨余垃圾产量较大的餐馆等场所。3、 各转运站的大型厢数量应根据垃圾产量合理分配。参考文献：1生活垃圾处理技术指南 住房和城乡建设部国家发展和改革委员会 2孙向军,冯蒂,吴冰思,等.上海市泔脚垃圾的处理及管理J.环境卫生工程,2002,10(3):130-132.3刘跃勇,任福民,汝宜红,等.北京市生活垃圾成分及理化特性分析J.北方交通大学学报,2002,26(4):50-52.附录：表1序号垃圾转运站名称厢数垃圾转运 量(吨/日)x坐标y坐标1九街站120170.9046352.2