一种新的高效平面点集凸壳构建算法 E2104246

一种新的高效平面点集凸壳构建算法

徐胜攀1,2，刘正军1,左志权1

（1．中国测绘科学研究院北京 100830; 2. 兰州交通大学兰州 730071）

摘要：本文提出一种新的平面点集凸壳构建算法，算法基于角域处理的过程对点集分而治之计算凸壳，基于特征角计算的方法成对查找角域特征点，利用初始角域划分和角域更新的机制不断缩小问题规模，从而迅速逼近凸壳边。针对大规模数据点集，算法又引入迭代思想，利用算法本身对非凸壳点的快速删除能力进一步加速凸壳求解进程，使得算法性能进一步提升。本算法时间复杂度和空间复杂度均为O(n)，实验表明，这是一个可行、高效而且稳定的算法，而且，本算法易于推广到三维，也容易改进成并行算法。

关键词：凸壳；平面点集；特征点；角域；分治；迭代

中图分类号：TP301.6

平面离散点集的凸壳计算是应用十分普遍的基本几何算子，论文提出一种基于角域处理的新算法，具有较高的计算效率和可靠性。建议作者适当修改后刊发：（1）由于在三维空间具有不同的几何性质，不宜简单说本算法易于推广到三维；（2）该文的方法是一种矢量计算机制，不知如何容易改进成并行算法？（3）将“具有最值特性的点：特征点”修改为外接矩形角点为好，因为任何一个点集都只有这4个特征点；（4）实验测试可多选择几个不同分布点集样例，图2所示的点集分布形态比较规则（凸壳比较规则）。

A new efficient algorithm for creating convex hull

for planar point set

Xu Shengpan1,2, Liu Zhengjun2, Zuo Zhiquan2

(1. Chinese Academy of Surveying & Mapping, Beijing, 100830;

2. Lanzhou Jiaotong University, Lanzhou,730071;)

Abstract: This paper presents a new algorithm for creating convex hull for planar point set, it uses the strategy of divide-conquer to calculate the convex hull by the process of triangle-region processing, finding trait-points in pair by means of trait-angle calculation, decreasing the scale of the problem by the mechanism of initial triangle-region partition and updating, thereby rapidly approaching to the edge of the convex hull. For large scale data set of points, the idea of iteration is introduced in, it uses the ability of quickly deleting the non convex hull points to accelerate the process of convex hull getting, making the performance of the algorithm enhanced further. Both of the time complexity and space complexity of the alg orithm are O(n), experiments manifest that it is a feasible, efficient and stable algorithm. Furthermore, this algorithm is easy to be extended to three-dimensional space as well as be improved to parallel type.

Key Words: Convex hull; planar point set; trait-point; triangle-region; divide-conquer; iteration

0 引言

凸壳（Convex Hull），也称凸包，是指包含给定点集的最小凸集。在二维情况下，凸壳是由点集中部分点按一定方向顺次连接形成的凸多边形。凸壳是计算几何中一种最普遍、最基本的结构[1]，许多问题可以归结为凸壳问题，凸壳在图像处理、模式识别、计算机图形学等领域有着广泛的应用[1-7]。

常见的凸壳构建算法包括“卷包裹”算法[8]、格雷厄姆算法[8]、分治算法[8]、增量算法[8]。“卷包裹”算法时间复杂度均为O(n2)；格雷厄姆算法、分治算法、增量算法时间复杂度均为O(nlogn)，但这些算法计算过程都较为麻烦。

近年来，又有学者提出新的凸壳构建算法，如2000年周培德提出的Z3-2算法[1]（称文献[1]算法），2006年樊广佺等提出的八方向极值快速凸壳算法[9]（称文献[9]算法），2007年郝建强提出的利用正负划分性求平面点集凸包的算法[10]（称文献[10]算法），2010年吴文周等提出的算法[11]（称文献[11]算法）等。文献[1]算法简化了凸壳计算过程，但由于该算法对凸壳特性利用仍不够（对不参与凸壳构建的点删除程度不够），计算效率仍不高，另外该算法在查找凸壳点的过程中对凸壳边进行不断分裂，随着凸壳边的增多，点到凸壳边距离的计算会变得越来越复杂；文献[9]算法将构建凸壳由以往的四方向极值扩展到八方向极值，初步删除了更多不参与凸壳构建的点，但该算法仍具有与文献[2]算法类似的缺点；文献[10]算法本质上是文献[2]算法的一个改进算法，它简化了求距离最大点过程，但整体运算过程并没有很大程度上的优化；文献[11]算法创造性地应用了分治思想，单纯利用分治减小问题规模，提高了效率，该算法对凸壳点的查找利用了格雷厄姆方法，过程较为麻烦。

本算法在深入研究前人成果的基础上，充分利用凸壳特性，提出一种新的凸壳构建算法。该算法的内核算法突破了传统算法思想，极大地加快了求解进程，在凸壳求解过程中，角域以极快的速度收敛，从而迅速逼近凸壳边。为进一步减小绝对运算次数，算法又引入迭代处理思想，从而再次提高算法效率。本算法论证严密，效率分析和实验测试表明，本算法是一个时间效率高、空间开销少、可行而且稳定的算法。

1.理论基础

1.1 本算法相关概念

为方便算法依据定理的阐述，先引入几个相关概念，必要时，对这些概念在算法中的运用加以说明。

1.1.1 特征点

点集中，X坐标值或Y坐标值具有最值特性的点称为特征点。在二维情况下，对于任意一个给定的点集，总是存在4类特征点：X值最小点、X值最大点、Y值最小点、Y值最大点。把X值最小点和X值最大点统称为X特征点；Y值最小点和Y值最大点统称为Y特征点。显然，特征点位于点集的最小外界矩形上。

一个点可以既为X特征点，也为Y特征点，点集中某类特征点也可以不止一个。本算法中，如果点集中的某点既为X特征点，也为Y特征点，则对这一点分别按X特征点和Y特征点存储；如果点集中某类特征点不止一个，则选取其中一个作为特征点。最终的特征点总数按4个处理。

1.1.2 特征项

给特征点以最值特性的坐标项称为特征项。X特征点具有X特征项，Y特征点具有Y特征项。对各特征点按逆时针方向顺次连接，称位于同一条线段上的两特征点为相邻特征点。容易推知，相邻特征点的特征项必然不同。

1.1.3 特征轴

过特征点，按其特征项所作的水平线或垂直线称为特征轴，并且称特征轴与该特征点相互关联。对于一个特征点P，如果它具有X特征项，则它关联X特征轴，直线方程为X=P.x；如果它具有Y特征项，则它关联Y特征轴，直线方程为Y = P.y。

1.1.4 角域

连接相邻特征点，并分别作过这两个特征点的关联特征轴，形成的直角三角形区域称为角域。如果两相邻特征点对应同一个点，则角域收敛为一个点。

1.1.5 特征角

一个点和一个特征点的连线与该特征点的关联特征轴之间的夹角称为该点的特征角。点与X特征点的相连形成的特征角称为X特征角，记为α；点与Y特征点的相连形成的特征角称为Y特征角，记为β。称角域内的所有点中，α值最小的点为α最小点，β值最小的点为β最小点，α最小点和β最小点统称最小角点。

特征角的计算方法为，设为特征点，为特征点，为角域内任意一点，则：

上式要求对角域内的任意点，存在P.y ≠A.y且P.x ≠ B.x，事实上在运算中必然成立。当某点P存在P.y ＝ A.y或P.x ＝ B.x时，它必然位于当前角域边界外部，不会纳入当前角域的考察点集（这样的点会在之前的角域处理中被删除）。

1.2 本算法相关定理

定理一：点集的特征点一定位于凸壳上。

证明：由于特征点位于点集的最小外界矩形上，因此，特征点一定位于凸壳上。

定理二：角域内的最小角点一定位于凸壳上。

证明：假设角域内的α最小点（设为M）位于凸壳内，角域的X特征点为A。根据凸壳性质[1]，角域内必然存在一点P，使得连接AP后，M位于AP左侧；根据α最小点的定义，M 为角域内与X特征轴夹角最小的点，因此M必然位于角域内任意点与A连线的右侧，矛盾。因此，α最小点必定位于凸壳上。对于β最小点可采用同样的方法证明。

