




已阅读5页,还剩44页未读, 继续免费阅读
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
摘要 选址问题是组合优化领域中的一类重要问题,它是对于一些网络 服务器、核电站或者物流中心等有限且重要的资源进行选址决策,在 生产管理与调度,网络通信,理论计算机科学等方面有广泛的应用。 本文研究了设施选址中的一类模型:多产品选址模型 ( k p u f l p ) 。h u a n g 和l i ( 2 0 0 7 ) 首先提出了一类在度量空间特性 下的多产品选址模型,并给出了一个近似比不超过2 k 一1 的启发式算 法。本文的主要工作如下: 第一章是绪论部分,简单地介绍了选址问题的相关定义、记号及 相关知识,描述了多产品选址模型的一些特性。 第二章研究了多产品选址问题的整数及线性模型。对于 k p u f l p n ( k 2 ) ,提出了一个改进的算法m e ,并证明了该算法最 坏性能比不超过昙七一1 。另外,对于算法m e 求解2 - p u f l p n ,给出 z 了2 是该算法紧界的证明。并讨论了它的线性规划问题的松驰的整数 间隙。 第三章对两类算法落到树结构上的性能进行了分析和讨论,通过 找到一个反例,给出了算法m e 的解落到树结构上不是最优解的推理 过程。 文章末,对工厂选址问题做出总结和研究展望。 关键词:选址问题,近似算法,最坏性能比,整性间隙,紧界 a b s t r a c t l o c a t i o np r o b l e mi sak i n do fi m p o r t a n tc o m b i n a t o r i a lo p t i m i z a t i o n p r o b l e ma n dh a v ee x t e n s i v ea p p l i c a t i o n sw i t h i np r o d u c t i o nm a n a g e m e n t , n e t w o r kc o m m u n i c a t i o na n dc o m p u t e rt h e o r y i tc a nm a k ed e c i s i o na b o u t t h el o c a t i o no ft h en e t w o r ks e r v e r ,n u c l e a rp o w e rp l a n ta n dl o g i s t i c s c e n t e r w es t u d y k - p r o d u c t i o nu n c a p a c i t a t e df a c i l i t yl o c a t i o np r o b l e m ( k p u f l p ) w h i c hw a sf i r s t l yp r o p o s e db yh u a n ga n dl i ( 2 0 0 7 ) b a s e do n m e t r i cs p a c ei nt h i sp a p e r h u a n ga n dl ia l s os h o wa2 k 1h e u r i s t i c a l g o r i t h m i ns e c t i o no n e ,t h i sp a p e rb r i e f l yi n t r o d u c e ss o m ed e f i n i t i o n s , n o t a t i o n sa n dr e l a t e di n f o r m a t i o na b o u t f a c i l i t yl o c a t i o na n dd e s c r i b e s s e v e r a lc h a r a c t e r i s t i c so fk p u f l p n s e c t i o nt w om a i n l ys t u d i e st h ei n t e g e rm o d e la n dl i n e a rm o d e lo f k - p r o d u c tu n c a p a c i t a t e dl 。c a t i o np r 。b l e m a 三七一1i m p r 。v e da l g 。r i t h m f o rs o l v i n gt h ek - p u f l p n ( k 2 ) h a sb e e np r o p o s e db yu s w ea l s o d i s c u s st h ei n t e g r a l i t yg a po ft h e2 - p u f l p n sl i n e a rp r o g r a m m i n g i nt h ee n d ,w e s u m m a r ya n dp r o s p e c tt h ef a c i l i t yl o c a t i o np r o b l e m k e yw o r d s :l o c a t i o np r o b l e m ,a p p r o x i m a t i o na l g o r i t h m ,w o r s t c a s e p e r f o r m a n c er a t i o ,i n t e g r a l i t yg a p ,t i g h tb o u n d 湖南师范大学学位论文原创性声明 本人郑重声明:所呈交的学位论文,是本人在导师的指导下,独 立进行研究工作所取得的成果。除文中已经注明引用的内容外,本论 文不含任何其他个人或集体已经发表或撰写过的作品成果。对本文的 研究做出重要贡献的个人和集体,均已在文中以明确方式标明。本人 完全意识到本声明的法律结果由本人承担。 学位论文作者签名: 沙降易月f 砂日 湖南师范大学学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定, 同意学校保留并向国家有关部门或机构送交论文的复印件和电子版, 允许论文被查阅和借阅。本人授权湖南师范大学可以将本学位论文的 全部或部分内容编入有关数据库进行检索,可以采用影印、缩印或扫 描等复制手段保存和汇编本学位论文。 本学位论文属于 1 、保密口,在年解密后适用本授权书。 2 、不保密口。 ( 请在以上相应方框内打“”) 作者签名: 国次日期:加繇备6 月l 、日 剥瞄红翩嗍游6 刖 | 多产品一l :厂选址问题的算法设计与分析 1 绪论 本章主要介绍选址址问题的研究背景、研究现状以及分类。并对 选址问题这类n p 问题的常用分析方法进行了介绍。 1 1 设施选址问题 选址问题( l o c a t i o np r o b l e m ) 是组合优化中一类有着重要理论 意义和广泛实际背景的问题,其实质是寻求对需求完成分配任务的合 理安排以得到某种意义下的最优结果。它在网络设施的安放、网格服 务点的分布、核电站的建址等诸多方面有着大量的应用。同时,它与 理论计算机科学和离散组合数学也存在着密切的联系。近几十年来, 选址问题得到了运筹学、工程学、管理学和计算机科学界的极大关注, 并且随着对经典选址问题研究的日趋深入,大量具有实际应用背景的 新问题不断涌现。设施选址是众多选址问题的一个重要研究领域。本 文所研究的多产品选址问题就是属于其范畴中。研究方法主要依靠组 合优化、运筹学等计量方法,这也是设施选址与其他选址问题的重要 区别。 。 设施选址是一个十分古老而又经典的问题,古代的选址决策往往 以经验、制度为依据,缺乏科学性。1 9 0 9 年德国学者韦伯第一篇选址 论文的发表标志着设施选址问题进入到科学研究的时代。在其发展的 百年历史上,各时期研究侧重点各有不同。按时间可分为三个阶段: 硕十学位论文 ( 1 ) 零散研究阶段( 1 9 0 9 1 9 6 0 年) 。该阶段研究侧重于解决生产、 生活中的各种实际问题,内容零散。早在19 0 9 年德国经济学家韦伯 ( a l f r e dw e b e r ) 在其工业区位论文中研究如何使单个仓库到不同客 户总距离最短。该文是最早的设施选址论文。另一个早期设施选址问 题研究学者h o t e l l i n g 在其1 9 2 9 年发表的论文【3 6 】中考虑两个竞争供应 商在一条直线上的区位选择并构建选址模型。随后s m i t h i e s ( 1 9 4 1 ) 【3 刀、 s t e v e n s ( 1 9 6 1 ) 【3 8 】对此问题进行了更深入的研究。上世纪5 0 年代,越 来越多的研究者偏重于设施选址的实际应用,包括电话网络程控交换 设备选址、网络服务网点的分布与设计、铁路货运编组站选址等。( 2 ) 系统研究阶段( 1 9 6 0 一1 9 8 0 ) 。h a k i m i 于1 9 6 4 年发表的关于网络多设 施选址的论文【3 9 】是设施选址问题发展为一个系统、科学理论的里程 碑。此后,选址问题被引入一个更宽广的领域,包括生产中心选址、 交通枢纽选址、变电站选址等等。研究方法也更集中于数学分析、运 筹学等。( 3 ) 不确定性问题研究阶段( 1 9 8 0 至今) 。进入上世纪8 0 年代,随着市场变化加剧,实际生产、生活中运输时间、需求量、需 求空间分布以及设施建造成本等输入变量不确定性加强,以往静态、 确定性选址模型与方法已不能适应选址研究的发展。随机选址问题已 成为众多学者关注的焦点。l o u v e a u x ( 1 9 8 6 ) 【4 0 】、w e a v e r 与c h u r c h ( 1 9 8 3 ) 【4 1 】等学者在对不确定中值问题研究时均将运输时间与需求设 为随机变量。b e r m a n 与o d o n i ( 19 8 2 ) 【4 2 1 、b e r m a n 与l e b l a n c ( 19 8 4 ) 4 3 1 将运输时间或运输成本设为不确定系统变量研究随机网络的交通问 题。 多产口1i :厂选址问题的算法设计与分析 近些年来,对于设施选址问题大致分为两大发展方向【5 2 】:( 1 ) 模 型构建( 2 ) 算法设计。首先在构建模型上,a ) 有很多的研究者结合 现代市场理念与思想构建模型。供应链管理思想的出现为设施选址问 题提供了新的研究角度。与过去选址文章只考虑单方利益不同,供应 链管理的目标是降低“整条链”的运营成本,在“链与链”的现代市场竞 争中取得优势。研究者结合库存论、供应链利益协调机制,建立多级 的选址模型。b ) 对模型的假设多样化。在很多情况下,需求是指数分 布或是离散分布,如一些服务系统的需求为指数分布。对于交通运输 时间的不确定性,大多数学者假设运输时间为离散概率分布,这种假 设使研究对象理论化、抽象化,便于计算,但同时也有不足,即缺乏 精确性。c ) 模型系统参量内涵应更具体、明确。有些模型系统参量内 涵过于宽泛,一个变量表示运输成本等多项内容,虽简化了模型,但 和实际情况不太吻合。算法设计方面,a ) 现有的算法不能满足求解某 些复杂选址问题的需要,因此有必要提供有效的快速算法。b ) 在积极 寻找其他研究方法的同时,继续对算法复杂性进行研究,构造快速算 法。选址问题很多是n p 难题,解决这一问题的关键在于寻找更具一 般性的、高效的启发式算法。 1 2 选址问题的分类和特点 离散选址问题即设施点被选址的地点是离散的。此类问题往往设 定设施点与需求点都位于在网络节点上,需求点区位确定,需求点与 其他一些节点作为设施被选点,需求点与设施被选点之间有连线相 硕十学佗论文 连。离散选址问题纷繁复杂,随着实际问题的变化,模型也有很大的 不同。b r a n d e a u ( 1 9 8 9 ) 【1 1 1 对离散选址问题进行了分类,在国外学者 的研究基础上,我们认为主要的离散选址问题有:中值问题、覆盖问 题、中心问题、多产品问题、动态选址问题、路径选址、多目标选址 与网络中心选址问题 1 2 1 离散选址问题的分类 1 1 中值问题 h a k i m i ( 1 9 6 4 ) 最早提出中值问题,中值问题的目标是使所有 需求点到设施的平均权重距离最短( 距离也可用交通、运输时间表 示) 。其文章假设每个节点是需求点同时也是设施点,网络中的线路 表示交通线路。作者提出对于任一给定设施数p ,总存在至少一个最 优解使得总距离最小。c o o p e r 的模型不仅在网络中选择设施区位, 而且确定设施在网络中的服务范围。g o l d m a n 研究在树状网上如何选 择一个设施点的中值问题,具体方法为首先任选一个节点,计算该点 的权重是否超过所有权重一半,如果是则为中值点。如果不是则该点 t 权重被计算在相邻点上,直到找到中值点为止。 在上世纪7 0 年代末以前,绝大多数学者构建的中值问题模型都 为确定型,即客户需求、运输时间、建设成本等系统变量为确定值, 这一假设与实际情况往往不符。而后很多学者将确定性模型拓展为不 确定模型,假设上述系统变量为随机变量,以随机需求与运输时间的 研究为主。中值问题随机模型主要可分为概率模型、排队模型和情景 多产品t 厂选址问题的算法设计与分析 模型三类。( 1 ) 概率模型。概率模型可分为需求随机模型与交通运输 随机模型两类( 对这两类模型的具体研究,可参考m i r c h a n d a n i ( 1 9 8 0 ) t 4 8 】 和m i r c h a n d a n i 与o d o n i ( 19 7 9 ) t 4 9 】的文献资料) 。( 2 ) 情景模型。情景 模型是研究在一系列具有发生概率的情况下的设施可靠区位的选址 问题。有些文献假设所有情景发生的概率是相等,一些文献中的情景 概率需要计算得出。通过比较情景条件下的最优值与可靠值( r o b u s t ) 得出遗憾值( r e g r e t ) 。( 3 ) 排队模型。概率模型中的一些参量引进排队 模型理论。l a r s o n 5 0 】首先将排队论应用到选址模型中,主要研究紧急 救助组织的车辆区位与服务范围。作者假设区内、区际间呼救时间呈 p o i s s o n 概率分布、服务时间服从指数分布,构建一个多服务者排队 系统。b r a n d e a u 与c h i u t 5 1 1 研究单个设施的随机排队区位问题,考虑 排队与交通时间延迟情况下服务客户的最短反应时间。 2 ) 覆盖问题 中值问题的应用非常广泛,但是在某些情况下以降低总运输成本 ( 总距离) 作为目标不太适宜。例如城市的消防车、医疗急救车辆要 求必须在特定时间内到达事故现场,此类设施点必须布置在与需求点 特定距离之内才能满足特别的需要。对覆盖问题的研究分两类:完全 覆盖问题与最大覆盖问题。完全覆盖与最大覆盖问题都假设网络上设 施被选点是有限的,但即使网络上的被选点是连接( 无限) ,该问题 也可转化为有限被选点问题研究。 3 、) 中心问题 完全覆盖问题目标方程求在特定距离( 时间) 内满足所有需求应 硕十学何论文 修建的最小设施数。与此不同,中心问题虽然也要求满足所有需求, 但设施数是给定,求任一需求点到与它最近设施的最小最大距离,即 最小最大化问题。 4 ) 多产品问题 需求点对服务与产品的需求往往不是单一的,零售商通常要提供 多种产品才能满足顾客或企业的正常需要。g e o f f r i o n 与g r a v e s 建立 了多产品的二级选址模型,即不同产品从工厂到分销商再到零售商 ( 需求点) 的物流过程n 3 f 。 5 ) 动态选址问题 一般而言,分销中心、配送中心、消防站、急救中心等设施一旦 修建要服务很长时间。但影响选址决策的因素如需求、运输成本是变 化的,再次规划、建设新的设施点成本太高,动态选址问题应运而生。 b a l l o u 在于1 9 6 8 年发表了第一篇关于动态选址问题文章m ,文章假 设在不同时段内设施可重新选址。他利用动态规划确定了一系列潜在 的最优仓库区位,这些仓库区位能最大化其服务区域。d r e z n e r 与 w e s o l o w s k y 1 4 1 的研究侧重于城市人口的变化对设施区位的影响,作者 假设随时间变化的城市人口的增长是可预测的( 但是用确定性的方 法) ,目标方程求为特定区域服务的单设施最小期望建设成本,同时 检验了不同时期重新布置设施点的概率。文章不仅重新选择设施区 位,而且确定重新选址的时间。上述模型都研究网络中单设施区位问 题,后来很多学者考虑多设旌选址的动态规划。s c o t t 1 5 3 研究问题为在 每个时段内布置一个设施点,一旦设施点被选定,它只为一个特定的 多产品t :厂选址问题的算法设计与分析 区域服务。w e s o l o w s k k y 与t r u s c o t t 1 6 1 扩展了上述模型,决策者可根 据预测的需求变化重新布置设施点。作者构建了整数规划模型,在约 束条件中加上了一个时期内可重新选址的次数。s h e p p a r d 1 刀从更广泛 的时间与空间领域对动态选址问题进行研究。他的模型不仅要确定多 个设施的区位,而且确定设施的规模,还要确定修建设施的时间与扩 建时间。e r l e n k o t t e r 18 】的文章侧重于算法,他比较了几种启发式算法 求解动态规划的有效性,认为不同的启发式算法相结合对多阶段选址 问题求解是非常有效的。研究动态选址问题的学者还有 f r a n t z e s k a k i s 19 1 、s h u l m a n 2 0 】等。 6 ) 多目标选址问题 通常情况下,不论是公共部门还是私人企业,囿于资源所限,设 施选址都不会只设定单一目标,经常将运输( 交通成本) 、投资成本 ( 建设成本) 、客户服务水平( 在特定时间、距离为客户提供服务) 、 设施能力的“平衡利用”等目标综合考虑。构建此类模型最常用的方 式是将成本最小化作为总目标,将要实现的目标做为限制条件。h e l l e r ( 1 9 8 9 ) 【4 5 1 研究医疗服务设施的中值问题,平均运输成本最小己不是 唯一目标,同时必须在特定时间内为病人提供服务。r e v e l l e 与 l a p o r t e 2 1 1 所构建的模型中有两个目标:最小化成本与特定时间内最大 程度满足需求。 7 ) 路径选址问题 路径选址问题的核心就是要寻找最佳的车辆安排时间表、路径同 时确定设施数量与区位。其目标就是使货物处于连续、不间断地运输 硕十学位论文 中,并降低成本,增加效益。最早进行路径选址问题概念性研究的是 v o n b o v e n t e r 等,虽然早期的研究是对综合路径选址问题的研究,但 将选址和运输问题隔离开来。l a t e r 和c o o p e r 认识到运输一选址问题 主要是找到供应商的最佳位置和从源头到目的地的最小的运输成本, t a p i e r o 综合了有关时间的复杂因素,建立了运输一选址模型,使该 项研究更精确、更深入。w a t s o n g a n d y 和d o h r n 是最先在运输一选 址问题框架内考虑多仓库车辆路径种类的学者,在其模型中增加了巡 回的任务,使路径选址疸问题求解比一般求解更复杂乜2 。2 引。 8 ) 网络中心选址问题 随着网络技术的发展,网络中心选址问题也受到很多学者的关 注。网络中心选址问题可描述为在无向网络中所有节点集合为k ,网 络中心为一个子集,另一个子集为终端( 非网络中心) ,所有终端与 网络中心相连。任何一条边如果有信息流通过,则这条边的端点至少 有一个为网络中心。与中值问题相似,此类模型目标寻求平均距离( 时 间) 最短。与中值问题区别在于信息流在网络中心之间的传输费用与 其在网络中心与终端间的传输费用不等。k l i n c e w i c z 嘶1 ,e r n s t 与 k r i s h n a m o o r t h y 2 6 - 与m a y e r 和w a g n e r 他7 3 研究无能力限制网络中心选 址问题的算法。a y k i n 瞳8 1 与o w e n n 2 1 等对有能力限制的网络中心选址模 型的算法进行研究。 1 2 2 设施选址问题的特点 在相互作用的设施网络中,实际上根据设施点的需求类型以及实 多产品r 厂选址问题的算法设计与分析 际应用的模型特点不同,不同类型在选址上的主要考虑因素不尽相 同。主要可以划分成下列三种特点的设施选址: 产品型 这种类型的设施网络是指以某一种或某一系列产品为中心,分别 建立不同的设施。例如:家电公司的电饭锅厂、电熨斗厂等,日用化 学品公司的护肤用品厂、洗涤用品厂等等。这种类型的主要目的是为 了能够进行大批量生产,各个厂分别面向所有的市场区域,运费是其 次的。这种类型的设施在选址时较注重接近原材料产地或供应商,在 可能的条件下,也应考虑产品外运的方便和低成本。 市场地区型 这种类型的设施网络是指各个设施分别面向各自一定的市场区 域。这种设置方法主要考虑的是运输问题( 运费、运输时间) ,常用 于体积、重量较大的产品。例如造纸、塑料、玻璃、管道等等制造业, 这些产品在每一地区均有需求,因此对于规模较大的企业来说,往往 以区域需要为中心来设置不同的生产设施。此外,为了以“快速交货” 为主要竞争重点,有时也采用这种方式布置设施。例如,在西方很多 国家都有的承诺“3 0 分钟以内送货上门”的快餐店,其选址自然选在 目标市场附近。 生产工艺型 这种类型的设施网络是指,以企业整个生产环节中的某一环节为 中心,分别建立不同的设施或工厂。每个厂有各自的生产工艺和技术, 分别负责整个生产过程的几个阶段,然后把其产品供应给装配总厂。 硕十学位论文 这种设施选址的方法使得各个不同厂的生产均可达到一定批量,以取 得规模经济效果。这种设置方法的各个设施之间的相互作用、相互依 赖性是最强的。 1 3 设施选址的方法 曲启发式方法( h e u r i s t i c s ) 启发式方法只寻找可行解,而不是最优解。负荷距离法中的重心 法就是一种启发式方法。有许多计算机化了的启发式方法,可解决m , n 达几百、几千的问题。早在6 0 年代,就有人提出了用启发式方法 解决大型设施选址问题。今天,启发式方法已经广泛在很多场合应用。 b ) 模拟方法( s i m u l a t i o n ) 模拟是试图通过模型重现某一系统的行为或活动,而不必实地去 建造并运转一个系统,那样会造成巨大的浪费,或根本没有可能实地 去进行运转实验。模拟方法有许多种应用,在选址问题中,模拟可以 使分析者通过反复改变和组合各种参数,多次试行来评价不同的选址 方案,模拟方法可描述多方面的影响因素,因此比运输表法有更大的 实用意义。这种方法还可进行动态模拟,例如,假定各个地区的需求 是随机变动的,通过一定时间长度的模拟运行,可以估计各个地区的 平均需求,从而在此基础上确定流通中心、生产中心的分布,还可通 过需求的变动模拟出库存的变动水平,用于帮助决定生产规模、生产、 运输出、仓储费用等。这种方法常用来求解较大型的、无法手算的问 题。例如,某公司有1 3 7 个需求中心,5 个地区性的配送中心,4 个 多产品i :厂选址问题的算法设计j 分析 生产工厂,通过动态模拟计算分析得出的结论时,如果把现有的5 个 配送中一t l , 归并成3 个,可是总成本最小,该方案得到了实施,实施后 每年可节约1 3 万美元。这是7 0 年代的一个真实事例。 c ) 优化方法( o p t i m i z a t i o n ) 运输表法实际上就是一种优化方法,虽然只是某一方位问题的最 优。这种方法求出的不是可行解、满意解,而是最优解,即:在所有 可能的方案中,不会有比它更好的了。但是由于这种方法要从理论上 证明是最优,所以它在使用上有两大局限性:1 ) 模型必须较抽象、 较简单,否则得不出解。但由此而使模型的描述距实际较远;2 ) 很 多定性因素被忽略掉了,因此不可能得出在考虑定性条件下可能得出 的很多结论。总之,在设施选址中,有很多方法可以应用,特别是计 算机技术的发展使得设施选址的方法更加多样化了,但这些方法仅只 是用来支持决策,使决策更方便也更节省时间、费用,不可能完全依 赖之。 d ) 简单的中线模式法 简单的中线模式法是一种厂址选择的方法。这种方法有其局限 性。这种方法只假设坐标上最优的点( 即是使总的运输距离最短的点) 是一个可行的建厂点,并不考虑在那里现在是否有道路,也不考虑自 然地形、人口密度,以及其他许多在布点时应考虑的重要事项。 e ) 德尔菲分析模型 典型的布置分析考虑的是单一设施的选址,其目标有供需之间的 运输时间或距离极小化,成本的极小化,平均反应时间的极小化。但 硕十学位论文 是,有些选址分析涉及多个设施和多个目标,其决策目标相对模糊, 甚至带有感情色彩。解决这类选址问题的一个方法是使用德尔菲分析 模型,该模型在决策过程中考虑了各种影响因素。使用德尔菲分析模 型涉及三个小组,即协调小组、预n d , 组和战略小组。每个小组在决 策中发挥不同的作用。使用该模型的步骤如下: i 成立两个小组。内外部的人员组成顾问团,充当协调者, 负责设计问卷和指导德尔菲调查。顾问闭中选出一部分人 成立两个小组。一个小组负责预测社会的发展趋势和影响 组织的外部环境( 预n d , 组) ;另一小组确定组织的战略 目标及其优先次序( 战略小组) 。战略小组的成员从组织 中各部门的高层经理人员中挑选; i i j 识别存在的威胁和机遇。经过几轮问卷调查后,协调小组 应该向预n d , 组询问社会的发展趋势、市场出现的机遇以 及组织面临的威胁。这一阶段,要尽可能听取多数人的意 见; i i i 确定组织的战略方向与战略目标。协调小组将预n d , 组的 调查结果反馈给战略小组。战略小组利用这些信息来确定 组织的战略方向与战略目标; i v 提出备选方案。一旦战略小组确定了长期目标,就应集中 精力提出各种备选方案; v 优化备选方案。步骤4 中提出的备选方案应提交给战略小 组中的有关人员,以获得他们对各方案的主观评价;在考 多产品 :厂选址问题的算法设计与分析 虑组织优势和劣势的基础上,该模型可识别出组织的发展 趋势和机遇。此外,该模型还考虑了企业的战略目标,在 现代公司中被作为一种典型的综合性群体决策方法广泛 使用; 1 4 近似算法和性能比分析 选址问题的算法( a l g o r i t h m ) 是指一个预先制定执行的程序,对 其算法对应求解类型中的任何一个具体实例( i n s t a n c e ) ,按照这个 程序操作后都可以得到一个可行的供应商指派。算法求解问题是需要 时间的,通常算法所用的时间是指算法中所含的加、减、乘、除、比 较等基本运算次数。而算法所用的时间与实例的规模有关,为此我们 用工厂集和客户集中元素个数以及产品种类来刻画实例的规模 将实例通过某种规则编码后输入计算机所占用的字节数称为该 实例的输入长度。对某一个可能的输入长度,算法解此输入长度的最 坏可能实例所需要的基本运算次数称为该算法的时间复杂性( 函数) 。 如果存在一个多项式函数p ( n ) ,使用算法的时间复杂性为o ( p ( n ) ) , 那么称该算法为多项式时间算法,否则称为指数时间算法。还有一类 算法叫做伪多项式时间算法,它的时间复杂性是关于实例输入长度n 和实例中最大数的二元多项式函数。在二进制编码下,伪多项式时间 算法并不是多项式时间算法,而是指数时间算法。由此出发,可以导 出计算复杂性理论的一系列重要概念和结论1 i 。 计算复杂性理论兴起于2 0 世纪6 0 年代,和算法的设计与分析密 硕+ 学位论文 切相关。通过几十年来人们在计算复杂性方面的研究,现今p n p 的 猜想已被基本接受。在此前提下,所谓的n p h a r d 问题就不可能在多 项式时间内找到最优解。从而,我们在解决方法的有效性、精确性和 时间可行性上寻求平衡。这样,一个自然的想法就是放弃对最优解的 寻找,而把研究的重点转向寻找能在较短时间( 多项式时间) 内得到 接近于最优解的可行解,称为近似解。这种寻求近似解的算法也就是 如前所述的近似算法。同时n p h a r d 问题中有一类更难的问题,称为 强n p h a r d ( s t r o n g l yn p h a r d ) 问题,这类问题不存在伪多项式时间 最优算法阳1 。 我们衡量近似算法的优劣可从两个方面来看,一是算法的时间复 杂性,二是算法得到的解的值与最优解的值的接近程度。另外一个在 实际中常用的方法是对n p h a r d 问题作一些限制从而得到一些子问 题,使其具有有多项式时间算法。这是因为一个问题是n p h a r d 的, 并不能排斥它的一些特殊子问题是多项式时间可解的。 由于绝大多数选址问题都是n p h a r d 问题,其最优解很难找到, 而且在实际应用中往往也没有必要去找到最优解,只需要找到满足一 定要求的启发式解或近似解。因此研究选址问题主要有两个方向。一 是对p 问题,即可解( s o l v a b l e ) 问题,寻找多项式时间算法( 又称 为有效算法) 来得到问题的最优解,或者对n p 难题在特殊情况下寻 找有效算法也就是研究难题的可解情况。二是设计性能优良的启发式 算法和近似算法。 衡量算法优劣有三种办法:数值算例计算、最坏情况分和析和概 多产品r 厂选址问题的算法设计与分析 率分析2 j 。这三种办法各有优点也各有不足。在理论分析( 最坏情况 分析和概率分析) 之前进行大量数值计算是非常有用的方法,一则可 以对理论分析给出估计和提供思路;再者可以与已有的算法进行实际 比较。最坏情况分析是分析算法在最坏情况下的形态,概率分析是分 析算法的“平均”形态,算法的概率分析可以参考考著b 3 i 。目前在理 论上用得最多的是最坏情况分析,对于使目标函数f 为最小的优化问 题,记i 是这个优化问题的一个实例,p 是所有实例的全体;并记“i ) 是实例i 的最优目标函数值,厶( ,) 是算法h 解实例i 的目标函数值。 如果存在一个实数r ( r 1 ) ,对于任何i p 有厶( ,) 2 ) ,提出了一个改进的算法m e ,并给出了该算法最 坏性能比的数学推导、证明过程。另外,对于算法m e 求解2 - p u f l p n , 给出了2 是该算法紧界的证明及实例说明。 文章末,对工厂选址问题做出总结和研究展望。 多产品f :厂选址问题的算法设计与分析 2 1k p u f l p 多种产品工厂选址问题 实际生活中,多种产品的工厂选址模型常常被用到。例如:有些 客户往往希望被提供多种产品,或有些客户需要不同的产品。 k l i n c e w i c z 等( 1 9 8 6 ) 阳1 、k l i n c e w i c z 和l u s s ( 1 9 8 7 ) 瞄1 都曾经就一个厂 址可以提供多种产品服务的模型提出过启发式算法和求最优解的算 法。f i s h e r 乜1 等证明了工厂只供应一种产品下的k 种产品工厂选址问题 满足下模集函数( s u b m o d u l a rs e tf u n c t i o n ) 的条件。h u a n g 和“ ( 2 0 0 7 ) 1 首先讨论了在度量空间里每个客户需要k 种产品,而每个 厂址只能用来供应一种产品的工厂选址模型,即一个客户需要由k 个工厂来提供后种产品的模型。这种问题被称为k 种产品的工厂选址 问题( k p u f l p ) 。h u a n g 和l i ( 2 0 0 7 ) 1 证明了当建厂费用为零时 的2 种产品的工厂选址问题( 即2 p u f l p n ) 是一个强n p 完全问题, 并对任意的k ,当建厂费用为零时的k 种产品的工厂选址问题( 即 k p u f l p n ) 给出了一个最坏性能比不大于2 k 一1 的启发式算法,而对 建厂费用不为零时的k 种产品的工厂选址问题( 即k p u f l p ) ,利用 对线性规划问题分数解进行整数化的方法给出了一个最坏性能比不 大于2 k + l 的近似算法。本章中,对于k p u f l p n 提出了一种改进算 法m e ,并且通过定理证明,该算法将性能比提高到三七一1 。当k = 2 时, z 该算法求解2 p u f l p n 的紧界为2 。 坝十字何论文 在本文中,我们规范术语,把产品供应商统一称为- l - ) - - ( f a c i l i t y ) , 工厂集合用f = i f , ,五,五) 来表示。把有产品需求的结点统一称为客户 ( c l i e n t ) ,客户集合用d = h e 2 , 来表示。工厂,在第l 层的建 厂费用为z 7 ,两点之间的运输费用为q ,o 对某个给定的目标函数我 们希望能够找到一个可行的工厂集划分( c u t ) 使其满足所有客户对 商品需求的同时,总服务费用达到最小( 建厂费用为零的选址模型) , 或总服务费用和建厂费用之和达到最小( 带建厂费用的选址模型) 。 2 1 1k p u f l p 的数学模型 问题描述:设西表示客户的集合,表示所有可能建立的工厂集 合。现有k 种产品p l ,= 1 ,2 ,k ,对于任意工厂f f 最多只能提供其中 一种产品给客户。设z 。,i f , 1 ,七表示工厂i 供应产品p t 时所需的建 厂费用。任意两个地址f ,_ ,f u d 之间的运输费用为c 0 。对于v f f ,工 厂i 只能用来供应一种产品,因而对于任意客户d 都必须由尼个工 厂来分别提供k 种产品。我们要确定f 的七个非空且互不相交的子集 互,i = 1 ,2 ,k ,里的厂址用来供应产品p i ,并使总费用达到最小。 在本章中,如果没有特别指出的话,我们总假设下面的条件成立: ( 1 ) 、z 7 0 ,v f f ,= 1 ,2 ,七; ( 2 ) 、c o o ,v i ,_ ,u d ; ( 3 ) 、c :f = c ,v i ,f w d ;服务费用满足对称关系 ( 4 ) 、勺+ ,v i ,j ,是ef u d ;服务费用满足三角不等式关系 y s l 变量弓,对于v f f ,d 且, 1 2 ,七) ,如果工厂f 向客户供 多产品f i 厂选址问题的算法设计与分析 应产品易,则令取值为1 ,否则弓取值为0 。定义变量,如果工 厂f 被建立用来向客户供应产品所,则令彰取值为1 ,否则取值为0 。 下面是k - p u f l p 的整数规划模型: ( p ) s t 七七 r a i n z 。+ c :f f 弓 l = 1i fl - ll f j e d 菇= l ,w d ,l = 1 2 ,七; 2 f e , 弓一,v f f ,j e d ,l = 1 ,2 ,七; 3 七 1 , f = l o ,1 ) , v i f ,je 巧, 1 ,2 ,7 ,七) 5 4 一 o ,l ,7v i f ,l e 1 2 ,k 6 上述模型中,约束2 保证了客户的每种产品只能由一个工厂供应。 约束3 说明如果客户能从工厂f 接收到产品易,则有工厂f 肯定被建 立并供应产品所的前提成立。约束4 则确保了每一个被建立的工厂最 多只能供应k 种产品中的一种产品。 2 2k p u f l p n 设所有工厂的建厂费用为零,即2 0 , v i ,= 1 2 ,缸。我们将 此类问题称为k - p u f l p n 。很显然,由于建厂费用为零,因此,所有 的厂址上都可以建立工厂而无须考虑费用的增加。下面是k - p u f l p n 的线性模型: ( p k ) r a i n 勺弓 7 硕十学位论文 s t 巧= 1 , i e f 艺, = 1 , ,= l 菇0 , o , d ,= 1 ,2 ,尼;8 v f f ,j d ,= 1 ,2 ,后;9 i f1o v i f ,d , 1 ,2 ,七) 11 v i f ,j 1 ,2 ,后 1 2 2 2 1k p u f l p n 的近似算法介绍 在进一步讨论近似算法之前,我们先分析p 。的分数最优解。后续 的近似算法都是基于分数最优解的基础上进行的。 引理通过以下步骤,我们能得到( p k ) 的分数最优解 第一步:令2 去,v l 1 ,2 ,七) ,f f 第二步:对于任意的客户_ ,d ,由离_ 最近的前| j 个工厂来供应 每种产品的i l 。若,之,l 是客户的前七个最近工厂,我们令 ,2 ,2 = ,2 去,v , 1 ,2 ,日 毛= o ,v ief ,f 仨 f l ,f 2 ,屯) , 1 2 ,七 证明:首先,可以很容易地发现被定义的解( z ,j ,) 满足线性规划模 型( 既) 的所有约束条件。并且在这个解中,客户- 的运输费用就 等于前尼个离歹最近的工厂到,的供应费用的总和。很显然,解( x ,y ) 是 ( p k ) 的最优解。 我们把由定理所求得的解作为寻一分数最优解。同时,把前七个离 多产。u 1r 厂选址问题的算法设计与分析 客户最近的工厂,s = 1 ,2 ,尼作为向提供去产品的工厂。很显然, 在这个i 1 一分数解中客户的服务费用是气,+ 气j + - + 气。 2 2 2 一类解决k p u f l p n 的启发式算法( d ) 在本币里,我们将介缁一荚求觯n p 元全i 叫趑k - p u f l p n 的届友 式算法( d ) 。该启发式算法( d ) 是由h u a n g & l i 等提出的【3 1 。通 过介绍该算法,我们能对求解k p u f l p n 问题的算法设计思路有新的 了解和认识,介绍该算法更必要的一点是,本文中的创新点之一改进 算法( m e ) 也是基于这类启发式算法基础之上提出的。 算法是基于己求解出n 紫的i 1 一最优解( 二,多) 基础上给出的,算 法( o - ) 如下:w d , 设e v = :。计勺毛。初始化零: 西:= d ,墨= 是= = s x = 矽。在第f 轮迭代中,选择一个客户je d 且 三,= 耐n 三一,i 西) 。令z 表示在第,轮迭代中被选中的客户并且将它 做为本轮迭代的中心客户。令表示为客户z 提供产品的七个工厂组 成的集合 , e = ,fi 虿= 妻,v ,“2 ,矗好 , 口= - ,面ij f e , 1 2 ,矗) ,且虿= 昌。很显然,口一定不为空集,因 为至少工口。令f = ,f 2 , ,s - s 。u f f ,v le 1 ,2 ,尼 ,万:= _ d , 将口作为第r 轮迭代的簇。接着,继续下一轮迭代。直虱j b = m ,循环 结束。 对于i ( u 是s ) ,可以将i 放到任意s ( ,= l ,2 ,k ) 中。 坝十宁何论又 _ 一 最后,令所有y ;,ies l 值为1 ,否则值为0 。对d ,令= i , 否则:o ,当f f ,( ,) ,其中,it ( ) 是s ,1 = 1 ,2 ,七中离客户最近的 工厂。 i 算法( d ) 的性能分析 定理1算法( d ) 产生的可行整数解的费用不超过最优费用的 2 后一l 证明:通过将算法( d ) 的可行整数解与线性模型求解出的最优 解进行比较,来证明该结论成立。 首先,分析每轮迭代中费用的变化。假设e = f l ,f 2 ,) ,在簇口中, 中心客户z 的整数解与最优解费用同为邑。对于其它j 口,j :j t ,令 e ,: f fi 焉:吾, 1 ,2 ,七) ) = 礼瓦,矗) ,的分数解费用为:。气,。 由于,_ ,d ,说明c 中至少有一个工厂为客户提供月垦务。即 fr 、f a 。不失一般性,假设;。:。客户的整数解费用为:。c f ( , 其中( ) 是s ,1 :i ,2 ,尼中离_ ,最近的七个工厂,利用三角不等式性质, 有如下推导成立: lk c ) j q , ,;i,= i 七 气+ ( 气 + + c 6 ,) 1 = 2 k = c j z + ( 七一2 ) 气 + 吆, l = l 七七 ( 尼一1 ) 气工+ 尼q 。j 因此,产生的可行整数解的费用不超过分数解( ;,歹) 费用的2 七一l 。 多产品t i 厂选址问题的算法设计与分析 有关启发式算法与本文所提出的改进算法( m e ) 在树结构上的相关 性质,将在第三章里进一步展开讨论。 2 2 3 当k 兰2 时,一种新的改进算法( m e ) 一种新的提局了性能比的近似算法( m e ) 在上一节中,介绍了解决n p 完全问题k p u f l p n 的启发式算法 ( d ) 。并且通过理论分析,证得该算法的最坏性能比为2 k 一1 。但是, 算法在每轮迭代中对于f 中的k 个工厂,没有在继续进行细致的分析。 因此,在h u a n g & l i 等研究者工作的基础上,本节中提出了一个新 的近似算法m e ,该算法进一步对每轮所构造的z 以及每轮d f 的构造 进行了分析及改进。并且,通过数学理论的分析证明,该算法把性能 比从2 尼
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 2025年建筑工程施工监理合同协议
- 银行抵押还款合同(标准版)
- 室内装修监理合同(标准版)
- 项目开工合同(标准版)
- 模具费用合同(标准版)
- 内江市委社会工作部招聘新兴领域党建工作专员考试真题2024
- 河南省第三人民医院招聘考试真题2024
- 难点解析-人教版八年级上册物理声现象《声音的特性》综合测评试卷(详解版)
- 考点解析-人教版八年级上册物理物态变化《熔化和凝固》综合测评试题(详解版)
- 2025年建筑识期末试题及答案
- 2025至2030中国电容膜片真空计行业项目调研及市场前景预测评估报告
- 女装秋冬商品培训
- 2025年新团员入团考试试题及答案
- 第2课《中国人首次进入自己的空间站》课件-2025-2026学年统编版语文八年级上册
- 2025年安全教育平台登录入口与模拟试题集
- 公司注销原合同补充协议
- 2025-2030中国区块链技术在供应链金融中的信用穿透效应
- 护理学用药安全知识培训课件
- 2025年《铁道概论》考试复习题库(含答案)
- 2025成人高等学校专升本招生统一考试政治试题及答案解析
- 益生菌与肝性脑病改善-洞察及研究
评论
0/150
提交评论