（运筹学与控制论专业论文）平面上的点线选址问题.pdf

摘要 选址问题，就是关于为需要设置的“设施”选择最优位置的问题选址 问题是一个有广泛现实意义的最优化问题，从2 0 世纪6 0 年代以来，受到 运筹学专家、管理专家、经济专家、军事专家、城市规划师、工程师等各方面 人士的关注，得到了迅猛发展 传统的选址问题考虑点到点距离意义下的服务点选择本文考虑点到直 线距离意义下的干线或设施位置选择我们主要研究了四个平面上的点线 选址问题a ，b ，c ，d 问题a 是求一直线到i t 个给定点的加权距离和为最 小，问题b 是求一点到竹条蛤定直线的加权距离和为最小问题c 是求一 直线到竹个给定点的最大加权距离为最小，问题d 是求一点到，l 条给定 直线的最大加权距离为最小 问题a 和问题b 是对偶问题我们发现问题a 和问题b 有很好的对 偶性质：问题a 的最优解可在某两个给定点的联线中找到：问题b 的最优 解可在某两条给定直线的交点中找到问题c 和问题d 也是对偶问题问 题c 和问题d 也有很好的对偶性质：在问题c 中，对应于一条最优直线， 至少存在三个“临界点”；在问题d 中，对应于一个最优点，至少存在三条 “临界直线”基于这种性质，这四个非线性优化问题便转化为组合问题，从 而得到迭代次数为多项式的算法 我们还研究了问题a ，b ，c ，d 的一些推广及两个“讨厌型”的中心选址 问题我们在最后提出了值得进一步研究的两个网络上的干线选址问题， 即问题e 和问题f 关键词：平面选址，点。线距离，最小最大，多项式算法 a b s t r a c t l o c a t i o np r o b l e m sa r ep r o b l e m sw i t hr e g a r dt o s e l e c t i n go p t i m a ls i t e sw h e r ef a c i l i t i e ss h o u l d b el o c a t e d l o c a t i o n p r o b l e m sa r eo p t i m a lp r o b l e m sc o m b i n e dw i t hr e a l i t ya n db ef o l l o w e dw i t h i n t e r e s tb yo p e r a t i o nr e s e a r c h e r s ，m a n a g e r s ，e c o n o m i s t s ，s t r a t e g i s t s ，u r b a n p l a n e r sa n de n g i n e e r s s i n c e1 9 6 0 s t h er e s e a r c ho nl o c a t i o np r o b l e m sd e v e l o p sr a p i d l yt h e s ey e a r s t h et r a d i t i o n a ll o c a t i o np r o b l e m ss t u d yl o c a t i o np r o b l e m sw i t hd i s t a n c ef r o mp o i n tt op o i n t w ec o n s i d e rl o c a t i o np r o b l e m sw i t hd i s t a n c ef r o mp o i n tt ol i n e w em a i n l yd i s c u s sf o u rp o i n t l i n el o c a t i o np r o b l e m si nt h ep l a n e f o u o w s ：p r o b l e ma i st od e t e r m i n eas t r a i g h t l i n et om i n i m i z et h et o t a lw e i g h t e dd i s t a n c e sf r o mng i v e np o i n t s ；p r o b l e mb i st od e t e m l i n ea p o i n tt om i n i m i z et h et o t a l w e i g h t e dd i s t a n c e sf r o m ng i v e ns t r a i g h t l i n e s ；p r o b l e mci st od e t e r m i n ea s t r a i g h t l i n et om i n i m i z et h em a x i m u mw e i g h t e dd i s t a n c e sf r o mng i v e np o i n t s ；p r o b l e mdi st o d e t e r m i n eap o i n tt om i n i m i z et h em a x i m u n l w e i g h t e dd i s t a n c e sf r o mng i v e ns t r a i g h t l i n e s p r o b l e maa n dp r o b l e mba md u a l t h e yh a v ead u a l p r o p e r t yt h a ta no p t i m a ls o l u t i o no f p r o b l e ma c o u l db eas t r a i g h t - l i n ec o n n e c t i n gt w og i v e np o i n t sa n da no p t i m a ls o l u t i o no f p r o b - l e mbc o u l db ea p o i n to fi n t e r s e c t i o no ft w og i v e ns t r a i g h t l i n e s p r o b l e mca n dp r o b l e md a r e a l s od u a l t h e yh a v ead u a lp r o p e r t yt h a tt h e r e 啪a tl e a s tt h r e e “c r i t i c a lp o i n t s ”c o r r e s p o n d i n gt o a no p t i m a ls t r a i g h t l i n ei np r o b l e mca n dt h e r e 啪a t l e a s tt h r e e “c r i t i c a ls t r a i g h t l i n e s ”c o r r b s p o n d i n gt o a l lo p t i m a lp o i n ti np r o b l e md f r o mt h e s ep r o p e r t i e s ，t h e s ef o u rn o n l i n e a r p r o b l e m sc o u l db et m n s f o r n m di n t oc o m b i n a t o r i a lp r o b l e m sa n dc o u l db es o l v e db ya l g o r i t h m sw i t h p o l y n o m i a l t i m ei m r a f i o n s w ea l s oc o n s i d e rt w oo b n o x i o u sc e n t e rp r o b l e m sa n ds o n l 8p r o b l e m sr e l a t e dt op r o b l e m sa ， b ，ca n dd a tl a s t ，w ep o s et w op r o b l e m so ns e l e c t i n go p t i m a lp a t hi nn e t w o r k s k e yw o r d s ：p l a n a rl o c a t i o n ，p o i n t l i n ed i s t a n c e ，m i n n l a x 。p o l y n o m i a la l g o r i t h m 第一章引言 第一节选址问题 选址问题，就是关于为需要设置的“设施”选择最优位置的问题人们经常在某种 系统中设置一个( 或多个) 集散物费、传输信息或执行菜种服务的。中心”。饲如物流管 理中的配送中心、通迅系统中的交换台站以及自来水厂、医院、核电站等。自然应考虑 选在什么位置才能使得系统的运行效船最佳选址问题是一个特殊类型的最优化问 题，属于非线性规划和组合最优化的研究范圈，但是。由于它本身的特点。存在单独研 究之必要 选址闽题可分为两种基本类型；连续裂( 中心及连线都可以在平面上连续变动) 和 离散型( 中心及连线只在网络的有限个点和边中选择) 前者也称为平面上的选址问 蘧，其研究方法多属徽积分及数学规期方面；后者也称为两络上的选垃阊题。其研究方 法与组合分析密切相关 选址问题是一个有广泛现实：t 义的同题( 参见 1 ) 在许多工程设计管理中，或者 某一系统的设计本身就是一个典型的选址问题。或者以选址问题作为一个子问题一 般意义下的选址问题可能是非常复杂的，涉及到自然的、社会的、时间的、空间的各种 复杂条件。还有 牟多未解决的闻题。我们下厦只介绍几种有明确的数学模型和切实可 行的解法的典型选址问题( 参见 2 卜一 6 】) 它们虽然是静态的、单日标的、确定性的， 但它们是处理其它动态的、多目标的、随机的实际选址问舔的基萄i l 平面欧氏距离单中位问题是求平面上的一点，使它到各给定点的加权距离和为最 小对于这个问题，有如下结论： 定理1 1 若给定点不是最优点。则唯一的最优点就是平街点( 逗留点) 2 】对这个问题的性质和解法作了概括，对日标函数及其梯度的力学、几何及解析 的意义结合起来进行了讨论，并论述了静力模拟法帮切铡法模拟法用力学方法为数 学方法的推导提供了思路切制法根据中位点在各给定点的凸包内这一明显的结论， 用几何作图法实现迭代法的逼近过程， 【2 。 7 讨论了有约束的平面欧氏距离单中位问题除了欧氏距离的情形，也有人 1 讨论矩式疆瓷鹣平鬻肇孛位l 薅蘸 对于平筒p 中位问题，由予它的目标函数既非凸又非凹。所以它难解得多，还没有 较理想的解法保证收敛列一个整体瘴优解察用中较好的方法箍a i a ( 交替谶址一分 配) 法裙分技是赛法【8 】，【9 】讨论了“嚣标”阉凌耀蔓联系的乎嚣多中位阅题 平面单中心问题是求平筒上一点，使它到各给定点的最火加权躐离为最小在税 乎蔑戆馕形，骞鲤下绫论： 定理1 2 点x 是最优解的究要条件：x 。是下述两种圆( 称为“界限锻”) 的圆 心 ( 1 ) 存畿三个给定点a 每，m ：及a 靠。使褥蝎磁参嚣为锐是三角形。且其处接圜包 含所有给定点 ( 2 ) 存在嚣令绘怒焘磊冬发鑫，使褥1 2 圭鑫掣晦荛耋绞懿整惫食鼹豢瓣绘定纛 对于权不平凡的情形，有类似的结论 辩予“嚣椽”翔蠢穗互袋装浆多碍聿舀阕嚣，有与其簿价秘糟模登 姆平面上的中位f 刚匿与巾心闯题对应。也有网络上的中位问题姆中心问题。其中 网络上两点阊距离怒指网络上两点问最短路的长度 阚终上骢单孛位阕囊是求嬲肇上一点，搜宅到各缭定点的加权暇襄之和为囊小 关于这个问勰。有如下两个性质( 参见【1 0 ，【1 1 】) 定理1 。3纛傀熹一怒胃渡在瓣缮翡疆赢集审筏鬟 定理l 。4 最优顶点一定是平德点。 对于在树上寻找平街点。有“小张大靠”的原砌 对子网终上鳆爹审位弱耀，毒类镟定理l 。3 翦结论 网络上的单中心问题是求网络上- - a ，使它到网络各顶点的最必加权躐离为最 夺。黪这个藤题，有辩下缩论： 定理l 。5 最优点一感是某象踌的重心。 由定理1 3 与定理1 5 。两络上鹩单中位陶题与革中心问题都可以转化菇组合闽 廷。 除了以上介绍的中位( m e d i a n ) 问题与中一b ( c 酬料) 问题，讨厌型( o b 由惜) 的中心 蓠瑟也受燮了久粕懿关注( 参冤【毪】) 。它燕求一设藏经重，旋英与各绘定塞羹翡聂夺 加权距离尽可能大 2 选缝闯繇蔗一令宙老酌鬻蘧，凑记载豹瀵论磷究至少胃渡遥溯刘十七键纪费鼋 ( p f e m u r ) 等人的工作从2 0 世纪鳓年代以来。经济和社会生活的各领域提出了大量 的逸艟离题，又由于溉优 i ：瀵论及计算计术静发展为滚址问磁的研究提供了有力的工 具，使褥选址问题的研究褥以迅猛发聂运筹学家、经济学家、管理专家、军事专家、城 市规划师、工程师等备方面人士均对选址问联表现了浓厚的兴趣。有麓的文献效以万 幸 狳了涉及疲罴方鬻豹文款参冤【1 3 】一【1 4 】) ，大豢耱文漱关注选熬| 霉蘧秘算法( 参 见 1 5 】 1 8 ) ，致力予提高算法的可择性与效率。多种计算方法，包攒遗传算法、模拟 退火法、漉浦算法以及近瓴冀法郡被藏用蓟了选址湖勰的研究中随鬻现代化社会工 业化、信息化的发震获最优化理论的发展，选娥闯题的深入磷究和广泛应用霹望获褥 更大的进展 第= 节主要研究问题与结粜 传统的选址问题考虑点到点距离意义下的服务点选挥本文考虑点到直线距离煮 义下的干线戏设麓饿麓选眷 袭暴患x 爨室绫知翦距蹇 问题c 平面上给定”个点p l ，p 2 ，r ，求一直线l ，使 勰叫( 魏，) 为簸小这虽，磷表零点曩的极，d ( 段，l ) 表承点p i 劐直线k 蚋距戎。 问毯d 平面上给定牡条直线l l ，l 2 k ，求一点x 。能 勰( x ，磊) 为最小这舅。砒表示点k 的权，a ( x ，厶) 表承点x 到直线厶的距离 3 + 阗蘧a 藤惩b 楚翼据疆数隽热较距褒箨戆嚣令对缓阏蘧，它粕寿缀黟鹃对器 性质：问题a 的最优解可在某两个给烧点的联线中找到；问题b 的最优解可在某两条 给定赢绞翦交点孛我翻羞予途释桎获，两个繇线佳德化闯越镁转化为组合阀耱，扶蔼 得到迭代次数为多项式的算法 问题c 和问题d 是目标丽效为溉大加投距离的两个对偶问题，像们也膏很好的 对馁性羼：在阏遂c 枣，踺应母一条簸优壹线，至少存在三令“瞧赛点”；在同越d 孛， 对应于一个墩优点，楚少存在三条“临界直线”基于这种性质。两个非鳙性优化问题便 转铯舞经合胬蘧，获释褥爨遗筏次羧菇多矮式懿算法。 本文的第二章、第三章、第四章、第五章分别讨论问题a 、问题b 、问题c 、问题d 的 最优往条件、算 玺，第六章推广了这登闯瑟，势舞出进一步研究静闯瑟 第二章 问题a 的最优性条件及算法 第一节问题与结果 问舾a 平面上给定n 个点p l ，p ：。，p n ，求一直线l ，使 谢( 只，l ) 为最小这里，啦表示点r 的权。d ( p i 。l ) 表示点只到直线l 的距离 问题a 是在油田警网设计及交通道路设计中的提出的一个干线选址问题它是求 一千线，使它到各服务点的加权距离和为最小 问题a 类似于求回归直线( 参见 2 1 】) ，但目标函数完全不同我们知道，在最小二 乘法中，目标函数是纵坐标之差的平方和，不是点到直线的距离之和 我们将发现。问题a 的最优解可在某两个给定点的联线中找到基于这个性质，这 个非线性优化问题便转化为组合问题，从而得到迭代次数为多项式的算法 本章的安排如下：第二节讨论问题a 的最优性条件，第三节讨论它的算法 第二节问题a 的最优性条件 记t = p 1 ，p 2 ，只) ，其中给定点只称为终端( 协l l 】i 】“) 设只的坐标为( a ；， 玩) ，i = 1 ，2 。n 并设直线l 的法式方程为 则点p ；到直线l 的距离为 l ：zc o s 0 + y d ，毋= r d ( p i ，l ) = i a # o s o + 6 芦妇口一r 于是问题a 的目标函数为 f ( r ，8 ) = 壹t 坫l 口i c o s o 十6 声白毋一r i ， - l 其中r o ，o 8 2 ，r 首先考虑当0 固定时，函数f 对变t r 的变化率显然，f 对r 的偏导数不存在， 但存在单侧导数直线l 把平面划分为两个半平面 h t 印。曲+ 勘8 r 。 h 一：而胡+ 挑曲胡 0 ，f r 一o 所以我们有 命题2 3 当0 固定时，直线l ( r ，口) 是最优解的充要条件是 珊寺。 ( 2 1 ) p j e h 啦 w ， ( 2 2 ) 只e 月 _ 其中= 撇 满足条件( 2 1 ) 及( 2 2 ) 的直线称为“中位线”最优直线一定是中位线；并且可以 选择这样的最优中位线。使它通过某一个终端只 其次。讨论当直线旋转时函数f 的变化率不妨考虑r = 0 = o 的情形，此时直线l 与y 轴重合，故可规定y 轴的正向为l 的方向原点o 把l 分为两部分：其正向一侧 的半直线记为l + 。其负向一侧的半直线记为l 。同时，半平面h + 为i ，i v 象限，h 一为 ，m 象限 当0 o 充分小时 f ( 0 ，口) 。只e u l + m ( 4 埘毋+ 6 面毋) p u l 一砌( 4 脚毋- f 如湖) ， 只e hu l只h u l f ( o 。一0 ) =嚣t 啮( 4 i 毋一6 蒯) 一嚣m ( 口# 毋一黾声b 毋) p e h l u lp e h u l 由此推出 命题2 4当直线l 绕原点o 旋转时，函数f ( 0 。口) 在0 = 0 处的两个方向导数 分别为 6 凡+ o o 2 p j 。u l + 啦tp ，。l j l _ i 蛐；， h h ，一 。 凡一( o o 卜一。u l + 咄一p 。氟。一蚴； 只h h + l i i 一+ 。 当直线l 不通过原点o ，而绕其中一点o 旋转时，可作坐标变换后再运用上述公 式此时，上式中的屯代以向量o t 在l 轴上的投影k 7 显然，若l 为最优直线。则岛+ i o 。岛一0 于是得到如下等价论断 命题2 5 若直线l 为最优解，则绕其上任一点0 ，作旋转时均有 只乳。一砌峨i ， ( 2 3 ) 距罗u 。一耻玩专m ， ( 2 4 ) 其中m = 窑啦b i 1 满足条件( 2 3 ) 及( 2 4 ) 的直线称为“平衡线”( 因为此条件类似于力矩的平衡) 注 意此条件只能判定局部最优解。对整体最优解而言不是充分的例如在图i 中，直线 l l 和k 均满足平衡条件( 2 3 ) 及( 2 4 ) ( 其中砌= 1 ，m = o ) ，但只有l 1 才是最优解 上l b ，j ) r t - z ，9 ) f ；包司 l r ( 旷i ) 圈1 命题2 6 存在最优直线l 通过某两个终端b 及r 证明 由中位条件，必存在最优直线l 过一个终端马若它只过一个终端b ，则 以b 为中心作l 的旋转，其两个方向的导数为 n + = 墨+ 啦玩7 一一啦6 i ， p i e h p t t 凡一= 墨一瑚b l 一+ m b i p j hp ，h 二者之间中必有其一为非正，不妨设岛+ o 予是可将l 沿逆时针方向旋转到通过另 一终端r ，得到直线l 。由于其目标函数值不增，故l 是一最优直线口 综上翳逡，我餐瑟泼跌酝謇嚣煮联竣孛，选箨窭潞是条襻( 2 。l 一 丢。蹰而p i 蠢 啦 考，故s 2 不可黼为中位线 瓣忿，受s l 是串整缓瓣，在翳麓与s i 不提交瓣缓段孛，狳每玄耀邵懿线襞骞譬 能是中位线( 满足情形( i ) 的条件) 乏外，其余线段均不可能为中位线，当然不可能为 最优解，从而可从。中删去，因此得到如下算法： 算法i( 开始时= o ) 第1 步令：= 十i 。从口中任取一线段作为s i 第2 步保持s 的方向，用对分法( b i 柏珂s 朗r c l l ) 作平移，找到经过某个终端的中 位线s7 若它只通过一个终端，则在目标函数不增的条件下作适当的旋转。使它通过 某两个终端( 见命题2 6 ) 这样得到的中位线为s i + 1 若它满足情形( 1 ) 的条件。则取 出相邻的中位线，作为s i + 。的候补元素 第3 步令i _ - i - i ，检查s 及其候补元素是否满足平衡条件( 2 3 ) 。( 2 4 ) 若 然，则得到局部最优解与先前记下的局部最优解进行比较。保留当前最优者 第4 步将s 以及所有与它不相交的线段从a 中删去若一= 口。则终止( 输出当 前最优的局部最优解，即整体最优解) ；否贝4 转第1 步 算法i 以搜索中位线为主，在最坏情形可能要找遗所有椎( ”一1 ) 条联线例如 厶 图i 所示的n = 4 的例子。6 条联线都是中位线，有可能都要搜索到然而，在常见的情 况下迭代次数会少得多事实上，对各点的权m 的随机分布而言，中位条件( 2 1 ) 及 ( 2 2 ) 的等号成立( e p 上述情形( 1 ) 出现) 是十分罕见的因此。我们可以假定这种情形 不会出现。从而每一方向上的中位线是唯一的另一方面，为了便予估算，不妨假定所 有终端只都处于凸多边形区域的边界上那么，算法的每一次迭代都至少删去由一个 顶点引出的所有边。故算法至多执行n 次迭代 我们看两个特例： ( n ) 当n = 3 。啦= i 时。3 个终端p “p 2 ，p 3 构成一个三角形，则三角形的最长边 为最优直线 ( 6 ) 当”= 4 ，m ；1 且4 个终端构成一个凸四边形时，它的最长对角线为最优直 线 第三章 问题b 的最优性条件及算法 第一节问题与结果 问题b 平面上给定n 条直线l 1 ，l 2 ，l n ，求一点x ，使 墨m d ( x ，厶) 为最小这里，硼表示直线厶的权，a ( x 。厶) 表示点x 到直线厶的距离 问题b 是问题a 的对偶问题，其实际意义是求一厂址( 或蕾地) 。使它到若干传输 线路( 如油、气、水、电等管线或铰路、公路) 的加权距离和为最小 我们将发现。问题b 的最优解可在某两条给定直线的交点中找到基于这个性质， 这个非线性优化问题便转化为组合问题，从而得到迭代次数为多项式的算法 本章的安排如下：第二节讨论问题b 的最优性条件，第三节讨论问题b 的算法 第：节问题b 的最优性条件 设直线k 的法式方程为 厶；4 # + b o p = 。 其中口2 + b i 2 = l 。q o 则目标函数为 g ( z ，y ) = 虽t 盐i 口# + 6 一q - i 问题是在平面上求一点o ，y ) 。使g o ，y ) 达到最小 由组合计数方法不难证明如下论断 命题3 1n 条直线至多把平面划分为专竹( 他+ 1 ) + 1 个凸多边形区域( 有的区 域为无界) 现设直线l l 。l 2 ，l i 把平面划分出的区域为r 1 ，r 2 ，欺( m 寺n ( ”+ 1 ) + 1 ) 每一个区域都是”个半平面的交集设直线厶翅1 分出的两个半平面为 厶+ ：口# + 6 ， 1 0 则每一个区域可表示为 r ( i ) = ( 口乒? ) n ( 衅j ) ， l ，j 其中，c l ，2 ，n 1 ，了= l ，2 ，n ) f 例如，区域r ( “，2 ，k ) ) 表示如下n 个半 平面的交： 口+ 6 c k 口i + l 茹十b k + 1 y 。 + 1 a + 6 c 。 注意对2 n 个子集，而言，不少区域r ( ，) 是空集同时，不妨假定这些直线是正常相交 的，即没有三条直线相交于一点 命题3 2 在每一个区域r i ( 1 i m ) i - i 弱数g ( * ，y ) 是线性的 证明不妨设r ；= r ( n 。2 ， ”则当( * ，y ) 最时， g ( * ，) = 蚕蛾( 口+ 6 一c i ) + ；互 i ( c i 一口一6 )+ i = ( j 妻1 0 0 , i - - ；奎。啪) * + ( 毫础i - - i 妻w i b 曲 一( 蚤叩r 。互、w i c i ) 十i 这是一个线性函数口 推论在区域r ；上，线性函数c ( x ，) 的法向量( 梯度) 为 g m d 皿( ) = ( 聊蹦一净胁，渺旷b 净i b i ) ， 其中r 产r ( ，) 由于g ( x , y ) 在每一个凸多边形区域r 上是线性的，其最优点可在多边形的顶 点上达到，所以我们有命题2 6 的对偶性质如下 命题3 3 必存在一个最优点( * ，y ) 是两直线厶与与的交点 命题3 4函数g ( # ，y ) 是凸函数 证明首先，容易由定义验证 q ( 冀，) = 砒l 口# + b l y q l 怒凸函数然后，有隈个凸函数之和仍为凸函数，敝得欲证( 关于凸蟊数的性质参见 2 2 ) 口 疆然g ( z ，) 是努净缓毪靛凸涵散，窀弱局部激傥舞一是是整体溉傥蘩箍翔定 局部最优解可以借助梯度向量喊( z ，y ) 由二缎线性规划的性质立得； 翕毯3 。5 考瘩蓦标蘧数c ( x ，) 狂凸多逡形嚣蠛急靛二雏绞往囊黧颡的 顶点p ( z ，y ) 是最优解的充要条件是：p 点的两条边与涤向量盛喇嗡o ，) 的夹角, r 2 事实上，毙条棒镣馥子：法怒叠g 豫氓专嚣壤冀琏缝子蘧遘p 熹豹簿篷缓( 郑与 焱向量垂童的直线) 的同侧 综上掰述，褥裂纛健舞判定壤熨 命纛3 6 设p o ，y ) 怒两条给寇赢线的交点，其周嘲邻接的4 个区域为r l ， r 2 ，r 3 及磁，烈p 怒攘俸最优辫缒充要焱绛是：p 怒r 上嚣绫性规划戆最优解( f = 1 ，2 。3 ，4 ) 例如，擞嚣= 3 ，撇；l 时，黧条直线l l ，2 。3 嘲成一个童角形a ，则虎焦最大 ( 因而高最小) 的顶点为最优点 第三节两题b 的算法 算法驳 第0 步在l 荣直线划分出的凸区域中任取一个有界区域r 第1 梦在嚣壤r 主箨竣秣蠡数g ，y ) 黪法态重g n d 趣( x ，了) ，并霭二缝缓魏规 划方法求出r 上的最优顶点p 筹2 多检壹璎赢p 餐按瓣毒令篷嚣域，羯定它蔗不是邃整嚣壤土懿缓甓鬟麓熬 最优点若然，则p 为接体最优解，终止 繁3 步在覆纛p 舔接豹敷壤孛，浚p 不是送壤嚣圭瓣囊霞鳞，令嚣一霹，转第 l 步 在上遴算法中，遨次爨二缭绫性栽惫| ，哥霪二缭强纂法( 足 鼙露鹜 t 键可罴数隳方 法由于所有直线的突点有丢抖( 抖一1 ) ，对上述算法带察的顶点序列，目标函数是严格 下簿静，辫苏迭蓑次数至多菇o ( n 2 ) 。 第四章问题c 的最优性条件及算法 第一节问题与结果 问越c 平面土给定n 个点p 1 ，p 2 ，r ，求一直线l ，使 k m a x 删t ( p i ) 为最小，这飘，m 表示点只的权，矗( 只，l ) 表示点鼠剩直线l 的距离 惩题c 罴在警弼设计及交遴遵踌设计皆提蹬的一个干线潦继翔越，瓣鳇是求予 线，使它到备服务点的加权距离在一个尽可能小的范圈内 我们将发现，在问题c 中，对应予一条最优直线。至少存农兰个“临赛点”基警这 个性质，这个非线性优化闻矮使转化为缀龠两惩，从简得蓟迭代次数为多项式的算法 本章的安排如下；第二节讨论问题c 的最优性焱件，第三节讨论l 可聪e 的算法。第 遴节讨论阕鼹c 在筱乎冗对翡祷形 第二繁麓毯c 的囊慌性条搏 砖乎鬻童妊一蹇绫 竣瓣熬e 骜嚣掭丞鼓秀 以l ) 2 勰谢( 只- l ) 善 “l ) = 啦，( l ) = m ， 一 弼称l 为娥优直线，m + 秀最德馕若雄( a ，。) = 辨，舞称巩为l 。对应秘耩再 点对于非临界点p i ，戳耐( b ，l 。) t * t 。 命毯4 1 若l 为秘麓c 酌囊傥赢绫，斑黧少存在3 个位子l 两德豹耩界 点 证酮壅吾檬鞭数兵l 。) 戆定义。搽存在一令嵇弄熹，德若灵在苁l 。) 秘一循 脊临界点，瓤在另一侧无临界点，则对于光临界点一侧的点只，有t 砸( 只l 。) m 露将王- 离蠢嵇赛纛一耱孚蓼惩够拳距赛楚云捷 f ( - l ) 2 勰叫( p t ，- l ) f ( l 。) = 勰叫( 只，l 。) = m ， 与毛+ 鹃最倪佳矛潘，敬嚣粥筠有糯雾泰不妨设p 2 ，p 2 是。两衡盼褥个l 晦雾赢， 若除此外无其它临界点。则 w l d ( p 1 ，王。) = 勘矗( p 2 ，) = m 。， 谢( 只，l 。) 2 蕊 2 娜。， 与l 。的最优性矛盾，故至少还存在一个临界点命题得证口 设只，露经予塞缓舀，i 翦一捷，最整警秀一燕，藏 脚1 一谢( p i 。如， ) = 叫( 马，k 。1 ) = 叫( p i ，如。 ) ， 燹黎壹绫珞。l 蔻| 霹鬈e 对于最，忍；逸三患懿舞蘩豢爱塞缓+ 注塞这髦篓赢苓是瓣嚣 的由命题4 i 知。问耀c 的整体最优直域l 。一定摄对于某量点( 不妨设为只，玛； 投) 懿是舔鬏爨塞线氛 澎整俸囊憷燕 m 。= 撕 = 叫( b ，b 。 ) * 州( 马，岛 ) = 瑚i ( 段，白 ) 下嚣考虑砖瘦予三豢曩，马；珞瓣愚郊鼍德塞缓，其枣只，马孝。l 黪一裁，魏在努一 侧+ 设直线k 与线段b r 相交于点m 。岢线段彤、相交予点n ( 如图3 ) 塞 叫( 只，“1 ) ；叫( 马，b ，t ) 一蜊( r ，k ， ) 攘豳 叫( 段，m ) = 刚( r 。m ) 。叫( 马，n ) = 谢( n ，n ) 。 从嚣 m ：掣n ；掣 獬十礅埘十勘 鞠m 是 魏，最 的重一。n 是 p j ，p l 鹃鳖心，这样静连缓鲥收褥直缄如。 ) 称秀篓角 形p ；雄、中关于p 霸的加权中像嫂当磁。w 时，川与p 易平行当m 粥时 遗直绫p 为上一熹p ， p ：蛾二嫱 搬一啦 由此得到如下结论 图3 命题4 2 对应于p i ，p j ；p l 的局部最优直线岛， 是三角形只f 娥中关于蹈 的加权中位线，且唯一确定 问题c 在”= 3 的情形有三条加权中位线。对应于三条局部最优直线。其中最优 者即为接体最优直线 对于一般情形。我们有如下结论 命题4 3 对应于只，b ；b 的局部最优直线k 1 是整体最优直线且，l i i 。= u 谚( p i ，k ，) = 缸矽( 马，k ，) = u 耐( r ，k ，1 ) 是整体最优值的必要条件是： 锄d ( p t ，k ， ) 脚( 1 z 筇) 证明 若w , i 为整体最优直线。啪。为整体最优值，砌 i ( b ， ) = 。r 。m 。x w a i ( p t ，l ) 2 撕 ， 故 叫( p l ，b 。1 ) m - 1 z ”口 第三节问题c 的算法 根据命题4 1 及命题4 2 ，最优直线l 。一定是某一局部量优直线，即莱一条加权 中位线我们检验所有符合命题4 3 条件的局部最优直线，从中可确定最优直线l 与 最优值，l 。由此得到问题c 的如下算法： 算法 1 5 开始时令m = + q o ；对i = 1 ，2 。，一l 及j = l + 1 ，执行如下过程， 过程f i 。j ；) s t e p0 令 = 1 s t e p 1 若 。a j ，则在三角形p 易r 中作关于p 毋的加权中位线b m 若 叫( a ，k ，1 ) 哪( 1 z 7 1 ) 且啦女 m ，贝4 记l 。：= k ，m - 卿，l ；否则转下 s t e p2 若 4 的攮影，霹戆c 戆最织塞缓萄糖苓难一，鐾霹耱不存农_ 兰令给定点只， b ，毂，使整体最优点线对这赢个点( 即竹= 3 时) 来说也是最优直线，如图4 ，p t 。p 2 ， p 。，p 4 为4 个给定煮，证予一歪方形孵璜赢上且权为1 。l l ，工噱垮为囊往直绫，瞧任兰 点的最优童线均不力l ，疋 h 壁奠 i ， 费 ￥t ， 图4 1 7 第五章 问题d 最优性条件及算法 第一节问燧与结果 问趣d 平面上给定 条直线l l ，l 2 ，k ，求一点x 。使 ，骥受乱秽( 赫厶) 为最小，这里。磷表糸直线五的权，d ( x ，厶) 表示点x 瓤耋线k 的距蒜 问题d 怒问题c 的对偶问题，其蜜际意义是求一设备位鬣，使它剿若干传输线路 ( 魏濑、气、承、惫等譬绫凌妖辫、公黪) 戆曩大鸯爨投照鸯凳囊零。 我们将发现，在嘲题d 中，对应予一个蕞优点。至少存在三条“临界直线”藻于这 个毪耩，这个赣缓缝纛佬褥慧艇转稔势疆龠鬻勰，获释褥蓟遗健次数为多饔式熬算法 举章的安排如下；第二节讨论闻煺d 的曩优性条传，第三节讨论嘲题d 的髯法 筹= 节羯题d 的最赞性条体 镁设箍豢誊缓燕逛鬻摇燮鹃，群较意蜀豢塞线遮耀交，萤没畜三条耋绫穗交予一 点 设阊题d 的茸椽硒数为 灭x ) 2 葱憋谢( x ，囊) 著 苁茇 2 瓣| 苁x ) 。封t 。， 则称x 为最优点，卅为最优饭。若州( x 。l k ) = 批。则称k 为x 对应的帻界直 线对于非临井直线k 。叫( x 。厶) ，l 愈囊s 。l 设x 燕鬻熬d 懿囊德赢，粼存在篡条绘定塞筑为i | 羹赛塞线，莛x 。 含于麓直线所圈三角形内域 证明由幅弄麓缓定义鲡至少= i 掌在一条疆弄直绫。不嫡设l t 秀雅赛誊线著狳 厶铃笼其它蠛赛宣绞，则 1 冀 w x d ( x ，1 ) ；m + ， 喇( x 。，厶) m 。( 2 f n ) 过x 作l 1 疆线，囊足为鱼，则将x 。沿垂线向垂足一侧移动足够小距离至x ，可使 兵x ) 。濯慧蚓( x ，叠) 爻x ) 。爰憋谢( x ，毛) = m ， 这鸯x 的最傥缝矛藩。敖鼙少还存在一条嵇界直线若只存在两条雅赛直线l 1 ，如， 设l l 与l 2 的交点为p ，则将x 。澄x 。p 方向穆动鼹够小鼹离至豆可使 ，( x ) 。l 嚣誉耐( x ，h ) 辨描，则在l ，2 ，岛中存农蹰条妻 线，比如如，l 3 ，使对予l 2 ，l 3 ，厶的局部最优点为x 2 鲥，且 镌戮一毪蠢酝，龟= 钧蠢蜀鳓岛) = 磁矗遥饕，三噶) 搿糯 证明根据命髓5 3 ，对4 条直线l l 。如，l 3 。l 丽言。酗不是整体最优点而它 的整体最优点必然燕荣三条瀛线，比如_ l 2 ，l 3 ，l 的蔺部聂优点x m 然而，对l l 。k ， 3 藤寓，x 搿又不是纛优点，簸 帕2 勰砌( k ) 黯州( 酗，k ) 勰谢( 硒，瓠) 。矾粥- 舀 命题5 。5 设数为对子岛，马，互唾的禺郄最优点，珊* 涮( 叛，吞) = 啦( 黾， 与) = 印( 茂* 。如) 则墨嚣为攘俸最优点且m 凇为整体最优使的充分必要条件是 辩垡。凇 辑潍| l i j k # l 。 证明必要性设z 伪为整体最优点且 ，1 1 2 3 为撩体最优值，则澍l j ”，由蜀i 的箭都最优住可知 搿粥。) 2 碧戮谢( x 妫，王喀) 谢( x 1 2 3 ，厶) ，m d ( x m 。b ) ，州( 配，l ) 嗽 谢( 叛，k ) ，m a ( x 瓣。秘) ，雄 琢，k ) ；2 鼬 敬 2 1 t m 瑙一豌 m 馘| l f m 1 2 3 ，与m 1 2 3 = ，橼 ll f m 呔 删( ，k ) ，叫( ，与) ，蜊( 琢，厶) l 。m 蠢2 擀 故x 不是最优点口 第三节阉题d 的算法 根据禽瓣5 。1 - - 5 。6 ，毒褥豢楚髦羚懿翔下算法。 算法v s t e p0 选三条给定直线为初始童线 s t e p1 令夏为这三条熏线所嘲三角形的。加投内心”。磊为更到遽三条嘉线的 加权距离若谢( 夏，k ) 赫( 1 z ，1 ) ，则令x ：= x ，i ：；历，输出最优点x 。及 蕞嚣穰m ，筹法终纛 s t e p2 若存在牡耐( 爱，h ) 罱，设原来三条直线的三个交点中与x 。在k 同侧 置蓟厶距离较大静都个交点为p ，菇蠢条直绫中交点为p 翡辫条童缡与毛一起，缀戚 新的三条直绞，转s t e p 1 根据命越5 4 ，算法中矿中历严格递增，衙历曩多有 步瓣。毽在塞菰专 算 中。步数远小于此 对于不翻权前僚形，i 荀越d 转纯为求藿麓翟阊麓：在平帮t 求一个瑟，警摊条煮 线均摆交( 包攒相切) ，使圆的半径为最小，则此圆的啷心为轰忱点，半径为最优值换 2 2 言之，找三条赢线，使其内切圆与所有直线均相交在实际计算中，可以从几何直观确 定一个较大的内切圆作为初始圆，然后以离它距离较大的直线替换原来的一条直线， 以得到更大的内切圆。直到找到覆盖圆为止 第六章推广及进一步研究 第一节问题的推广 上面研究了四种形式的平面点线选址问题，即问题a ，b ，c ，d 其中a ，b 以线性 和为目标，整体最优解可归结对于其中两个对象的局部优解( a 中最优直线是过两个 给定点的直线，b 中最优点是两条给定直线的交点) ；c ，d 以最大最小为目标，整体最 优解可归结为对于其中三个对象的局部最优解( c 中最优直线对应于三个临界点，d 中最优点对应于三条临界直线) 下面讨论这四个问题的一些推广 我们沿两个方向推广问题a ，一个方向是将平面上的干线选址河题推广为欧氏空 间中的平面选址问题，一个方向是将干线的数日由一条推广为两条或多条 问题a 1 在三维欧氏空间上给定牲1 x g p l ，p 2 。r ，求一个平面a ，使 叫( p i ，口) l - i 为最小这里，啦表示点只的权，d ( 只，a ) 表示点只到平面a 的距离 对于问题a 1 ，与命题2 6 类似，我们可以得如下结论 命题6 1 存在最优平面n 。通过莱三个终端只，p j ，玖口 关于推广到n 维空间的情形。可参见 2 3 我们考虑允许2 条干线的如下干线选址问题 问题a 2 在平面上给定椎个点p l 。p 2 ，只。求平面上两条直线l l ，l 2 ，使 壹砒i n i n d ( r ，l 1 ) d ( 只，l 2 ) ) f i 为最小这里，啦表示点只的权。d ( 只，l 1 ) 与a ( p i ，k ) 分别表示点p i 到直线l l 。l z 的距离 2 4 砖予闻越恕，每鑫瑟2 6 类铋，我餐霉黻褥黉翔下缝论 命题6 ，2 襻在最优艇( l ；，l ；) ，使w ，l 。t 均分别过慕秀令终溃+ 证