定理三：在角域内，设α最小点为P i，β最小点为P j，则：

（1）如果P i＝ P j，则插入P i至凸壳后，该角域内的凸壳边构建完毕；

（2）如果P i≠P j，设A为角域内的X特征点，B为Y特征点，顺次连接A、P i、P j、B，则在连接线左侧的点不能参与凸壳构建，可以直接删除，且在剩余点集中，P i是X特征点，P j是Y特征点。

图1 分布情形图

证明：

首先证明（1）。如图1(a),由于P i＝ P j，则点P i既是α最小点又是β最小点，因此，该角域内不存在其他能参与凸壳构建的点，否则，与P i既是α最小点又是β最小点矛盾，故此时该角域内的凸壳边构建完毕。

证明（2）。如图1(b),由于在角域内，连接A、B后，A、P i、P j、B左侧的点位于多边形AP i P j B内部，故这些点不能参与凸壳构建，应予删除。根据特征角的性质，角域内的点必然位于按逆时针方向顺次连接特征点和最小角点构成的折线段（如图AP i P j B）的左侧，即剩余点集应位于以两最小角点的连线（如图P i P j）为一条边、以最小角点与相应特征点的连线（如图AP i、BP j）之交点为另一个顶点(设为M)的三角形内部。根据α最小点和β最小点的性质，P i、P j是三角形P i P j M范围内分别离X特征轴和Y特征轴最近的点，故P i、P j分别是剩余点集的X特征点和Y特征点。

定理一和定理二给出了凸壳点的选取法则，定理三则回答了如何寻找满足条件的凸壳点以及何时可以终止对凸壳点的查找。定理三是一个重要定理，它说明了新角域的形成法则、新特征点的产生法则以及前后两代特征点之间的继承法则。思考定理三不难发现，而情形（1）是情形（2）的一种特例：当情形（2）退化成情形（1）时，新角域退化成一个点，则新的考察点集为空集，所以这个角域内的凸壳边构建完毕。

2.算法思想与算法描述

2.1 算法基本思想

本文第一部分的三个定理及其证明过程已经部分地暗示了本算法的大体步骤。如果不考虑迭代思想，算法步骤应该是：首先找到点集内的4个特征点，分别连接相邻个特征点并利用特征轴构建4个（或3个或2个）角域，将点集加入角域（删除不能加入到任何角域的点），然后对各角域逐次查找α最小点和β最小点将其插入凸壳，根据定理三删除不会参与凸壳构建的点同时进行角域更新。角域不断收敛，当所有角域考察点集均为空集时，凸壳构建完毕。

称上述过程描述的算法为本算法的内核算法。内核算法总是会成对查找特征点，并且会最大限度地缩小问题规模点集。尽管内核算法实际上已经非常高效，但当算法的问题规模n 很大时，算法中α、β的绝对运算次数仍然很大。考虑到本算法对非凸壳点的强大的快速删除能力，将迭代思想运用于角域处理：由于凸壳上的顶点必然包含于其子凸壳顶点中，因此当进行角域处理时，如果角域内的点数量大于某个常数（称为问题规模限定数），可以先递归调用本算法，得到一个子凸壳，将子凸壳的顶点作为角域的输入点集，再执行角域处理。

2.2 算法过程描述

3.算法复杂度分析

3.1算法时间复杂度分析

本算法可看成是对点集进行初始划分然后对各角域进行角域处理的过程，在角域处理过程中，不断查找当前角域的特征点并对角域进行更新，角域不断收敛，进而迅速逼近凸壳边界。由于算法在初始划分阶段对非凸壳点的删除比例以及角域处理过程中对非凸壳点的删除比例等都取决于点的分布情况，现运用概率统计相关方法来分析本算法的时间复杂度。

设算法初始输入点数为N，总的运算次数为T(N)；初始划分的角域数量为k，经过初始划分后，剩余点数与初始输入点总数之比为a；在角域处理过程中，对问题规模为n的点集，基本运算次数为F(n)。由于算法在初始划分阶段需要遍历所有点以划分角域，然后执行角域处理，故：

设角域处理时，问题规模限定数为B。对于点数为n的角域，当n=B时，则先递归调用本算法以减小问题规模(设问题规模减小比例的平均值为c)，然后执行与n

f(n)满足下列关系式：

解f(n)，再将f(n)代入式2得：

由于经过初试划分之后，各角域内点的数量不尽相同，因此T(N)的表达式不易确定，下面考虑两种特殊情况，并且在下列两种情况下，各角域内的点均匀分布。

(1)n1到n k均小于B时

各角域的表达式为：

联立式（2）和式（6），解方程组得：

(2)n1到n k均大于B且各角域内经过递归处理后，点的数量仍大于B时（相当于是各角域内

的点数均为无限多的情况）

各角域F(n)的表达式为：

联立式（2）和式（7），解方程组得：

由于a、b、c、p均与点的分布特点相关，而与点的数量N无关，因此，从式（7）和式（9）可知，上述两种情况下，算法时间复杂度均为线性次。由于上述两种情况代表了点数很少和点数极多两种极限情况，实际情况总是介于两者之间，且算法复杂度与点的分布无关，因此，本算法时间复杂度为线性次，即O(n)。算法的具体运算次数与点的分布状态相关，不同状态分布的点，算法运行时间线性增长的情况会有不同。

3.2算法空间复杂度分析

显然，本算法中占用空间最多的时候是刚开始时进行角域划分的时候，以后，随着算法的运行，角域逐渐收敛，所需要存储的点数也随之减少。因此，本算法的空间复杂度为。

4. 实验

为评价本算法运行效率，采用两种不同坐标尺度和分布特征的数据进行了实验，并与经典的Graham算法[13]进行了对比。实验数据均采用计算机代码产生的随机点（随机方式不同），第一组数据坐标范围约为X∈（100，1600），Y∈（80,700），第二组数据坐标范围约为X∈（0，300000），Y∈（0,150000）。图2（a）、2（b）分别是对两组数据中，点数为200万的文件点及其凸壳可视化后的效果图，表1、2分别为堆两组数据用Graham算法和本文算法对各数据测试多次后的时间统计表（由于当点数达到20万时，Graham算法运行速度较慢，与本文算法相比已经出现很大差距，对Graham算法进一步测试意义不大，因此，对于20万以后的数据，本文没有进行进一步实验）。本试验采用的计算机主频为2.2G赫兹，内存为2.0G，采用的编译器为Visual Studio 2008。实验中，本文算法的问题规模限定数为 Bound Number = 200。

（a）（b）

图2 两组数据中的200万点及其凸壳效果图

第一组第二组

点数Graham算法运行

平均时间（ms) 本文算法运行

平均时间（ms)

Graham算法运行

平均时间（ms)

本文算法运行

平均时间（ms)

2000 18 3 15 6 5000 125 9 117 21 10000 484 12 472 43

表1 算法测试结果统计表

从以上时间统计表中可以看到，相对于经典的Graham 算法，本文算法表现出巨大优势。算法运算稳定，在很短的时间内，即可完成大数量点的凸壳构建。实验中，进一步绘制了本

文算法对两组数据的运行时间曲线图，并进行了线性拟合，拟合结构为第一组R 2

= 0.9988,

第二组R 2

= 0.9998，算法运行时间随点数的增长表现出极强的线性规律，印证了本文关于算法时间复杂度的推理。

图3 算法运行时间图

5. 结论与展望

本文提出了一种新的凸壳构建算法，算法可划分为“划分”和“查找”两大：“划分”过程确定初始凸壳，将落在初始凸壳内部的点剔除而将其余点划分至各自所属角域；“查找”过程不断查找新的最小点和最小点以完善凸壳边，得到最终凸壳，在“查找”前，如果角域内点的数量大于问题规模限定数，则先对角域执行分治处理，以提高算法效率。分析表明算法时间复杂度为线性次，具有极高的运算效率，这些结论通过实验得到了验证。

