基于P-中位模型的网络关键设施识别问题的算法设计与实现 被引量：9

1

作者 杨珺 张敏 王世伟 《管理科学》 CSSCI 2008年第4期46-53,共8页

在网络服务系统中,存在由于各种人为因素(恐怖行为、黑客袭击等)导致网络设施服务中断的情况。为抵御有预谋的攻击,需要更加重视如何识别网络系统中的关键设施。结合P-中位选址模型,以设施失效对网络系统运行效率影响最大化为目标,给出... 在网络服务系统中,存在由于各种人为因素(恐怖行为、黑客袭击等)导致网络设施服务中断的情况。为抵御有预谋的攻击,需要更加重视如何识别网络系统中的关键设施。结合P-中位选址模型,以设施失效对网络系统运行效率影响最大化为目标,给出针对基于P-中位模型的网络关键设施识别问题(即R-中断模型),并针对该模型提出贪婪搜索、邻域搜索和禁忌搜索3种算法。结合Galvo、Europe 150和USA 263等大型的测试实例,对上述算法进行比较分析,得出禁忌搜索算法最有效的结论。最后,结合Europe 150数据的例子比较了P-中位问题与R-中断问题,认为在选址决策中事先考虑到人为攻击导致的中断问题可以增加网络的抗攻击能力,减少损失。 展开更多

关键词 关键设施识别 中位问题 中断模型 启发式算法

原文传递

基于分级选址模型的学校选址问题 被引量：8

2

作者 万波 杨超 +1 位作者 黄松 董鹏 《工业工程与管理》 北大核心 2010年第6期62-67,共6页

考虑到我国中小学选址问题的特性,本文引入分段效用函数,综合考虑距离、服务质量等多种选址因素,提出基于效用函数的分级的带容量限制的中位模型。模型约束条件包括需求的全覆盖、设施的最小容量约束、需求点就近分配给设施点、需求点... 考虑到我国中小学选址问题的特性,本文引入分段效用函数,综合考虑距离、服务质量等多种选址因素,提出基于效用函数的分级的带容量限制的中位模型。模型约束条件包括需求的全覆盖、设施的最小容量约束、需求点就近分配给设施点、需求点单一分配给设施点及开放与关闭设施数目限制等。本文使用拉格朗日松弛算法,以武汉市经济技术开发区为例,就目前学校选址及分配的合理性问题、学校最小容量的合理设置问题和需求波动后的重新选址及分配问题进行了分析。 展开更多

关键词 学校选址 中位问题 效用函数 拉格朗日松驰算法

原文传递

中值等式问题证明的方法探究

3

作者 张锐 詹紫浪 《甘肃高师学报》 2024年第2期62-67,共6页

文章以历届全国研究生入学考试高等数学考题及历届全国大学数学竞赛真题(含某些省市的竞赛试题)为例,对中值等式问题的证明作了比较详尽的分析.得出结论:在中值等式问题的证明中,一般需要构造辅助函数,而辅助函数的构造可以用间接积分... 文章以历届全国研究生入学考试高等数学考题及历届全国大学数学竞赛真题(含某些省市的竞赛试题)为例,对中值等式问题的证明作了比较详尽的分析.得出结论:在中值等式问题的证明中,一般需要构造辅助函数,而辅助函数的构造可以用间接积分的方法得到,而且此方法坡度小、难度低,学生容易掌握. 展开更多

关键词 中值问题 中值定理 辅助函数 间接积分法

下载PDF 职称材料

顾客为子树结构的树上半厌恶型2-中位问题 被引量：1

4

作者 柏春松 姚云飞 王茂华 《运筹与管理》 CSSCI CSCD 北大核心 2012年第5期119-122,共4页

树上半厌恶型加权中位问题是确定一个设施集合,使得目标函数最小的问题。这类问题有两个不同的目标函数:一个是最小化所有顾客到达设施集合的最小加权距离之和,另一个是最小化所有顾客到达设施集合的加权最小距离之和。对于第二个目标函... 树上半厌恶型加权中位问题是确定一个设施集合,使得目标函数最小的问题。这类问题有两个不同的目标函数:一个是最小化所有顾客到达设施集合的最小加权距离之和,另一个是最小化所有顾客到达设施集合的加权最小距离之和。对于第二个目标函数,本文研究了顾客为子树结构树图上半厌恶型加权2-中位问题,当2-中位限制在顶点上时,我们给出了一个时间复杂度为O(mn3)的多项式时间精确算法,其中n和m分别表示树图的顶点数和边数。 展开更多

