首页 正方形_分散数列_的提出及其LINGO实现

正方形_分散数列_的提出及其LINGO实现

举报
开通vip

正方形_分散数列_的提出及其LINGO实现  第 18卷  第 2期 厦门理工学院学报 Vol. 18 No. 2   2010年 6月 Journal of Xiamen University of Technology Jun. 2010   [收稿日期 ] 2010 - 01 - 12     [修回日期 ] 2010 - 03 - 13 [基金项目 ] 福建省教育厅科技项目 (JB08210) [作者简介 ] 严丽玉 (1978 - ) , 女 , 福建厦门人 , 讲师 , 硕士 , 从事概率论与数理统计研究. 正方形 “分散数列 ”的提出及其...

正方形_分散数列_的提出及其LINGO实现
 第 18卷  第 2期 厦门理工学院学报 Vol. 18 No. 2   2010年 6月 Journal of Xiamen University of Technology Jun. 2010   [收稿日期 ] 2010 - 01 - 12     [修回日期 ] 2010 - 03 - 13 [基金项目 ] 福建省教育厅科技项目 (JB08210) [作者简介 ] 严丽玉 (1978 - ) , 女 , 福建厦门人 , 讲师 , 硕士 , 从事概率论与数理统计研究. 正方形 “分散数列 ”的提出及其 L INGO实现 严丽玉 1 , 吕志生 2 , 钟俊江 1 (1. 厦门理工学院数理系 , 福建 厦门 361024; 2. 厦门理工学院机械系 , 福建 厦门 361024) [摘  要 ] 基于工农业及生产、生活中的需要 , 提出了正方形 “分散数列 ”概念 , 建立了以最小分散 数最大为目标函数的优化设计模型. 运用基于 L INGO软件的优化算法 , 实现了不同点数的正方形 “分散数 列 ”的最小分散数及其坐标分布的求解. [关键词 ] 分散数列 ; 正方形最小分散数 ; L INGO [中图分类号 ] O22  [文献标志码 ] A  [文章编号 ] 1008 - 3804 (2010) 02 - 0024 - 05 1 问题的提出 在工农业或生活中会遇到如下问题 : 1) 在机械加工中有一种加工 方法 快递客服问题件处理详细方法山木方法pdf计算方法pdf华与华方法下载八字理论方法下载 叫做冲压 , 冲压有几道工 序 , 其中最后的一道工序就是落料 , 也就是整个冲压件形状的形成 , 如果所需要的冲压件的形状是圆 形的 , 为了方便送料 , 板料的形状为条状的长方形 , 怎么安排才能使得该长方形的板料能够得到的冲 压件最多 , 最多能够得到多少冲压件 ? 2) 自然界的所有的种群当中 , 各个生物都需要一定的间距 , 如种树 , 各个树苗之间的距离 , 若距离太小则长到一定程度的时候必定会互相妨碍生长 ; 又如种田 , 每相邻两撮的距离不能太大 , 太大了浪费土地 , 太小了又会妨碍各自的自由生长. 现在有 01067 hm2 正方形的田地 , 要进行插秧 , 如何布局才能不浪费土地又能使植物更好地生长发育 ? 譬如此种工农业或生活中节约的问题 , 前人已有考虑. 但在此主要考虑在封闭的某区域内 (如 正方形或长方形 ) 投入 n (≥ 2) 个点 , 能够使得所有的放入的点都尽可能的分散开来 , 而且每个对应 的点数都对应于一个具体的数. 于是 , 提出 “分散数 ”与 “最小分散数 ”概念. 定义 1 把具体的 n (≥ 2) 个点放入某区域内 , 不管怎么调整这些点的位置 , 都存在其中 2个点 之间的欧氏距离 (或度量 ) ≤1个数 a, 则 a称为该区域的 1个分散数 , 若 a取到最小值 , 那么就称 a为该区域内关于点数 n的最小分散数. 这些数就构成了最小分散数列 , 简称最小分散数. 文中主要考虑在正方形区域的情形 , 下面给出正方形分散数与最小分散数的概念. 定义 2 把具体的 n (≥ 2) 个点放入正方形内 , 不管怎么调整这些点的位置 , 都存在其中两个点 之间的距离 ≤1个数 a, 则 a称为该正方形的 1个分散数 , 若 a取得最小值 , 那么就称 a为该正方形 关于点数 n的最小分散数. 定理 1 任何封闭几何图形的关于放入确定点数的最小分散数必定存在. 这是显然成立的 , 一方面几何图形是封闭的 , 大小是确定的 , 那么最小分散数肯定不会趋向无穷 大 , 又因为所有点不论怎么组合都必然存在距离最短的两点 , 这 2点的距离必定会小于等于最小分散 数 , 所以最小分散数会是在 0到封闭几何图形的最大尺寸之间的一个具体的数. 这类似于中值定理. 2 建立模型并求解分析 211 模型的理论求解 ( n = 3, 4, 5) 当 n较小时 , 可以容易求解与证明. 下面分别针对 n = 3, 4, 5进行证明.  第 2期   严丽玉 , 等 : 正方形 “分散数列 ”的提出及其 L INGO实现 例 1 证明正方形关于放入 3个点时的最小分散数为 6 - 2. 解 : 1) 3个点至少有 1个点与正方形的端点重合 (见图 1所示 ) . 对于这种情况 , 设考虑的 3个点为 A, G, H. 若 G、H在 BC、DC上 , 作正 △A EF (边长为 6 - 2 ) . 若 H在 D F上 , 则 AH j≥1, i∈ Z, j∈ Z; 0 ≤ xi , yi ≤ 1 ( i, j = 1, 2, ⋯, n) . 因此 , 可以将此问题转化为多目标的优化问题 , 从而可以借助于 L INGO软件来实现. 213 程序设计 如前所述 , 该问题属于多变量非线性优化模型 [ 3 - 4 ] , 运用 L INGO 1110编程程序如下 : Model:   data:   n = 24; ! 点数根据需要进行变动 ;   enddata   sets:    xb /1. . n /: x, y; ! 定义属性集 ,分别 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 示横、纵坐标 ;   endsets   init:    x, y = @ole ( ’ chushi. xls’ ) ; ! 初始点放置在 excel文件中 ,这里进行调用 ;       endinit    max = ( ( x (1) - x (2) ) 2^ + ( y (1) - y (2) ) 2^) 0^. 5; ! 目标函数 ;     @for( xb ( j) | j#lt#n: ! 对 j的限制 ;       @ for( xb ( i) | i#gt#j: ! 对 i的限制 ; ( x (1) - x (2) ) 2^ + ( y (1) - y (2) ) 2^ < = ( x ( j) - x ( i) ) 2^ + ( y ( j) - y ( i) ) 2^) ) ; ! 约束条件 ;  @ for( xb ( i) : x ( i) < = 1) ; ! 横坐标的取值范围 ;  @ for( xb ( i) : y ( i) < = 1) ; ! 纵坐标的取值范围 ; end 214 结果的实现及分析 21411 分散数的结果及分析 开启 L INGO的全局最优解器 , 可以得到分散数的结果 , 整理得到表 1和表 2. 表 1 点 n = 2~25的分散数 Tab. 1 The d isp e rs io n num be rs o f n from 2 to 25 点数 分散数 点数 分散数 点数 分散数 点数 分散数 2 1. 414 214 8 0. 517 638 14 0. 348 915 20 0. 286 612 3 1. 035 276 9 0. 500 000 15 0. 341 081 21 0. 271 812 4 1. 000 000 10 0. 421 280 16 0. 333 333 22 0. 267 958 5 0. 707 107 11 0. 398 207 17 0. 306 120 23 0. 258 774 6 0. 600 925 12 0. 388 730 18 0. 300 463 24 0. 254 333 7 0. 535 898 13 0. 366 096 19 0. 289 542 25 0. 250 000   注 1: 为了提高 lingo的运行速度 , 分别对每个点相应的程序取适当的初值 ; 注 2: 点得到的分散数为全局最优 , 其余虽然为局部最优 , 但是运行足够长的时间 (每点的运行时间长短不一 ) 目标值接近最优解 , 可视为全局最优解 . ·62·  第 2期   严丽玉 , 等 : 正方形 “分散数列 ”的提出及其 L INGO实现 表 2 点 n = 2~6的坐标点解之一 Ta b. 2 O ne o f coo rd ina te so lu tio n s o f n from 2 to 6 点数 解的各点坐标 2 (1. 000 000, 0. 000 000)     (0. 000 000, 1. 000 000) 3 (1. 000 000, 1. 000 000)     (0. 732 050 8, 0. 000 000)   (0. 000 000, 0. 732 050 8) 4 (1. 000 000, 1. 000 000)     (1. 000 000, 0. 000 000)    (0. 000 000, 1. 000 000) (0. 000 000, 1. 000 000) 5 (1. 000 000, 1. 000 000)     (0. 500 000, 0. 500 000)    (0. 000 000, 0. 000 000) (0. 000 000, 1. 000 000)     (0. 000 000, 0. 000 000) 6 (0. 666 666 7, 0. 5000 000)   (1. 000 000, 1. 000 000)    (0. 333 333 3, 0. 000 000) (1. 000 000, 0. 000 000)     (0. 000 000, 0. 500 000 0)   (0. 333 333 3, 1. 000 000)   注 1: 该表为得到表 1全局最优解时所对应点分散数的坐标点 (由于数据量比较大 , 只列出其中点 n = 2~6的 ) ; 注 2: 由于正方形的对称性 , 因此解不唯一 , 每组坐标点只是其中之一组解. 由表 1可以看出各分散数随着点数增加而减小. 用 excel 对 n = 2, 3, ⋯, 25作散点图. 令分散数数列为变量 y, 点数为 n, 拟合得到二者的关系 图 5和关系式 : y = 2. 220 4 n- 0. 692 3 . 从图 5拟合图中可以看出 除 n = 4这点外 , 模型拟合得相当好 , 分散数确实随着点数呈 现递减的规律. 由此 , 当不需要特别精确的分散数时 , 可以利 用该关系式来获得. 由 2~25点坐标点解 (2~6点坐标点解见表 2) 可以得到如下结论 : a) 至少有 1个点落在顶点上 ; b) 有若干点落在正方形的 4条边上 (包括顶点 ) ; c) 大部分点至少存在某组坐标解关于正方形的 4条对称轴 y = 0. 5, x = 0. 5, x = y, x + y = 1某 几条对称. 例如  6个点的情况 , 作出其坐标图见图 6 ( a). 从图 6 ( a) 中可以看出 : (1, 1) 与 (1, 0) 在顶 点上 , 且有 5个点落在正方形的 4边上. (1, 1) 与 (1, 0) , (0. 333 333, 1) 与 (0. 333 333, 0) , (0, 015) 与 (0. 666 667, 0. 5) 分别关于直线 y = 015对称. 再如 , 23点的情况 , 作出其坐标图如图 6所示 ( b). 从图 6 ( b) 可以看出 (0, 0) 1个点落在原 点上 , 且共有 14个点落在 4边上. 同时 , 所有点都分别关于正方形的 4条对称轴对称. 21412 平方个点的分散数的结果及分析 为了提高 L INGO软件的运行速度 , 基于以上的结论合理设定初始值得到的平方个点的分散数 , ·72· 厦门理工学院学报 2010年 见表 3所示. 表 3 n = 2~15的平方个点的分散数 Ta b. 3 Squa re spo t sca tte re d num be rs o f n from 2 to 15 点数 分散数 点数 分散数 点数 分散数 点数 分散数 22 1. 000 000 0 62 0. 200 000 102 0. 111 111 142 0. 076 923 32 0. 500 000 72 0. 166 667 112 0. 098 925 152 0. 071 429 42 0. 333 333 82 0. 142 857 122 0. 092 247 52 0. 250 000 92 0. 125 000 132 0. 083 333   注 1: 为了提高 lingo软件的运行速度 , 分别对每个点坐标取适当的初值 ; 注 2: n = 4点得到的分散数为全局最优 , 其余为局部最优. 从表 3可以看出 2~15的平方点除了满足上述的性质外 , 第 n2 点的分散数都等于 1 / ( n - 1) 2 (由 于存在误差 , 所以个别点软件运行结果是接近于该结论 ) . 同时 , 它们的坐标点都均匀分布在整个正 方形内 , 它们的横坐标和纵坐标都从 0取到 1 (公差为 1 / ( n - 1) ) . 由此 , 可以得到任意平方点的分 散数及其坐标. 3 结语 从人们制造生产各种各样的物品或是军队的排兵布阵等问题 , 提出了最小分散数和最小分散数列 的概念. 由于理论证明与求解的不易 , 文中采用 L INGO软件编程实现了正方形内部点数为 n的分散 数及其对应坐标 , 并得到了一些相关的性质. [参考文献 ] [ 1 ] 陈景林. 抽屉原理及其应用 [ J ]. 唐山师专学报 , 1999, 21 (5) : 23224. [ 2 ] 肖美英. 抽屉原理及其应用 [ J ]. 晋中师范高等专科学校学报 , 2002, 19 (3) : 2032204. [ 3 ] 温斯特. 运筹学 : 数学规划 [M ]. 北京 : 清华大学出版社 , 2004. [ 4 ] 何坚勇. 运筹学基础 [M ]. 北京 : 清华大学出版社 , 2008. [ 5 ] 谢金星 , 薛毅. 优化建模与 L INDO /L INGO软件 [M ]. 北京 : 清华大学出版社 , 2005. The Proposa l of Square “D ecen tra lized Ser ies”and Its Im plem en ta tion on L INGO YAN L i2yu1 , LüZhi2sheng2 , ZHONG Jun2jiang1 (1. Faculty ofMathematics & Physics, Xiamen University of Technology, Xiamen 361024, China; 2. Faculty ofMechanical Engineering, Xiamen University of Technology, Xiamen 361024, China) Abstract:Based on the needs from industry, agriculture and daily life, the concep t of square “decentral2 ized series”is p roposed and an op tim ized model with the m inimum number of dispersion objective function es2 tablished. The utilization of op tim ization algorithm based on the L INGO software has realized the solution of the m inimum disperser number and the coordinates distribution of the different points square “decentralized se2 ries”. Key words: dispersion series; the number of square m inimal dispersion; L INGO ·82·
本文档为【正方形_分散数列_的提出及其LINGO实现】,请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑, 图片更改请在作品中右键图片并更换,文字修改请直接点击文字进行修改,也可以新增和删除文档中的内容。
该文档来自用户分享,如有侵权行为请发邮件ishare@vip.sina.com联系网站客服,我们会及时删除。
[版权声明] 本站所有资料为用户分享产生,若发现您的权利被侵害,请联系客服邮件isharekefu@iask.cn,我们尽快处理。
本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用。
网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
下载需要: 免费 已有0 人下载
最新资料
资料动态
专题动态
is_460290
暂无简介~
格式:pdf
大小:503KB
软件:PDF阅读器
页数:5
分类:互联网
上传时间:2010-09-07
浏览量:21