写好一篇数学建模论文的摘要.doc

写好一篇论文的摘要一篇成功的论文，论文摘要的撰写很重要，简洁性、高度概括性是论文摘要的特点，但它所要起到的效用却远在篇幅之外：1 你的摘要应告诉读者你的文章考虑了一个什么样的问题；2 你把它归结为一个什么样的数学模型；3 你主要采用了什么样的数学方法进行求解；4 你得到了哪些主要结果；5 特别就数学建模竞赛，赛题包括一些具体的算例、问题你可以列出你的答案；6 哪些结果你认为很得意，需要提请读者留意；存在哪些不足，给出可能的改进方向。下面就我讲过的“方体切割模型”尝试着给出它的摘要，你可给以批评：本文在假定六个侧面有着不同的切割费率更为一般的情形下，就方体切割问题建立了一个多阶段动态规划模型；在换刀费用 时，得到并论证了一个非常简明的优化准则：六面按照厚度费率比从大到小排序并依序切割总费用最省；就 没能给出类似 时的最优准则，但对后者一个自然的变形就可将时的最优准则解释为大者先切，作者给出了静态和动态两个准则（文中“准则1”、“准则2”），一并考虑“切割费用面小者先切”（文中“准则3”），就具体算例以指标验之，在随机取例1，000，000个，如前指标的平均值，“准则1”：0.03314、“准则2”：0.000102 、“准则3”：0.2012；（注：前面三个数字均信手粘来，具体作文须用本来数据，科学研究忌臆想）在几个中，“准则2”是相对最优的；本文也考虑了“待加工产品的预置位置可调整”，论证了产品尽可能“贴近”毛培的一个角时费用最少；就题目中的问题，我们给出了如下解答（略）不能准确地表达自己的想法，毋宁做一个哑巴！要尽可能做到每文必掷地有声，一大堆含糊不清的文字相当于什么也没做。12.2 方体切割建模问题（97全赛B） 截断切割 一 模型假设1） 贵重石材加工等的截断切割加工方式：是指将物体沿某个切割平面分成两部分；2）毛坏、成品均为长方体，且这两个长方体的对应面是平行的，如下图：毛坏的六面分别以、标识，为方便，也以面1、2、3、4、5、6分别表示面、；而、分别表示“成品”的贴近、的六面；3）毛坏的三组棱长：、分别表示到、到、到的距离；、分别表示到、到、到的距离；4）分别表示到、到、到、到、到、到的距离；显然应有、；5）分别表示在切割第侧面时的费率，依题意：，；6）：当用一把刀具连续切割相邻的两侧面时需额外付出的刀具调整费用，这里假定有两把刀具，一把水平放置，用于切割二面，一把竖直放置，用于切割四面；二 模型建立（只讨论的情形，时为思考题）本图为方体切割问题对应的多阶段动态规划决策（示意）图，各边之边权对应的切割费用，在图中未做标示1） 表示初态，即没有进行任何加工；2） 对应一个完整的加工策略事实上为的一个全排列；而的任一子集对应某个策略在对毛坯加工过程中某个中间状态；3） 在对毛坯加工过程中某个中间状态 ,它仅与在它之前截掉了那些面的组合有关,而与过程(即排列)无关；4） 的 个子集（由它们组成的集合记为构成方体切割的所有可能的状态（包括初始状态，终态）：l 以的64个子集构造有向图，以为起点，以为终点连边，且,使得；l 对有向图边赋权：任取有向图一边，不妨设其以为起点，以为终点，（或记为）表示在状态，截去面所需费用；l 这些集合按照其包含元素数目的多少可分为7组，从多到少排序，相邻两组间构成一个决策阶段；因此得如下“6”阶段动态规划问题：l 的表述：记分别表示方体的长、宽、高（这1面到2面、3到4、5到6的距离），可得：三 模型求解l 这是一个典型的动态规划模型，可以用动态规划问题的求解算法进行计算。定理（最优准则）：设，若策略满足：，则策略必为截断切割的最优策略。证明：某截断切割策略，若满足，且，即称构成策略的一逆序对（逆序数？）；（以下证明对任一策略，若策略中存在逆序对，则总可以构造某截断切割策略，其逆序数小于策略的逆序数，但总的切割费用不比策略的多） 设某截断切割策略的逆序数大于0，则必存在相邻的“两刀”构成策略的一逆序对，交换的次序，此时与比较，前者的逆序数比后者的减少“1”，而在下面证明前者的切割费用不比后者的多： 当面、相对时，仅仅交换相邻两刀的次序对切割费用没有影响；当面、相邻时，不妨设、：此时，与切割费用之差等于：其符号与相同，由假设，即的切割费用比的少。思考题1. 状态除了以未切割的面组成的集合表示,也可用一个六维0、1向量表示, 比方设,第面未切割。试以此数据形式刻画该模型；2. 的情形作者张剑95 电信侯哲95 计算徐绍军95 电信本文获成功参赛奖加工业中截断切割的优化设计一摘要本文讨论了加工业中 截断切割的优化排序策略我们对于不同的切割3. 方式总数用穷举法得到720 种所可行解及其费用并对于原问题建立了决策4. 模型基于全局静态和局部动态两个思路入手进行优化求解给出三种更实用5. 的算法并对所给出的算法进行了分析和检验6. 1.在简化的二维问题中,我们归纳出解决问题的简明法则,并将其类比到三7. 维空间,从而提出了将面间距统一成判断权重来作为排序准则的算法,同时证明8. 了e = 0 的情况下根据这种简明准则能够实现题目所要求的优化目标9. 2.对于e 0 时我们对算法1 的优化准则改进并结合动态规划思想提10. 出得到问题最优解的方法11. 3.然后我们又从组合优化方向出发采用了行之有效的模拟退火法12. 最后我们结合实际问题 将本问题进行了拓展讨论了当最终产品(成品)13. 在毛坯(待加工长方体)中位置不预定时应如何实施加工方案以达到节省费用14. 和节约资源的目的,使我们的方案适用于更为广阔的领域15. 二问题的重述16. 随着人类的发展 自然资源不断地被开发利用科学技术也日新月异而17. 对原材料的加工是工业生产的基础环节是将资源转化为劳动产品的第一步18. 因此采用何种加工方式能使加工费用最少资源最大利用从而降低产品的19. 成本是加工工业中一个重要问题对本题所给出的问题我们首先面临的对20. 加工次序的排序策略然后我们考虑当毛坯和产品位置不预定的时候如何采取21. 策略以达到我们的优化目的22. 1.1 工件和刀具的情况 从一个长方体中加工出一个已知尺寸位置预定23. 的长方体(这两个长方体的对应表面是平行的) 要经过6 次截断切割水平切24. 割单位面积的费用是垂直切割单位面积费用的r 倍当先后两次垂直切割的平25. 面不平行时因调整刀具需付出额外费用e 另外由于工艺要求与水平工26. 作台接触的长方体底面是事先指定的27. 1.2 问题28. 229. l 考虑不同切割方式的总数30. l 建立数学模型分析如何实现最优切割方式(即安排一种各面加工次序使加31. 工费用最少)32. l 对每次选择一个加工费用最少的待切割面进行切割的加工方式进行评价33. l 对调整刀具e = 0 的情况下提出简明优化准则34. l 对于给出的实例验证所提出的方法并作讨论(实例数据略)35. 二模型的基本假设和符号说明36. 基本假设37. 1. 切割足够精确每次切割的产品均合格38. 2. 切割刀具为两个一个水平放置一个为垂直放置39. 3. 第一次作垂直切割时不需调整垂直刀具40. 4. 毛坯与水平工作台接触的底面事先指定41. 5. 毛坯正面的水平棱为长侧面水平棱为宽垂直棱为高42. 假设说明43. 1. 切割精度高可以保证最终产品与毛坯对应表面是平行的从而忽略废44. 品情况对加工费用只考虑切割费用和刀具调整费用之和45. 2. 水平方向只需平行移动水平刀具垂直方向只平行移动或调整后再平行46. 移动刀具因此调整费用e 是否付出仅取决于先后两次垂直切割是否平行而47. 不记是否穿插着水平切割48. 3. 第一次垂直切割时刀具不需调整因此只需考虑切割过程中的刀具调整49. 费用50. 符号说明51. l a,b, c 毛坯的长宽高单位厘米52. l a ,b,c 最终产品的长宽高单位厘米53. l X1, X2,Y1,Y2,Z1,Z2 毛坯的左表面右表面前表面后表面上表面下54. 表面55. l x1, x2, y1, y2, z1, z2 最终产品的左表面右表面前表面后表面上表面56. 下表面(有时我们为了叙述问题的方便将其依次记为5,6,3,4,1,2)57. l d j 最终产品与毛坯的对应表面的距离j = 1,2,L,658. l r 水平切割单位面积费用与垂直切割单位面积费用之比59. l e 调整垂直刀具的额外费用60. l p 垂直切割单位面积费用61. l ti 加工过程中的第i 刀切割第ti 个面62. l63. r64. T ( ) r65. T = t t Lt 1 2 6 称作切割向量t t t 1 2L 6为1,2,L,6的一个排列66. l wi 第i 次切割的切割费用单位元67. l vi 第i 次切割被切割掉部分的体积单位立方厘米68. 369. l si 第i 次切割时切割面积70. 其它变量如果出现 则在使用时另行说明71. 三模型的建立72. 通过对原型的分析,产品的加工可以经过平行(毛坯)的表面的前后六刀73. 得到这里我们将称在切割过程中从毛坯到最终产品的序列半成品称为中间产74. 品75. 我们可以将产品的加工看作一个决策过程 决策的状态可以由毛坯或各中76. 间产品待切削面的集合表示如再将毛坯表示为状态S = x x y y z z 1 2 1 2 1 2 , , , , , 经77. 过切割x1 的中间产品可以由S = x y y z z 2 1 2 1 2 , , , , 如此等等而最终产品的状78. 态可以由f来表示79. 这样 一个切割方式对应六个状态80. S S S S S S S 1 2 3 4 5 681. S6 = f82. 而从状态Si 到Si +1 的一个决策对应着Si 中的一个元素di +1 且满足83. S S d i i i = +1 +184. 这时可将每一步的切割的费用定义为状态 Si 与决策di +1 的函数85. f S d i i ( , ) +186. 而一个切割方式所需总费用87. f88. i89. =90. = 91. f(S ,d i i+1 )92. 093. 594. 至此 希望得到总费用最少的决策可以由下列模型刻划95. min f96. i97. =98. = 99. f(S ,d i i+1 )100. 0101. 5102. s.t S S i ,103. S S d i i i = +1 +1104. 四模型的求解105. 对二维平面切割问题的讨论106. 我们首先讨论简单的二维问题,例如在107. 一块长方形的钢板(l l ) 1 2 上切割一块面积108. 以知l l 1 2109. 110. 111. 112. ,且位置确定的小块钢板,每一113. 次切割的费用与切割长度成正比,不妨令其114. 为h ,水平切115. 图1116. 4117. 割单位长度的费用是垂直切割单位长度费用的r 倍,为简化此问题不妨不考虑118. 调整刀具的,并设以底边起逆时针方向四边的序号为1,2,3,4;且x x x x 4 3 2 1 ;119. 任给一种切割方式(4,3,2,1),然后随意调整两个边的切割次序如2 和3,得新120. 的排序(4,2,3,1)这两种切割方式的费用之差为121. c c x rx 2 1 3 2 - = -122. 所以 若 x rx 3 2 , 则c1 优于c2123. 若 x rx 3 2 时c1 劣于c3127. 若 x rx 1 2 则c1 优于c3128. 综上我们可以总结得到将应的边距转换成统一的权重,对于水平方向的权129. 重w x i i = ,垂直方向的权重n rx i i = ,这样一来得到一个统一标度下的权重;然后对130. 权重w从大到小排序,排列的结果就是对应边的切割次序.131. 以这种统一的权重作为排序的准则的方法可以得到很好的验证:132. 在r=1 时用穷举法验证可得到最优的结果(4,3,2,1),由此我们可以将二维的方法133. 类比推广应用到三维,采用将对应的平行平面的面间距转换为统一的标准权重,134. 作为对各面加工的次序排定的准则.135. 对三维情况的讨论 算法一136. 权重设定方法 对垂直面权重 wtm r tm = ,对于水平面权重 w t tm m =137. 名词约定138. 逆序 如果m n且w w tm tn 则称切割向量中存在一个逆序139. 并记n 为一个切割向量的逆序数140. 半成品i 切割i 次后得到的多面体141. 定理切割方案的优越性反比于逆序数n 如果n = 0 则该切割方案是最优的142. 证明143. 假设存在一个最优切割方案 该方案的切割向量的逆序数n 0144. 则切割向中至少有相邻的两个分量t t i i , +1 使得w w ti ti 1 176. c(T ) c(T)177. r r178. - 0179. 方案180. r181. T 得到第i + 1个产品182. 的费用c(T ) c(T)183. r r184. 0216. 就不能保证所得结论是最优方案因此为处理更一般的情况我们应将/y 考217. 虑在内218. 我们可以从上面e = 0 所给出的优化准则中得到启发当e = 0 时我们根据219. v220. s221. i222. i223. 的大小来决定切割次序我们可以看出当每切一刀切得的体积越大那么224. 以后切割就可以节省更多的费用实际上vi 是与这个节省费用成正比的而si225. 则是与当前切割的费用成正比的所以v226. s227. i228. i229. 实际上代表的含义就是230. 节省费用231. 费用232. 图2233. 6234. 所以对于e 0 节省费用仍然与vi 成正比但费用则应该是235. ps xe i +236. p 为切割单位面积所花费的费用x 为一布尔变量当切割时若需要调整237. 垂直刀具则x = 1 否则x = 0238. 我们利用动态规划思想 在每一步决定切割面时计算当前状态所有面的239. 切割权重选择权重最大的一个面进行下一次切割直到得到最终产品240. 特别地 判断准则在e = 0 的情况下切割权重就变成了前一个方案的判断241. 权重此时两者的判断本质是一样的动态优化问题与静态排序达到了同样242. 的最优化目标(算法和源程序详见附录)243. 用模拟退火法解决本问题 算法三244. 对于原问题的最一般的方法就是将决策集合 D中所有可能一一穷举再代245. 入费用函数寻求最优方案对于本题六面体的加工问题其所有可能排列也246. 就n! = 720 种方案如果面数增加那么可能的排列数就是以/y 递增产生组合爆247. 炸为解决这一问题我们参考了神经网络中解决组合优化问题的方法并使248. 用模拟退火算法解决本题249. 我们把每种可行方案250. r251. T看成某一物质系统的微观状态而c(T)252. r253. 看成物质系254. 统在状态255. r256. T 下的内能并用控制参数F 类比温度让F 从一个足够高的值缓慢257. 下降模拟出每个F 的热平衡态即对当前状态258. r259. T 作一个随机拢动产生一个新260. 状态261. r262. T 计算增量Dc = c(T ) - c(T)263. r r264. 并以概率exp(-Dc / kF)接收S 作为新的当前265. 状态如此重复随机拢动足够次数后状态266. r267. Ti 出现为当前状态的概率服从波尔268. 兹曼分布即269. f Z(F)e ( ) = -c Ti /kF270. 其中 Z(F) ( )271. e c T kF272. i273. i274. = - 275. 1276. / , k 为玻尔兹曼常数277. 若F下降足够慢且F 0 则当前状态将具有最少c(T ) i278. r279. 的状态280. 模拟退火算法主要由由三部分组成281. (1).以一定的概率密度跃迁到新状态称该概率密度函数为生成函数282. (2).以一定的概率密度容忍评估函数的偶然上升称该概率密度函数为容忍283. 函数284. (3).以一定的冷却方式降低温度这个等效温度是控制参量确定所引入的285. 随机扰动强度286. 我们对于算法的重要参数处理如下287. (1). F0 的选择为100288. (2).随机扰动的产生方式从289. r290. Z 的邻域产生一个状态我们就是随机地对调了291. 排列中两个相邻分量的位置292. 7293. (3). F减小的方式F lF,0 l 1可取l 0.2,0.99294. (4).算法终止取F小于阀值0.01295. (模拟退火法的详细算法和程序实现详见附录)296. 对题目所给准则的评价297. 原题中给出的一项准则 每一次选择一个加工费用最少的待切割面进行切298. 割我们认为这种准则是不好的当然它也有适用的时候我们可以从二维的299. 情况来论证并假设e = 0, r = 1300. /y301. 对于图1 我们给出的算法得出结果是302. ( )303. ( )304. 2 4 3 1305. 2 4 1 3306. , , ,307. , , ,308. 309. 310. 或311. ( )312. ( )313. 4 2 3 1314. 4 2 1 3315. , , ,316. , , ,317. 318. 319. 它的算法320. 可以得到同样的结果 说明它的准则在某些特殊情况是有321. 效的322. 对于图2 我们的算法给出的最优排序是323. ( )324. ( )325. 1 3 2 4326. 1 3 4 2327. , , ,328. , , ,329. 330. 331. 或332. ( )333. ( )334. 3 1 2 4335. 3 1 4 2336. , , ,337. , , ,338. 339. 340. 而原题341. 给出的算法得出结果却是(2,4,1,3)或(4,2,1,3)342. 分析原因它的准则在处理第一次切割时选择加工费用最少的待切割面实343. 际上是由毛坯的外形决定的而与最终产品在毛坯中的相对位置无关所以对344. 于给定的毛坯它的第一次切割永不会改变这显然是极不合理的对于三维345. 的情况更是如此所造成的误差更大所以我们认为题目给出的准则是不可取346. 的347. 五模型的检验和结果分析348. 下表给出我们采用过的四种方法(包括穷举法)对e = 0 时3 个具体点的求解349. 情况350. 算法名351. 称352. r=1353. 最优解 时间354. r=1.5355. 最优解 时356. 间357. r=8358. 最优解 时359. 间360. 算法一2,5,1,3,6,4 374361. 无362. 2,5,3,1,6,4 374363. 5,2,3,6,1,4 437.5364. 无365. 5,3,2,6,1,4 437.5366. 5,3,6,2,4,1 540.5367. 无368. 算法二2,5,1,3,6,4 374369. 0的情况则无能为力423. 2.方法二在e 0时仅能找到近似最优解而且随着e 的增大误差也随着424. 增大425. 3.方法三要求退火速度缓慢因此使程序在解决低阶情况时时间开销较426. 大必须借助计算机进行搜索427. 七模型的改进方向428. 改进方向429. 方法二 我们可以在每一次判断时对连续两次切割的结果加以考虑即选430. 择权重时多考虑一步这样就提供了算法的预见性使结果时误差减小但这431. 样也增加了算法的复杂