关键词 运筹学 选址问题 中位问题 半厌恶型 子树结构顾客

下载PDF 职称材料

树状网络中带度约束的树状median问题 被引量：1

5

作者 陈光亭 李守伟 丁蔚 《杭州电子科技大学学报（自然科学版）》 2009年第3期72-75,共4页

该文研究一种新的树状median问题——在树状网络中寻求带有度约束的树状median问题,即每一个节点的度数都不超过一个给定的正整数值k,且从原网络中各点到该子树的加权距离和最小。这是关于树状median问题的一种新的模型,并且利用动态规... 该文研究一种新的树状median问题——在树状网络中寻求带有度约束的树状median问题,即每一个节点的度数都不超过一个给定的正整数值k,且从原网络中各点到该子树的加权距离和最小。这是关于树状median问题的一种新的模型,并且利用动态规划得到了O(n2)时间算法。该模型是对tree core问题的一种推广,具有很强的理论意义和实际背景。如果模型中能够对median再适当增加约束,或在一般网络中寻找树状median,将会更有实际意义。 展开更多

关键词 中心问题 度约束 动态规划

下载PDF 职称材料

基于插值法的中值问题证明

6

作者 刘冬兵 马亮亮 陈龙 《温州大学学报（自然科学版）》 2012年第5期28-32,共5页

将插值法和中值问题联系起来,借助罗尔定理,通过构造插值多项式,简洁地证明了一些中值问题.

关键词 罗尔定理 中值问题 插值法

下载PDF 职称材料

一类含二阶导数的中值问题中辅助函数的构造

7

作者 陈思源 《黑龙江工业学院学报（综合版）》 2021年第1期38-40,共3页

证明中值问题可以锻炼逆向思维以及转化数学问题的能力,证明过程中往往需要借助辅助函数来完成,辅助函数的构造一直是难点。针对一类含二阶导数的中值问题中辅助函数的构造,采用逆向思维法,先构造微分方程,然后用降阶法求出未知函数导... 证明中值问题可以锻炼逆向思维以及转化数学问题的能力,证明过程中往往需要借助辅助函数来完成,辅助函数的构造一直是难点。针对一类含二阶导数的中值问题中辅助函数的构造,采用逆向思维法,先构造微分方程,然后用降阶法求出未知函数导数满足的关系式,最后找到任意常数的表达式,即为要寻找的辅助函数。通过相关试题详细阐述了构造辅助函数的逆向思维,帮助大家建立解题方法与结构,从而顺利解决这类问题。 展开更多

关键词 中值问题 辅助函数 逆向思维

下载PDF 职称材料

基因组移位变换中值问题的近似算法

8

作者 王骁力 夏云清 《河南大学学报（自然科学版）》 CAS 北大核心 2011年第4期339-344,共6页

讨论基因组在移位变换下的中值问题(TMP).给定m个基因组,每个基因组含N条染色体,TMP问题是求另一个基因组,使该基因组与其它基因组之间的移位距离和最小.对无向模型,用转化为旅行售货员问题的断点中值问题给出其近似解;对有向模型,借助... 讨论基因组在移位变换下的中值问题(TMP).给定m个基因组,每个基因组含N条染色体,TMP问题是求另一个基因组,使该基因组与其它基因组之间的移位距离和最小.对无向模型,用转化为旅行售货员问题的断点中值问题给出其近似解;对有向模型,借助于求图的最大权匹配给出TMP问题的近似算法. 展开更多

关键词 移位距离 中值问题 基因组重构 近似算法

下载PDF 职称材料

区间图上可带负权的2-中位选址问题(英文)

9

作者 程郁琨 《运筹学学报》 CSCD 2010年第2期23-36,共14页

Abstract本文研究了区间图上可带负权的2-中位选址问题.根据目标函数的不同,可带负权的p-中位选址问题(p≥2)可分为两类:即MWD和WMD模型;前者是所有顶点与服务该顶点的设施之间的最小权重距离之和,后者是所有顶点与相应设施之间的权重... Abstract本文研究了区间图上可带负权的2-中位选址问题.根据目标函数的不同,可带负权的p-中位选址问题(p≥2)可分为两类:即MWD和WMD模型;前者是所有顶点与服务该顶点的设施之间的最小权重距离之和,后者是所有顶点与相应设施之间的权重最小距离之和.在本篇论文中,我们讨论了区间图上可带负权2-中位选址问题的两类模型,并分别设计时间复杂度为O(n^2)的多项式时间算法. 展开更多

关键词 运筹学 选址问题 中位问题 可带负权 区间图