虽然本算法是针对二维设计的，但可以看到，无论是特征点的查找、划分角域，还是最小角点的计算，这些关键过程都可以推广到三维，三维情况下，最小角点查找由点与特征轴夹角的计算的变为点与特征面的夹角的计算，在三维这种更加复杂的情况下，本算法的优势将进一步得到体现。另外，本算法将构建凸壳的过程分解为求解2到4个角域凸壳边的过程，各角域的处理是独立进行的，并行处理是目前计算机行业发展的重要趋势，本算法为并行求解

20000 1931 22 1877 72 50000 11941 50 16362 102 100000 47580 97 103875 200 200000 191382 181 214549

314 500000 - 449 - 915 1000000 - 899 - 1840 2000000 - 1848

- 3966

凸壳提供了可能。

参考文献

[1]Zhow P D. Computional Geometry: Algorithms Design and Analysis[M] .2nd. Beijing Tsinghua

University Press,2005: 57-78. [周培德. 计算几何：算法分析与设计[M]. 第二版. 北京：清华大学出版社，2000: 57-78. ]

[2]Guo R Z, Ai T H. Simplification and Aggregation of Building Polygon in Automatic Map

Generalization[J]. Journal of Wuhan Technical University of Surveying and Mapping, 2000, 25(1) : 25-30.[郭仁忠，艾廷华. 制图综合中建筑物多边形的合并与化简[J]. 武汉测绘科技大学学报, 2000, 25(1) : 25-30.]

[3]Liu J Y, Wang X S, Zhuang D F, etc.Application of Convec Hull in Identifying the Types of Urban

Land Expansion[J].ACTA Geographica Sinica, 2003, 58(6): 885-892.[刘纪远，王新生，庄大方等. 凸壳原理用于城市用地空间扩展类型识别[J].地理学报，2003, 58(6): 885-892.] [4]Meng F J, Guo B L, Li X W, etc. New image retrieval method based on convex hull of inter est

points[J]. Journal of Optoelectronics Laser, 2010, 21(6) : 936-939.[孟繁杰，郭宝龙，李新伟等. 基于兴趣点凸包的图像检索方法[J]. 光电子激光, 2010, 21(6) : 936-939.]

[5]Lu J, Liu Z. An approach for smart phone barcode positioning and correction based on an

improved convex hull algorithm[J]. Journal of Zhejiang University of Technology, 2010, 38(6): 661-665.[鲁剑，刘志. 基于改进凸包算法的移动端条码图像定位与校正[J]. 浙江工业大学学报，2010, 38(6): 661-665.]

[6]Chen X G, Chen S Q, Wang L Q. An Algor ithm of Building Delaunay Tr iangulation Based on

Convex Hull[J]. Computer Engineering and Applications,2006 ,6: 27- 29.[陈学工，陈树强，王丽青. 基于凸壳技术的Delaunay三角网生成算法[J]. 计算机工程与应用. 2006 ,6: 27-

29.]

[7]Yang Y , Liu Y C, Liu M Y ,etc. A Path Planning Algorithm Based on Convex Hull for

Autonomous Service Robot[J]. Transactions of Beijing Institute of Technology, 2011, 31(1).

[杨毅，刘亚辰，刘明阳. 一种基于凸壳的智能服务机器人路径规划算法[J]. 北京理工大学学报, 2011, 31(1).]

[8]Joseph O R. Computational Geometry in C, 2nd [ M ] .Cambridge , UK: C ambridge University

Press , 1998 .

[9]Fan G , Ma L P , Yang B R. An Efficient Algorithm for the Convex Hull of Plannar Point Set[J].

Geography and Geo-Information Science , 2006, 22(6) : 38-41.[樊广佺，马丽平，杨炳儒. 平面点集凸壳的一种快速算法[J]. 地理与地理信息科学，2006, 22(6) : 38-41.]

[10]Hao J Q. Optimum Algorithm for Constructing Convex Hull of Planar Point Set Utilizing Plus

or Minus Characteristic of Demarcation[J]. Journal of Image and Graphics , 2007, 12(5) : 910-916. [郝建强. 利用正负划分性求平面点集凸包的最优算法[J]. 中国图像图形学报，2007, 12(5) : 910-916.]

[11]Wu W Z, Li L F, Wang J C. Analysis on wetland dynamic changes of Tianjin Binhai new area

