【摘 要】
：
设施选址问题是一类经典的组合优化问题,该问题虽结构简单但应用背景广泛,在互联网、区域规划、电路排布、航空调度等许多领域具有广泛的研究和实用价值.由于设施选址问题是NP-困难的,当P≠NP时,难以在多项式时间内精确求解.所以我们一般用近似算法来解决设施选址问题.由于简单的模型无法刻画现实世界中我们所遇到的复杂而多变的情况,从而大量基于实际情况的新模型近年来被相继提出且发展势头强劲.本文研究了带惩罚和
论文部分内容阅读
设施选址问题是一类经典的组合优化问题,该问题虽结构简单但应用背景广泛,在互联网、区域规划、电路排布、航空调度等许多领域具有广泛的研究和实用价值.由于设施选址问题是NP-困难的,当P≠NP时,难以在多项式时间内精确求解.所以我们一般用近似算法来解决设施选址问题.由于简单的模型无法刻画现实世界中我们所遇到的复杂而多变的情况,从而大量基于实际情况的新模型近年来被相继提出且发展势头强劲.本文研究了带惩罚和异常点的动态设施选址问题,在这个问题中顾客的需求与相关费用均随着时间的变化而变化、顾客带有一定的惩罚费用同时允许部分顾客不被服务.所谓动态是指在模型中,设施的开设成本、顾客与设施的连接成本以及顾客需求都是随时间变化而变化的;带惩罚是指存在部分顾客距离已经开设的设施太远,而为这部分顾客单独开设设施则会导致资源的浪费,因此决策者可以选择不为这部分顾客提供服务,并通过支付一定的惩罚费用以弥补他们的损失;带异常点是指在整个模型中,允许存在不被服务的顾客,且无需支付惩罚费用.模型中规定这种异常点顾客至多有l个.带惩罚和异常点的动态设施选址问题更加贴近生活中的实际应用场景,增强了设施选址问题模型的应用价值.在这篇文章中首先介绍了无容量设施选址问题的数学模型以及其经典的常数近似比为3的原始对偶算法.其次分别介绍了三类单一变形问题,然后综合三类变形给出了带惩罚和异常点的动态设施选址问题的线性规划模型及其对偶规划,最后利用原始对偶技巧为该问题设计了近似比为3的近似算法并给出了相关的近似比分析.
其他文献
目标跟踪是许多计算机视觉任务的基础,随着深度学习的发展和工业应用的推动,该技术在学术界和工业界都取得了明显进步,然而面临一些具有挑战性的困难场景,算法性能和鲁棒性仍需进一步提升。许多研究为了提高算法性能加入了很多技巧和策略,导致方法过于复杂而难以落地;一些算法专注于提升特征的丰富性而忽视了判别性。针对上述的不足和难点,本文从目标时空特征建模的角度出发,提出了基于空间特征建模的实例感知跟踪算法和基于
多变量系统控制器设计一直是热点难点问题,针对复杂的大规模系统控制器设计以及中小规模的快采样系统的控制器设计还没有完美的解决方案。而在多变量控制算法中,模型预测控制（Model Predictive Control,MPC）可以处理大规模和复杂系统控制问题,是多变量系统控制方法的重要研究方向,同时于流程工业中取得很好的应用效果。但是模型预测控制算法由于其计算的复杂性,一般应用于上位机,难以应用于下位
随着工业社会的发展,人们的生活质量不断提高,但心血管疾病依然是威胁人类健康的一大问题。截至2021年,在全球疾病致死排行中心血管疾病已经连续多年位居榜首。心血管疾病的危险诱因在微观上主要表现为受钙离子调控的心肌细胞功能异常。钙离子在生物体内分布非常广泛,生物体内的许多生理活动,都充斥着钙离子的影子。钙离子的一大主要功能为参与钙信号的传递,这一传递功能与心肌细胞的兴奋和收缩都有着多方面的相关性。心律
含氮杂环化合物是一类具有重要价值的化合物,在医药、农业、催化、染色等领域被广泛应用。尤其在医药领域,现今药物数据库中超半数小分子药物为氮杂环化合物,也因此,该类化合物受到化学家和生物学家的广泛关注。其中,螺环吡唑啉酮类化合物的结构新颖独特,具有广泛的生物活性。而吡唑啉酮环外烯烃作为重要的有机合成砌块,具有不同的反应位点,能够发生不同类型的环加成反应,并能够高效、简洁地合成结构类型新颖多样的螺环吡唑
随着互联网的蓬勃发展和新型应用场景的不断涌现,用户生成内容急剧增长,使得人们无法从海量数据中获取所需要的信息,由此产生了“信息过载”问题。推荐系统作为一种解决信息过载问题的关键技术,可以在用户没有明确目的的情况下主动向用户推荐其潜在兴趣的项目,已经广泛应用于电子商务、社交媒体等互联网诸多领域,并取得了显著效果。然而,传统推荐系统主要依赖用户历史交互信息生成推荐,缺乏与用户的互动交流,影响了推荐的效
我国是家禽生产和消费大国。2019年,我国禽肉产量居全球第二,并呈快速发展的趋势。兽药是提升禽肉产量的重要保障。然而,在家禽养殖过程中存在的兽药乱用滥用情况易造成家禽产品中多种兽药残留问题,对人体健康造成威胁。因此,家禽产品的安全问题不容忽视。为保障家禽产品的安全,检测方法需高效、灵敏、高通量且便于进行现场监测。然而,传统的样品前处理方法耗时长、步骤繁琐,且需要使用有毒性的挥发性有机试剂。色谱法等
电化学阻抗检测方法由于检测快速、免标记等优点,在食品安全现场检测中倍受关注。现今亟需能进行现场快速筛查或可远程检测的仪器设备,但目前阻抗检测系统以进口商业化实验室分析仪器为主,体积大、价格高,无法适用于现场检测应用,限制了该检测方法的推广。此外,随着科技的发展,智能手机等移动设备作为强大的处理和控制设备得到了广泛的应用,它提供了方便快捷的软件开发平台,强大的本地处理能力,以及连接云服务器进行后续处
作为现代控制理论的一个主要分支,最优控制理论主要研究使控制系统的性能指标实现最优化的条件和方法.随着随机微分方程及其相关理论的发展,人们发现用随机微分方程来描述控制系统可以更好地解释一些实际现象,因此,人们把由随机微分方程刻画的控制系统称为随机控制系统,把研究使随机控制系统的性能指标实现最优化的理论称为随机最优控制理论.随后,随机最优控制理论迅速发展,并取得了丰富的研究成果.在前人的基础上,本文主
人体步态识别是通过分析人的身体特征以及步行时的运动姿态来进行身份验证的一种生物识别技术。因其无侵犯性、低分辨率下识别效率高以及较远距离下可识别得等特点,使得步态识别技术在视频监控领域有极高的应用价值,也是目前最具发展潜力的生物识别技术之一。现有研究大多针对侧面步态,并且提取的特征较为单一,而对于正面视角步态识别的专门研究则较为缺乏,因此针对正面步态识别技术中的运动目标识别、步态周期检测、特征提取以
高压密实化技术是一种绿色高效的速生林木材密实化加工技术,这种技术能够快速地减小木材内部孔隙的体积,从而提高速生林木材的密度和力学性能。然而,经高压密实化处理后,密实化木材存在形状不规则、有效利用率低,以及压缩形变不稳定、尺寸稳定性差的问题。本文探究了杨木在高压密实化处理后的形变的各向异性,并运用新测量装置探究密实化杨木的弹塑性应变的变化规律。本文还研究了切割方式对密实化杨木的形变和有效利用率的影响