下载PDF 职称材料

中心问题与中位问题的研究现状 被引量：22

10

作者 黎青松 杨伟 曾传华 《系统工程》 CSCD 北大核心 2005年第5期11-16,共6页

p-中心问题与p-中位问题是两类基本的选址问题,在选址问题的研究中占有十分重要的地位。本文从问题的性质、算法设计思想与计算复杂性等方面总结了现有的研究成果,并指出了进一步研究的方向。

关键词 运筹学 网络选址 综述 p-中心问题 P-中位问题

下载PDF 职称材料

一种改进的禁忌搜索算法及其在选址问题中的应用 被引量：16

11

作者 郭崇慧 覃华勤 《运筹与管理》 CSCD 2008年第1期18-23,共6页

本文研究了选址问题中无容量限制的p-中值问题,在Rolland等人提出的有效禁忌搜索算法基础上,提出了一种以目标函数变化量作为评价函数的改进禁忌搜索算法,并进行了理论分析,然后将其与有效禁忌搜索算法作了性能比较。通过比较三个公共... 本文研究了选址问题中无容量限制的p-中值问题,在Rolland等人提出的有效禁忌搜索算法基础上,提出了一种以目标函数变化量作为评价函数的改进禁忌搜索算法,并进行了理论分析,然后将其与有效禁忌搜索算法作了性能比较。通过比较三个公共测试数据集的计算结果,验证了本文提出的禁忌搜索算法的可行性和有效性。 展开更多

关键词 运筹学 选址问题 禁忌搜索算法 p-中值问题

下载PDF 职称材料

遗传算法求解电力设施选址问题 被引量：11

12

作者 莫汉培 陈秋良 张子臻 《计算机技术与发展》 2016年第3期197-201,共5页