and their effects[J]. Science of Surveying and Mapping , 2010, 35(6): 123-125. [吴文周，李利番，王杰臣. 平面点集凸包Graham 算法的改进[J]. 测绘科学，2010, 35(6): 123-125.] [12][Mark D B,Otifried C, Mark V K. Deng J H. Computional Geometry: Algorithms and

Applications[M]. 3th. Beijing: Tsinghua University Press, 2009: 2 – 9. [Mark D B,Otifried C, Mark V K. 邓俊辉译. 计算几何: 算法与应用[M]. 第三版. 北京：清华大学出版社，2009:

2 – 9.]

[13]Dan S. The Convex Hull of a 2D Point Set or Polygon[DB/OL].(2001-2006)[2011-11-20].

https://www.doczj.com/doc/0314304908.html,/Archive/algorithm_0109/algorithm_0109.htm

作者简介

徐胜攀（1987- ）：男，湖北孝感人，兰州交通大学与中国测绘科学研究院联合培养硕士研究生，专业为地图学地理信息系统。现在中国测绘科学研究院从事学习和相关研究工作。主要研究方向为三维可视化，激光雷达数据处理等。Email：jack_1227x@https://www.doczj.com/doc/0314304908.html,

刘正军（1974- ）：男，博士，研究员。现在工作于中国测绘科学研究院摄影测量与遥感所，主要从事遥感影像信息提取与生态环境监测，突发事件应急地理信息技术等方面的研究工作。Email: zjliu@https://www.doczj.com/doc/0314304908.html,

左志权（1983- ）：男，博士。主要研究方向：摄影测量与遥感、模式识别、LiDAR信息提取等。Email: zqzuo@https://www.doczj.com/doc/0314304908.html,

附录A 算法时间复杂度分析部分结论性公式推理过程

本附录仅对文中未详细证明的结论性公式给出推理过程。

1.对式（5）

由于

对上述方程组中的第一个方程对n微分，有：

联立式（3），式（5）即可得证。

2.对式（9）

由于

即

现在来解这个方程组，试图解出T(N)。

以上推出了三组表现出较强的规律性，因此作出如下猜想：

下面证明：

假设T(n)的通式成立，则：

F(n)的通式得证。

此时，

T(n)的通式也得证。

故：

附录B 算法运行时间统计表

整数规划割平面法

割平面法 求解整数规划问题： Max Z=3x 1+2x 2 2x 1+3x 2?14 4x 1+2x 2?18 x 1,x 2?0，且为整数 解：首先，将原问题的数学模型标准化，这里标准化有两层含义：（1）将不等式转化为等式约束，（2）将整数规划中所有非整数系数全部转化为整数，以便于构造切割平面。从而有： Max Z=3x 1+2x 2 2x 1+3x 2+x 3=14 2x 1+x 2+x 4=9 x 1,x 2?0，且为整数 利用单纯形法求解，得到最优单纯形表，见表1： 表1

最优解为：x 1=13/4, x 2=5/2, Z=59/4 根据上表，写出非整数规划的约束方程，如： x 2+1/2x 3-1/2x 4=5/2 (1) 将该方程中所有变量的系数及右端常数项均改写成“整数与非负真分数之和”的形式，即： (1+0)x 2+(0+1/2)x 3+(-1+1/2)x 4=2+1/2 把整数及带有整数系数的变量移到方程左边，分数及带有分数系数的变量称到方程右边，得： x 2 - x 4-2 =1/2-(1/2x 3+1/2x 4) (2) 由于原数学模型已经“标准化”，因此，在整数最优解中，x 2和x 4也必须取整数值，所以(2)式左端必为整数或零，因而其右端也必须是整数。又因为x 3,x 4?0，所以必有：

由于(2)式右端必为整数，于是有： 1/2-(1/2x 3+1/2x 4)?0 (3) 或 x 3+x 4?1 (4) 这就是考虑整数约束的一个割平面约束方程，它是用非基变量表示的，如果用基变量来表示割平面约束方程，则有： 2x 1+2x 2?11 (5) 从图1中可以看出，(5)式所表示的割平面约束仅割去线性规划可行域中不包含整数可行解的部分区域，使点E(3.5，2)成为可行域的一个极点。 图1 在(3)式中加入松弛变量x 5，得： -1/2x 3-1/2x 4+x 5=-1/2 (6) 将(6)式增添到问题的约束条件中，得到新的整数规划问题： Max Z=3x 1+2x 2 2x 1+3x 2+x 3=14 2x 1+x 2+x 4=9

平面点集的最小包围圆算法设计 及实现

平面点集的最小包围圆算法设计 及实现 王立（P1016017）张涵初（P1016015）张超（P1016005） 华北计算技术研究所 一、问题背景 欲在一平面区域内建立一个固定的无线信号收发中转基站，平面区域内有若干个固定的无线通信用户（可抽象为平面内一点）。各无线通信用户之间若要实现互联通信，均需要无线通信用户先与中转基站建立无线链接，再通过中转基站链接区域内任一点。那么这个无线信号中转基站应该选在哪里呢？根据直觉，应该选在中转基站射频作用距离范围的“中心”。准确地讲，也就是包围这些点的那个最小圆的圆心——该位置的好处是，中转基站与它射频作用范围内的点实现通信时，射频发射机的发射功率即功耗达到最小化（无线射频通信中，作用距离越短，射频发射机功耗越小）。于是可抽象出如下问题：给定由平面上n个点所组成的一个集合P（对应于中转基站射频作用范围覆盖的区域内的通信用户），试找出P的最小包围圆（smallest enclosing disc），即包含P中所有点并且半径最小的那个圆。可以证明，这个最小包围圆有且仅有一个。 二、实验内容 本实验主要完成了平面上随机点集P的生成和关于P的最小包围圆的计算。在生成平面随机点集时，通过伪随机函数rand()函数实现了在平面矩形区域、平面圆形区域以及平面环形区域内的均匀随机分布。在计算最小包围圆的过程中，使用并改进了一种比较高效的线性算法，在O(n)的时间内计算出了覆盖平面点集P的最小圆。 生成平面随机点集P时，我们将点的分布区域设置为平面矩形、圆形和扇形等，并将上述算法分别作用到不同分布区域的平面点集P，对比分析了其各自时间复杂度。

三、算法的理论描述 在我们熟悉的二维平面的线性规划问题中，在目标函数和给定的初始边界条件共同确定出最优顶点P时，若引进一张半平面S1，顶点P落在S1所包围的区域内，则当前的最优点可以保存前一次所求出的最优顶点P而不必修改。将此思路应用于最小外接圆算法：对于由平面点集P内的多个点p1，p2，……，p i（相当于i个初始边界条件）确定出一个最小包围圆C i, 如果引入一张新的半平面S i+1，此半平面为以C i的圆心o i为圆心，以平面上不包含于P的一点p i+1与C i的圆心o i的距离|p i+1o i|为半径。只要此前的最优解顶点（即唯一确定最小包围圆的几个关键顶点）能够包含于半平面S i+1中，则不必对此最优解进行修改，亦即此亦为新点集的最优解；否则，新的最优解顶点必然位于这个新的半空间的边界上。其形式如图1所示： 图1——若p i∈C i?1，则C i=C i?1，若p i+1?C i，则C i+1更新 上述性质为一几何引理，它构成了本文及本次实验的理论基石，本文所讲述的算法也将围绕该引理展开。 仿照线性规划的随机增量式算法，我们可以得到期望在线性时间内的完成的最小包围圆算法，将此算法命名为MCC算法（Minimum Circumscribed Circle）。定义圆C i为相对于平面点集P的最小包围圆。根据上述引理，可知当P中新引入一点p i时，若p i+1包含于圆C i内，则维护圆C i，作为此时P的最小包围圆，即C i+1=C i。而此算法实现的关键在于对于p i+1?C i时的处理。显然，当p i+1?C i，则需要对C i进行更新。而且，圆C i+1必然经过p i+1。因此，此种情况下的最小包围圆是过p i+1点且覆盖点集P={p1，p2，……，p i}的最小包围圆。则仿照上述处理的思路，初始化圆C i的修改值，令其为圆C i‘，此圆通过点p1和p i+1，进而逐个扫描判断点集{p2，p3，……，p i}。当p k∈C i’，则维护C i’不变，如果存在p k?C i’，则再次修改圆C i’的值为圆C i“，此时圆C i“通过点p k，p i+1。接着，再依次对点集{p1，p2，……，p i?1}进行逐个扫描，判断其是否满足p l∈C i”，若存在p l?C i“，则C i”即由点p k, p l, p i+1三点确定。

第五章 整数规划练习题答案教程文件

第五章整数规划练习 题答案

精品资料 仅供学习与交流，如有侵权请联系网站删除 谢谢2 第五章 整数规划练习题答案 一. 判断下列说法是否正确 1. 用分枝定界法求解一个极大化的整数规划问题时，任何一个可行整数解的目标函数值是 该问题目标函数值的下界。( ) 2. 用割平面法求解整数规划时，构造的割平面有可能切去一些不属于最优解的整数解。( ) 3. 用割平面法求解纯整数规划时，要求包括松弛变量在内的全部变量必须取整数值。( ) 4. 指派问题数学模型的形式与运输问题十分相似，故也可以用表上作业法求解。( ) 二. 设有五项工作要分派给五个工人，每人的作业产值如下表所示，为了使总产值最大，问 应如何分配这五项工作，并求得最大产值。 答案： 设原矩阵为A ，因求极大问题，令B=[M-a ij ]，其中M=Max {a ij }=10，则： 16425105 3140 42132 510425 1042 4003B 13752102641015406241515130450203057470574704646111 -???? ?? ? ? ? ? ? ? ? ? ? =→→- ? ? ?- ? ? ? ? ? ??????? --- m 4n 5 l m 44213421324324315415452352346464646=<===???? ? ??? ? ? ? ?→→????→?? ? ? ?? ? ? ? ???????0 3102340031 15406020303535?? ? ? ? ? ? ??? 31234311546233535??? ?? ? ?→ ?? ? ??? m=5=n ，得最优解。解矩阵*00 01000100X 00 0010100010000?? ? ? ?= ? ? ??? 。

怎样计算平板的平面度

怎样计算平板的平面度 1、最近很多朋友都向我咨询铸铁平板的平面度怎么计算，我整理了一些资料不知道对大家有没有帮助；有兴趣的朋友可以参考一下。对于用刀口尺和微米量块检定尺寸较小的平板，其平面度算法比较简单。但是对于大尺寸平板需要用电子水平仪或者自准直仪来检定，其数据处理是比较繁琐，也没有更好的手算方法，通常只能借助程序进行数据处理。对于小铸铁平板，按照米字形测量，其算法如下： a1 a2 a3 b1 b2 b3 c1 c2 c3 测量a1b2c3对角线，在a1、c3位置架设1mm的等高量块，在b2位置塞入恰好能塞入的量块（原理同塞尺），如恰好塞入1.003mm的量块，说明受检点处凹下0.003mm，同理测量米字形的八条线，记下数据。如得到一组测量数据（单位：μm）： a1，b2，c3=0，-3，0 c1，b2，a3=0，-3，0 a1，a2，a3=0，-1，0 b1，b2，b3=0，-1，0 c1，c2，c3=0，-1，0 a1，b1，c1=0，-2，0 a2，b2，c2=0，-2，0 a3，b3，c3=0，-1，0 得到米字形数据表为： 0 -1 0 -2 -3 -2 0 -1 0 平板的平面度为3μm 以上不过这是特例，很多平板的对角线所测得的数据是无法正好重合的，需要以一根对角线为基准，另外七条线采用数据叠加的方法运算，但道理是相通的，如果大家有什么不明白的可以再问我。以下大家可以参考一下啊。 铸铁平板1、范围本标准规定了精度等给为000级、00级、0级、1级、2级、3级铸铁平板的型式与尺寸，技术要求，检验方法，标志与包装等。本标准适用于工作面为160m×100mm～ 4000mm×2500mm（长度×宽度）的铸铁平板（以下简称平板）。2、引用标准下列标准所包含的条文，通过在本标准中引用而构成为本标准的条文，本标准出版时，所示版本均为有效。所有标准都会被修订，使用

割平面法

题目：割平面法及其数值实现 院系：数理科学与工程学院应用数学系 专业：数学与应用数学 姓名学号：*** 1****** *** 1****** *** 1****** *** 1****** 指导教师：张世涛 日期：2015 年 6 月11 日

整数规划与线性规划有着密不可分的关系，它的一些基本算法的设计都是从相应的线性规划的最优解出发的。整数规划问题与我们的实际生活有着密切的联系，如合成下料问题、建厂问题、背包问题、投资决策问题、旅行商问题、生产顺序表问题等都是求解整数模型中的著名问题。所以要想掌握生活中这些解决问题的方法，研究整数规划是必然的路径。用于解决整数规划的方法主要有割平面法，分支定界法，小规模0-1规划问题的解法，指派问题和匈牙利法。本文重要对整数规划中经常用的割平面法加以介绍及使用Matlab 软件对其数值实现。 割平面法从线性规划问题着手,在利用单纯型法的时候,当约束矩阵中出现分数,给出一种"化分为整"的方法。然后在割平面方法来解决整数线性规划的理论基础上,把"化分为整"的方法进行到底，直到求解出最有整数解。 关键词：最优化；整数规划；割平面法；数值实现；最优解；Matlab软件。 Abstract The integer programming are closely related to the linear programming. Some of the basic algorithms of the former are designed from the optimal solution of the corresponding linear programming. What’s more, our daily life has a close relationship with it as well, such as synthesis problem, plant problem, knapsack problem, investment decision problem, traveling salesman problem and production sequence table problems. They are famous questions in solving integer model. So, to study the integer programming is the inevitable way to master the methods of solving these problems in life. The methods used in solving the integer programming include cutting plane method, branch and bound method, and solving the problem of small-scale 0-1 programming, assignment problem and Hungarian method. In this paper, we introduce the cutting plane method and use Matlab to get its numerical implementation in the integer programming. Cutting plane method, giving us a "integrated" method when we meet the constraint matrix scores in the use of simplex method, starts from the linear programming problem. Then, based on the theory of cutting plane method to solve the integer linear programming, we use “integrated” method until the most integer solution is solved. Keywords:Optimization; Integer programming; Cutting plane method; Numerical implementation; Optimal solution; Matlab software.

平面度误差计算(精)

平面度误差计算 第1章、绪论 1.1、引言平面是由直线组成的，因此直线度测量中直尺法、光学准直法、光学自准直法、重力法等也适用于测量平面度误差。测量平面度时，先测出若干截面的直线度，再把各测点的量值按平面度公差带定义利用图解法或计算法进行数据处理即可得出平面度误差。也有利用光波干涉法和平板涂色法测量平面误差的。而基于3坐标测量机（以下简称CMM）的平面度测量和数据处理具有方便、快捷、高效的优势，这是因为3坐标测量机具有通用性强、测量精确高、测量效率高等优点，所以其他测量方法很难与之比拟。 3坐标测量机自从1959年由英国的Fementi公司发明以来，在这近510年的时间里，已经得到了极大的发展。特别是经过近210多年的发展和应用，在机械制造领域已经比较普及。但是随着科技的发展，也不断出现1些需要提高的想法，特别是超精密加工技术的发展，引起更多的构想。而现在随着微机械和纳米的兴起，对3坐标测量机的要求就更是提出了更多的想法，尤其是我国，因为处于发展之中，所以就这些方面，就更应当有个比较合适、周密的思考。例如在坐标测量机出现之前，很多0部件的测量是10分困难的，特别是复杂的0部件的测量，往往采取化整为0的办法，多次定位，逐个尺寸进行测量，尤其是测量时间太长，测量的误差又大，这是可以想象得到的。特别是自动化加工的出现，测量1直被认为是机械制造生产率提高和精度提高的瓶颈。特别是复杂的构件，测量的时间比制造的时间还长，如果百分之百的检测，那是无法想象的。比如汽车的外形测量，更是困难重重。 正是因为3坐标测量机的出现，这种现象便排除了。不仅解决了测量的速度，而且提高了测量的精度，特别是机械加工的换刀机构的移植到测量上，更扩大了功能，这对制造领域提高质量方面引起了很大的促进作用，特别是精密型CNC3坐标测量机(CNC－CMM)，促进了计量的自动化，大幅度提高了测量的效率和精度，并且代替了当前计量室的大部分测量工作，而将测量工作能在生产第1线上得到解决。国内外发展的FMC、FMS的生产线上大部分配置了3坐标测量机，这样就可能在制造1完成，质量也得到了评价，甚至起到质量的监控的作用。例如德国的MTO(发电机涡轮制造厂)的28种复杂0件的加工车间，是以自动化加工为主的，全部产品的检验是由4台Zeiss公司的CMM 组合在1起的测量中心测量，当天生产，当天测量，不仅测量了0件，而且可以发现加工设备的处在什么状态，起到了质量监控的作用。 本文就是在传统测量平面度误差的基础上进1步拓展测量视野，以计算机为依托，使用目前世界上最先进最流行的3坐标测量机进行平面度误差测量。

整数规划(割平面法)

割平面法 求解整数规划问题： Max Z=3x1+2x2 2x1+3x2?14 4x1+2x2?18 x1,x2?0，且为整数 解：首先，将原问题的数学模型标准化，这里标准化有两层含义：（1）将不等式转化为等式约束，（2）将整数规划中所有非整数系数全部转化为整数，以便于构造切割平面。从而有：Max Z=3x1+2x2 2x1+3x2+x3=14 2x1+x2+x4=9 x1,x2?0，且为整数 利用单纯形法求解，得到最优单纯形表，见表1： 表1

最优解为：x1=13/4, x2=5/2, Z=59/4 根据上表，写出非整数规划的约束方程，如：x2+1/2x3-1/2x4=5/2 (1) 将该方程中所有变量的系数及右端常数项均改写成“整数与非负真分数之和”的形式，即：(1+0)x2+(0+1/2)x3+(-1+1/2)x4=2+1/2 把整数及带有整数系数的变量移到方程左边，分数及带有分数系数的变量称到方程右边，得：x2 - x4-2 =1/2-(1/2x3+1/2x4) (2) 由于原数学模型已经“标准化”，因此，在整数最优解中，x2和x4也必须取整数值，所以(2)式左端必为整数或零，因而其右端也必须是整数。又因为x3,x4?0，所以必有： 1/2-(1/2x3+1/2x4)<1 由于(2)式右端必为整数，于是有： 1/2-(1/2x3+1/2x4)?0 (3) 或 x3+x4?1 (4) 这就是考虑整数约束的一个割平面约束方程，它是用非基变量表示的，如果用基变量来表示割平面约束方程，则有： 2x1+2x2?11 (5)

从图1中可以看出，(5)式所表示的割平面约束仅割去线性规划可行域中不包含整数可行解的部 分区域，使点E，2)成为可行域的一个极点。 图1 在(3)式中加入松弛变量x5，得： -1/2x3-1/2x4+x5=-1/2 (6) 将(6)式增添到问题的约束条件中，得到新的整数规划问题： Max Z=3x1+2x2 2x1+3x2+x3=14 2x1+x2+x4=9 -1/2x3-1/2x4+x5=-1/2 x i?0，且为整数，i=1,2,…,5 该问题的求解可以在表1中加入(6)式，然后运用对偶单纯形法求出最优解。具体计算过程见表2： 表2

