关于Steiner问题的一个注记——连接五点之最小网络的一种寻优方案

本文讨论如何寻找连接平面上五个给定点的最小网络这一问题．通过发展越民义证明Pollack在1978年所给出的一个关于寻找连接平面上四个给定点的最小网络的重要结论的方法,我们给出了一个采用简单几何作图方法快速求解该问题的方案．     

平面上的点-线选址问题

本文研究两类平面选址问题：（1）求一直线到n个给定点的加权距离和为最小；（2）求一点到n条给定直线的加权距离和为最小，对这两个非线性最优化问题，欠给出迭代次数为多项式的算法。     

平面上的min-max型点-线选址问题

本文研究两类平面选址问题：(1)求一直线到n个给定点的最大加权距离为最小；(2)求一点到n条给定直线的最大加权距离为最小．对这两个非线性优化问题，我们给出最优解的刻划及迭代次数为多项式的算法．     

干线网络的选址问题研究

考虑平面上和三维空间中同时确定多条干线的干线网络选址问题.对于平面上情形,通过最小化每个点到离它最近干线的加权距离之和,给出了一种有限步终止算法和基于k-means聚类分析、加权全最小一乘和重抽样方法的线性类算法;对于空间情形,给出了线性聚类算法.通过计算机仿真说明以上算法可以有效地确定平面和空间中干线网络位置.     

平面凸集存在最小凸生成集的充要条件

本文在平面上解决了StevenRLay在 [1 ]中提出的开放性问题“什么样的凸集存在唯一的最小凸生成子集” ,给出并证明了“平面上的凸集存在唯一的最小凸生成子集”的一个充要条件 .同时证明了En 中的开集一定不存在最小凸生成集 .     

三角形费马点的再推广

1问题的提出1640年,费尔马提出如下问题:“在平面上给出A、B、C三点,求一点P使距离和PA+PB+PC达到最小.”这就是数学史上著名的“费尔马问题”.特别地,点A、B、C三点不共线时,使PA+PB+PC最小的点P称为△ABC的费尔马点.文[1]把费马点问题推广到“两定点、一条定直线”的情形,下面笔者再对“费马点”问题做出如下推广:推广一在平面内,已知三条定直线l1、l2、l3,在平面内求一点P,使点P到直线l1、l2、l3的距离之和最小.     

三个点的加权点组的费马问题

平面上三个点的加权点组的费马问题是 :A、B、C是平面上三个定点 ,设 a′、b′、c′是非负实数 ,在平面上试求点 P,使F =a′ PA b′ PB c′ PC为最小 .当 a′=b′=c′=1时即为法国数学家费马 ( Fermat,1 6 0 1～ 1 6 6 5)于 1 6 40年前后向意大利物理学家托里拆里 ( Torricelli,1 6 0 8～1 6 47)提出的问题 ,通常被人们称之为平面上给定三点的费马问题 .对于平面上三个点的加权点组的费马问题 ,人们有过许多研究 ,可参阅文献 [1 ]～[4 ],但据笔者所知 ,其结论多用模拟力学机构给以说明 ,未见到纯几何解答 .在本文中 ,笔者用纯几何…     

Worm Problem的一个新上界

1966年,Leo Moser提出了一个基本的几何问题,即Worm Problem．该问题是指:在平面上寻找一个面积最小的(凸)区域,使得任何一条长为1的平面曲线都能够通过旋转和平移完全放入该(凸)区域之中．对于要寻找的区域是凸的情形,本文将把目前所知道的最小的上界由0．2738086降低至0．270911861．在最后一部分,我们推广了Worm Problem,并初步给出了一些相应的结果．     

双会议服务器选址问题研究

中位选址问题一直是管理学科的研究热点,本文考虑平面点集选址问题中的双会议服务器选址问题,该问题可以看成是2中位问题的衍生问题。令P为平面上包含n个点的点集,双会议服务器选址问题即为寻找由该点集构成的一棵二星树,使得这棵树上所有叶子之间的距离和最小。本文给出求解该问题的关键几何结构和最优解算法设计,并证明所给算法时间复杂性为O(n³logn)。     

费尔马定理的又一证法及费马点轨迹初探

“最短网络”问题 ,是美国贝尔电话公司收费时所遇到的 .它的历史可以追溯到费马 .1 640年 ,费马提出如下问题 :在平面上给出Ａ ,Ｂ ,Ｃ三点 ,求一点Ｓ使距离和ＳＡ +ＳＢ+ＳＣ达到最小 .该问题引起科学家的兴趣 .其证明方法多种多样 .但这些方法大多限于几何[1] .本文巧妙地利用初等数学中对称的思想 ,给出费马定理的一个简单证法 ,并由此探讨费马点的轨迹 ,最后给出一种特殊“最短网络”的铺设构想 .现将上述的三角形两个顶点Ａ ,Ｂ放置在直角坐标系中 ,且Ａ ,Ｂ在Ｘ轴同侧 ,记在Ａ ,Ｂ及Ｘ轴同侧求一点Ｓ ,使Ｓ到Ａ ,Ｂ及Ｘ轴的距离最短…     