电力系统设施选址优化问题是电力系统规划和设计中的一个基础性问题,可以抽象成约束型的p-中位(p-median)问题,这是一个经典的NP-hard问题。该问题可以描述为从一个点的集合中选择p个有容量限制的中位点,让它们去服务一些有需求的点(客... 电力系统设施选址优化问题是电力系统规划和设计中的一个基础性问题,可以抽象成约束型的p-中位(p-median)问题,这是一个经典的NP-hard问题。该问题可以描述为从一个点的集合中选择p个有容量限制的中位点,让它们去服务一些有需求的点(客户),要求每一个中位点都不超出容量,并且总花费最小。文中针对这一优化问题,在经典遗传算法的基础上,提出了一种改进的遗传算法,并混合使用局部搜索算法,进行问题的求解。该算法能够利用遗传算法的全局收敛性,并且有效克服遗传算法的局部收敛和早熟问题,从而得到更准确的近似解。最后,使用网上的公开测试数据集以及经地理信息平台(GIS)收集的某供电局的坐标信息进行实验验证。结果表明,提出的算法能够有效解决设施选址问题,并且为企业提供切实可行的方案。 展开更多

关键词 设施选址 遗传算法 约束型p-中位问题 GIS平台

下载PDF 职称材料

多阶段粒子群优化算法求解容量约束p-中位问题 被引量：10

13

作者 王竹荣 薛伟 +2 位作者 黑新宏 费蓉 伊珍珍 《计算机学报》 EI CSCD 北大核心 2020年第6期1139-1160,共22页

容量约束p-中位问题(Capacitated P-Median Problem,CPMP)已被证明是一类计算机难以求解的具有NP-hard特性的组合优化问题.本文提出一种多阶段粒子群优化算法(Multi-Phase Particle Swarm Optimization,MPPSO)及在算法设计中应用模式有... 容量约束p-中位问题(Capacitated P-Median Problem,CPMP)已被证明是一类计算机难以求解的具有NP-hard特性的组合优化问题.本文提出一种多阶段粒子群优化算法(Multi-Phase Particle Swarm Optimization,MPPSO)及在算法设计中应用模式有关理论和方法.所提MPPSO在标准PSO基础上,考虑CPMP结构特征信息,采用一种以字符编码为基础的结构体编码结构,重新定义粒子速度与位置更新方式.它将CPMP优化求解分为种群粒子初始化阶段及两个优化阶段.在优化求解第一阶段,分析了惯性因子对所求问题编码结构粒子搜索的局限性,设计一种保留粒子最优特征中位点信息的变异算子.以粒子全局搜索算子操作为重点,期望从整个搜索空间搜索到好的模式结构分布特性的粒子.在优化求解第二阶段,对高适应性粒子执行一种改进的迭代局部搜索操作,达成对粒子精度的进一步提升.迭代局部搜索分为基本局部搜索和深层次局部搜索.基本局部搜索侧重对粒子需求点和中位点提炼用于发现候选粒子相邻的局部最优解.在深层次局部搜索中,采用对粒子执行扰动算子操作,使得算子操作在更大邻域范围内搜索粒子新的模式结构,从而发现蕴含高适应性模式结构的潜在更好解.文中提出模式范数及模式结构距离等概念,并将它们用于扰动算子设计.实验测试表明:MPPSO对4大类CPMP用例问题进行求解得到的实验数据,与4种文献对比算法提供的数据相比有一定优势,且能发现3个大数据集用例新的最好解. 展开更多

关键词 容量约束p-中位问题 粒子群优化算法 自适应变异算子 迭代局部搜索 模式分析方法

下载PDF 职称材料

考虑设施可靠性的线状需求物流节点选址研究 被引量：7

14

作者 周浩 周建勤 《工业工程》 北大核心 2021年第2期148-154,共7页

为了解决交通线路建设物资的物流节点选址问题,在服务线路和需求密度已知的前提下,考虑物流节点可靠性以及物资运输时间约束,建立以运输成本和时间惩罚成本之和为目标函数的数学模型。为了求解该模型,在经典p−中值选址模型基础上,采用... 为了解决交通线路建设物资的物流节点选址问题,在服务线路和需求密度已知的前提下,考虑物流节点可靠性以及物资运输时间约束,建立以运输成本和时间惩罚成本之和为目标函数的数学模型。为了求解该模型,在经典p−中值选址模型基础上,采用线积分取代离散点来表示线状需求,证明目标函数在给定区间内为凸函数,并利用二次插值和黄金分割法相结合的算法对模型进行求解。通过对是否考虑可靠性的2种选址结果进行对比研究,以及对可靠性间的相关性对选址结果的影响进行灵敏度分析。算例分析表明,与不考虑可靠性相比,提高可靠性可以降低选址系统运营总成本,也可定量地刻画出可靠性间的相关性对选址结果的影响。 展开更多

关键词 线状需求 设施选址 可靠性 时间惩罚成本 p−中值问题

下载PDF 职称材料

带投资约束p-中位问题的混合蚁群算法 被引量：7

15

作者 李倩 张惠珍 Cesar Beltran-Royo 《计算机应用研究》 CSCD 北大核心 2017年第6期1704-1707,1725,共5页

将投资限制引入经典约束p-中位问题,提出带投资的约束p-中位问题,该问题更适用于交通、物流等领域的设施选址。在深入分析带投资约束p-中位问题的数学模型的基础上,首先提出了适用于该问题求解的局部搜索策略;其次,将局部搜索策略与拉... 将投资限制引入经典约束p-中位问题,提出带投资的约束p-中位问题,该问题更适用于交通、物流等领域的设施选址。在深入分析带投资约束p-中位问题的数学模型的基础上,首先提出了适用于该问题求解的局部搜索策略;其次,将局部搜索策略与拉格朗日启发式算法和蚁群算法相结合,设计了求解该问题的拉格朗日混合蚁群算法。实验结果表明,带投资的约束p-中位问题能够根据投资金额规划不同的投资方案;且提出的混合蚁群算法较大程度上提高了蚁群算法和拉格朗日启发式算法的求解精度,具有较好的收敛性。 展开更多

关键词 拉格朗日启发式 蚁群算法 局部搜索 约束p-中位问题

下载PDF 职称材料

一种新的求解约束P-中位问题的启发式算法 被引量：4

16

作者 李有梅 陈晔 《计算机工程》 CAS CSCD 北大核心 2005年第19期162-164,共3页

针对约束P-中位问题的特点,提出了一种新的启发式算法。该算法借鉴了蚁群算法的信息素学习机制,同时针对问题的结构设计了合理的对象分配方式。模拟计算表明,该算法具有更好的全局优化性能和计算效率。

关键词 约束P-中位问题 信息素机制 启发式算法

下载PDF 职称材料

公共服务空间公平性区位问题研究进展与展望

17

作者 连晨晨 张广利 +1 位作者 孔云峰 翟石艳 《地球信息科学学报》 EI CSCD 北大核心 2024年第4期915-926,共12页

兼顾公平与效率的公共服务规划受到学术界、决策者和公众的长期关注。本文从公共服务设施布局规划的角度,对空间公平性区位问题研究进行了回顾和展望。首先,在辨析公共服务公平性概念的基础上,总结了空间公平性的度量指标。其次,根据空... 兼顾公平与效率的公共服务规划受到学术界、决策者和公众的长期关注。本文从公共服务设施布局规划的角度,对空间公平性区位问题研究进行了回顾和展望。首先,在辨析公共服务公平性概念的基础上,总结了空间公平性的度量指标。其次,根据空间公平性区位问题的建模原理,将建模途径划分为3类:直接使用公平性指标,构建单目标优化模型、多目标优化模型,或带公平性约束条件的优化模型;根据罗尔斯“无知之幕”公平正义性原则,使用有序距离加权函数构建有序中值问题模型;以及遵循社会学“不公平厌恶”原理,构建能够权衡公平与效率的公平聚合目标函数。一般地,能否找到“公平有效”的设施布局方案是空间公平性建模的一般准则,构建严格满足或“弱满足”不公平厌恶聚合函数是区位建模的技术途径。最后,对空间公平性区位建模进行了展望:引入距离阈值,简化有序距离加权函数,并将其一般化;证明了新函数是单调函数,且“弱满足”Pigou-Dalton转移规则;讨论了使用新函数改进P中值问题的可行性。 展开更多

关键词 公共服务 区位问题 空间公平性 数学模型 公平聚合函数 空间妒忌 Pigou-Dalton转移规则 改进P中值问题

原文传递

基于并行分散搜索的p-中心定位算法 被引量：5

18

作者 闫志远 孙文彬 +2 位作者 周长江 熊婷 王江 《地理与地理信息科学》 CSCD 北大核心 2013年第4期39-42,共4页

在p-中心定位问题中,经典启发式算法或元启发算法均无法兼顾解的质量与计算效率。为此,提出一种并行分散搜索算法,对分散搜索框架中的解优化和解组合过程进行了并行化处理,从而提高解的质量和计算效率,并应用模拟路网数据进行了相关实... 在p-中心定位问题中,经典启发式算法或元启发算法均无法兼顾解的质量与计算效率。为此,提出一种并行分散搜索算法,对分散搜索框架中的解优化和解组合过程进行了并行化处理,从而提高解的质量和计算效率,并应用模拟路网数据进行了相关实验。实验表明:与串行算法相比,并行分散搜索算法效率得到了大幅提升,并可以获得比Densham-Rushton算法更高质量的解。 展开更多

关键词 网络分析 p-中心定位 启发式算法 分散搜索

下载PDF 职称材料

改进的求解约束P-Median问题的分散搜索算法 被引量：5

19

作者 徐先瑞 李响 李小杰 《计算机工程与应用》 CSCD 北大核心 2011年第20期28-30,104,共4页

对解决约束P-中位问题已有的分散搜索算法进行改进。通过划分中心点服务范围的新方法指派需求点以构造初始解,用基于外包矩形的局部搜索方法来提高邻域解搜索的效率,结合路径重连算法,扩展邻域解的搜索范围,来提高解的质量。实验表明此... 对解决约束P-中位问题已有的分散搜索算法进行改进。通过划分中心点服务范围的新方法指派需求点以构造初始解,用基于外包矩形的局部搜索方法来提高邻域解搜索的效率,结合路径重连算法,扩展邻域解的搜索范围,来提高解的质量。实验表明此算法能够得到优化且连续的解。 展开更多

关键词 约束P-中位问题 分散搜索算法 λ-交换 邻域解 替换插入

下载PDF 职称材料

库区水上应急救助设施多因素P-median选址模型 被引量：2

20

作者 张进峰 刘永森 +2 位作者 牟军敏 董唏中 王晓鸥 《中国安全科学学报》 CAS CSCD 北大核心 2016年第11期163-168,共6页

为提高库区水域的水上应急救助能力和救助设施选址决策的科学性,在深入分析救助设施最优选址问题的基础上,引入应急需求点安全风险权重系数,以应急救助点覆盖半径为约束条件,建立同时考虑救助时间和安全风险的P-median水上应急救助设施... 为提高库区水域的水上应急救助能力和救助设施选址决策的科学性,在深入分析救助设施最优选址问题的基础上,引入应急需求点安全风险权重系数,以应急救助点覆盖半径为约束条件,建立同时考虑救助时间和安全风险的P-median水上应急救助设施选址模型。将所建模型应用于甘肃刘家峡库区水上应急救助设施选址问题,采用免疫算法求解模型,得到应急救助点最优选址方案。结果表明,用免疫算法能有效求得P-median应急救助设施选址模型的最优解。 展开更多

关键词 P-median 水上应急救助 选址 库区 安全风险

下载PDF 职称材料