平面度误差的测量

平面度误差的测量 一、平面度误差的评定方法有； 1. 最小条件法，由两平行平面包容实际被测要素时，实现至少四点或三点接触。且具有下列形式之一者，即为最小包容区域，其平面度误差值最小。最小条件判别方法有下列三种形式。 （1）两平行平面包容被测表面时，被测表面上有3个最低点（或3个最高点）及1个最高点（或1个最低点）分别与两包容平面接触，并且最高点（或最低点）能投影到3个最低点（或3个最高点）之间，则这两个平行平面符合最小条件原则。见图1(a)所示。 （2）被测表面上有2个最高点和2个最低点分别与两个平行的包容面相接触，并且2个最高点投影于2个低点连线之两侧。则两个平行平面符合于平面度最小条件原则。见图1(b)所示。 (3)被测表面的同一截面内有2个最高点及1个低点（或相反）图1 平 面度误差的最小区域判别法 分别和两个平行的包容面相接触。则该两平行平面符合于平面度最小包容区原则，如图1(c)所示。 2.三角形法是以通过被测表面上相距最远且不在一条直线上的3个点建立一个基准平面，

各测点对此平面的偏差中最大值与最小值的绝对值之和为平面度误差。实测时，可以在被测表面上找到3个等高点，并且调到零。在被测表面上按布点测量，与三角形基准平面相距最远的最高和最低点间的距离为平面度误差值。 3. 对角线法是通过被测表面的一条对角线作另一条对角线的平行平面，该平面即为基准平面。偏离此平面的最大值和最小值的绝对值之和为平面度误差。 二、平面度测量步骤 检测:工具：平板、带千分表的测量架等。 检测时，将被测零件放在平板上，带千分表的测量架放在平板上，并使千分表测量头垂直地指向被测零件表面，压表并调整表盘，使指针指在零位。然后，按（图2）所示，将被测平板沿纵横方向均布画好网格，四周离边缘10mm，其画线的交点为测量的9个点。同时记录各点的读数值。全部被测点的测量值取得后，按对角线法求出平面度误差值。 图 2