广义斯坦纳问题与六角坐标

斯坦纳问题是图论中的一个古老问题。它可表述如下:在平面上给定n个点a_1,a_2,…,a_n的集合A,求作连通图G=G(V,E),使在某种距离下,图的总长为最小。G必然是棵树,被称作给定集A上的这种距离下的斯坦纳最小树,简记为SMT。本文只限于研究欧氏距离。首先我们给出一些基本定义及已知结果。 A中的点称为给定点,集S(=V-A)中的点称为附加点,并记之为s_1,s_2,…,s_m。若     

例谈轨迹圆的条件与应用

<正>满足什么样的条件的点的轨迹是圆?平面内与定点距离等于定长的点的轨迹是圆;平面内与两个定点距离之比为不等于1的正数的点的轨迹也是一个圆.在解题中也常会遇到一些轨迹是圆的问题,本文拟通过一些实例来谈谈轨迹圆的条件与应用.一、阿波罗尼斯圆:平面内与两个定点距     

连接主干道的多站点线路规划

将平面上多个已知站点和一条主干道相连接,使线路总长度最小,这是具有广泛应用的线路规划问题.文章从研究两点问题和三点结构的基础模型入手,设计出多站点线路规划树的优化调整方法.进一步构造出以整体调整为特征的定位反演算法,具有计算量小,操作方便的优点.     

空间定点的阳光投影轨迹及其应用

在直角坐标系中利用圆锥曲面理论讨论空间定点在地平面上的阳光投影轨迹,得到轨迹的四种主要基本性状:直线、双曲线、抛物线、椭圆,基本性状由太阳赤纬和观测点所处纬度决定,离心率等于cosβ/sin|γ|.首先,推导空间定点在地平面上的阳光投影轨迹是圆锥曲线,并确定投影轨迹的理论方程或函数;其次,基于实际数据资料利用最小二乘法得到影子定位模型;最后,利用影子定位模型解决两个问题.     

圆的基本问题(上)

<正>圆是平面内到定点的距离等于定长的点的集合.这个定点是该圆的圆心,定长是该圆的半径.只要圆心与半径确定了,该圆也就确定了.因此,找圆心和确定半径是圆的基本问题.不共线的三点可以确定一个圆.圆是轴对称图形,也是中心对称图形.1.圆的基本问题例1在平面上设法找出2017个点,使这些点中的任何三点都不共线.分析由圆的定义及不在一直线上的三点决定一个圆的结论可知,一个圆上任何三点都不共线.因此,我们可得如下解法:     

带有模糊容量限制的网络中的最佳最小费用最大流

本文主要讨论当网络中的弧容量限制和最大流目标要求带有模糊性时的最小费用最大流问题，通过构造带费用的增量网络并设法寻找其中的最佳最小费用路，给出了求解这类模糊网络流问题的算法。     

有向网络中具有一个枢纽点的最小支撑树的计算方法

对有向网络中具有一个枢纽点的支撑树的问题和性质进行了研究,给出了在有向网络图中寻找以某一定点为枢纽点的最小支撑树的计算方法,并对算法的复杂性进行了讨论,最后将该算法应用于实际算例的计算．     

圆的一个性质的探求

一、问题的提出在高级中学课本《平面解析几何》(必修 )第 68页上有这样一道例题 :已知一曲线是与两个定点Ｏ(0 ,0 )、Ａ(3 ,0 )距离的比为12 的点的轨迹 ,求这个曲线的方程 ,并画出曲线 .课本中给出本题的答案是 :所求的轨迹方程为 (ｘ+ 1) 2 +ｙ2 =4,它是以Ｃ(-1,0 )为圆心 ,ｒ =2为半径的圆 (如图 ) .一般地 ,我们还可以证明 :与两个定点Ｍ1 、Ｍ2 距离的比是一个常数ｍ(ｍ >0 ,ｍ≠ 1)的动点轨迹是一个圆 (证明从略 ) .现在我们要思考的问题是 ,这两个定点及定比与所得的圆是什么关系 ?对于一个圆 ,是否一定存在一对点 (唯一还是无穷多…     

带次模惩罚和随机需求的设施选址问题

考虑带次模惩罚和随机需求的设施选址问题,目的是开设设施集合的一个子集,把客户连接到开设的设施上并对没有连接的客户进行惩罚,使得开设费用、连接费用、库存费用、管理费用和惩罚费用之和达到最小. 根据该问题的特殊结构,给出原始对偶3-近似算法. 在算法的第一步,构造了一组对偶可行解;在第二步中构造了对应的一组原始整数可行解,这组原始整数可行解给出了最后开设的设施集合和被惩罚的客户集合. 最后,证明了算法在多项式时间内可以完成,并且算法所给的整数解不会超过最优解的3倍.     

混合整数二次规划问题的全局最优性条件

本文给出了混合整数二次规划问题的全局最优性条件,包括全局最优充分性条件和全局最优必要性条件.我们还给出了一个数值实例用以说明如何利用本文所给出的全局最优性条件来判定一个给定点是否是全局最优解.