平面度算法说明

。 1欢迎下载 检测工件平面度算法说明： 1：在基准面上取3个点分别为P1（x1,y1,z1），P2（x2,y2,z2），P3（x3,y3,z3）利用三点成面的公式计算出平面AX+BY+CZ+D=0作为基准平面 注：1、P1的X ，Y 坐标由人工输入，其余点有输入的X ，Y 移动量计算得出 2、所有点的Z 坐标由激光测距仪提供 3、计算平面公式时，须计算出A,B,C,D A=y1*z2-y1*z3-y2*z1+y2*z3+y3*z1-y3*z2; B=-x1*z2+x1*z3+x2*z1-x2*z3-x3*z1+x3*z2; C=x1*y2-x1*y3-x2*y1+x2*y3+x3*y1-x3*y2; D=x1*y2*z3-x1*y3*z2-x2*y1*z3+x3*y1*z2+x2*y3*z1-x3*y2*z1; 2:在计算面上取3个点分别为P4（x4,y4,z4），P5(x5,y5,z5)，P6(x6,y6,z6)利用点到平面的距离公式分别求出D1,D2,D3，然后计算出D1,D2,D3的平方差，通过平方差的大小来判断计算面与基准面之间的平行度 注：1、计算点到面的距离公式是：D=abs(ax0+by0+cz0+d)/sqrt(a*a+b*b+c*c)； 2、计算方差公式为：Avg = （D1+D2+D3）/3 Var = (（D1-Avg ）^2+（D2-Avg ）^2+（D3-Avg ）^2)/3 3、假设Par 为设定的公差，则Par 与Var 之间的转换公式为Var = (4*Par*Par)/9,这 个Var 即为设定的Var 的上限（利用求极限法求出的） 4、程序运行页面显示的测量值为Display = Max （D1,D2,D3）-Min （D1,D2,D3），理由 为Display 在Par 之内才能算计算面的上下浮动的合理范围之内要是Display 大于 Par ，则肯定表示在Par 之内。 基准面

第五章 整数规划练习题答案

第五章 整数规划练习题答案 一. 判断下列说法是否正确 1. 用分枝定界法求解一个极大化的整数规划问题时，任何一个可行整数解的目标函数值是 该问题目标函数值的下界。() 2. 用割平面法求解整数规划时，构造的割平面有可能切去一些不属于最优解的整数解。() 3. 用割平面法求解纯整数规划时，要求包括松弛变量在内的全部变量必须取整数值。() 4. 指派问题数学模型的形式与运输问题十分相似，故也可以用表上作业法求解。() 二. 设有五项工作要分派给五个工人，每人的作业产值如下表所示，为了使总产值最大，问 应如何分配这五项工作，并求得最大产值。 工作 工人 A & B C D E 甲 9 4 6 8 5 \ 乙 8 5 9 10 6 丙 9 7 3 ' 5 8 丁 4 8 6 9 5 戊 10 ； 5 3 6 3 答案： 设原矩阵为A ，因求极大问题，令B=[M-a ij ]，其中M=Max {a ij }=10，则： 16425105 3140 42 13251042510424003B 1 3752102 64 10 154062415151 3045 020305 7470574704646111-?????? ? ? ? ? ? ? ? ? ? =→→- ? ? ?- ? ? ? ? ? ??????? --- m 4n 5l m 4 4 21342132432431541545235234 6 4 64 6 4 6=<===? ??? ? ??? ? ? ? ?→→????→?? ? ??? ? ? ? ???? ? ? ? 031023 4003115406020303535?? ? ? ? ? ? ?? ? 31234311546233 5 3 5? ?? ?? ? ?→ ?? ? ?? ? m=5=n ，得最优解。解矩阵*0001000100X 0000101 00010000?? ? ? ?= ? ? ??? 。

§3.2 Gomory 割平面法

§3.2 G o m o r y 割平面法 1、G o m o r y 割平面法的基本思想 ??? ?? ??≥=为整数向量x x b Ax t s x c T 0..min （P ） ?????≥=0..min x b Ax t s x c T （P 0） 称（P 0）为（P ）的松弛问题。记（P ）和（P 0）的可行区域分别为D 和D 0 , 则 （1）0D D ?； （2）若（P 0）无可行解，则（P ）无可行解； （3）（P 0）的最优值是（P ）的最优值的一个下界； （4）若（P 0）的最优解 0x 是整数向量，则 0x 是（P ）的最优解。 基本思想： （1）用单纯形法求解松弛问题（P 0），若（P 0）的最优解 0x 是整数向量， 则 0x 是（P ）的最优解。计算结束。 (2) 若（P 0）的最优解 0x 不是整数向量，则对松弛问题（P 0）增加一个 线性约束条件（称它为割平面条件）， 新增加的约束条件将（P 0）的行区域D 0割掉一块，且这个非整数向量 0x 恰在被割掉的区域内，而原问题（P ）的任何一个可行解（格点）都没有被割去。记增加了割平面的问题为（P 1）， 称（P 1）为（P 0）的改进的松弛问题。 （3）用对偶单纯形法求解（P 1），若（P 1）的最优解 1x 是整数向量，则 1x 是（P ）的最优解。计算结束。否则转（2）

割平面的生成： 对给定的（P ）， 用单纯形法求解它的松弛问题（P 0），得到（P 0）的最优基 本可行解 0x ，设它对应的基为 ),,(1m B B A A B Λ=， m B B x x ,,1Λ为 0x 的基变量，记基变量的下标集合为 S ，非基变量的下标集合为 S 。则松弛问题（P 0）的最优单纯形表为 ∑∈=+S j j j z x z 0ξ m i b x a x S j i j ij B i ,,1,Λ==+∑∈ （3.2.1） 为了使符号简便，令 000,,0z b a z x j j B ===ξ。如果 m i b i ,,1,0,Λ= 全 是整数，则 0x 是（P ）的最优解。计算结束。否则至少有一个 l b 不是整数 )0(m l ≤≤，设 l b 所对应的约束方程为 , ∑∈=+S j l j lj B b x a x l （3.2.2） 用 ][a 表示不超过实数 a 的最大整数，则 ,][, , ][l l l lj lj lj f b b S j f a a +=∈+= （3.2.3） 其中，lj f 是 lj a 的分数部分，有 S j f lj ∈<≤,10， l f 是 l b 的分数部分， 有 .10<≤l f 由于在（3.2.2）中的变量是非负的，因此有 ∑∑∈∈≤S j j lj S j j lj x a x a ][ （3.2.4） 所以由（3.2.2）得 , ][∑∈≤+S j l j lj B b x a x l （3.2.5） 因为在ILP 中 x 限制为整数向量，故（3.2.5）的左端为整数，所以右端用 l b 的整数部分去代替后，（3.2.5）式的不等式关系仍成立，即

位置度平面度的定义标注及测量

位置度平面度的定义标注及测量 笔者在数年建筑工程施工图审查工作中，通过多项建筑工程的施工图审查，发现了建筑设计中总平面图设计、建筑说明、建筑平面、立面、剖面、建筑构件有关深度设计及强制性条文等内容设计中较为常见的问题，现分别总结如下:一、总平面布置图送审的施工图文件中，总平面布置图基本上都有，但表达深度差别较大，大部分工程只做到平面定位图，不符合《建筑工程设计文件编制深度规定》的有关要求。主要问题有:1.总平面图要有一定的范围。只有用地范围不够，要有场地四邻原有规划的道路、建筑物、构筑物，多数施工图只有用地范围内的布置图。2.保留原地形和地物。场地测量坐标网及测量标高，包括场地四邻的测量坐标或定位尺寸，有些工程的总图设计往往无保留。3.竖向设计。往往只有标注建筑物的±0.000 设计标高的相对场地的测量标高数值，有的只有标注室内外高差数而已。结果是:1竖向设计标高不符合规划部门的控制标高。2场地内与场地外围的城市道路标高不衔接，不合理。3场地及其道路的标高不利于排水。4场地内道路无设计标高，特别是交接处、建筑物的入口处，也无标注道路坡长、坡向、坡度以及地面的关键性标高，也无路面的设计断面。4.没土方工程平衡设计。盲目的竖向设计，往往会带来不必要的挖方或填方，增加造价，造成经济损失。5.总图设计没有必要的详图设计。比如道路横断面、路面结构，反映管线上下、左右尺寸关系的剖面图，以及挡土墙、护坡排水沟、广场、活动场地、停车场、花坛绿地等详图，场地的排水、场地内道路与城市道路的关系，给施工带来困难，也无法保证总图的合理性。 6.消防车道宽度不满足消防要求。消防车道距离高层建筑外墙小于5 米，不满足消防登高面要求。二、建筑设计说明部分1.装饰做法光是文字说明表达不完整。最好是有各种材料做法一览表各部位装修材料一览表方能完整地表达清楚，少数能做到，多数工程还只是文字说明。总说明中占地面积一般都缺标注。2.门窗表。一般都有，但关键对一些组合窗，非标准窗表示不清楚，对组合窗及非标窗，应画出立面图，并应把拼接件选择、固定件、窗扇的大小、开启方式等内容标注清楚，如组合窗面积过大，请注明要经有资质的门窗生产厂家设计方可，还有就是对门窗性能，如防火、隔声、抗风压、保温、空气渗透、雨水渗透等技术要求应加以说明。比如建筑物1-6 层和七层及七层以上对门窗气密性要求不一样1-6 层为3 级，七层及以上为 4 级。3.防火设计说明普遍存在问题。按《建筑工程设计文件编制深度规定》要求每层建筑平面中要注明防火分区面积和分区分隔位置示意图，宜单独成图，如为一个防火分区，可不注防火分区面积。4.有关夏热冬冷地区节能设计的说明，也普遍存在问题居住建筑的节能设计:1外窗，特别东西窗缺保温隔热措施。2导热系数的主体部位值与平均值概念不清，把建筑主体部位的K 值作为平均K 值说明。3缺节能设计计算书及节能设计审查文件，造成节能设计不经济。5.幕墙工程。包括玻璃幕墙、金属幕墙、石材幕墙等及特殊的屋面工程，与其它特殊构造，对其设计、制作、安装等技术要求未加说明。6.缺电梯自动扶梯，选择及性能说明包括功能、载重量、速度、停站数、提升高度等等。 7.墙体预留孔及楼板预留孔，管道井楼层的封堵方式等未说明。 8.屋面防水等级未说明，或屋面具体做法不符合相应的防水等级要求。常见问题为:把屋面砼结构层作为一道防水设防，或卷材厚度不符合相应防水等级要求

第章整数规划割平面法

第章整数规划割平面法 This manuscript was revised on November 28, 2020

割平面法 求解整数规划问题： Max Z=3x1+2x2 2x1+3x214 4x1+2x218 x1,x20，且为整数 解：首先，将原问题的数学模型标准化，这里标准化有两层含义：（1）将不等式转化为等式约束，（2）将整数规划中所有非整数系数全部转化为整数，以便于构造切割平面。从而有：Max Z=3x1+2x2 2x1+3x2+x3=14 2x1+x2+x4=9 x1,x20，且为整数 利用单纯形法求解，得到最优单纯形表，见表1： 表1

最优解为：x1=13/4, x2=5/2, Z=59/4 根据上表，写出非整数规划的约束方程，如：x2+1/2x3-1/2x4=5/2 (1) 将该方程中所有变量的系数及右端常数项均改写成“整数与非负真分数之和”的形式，即：(1+0)x2+(0+1/2)x3+(-1+1/2)x4=2+1/2 把整数及带有整数系数的变量移到方程左边，分数及带有分数系数的变量称到方程右边，得： x2 - x4-2 =1/2-(1/2x3+1/2x4) (2)由于原数学模型已经“标准化”，因此，在整数最优解中，x2和x4也必须取整数值，所以(2)式左端必为整数或零，因而其右端也必须是整数。又因为x3,x40，所以必有： 1/2-(1/2x3+1/2x4)<1 由于(2)式右端必为整数，于是有： 1/2-(1/2x3+1/2x4)0 (3) 或 x3+x41 (4)

这就是考虑整数约束的一个割平面约束方程，它是用非基变量表示的，如果用基变量来表示割平面约束方程，则有： 2x1+2x211 (5) 从图1中可以看出，(5)式所表示的割平面约束仅割去线性规划可行域中不包含整数可行解的部分区域，使点E，2)成为可行域的一个极点。 图1 在(3)式中加入松弛变量x5，得： -1/2x3-1/2x4+x5=-1/2 (6) 将(6)式增添到问题的约束条件中，得到新的整数规划问题： Max Z=3x1+2x2 2x1+3x2+x3=14 2x1+x2+x4=9 -1/2x3-1/2x4+x5=-1/2 x i 0，且为整数，i=1,2,…,5 该问题的求解可以在表1中加入(6)式，然后运用对偶单纯形法求出最优解。具体计算过程见表2： 表2

第五章 整数规划练习题答案

第五章 整数规划练习题答案 一. 判断下列说法是否正确 1. 用分枝定界法求解一个极大化的整数规划问题时，任何一个可行整数解的目标函数值是 该问题目标函数值的下界。() 2. 用割平面法求解整数规划时，构造的割平面有可能切去一些不属于最优解的整数解。() 3. 用割平面法求解纯整数规划时，要求包括松弛变量在内的全部变量必须取整数值。() 4. 指派问题数学模型的形式与运输问题十分相似，故也可以用表上作业法求解。() 二. 设有五项工作要分派给五个工人，每人的作业产值如下表所示，为了使总产值最大，问 应如何分配这五项工作，并求得最大产值。 工作 工人 A B C D E 甲 9 4 6 8 5 乙 8 5 9 10 6 丙 9 7 3 5 8 丁 4 8 6 9 5 戊 10 5 3 6 3 答案： 设原矩阵为A ，因求极大问题，令B=[M-a ij ]，其中M=Max {a ij }=10，则： 16425105 3140 42 13251042510424003B 1 3752102 6410 1540 62 415151 3045 020305 7470574704646111-?????? ? ? ? ? ? ? ? ? ? =→→- ? ? ?- ? ? ? ? ? ??????? --- m 4n 5l m 4 4 21342132432431541545235234 6 4 64 6 4 6=<===? ??? ? ??? ? ? ? ?→→????→?? ? ??? ? ? ? ???? ? ? ? 031023 4003115406020303535?? ? ? ? ? ? ???

平面度算法说明

检测工件平面度算法说明： 1：在基准面上取3个点分别为P1（x1,y1,z1），P2（x2,y2,z2），P3（x3,y3,z3）利用三点成面的公式计算出平面AX+BY+CZ+D=0作为基准平面 注：1、P1的X，Y坐标由人工输入，其余点有输入的X，Y移动量计算得出 2、所有点的Z坐标由激光测距仪提供 3、计算平面公式时，须计算出A,B,C,D A=y1*z2-y1*z3-y2*z1+y2*z3+y3*z1-y3*z2; B=-x1*z2+x1*z3+x2*z1-x2*z3-x3*z1+x3*z2; C=x1*y2-x1*y3-x2*y1+x2*y3+x3*y1-x3*y2; D=x1*y2*z3-x1*y3*z2-x2*y1*z3+x3*y1*z2+x2*y3*z1-x3*y2*z1; 2:在计算面上取3个点分别为P4（x4,y4,z4），P5(x5,y5,z5)，P6(x6,y6,z6)利用点到平面的距离公式分别求出D1,D2,D3，然后计算出D1,D2,D3的平方差，通过平方差的大小来判断计算面与基准面之间的平行度 注：1、计算点到面的距离公式是：D=abs(ax0+by0+cz0+d)/sqrt(a*a+b*b+c*c)； 2、计算方差公式为：Avg = （D1+D2+D3）/3 Var = (（D1-Avg）^2+（D2-Avg）^2+（D3-Avg）^2)/3 3、假设Par为设定的公差，则Par与Var之间的转换公式为Var = (4*Par*Par)/9,这个Var 即为设定的Var的上限（利用求极限法求出的） 4、程序运行页面显示的测量值为Display = Max（D1,D2,D3）-Min（D1,D2,D3），理由为 Display在Par之内才能算计算面的上下浮动的合理范围之内要是Display大于Par， 则肯定表示在Par之内。 基准面

分支定界法和割平面法

分支定界法和割平面法 在上学期课程中学习的线性规划问题中，有些最优解可能是分数或消失，但现实中某些具体的问题，常要求最优解必须是整数，这样就有了对于整数规划的研究。 整数规划有以下几种分类：（1）如果整数规划中所有的变量都限制为（非负）整数，就称为纯整数规划或全整数规划；（2）如果仅一部分变量限制为整数，则称为混合整数规划；（3）整数规划还有一种特殊情形是0-1规划，他的变量取值仅限于0或1。本文就适用于纯整数线性规划和混合整数线性规划求解的分支定界法和割平面法，做相应的介绍。 一、分支定界法 在求解整数规划是，如果可行域是有界的，首先容易想到的方法就是穷举变量的所有可行的整数组合，然后比较它们的目标函数值以定出最优解。对于小型问题，变量数量很少，可行的整数组合数也是很小时，这个方法是可行的，也是有效的。而对于大型的问题，可行的整数组合数很大时，这种方法就不可取了。所以我们的方法一般是仅检查可行的整数组合的一部分，就能定出最有的整数解。分支定界法就是其中一个。 分枝定界法可用于解纯整数或混合的整数规划问题。在二十世纪六十年代初由Land Doig 和Dakin 等人提出。由于这方法灵活且便于用计算机求解，所以现在它已是解整数规划的重要方法。目前已成功地应用于求解生产进度问题、旅行推销员问题、工厂选址问题、背包问题及分配问题等。 设有最大化的整数规划问题A ，与它相应的线性规划为问题B ，从解问题B 开始，若其最优解不符合A 的整数条件，那么B 的最优目标函数必是A 的最优目标函数z *的上界，记作z ；而A 的任意可行解的目标函数值将是z *的一个下界z 。分枝定界法就是将B 的可行域分成子区域再求其最大值的方法。逐步减小z 和增大z ，最终求到z *。现用下例来说明： 例1 求解下述整数规划 219040Max x x z += ??? ??≥≥+≤+且为整数0,7020756792 12121x x x x x x 解 （1）先不考虑整数限制，即解相应的线性规划B ，得最优解为： 124.81, 1.82,356 x x z === 可见它不符合整数条件。这时z 是问题A 的最优目标函数值z *的上界，记作z 。而X 1=0，X 2=0显然是问题A 的一个整数可行解，这时0=z ，是z * 的一个下界，记作z ，即0≤z *≤356 。 （2）因为X 1X 2当前均为非整数，故不满足整数要求，任选一个进行分枝。设选X 1进行分枝，于是对原问题增加两个约束条件： [][]114.814, 4.8115 x x ≤=≥+= 于是可将原问题分解为两个子问题B 1和B 2（即两支），给每支增加一个约束条件并不影响问题A 的可行域，不考虑整数条件解问题B 1和 B 2 ，称此为第一次迭代。得到最优解

平面度误差最小区域新算法——有序判别法(精)

平面度误差最小区域新算法——有序判别法 核心提示：中文摘要：提出一种平面度误差最小区域新算法--有序判别法.该方法以最小区域准则为基础,直接以排序的高点和低点构成的初始评定平面进行最小包容区域的判定和搜索,最终求得平面度误差值.该方法易于理解和掌握,搜索判别有序.实例运算表明,首轮搜索成功率高、速度快. 1998 年 1 月计量... 中文摘要：提出一种平面度误差最小区域新算法--有序判别法.该方法以最小区域准则为基础,直接以排序的高点和低点构成的初始评定平面进行最小包容区域的判定和搜索,最终求得平面度误差值.该方法易于理解和掌握,搜索判别有序.实例运算表明,首轮搜索成功率高、速度快. 1998 年 1 月计量学报平面度误差最小区域新算法 ???有序判别法张之江于瀛洁张善钟 (哈尔滨工业大学机电学院 ,哈尔滨150001) 摘要提出一种平面度误差最小区域新算法 ???有序判别法。该方法以最小区域准则为基础 ,直接以排序的高点和低点构成的初始评定平面进行最小包容区域的判定和搜索 ,最终求得平面度误差值。该方法易于理解和掌握 ,搜索判别有序。实例运算表明 ,首轮搜索成功率高、速度快。关键词 : 平面度最小区域法误差本文于 1996 - 04 - 03 收 到 ,1997 - 05 - 11 修改收到。目前对平面度误差最小区域算法研究有不少〔1 - 3〕。通常 ,由于某些算法物理几何概念不够清晰 ,层次不明 ,搜索盲目性大 ,既影响运算速度又影响读者对方法的掌握和理解 ,不利于方法在实际中应用。为此 ,作者提出一种新的平面度误差最小区域算法 ???有序判别法。为使平面度误差计算结果精确唯一 ,其根本问题是要确定符合最小区域的两个包容平面。判别包容所有测量数据的两平行平面是否符合最小区域 ,有三条判别准则〔4 ,5〕,即 : (1)三角形准则 (图 1a) 两平行平面之一至少含有三个等值最高 (低) 点 ,另一平面至少含有一个最低 (高)点 ,且该最低 (高)点的投影在三个等值最高 (低)点组成的三角形之内。 (2)交叉准则 (图 1b) 两平行平面之一至少含有两个等值最高点 ,另一个平面至少含有两个等值最低 点 ,且前两点连线的投影与后两点连线互相交叉。 (3)直线准则 (图 1c) 两平行平面之一至少含有一个最高 (低) 点 ,另一平面至少含有两个等值最低(高)点 ,且该最高 (低)点的投影处于两等值最低 (高)点的连线上。图 1 当符合上述三条准则中的任一条时 ,则包容所有测量数据的两平行包容面便为符合最小转载区域的包容面。先求各采样点偏差值的最小二乘平面方程 ,设该平面方程为 :则各采样点到最小二乘平面的沿 z 轴的距离Δz i 为 :Δz i = z i - ( ax + by + c) (2)式中 z i 为各采样点的偏差值。然后以最小二乘平面为分界面 ,将采样点区分为高点和低点。即将Δz i > 0 的点 ,也就是位于最小二乘平面上方的点称为高点 ;将Δz i < 0 的点 ,也就是位于最小二乘平面下方的点称为低点。对各高点 (Δz i > 0 的点) 按高低次序排序。高的点(Δz i 值大的点) 在前 ,低的点 (Δz i 值小的点) 在后。对于等高的点 ,即Δz i 值相同的点 ,则按该点离最高点位置远近排序 ,远的排在前 ,近的排在