检索结果-南通市图书馆

维普期刊数据库

同方期刊数据库评论

在线全文

学校读者我要写书评

暂无评论

混合整数规划性质及其构造的超加性函数

华侨大学学报（自然科学版） 2016年第2期37卷 257-260页

作者：杨孝斌凯里学院数学科学学院贵州凯里556011

针对混合整数规划的一般性案例,给出其对应的线性松弛规划表达.用3个具体案例来解读有效不等式在整数规划问题中的使用,引出Gomory整数割平面.构造超加性函数并探寻它和混合整数规划割平面的关系.分析结果表明:当超加性函数中的参数取... 详细信息

针对混合整数规划的一般性案例,给出其对应的线性松弛规划表达.用3个具体案例来解读有效不等式在整数规划问题中的使用,引出Gomory整数割平面.构造超加性函数并探寻它和混合整数规划割平面的关系.分析结果表明:当超加性函数中的参数取值不同时,可以获得Gomory整数割平面、混合整数规划的取整割平面及混合整数规划的整数割平面.

关键词：混合整数规划超加性函数割平面线性松弛规划

维普期刊数据库

同方期刊数据库评论

在线全文

学校读者我要写书评

暂无评论

分支—切割法与分块TSP的分支—切割法

分支—切割法与分块TSP的分支—切割法

作者：王艳红兰州大学

学位级别：硕士

在解决各类整数规划问题时,分支-切割法是一个非常成功的方法,并且它能保证给出一个最优解。分支-切割法可以用来解决许多组合最优化问题,特别是大规模问题,例如旅行商问题(TSP)。本文在此方法的基础上,从割平面和分支两方面对该方法进... 详细信息

在解决各类整数规划问题时,分支-切割法是一个非常成功的方法,并且它能保证给出一个最优解。分支-切割法可以用来解决许多组合最优化问题,特别是大规模问题,例如旅行商问题(TSP)。本文在此方法的基础上,从割平面和分支两方面对该方法进行分析。进而,考虑一类特殊的TSP。这种TSP中的城市可被分成若干组,我们将这种特殊的TSP用0.1混合整数线性规划(MILP)来描述,然后,对其使用分支-切割法并从割平面和分支两方面来讨论。这种将TSP分块处理的方式,可降低规模,不失为一种好方法,用分支-切割法来解决,更显分支-切割法的优点。

关键词：分支-切割旅行商问题混合整数线性规划分支割平面

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

基于无人机平台的黑广播定位与追踪

基于无人机平台的黑广播定位与追踪

作者：赵明杰浙江理工大学

学位级别：硕士

黑广播(即非法无线电台)频繁出现,非法占用正常广播频段,在一定区域范围内具有发射功率大、干扰严重、持续散播虚假信息等特点,其扰乱公共秩序、干扰民航飞行、严重危害国家通信安全,影响了社会稳定。然而,目前定位排查黑广播主要采用... 详细信息

黑广播(即非法无线电台)频繁出现,非法占用正常广播频段,在一定区域范围内具有发射功率大、干扰严重、持续散播虚假信息等特点,其扰乱公共秩序、干扰民航飞行、严重危害国家通信安全,影响了社会稳定。然而,目前定位排查黑广播主要采用监测车结合手持设备的方式,这种方法受地面多径衰落和复杂交通环境影响严重,定位速度慢且精度差。另一方面,无人机因其优秀的通信、自主导航和视频捕获能力受到密切关注,在农业、救灾、航拍、电力巡检等领域已广泛应用。因此,本文考虑基于无人机平台并结合强化学习以及凸优化理论建立有效的定位导航模型,实现快速准确的黑广播定位与追踪。本文在充分了解目前国内外关于非法无线电定位研究的基础上,深入研究了强化学习以及凸优化技术在无人机平台下的黑广播定位与追踪问题,结合无人机自身的优势,建立有效的数学模型,并设计定位算法优化求解。本文的主要研究工作如下:(1)提出基于无人机平台的黑广播定位模型。针对传统黑广播定位方法受复杂交通环境和多径衰落影响严重的问题,提出了基于无人机平台的强化学习黑广播定位模型。相比传统的黑广播定位方法,无人机低空飞行可以有效避开地面复杂交通环境和多径衰落影响,同时结合强化学习算法控制无人机在未知环境中不断探索学习可以实现无人机对黑广播的自主定位导航,极大的减少人力物力成本。(2)提出基于定向天线的方向Q学习算法。无人机接收黑广播信息是非合作方式,接收天线在每个定位点处只能获取到一个接收信号强度信息,在噪声的影响下强化学习算法的探索过程会更长。考虑到信息采集的成本以及实时定位的需求,在(1)的基础上,重新设计强化学习算法并引入定向天线以获取多个方向上的信号增益和接收信号强度信息,根据不同方向上的接收信号强度信息重新设计奖惩值并优化方向选择策略,从而有效抑制噪声影响,缩短探索过程,加快学习速度,使得无人机能够更快的定位追踪黑广播。(3)提出基于割平面思想的黑广播定位模型。基于强化学习算法的定位模型需要不断的探索学习,无人机飞行速度一般较慢,且无人机起飞点在离黑广播较远时接收信号强度变化微弱,噪声影响成为主要信息,无人机需要更多的探索学习过程甚至产生原地盘旋的情况,此时远距离的黑广播预定位显得尤为重要。在无人机搭载定向天线的基础上,本文提出基于割平面算法的黑广播预定位模型,确定初始约束区域后通过选择定向天线方向角的夹角范围边界作为割平面不断切割约束区域多余部分,然后寻找约束区域的解析中心作为定位点,在定位点添加割平面形成新的约束区域,最后不断迭代更新定位点实现黑广播预定位。基于割平面算法寻找约束区域解析中心位置可以实现快速远距离黑广播预定位,经过较少次数的迭代即可逼近黑广播位置,能快速有效解决远距离定位黑广播问题。

关键词：凸优化强化学习无人机割平面 Q-Learning 方向天线黑广播

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

两类多层线性规划问题

两类多层线性规划问题

作者：徐林西湘潭大学

学位级别：硕士

具有上下层关系的结构称为递阶在实际生活中，绝大多数问题都具有系统递阶性，因此多层规划逐渐引起人们的重视，而作为多层规划最基4＼的形式二层线性规划，已绎取得很多重要成果本文基于二层线性规划的最优解可在极点达到这一性质，... 详细信息

具有上下层关系的结构称为递阶在实际生活中，绝大多数问题都具有系统递阶性，因此多层规划逐渐引起人们的重视，而作为多层规划最基4＼的形式二层线性规划，已绎取得很多重要成果本文基于二层线性规划的最优解可在极点达到这一性质，利用约束域顶点的相邻极极点：生割平面，再结合单纯形法与对偶理论来求解一层线性规划问题本文分为5章第l章介绍了多层规划问题的发展和应用，并总结了目前求解二层规划的主要思想和方法第2章给出了4\文要用到的概念和结果第3章讨论了二层线性规划的些基4\性质，并给出了求解二层线性规划的方法及数值例子.第4章对三层线性规划进行了讨论第5章对本文内容进行了小结

关键词：二层线性规划对偶埋论极点割平面

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

半定规划问题的两种数值解法

半定规划问题的两种数值解法

作者：薛丹青岛大学

学位级别：硕士

本文研究非线性半定规划问题的最优性条件和数值解法。全文包括三个部分。第一章介绍了半定规划有关的基本知识和最优性理论,对于含等式约束的一类非光滑半定规划问题证明了其一阶必要性条件和二阶的充分和必要性条件。第二章针对一般... 详细信息

本文研究非线性半定规划问题的最优性条件和数值解法。全文包括三个部分。第一章介绍了半定规划有关的基本知识和最优性理论,对于含等式约束的一类非光滑半定规划问题证明了其一阶必要性条件和二阶的充分和必要性条件。第二章针对一般非凸半定规划问题,给出了一个非线性Lagrange函数,讨论了函数在KKT点的性质,推广了Lagrange乘子法。分析了算法的收敛性,并给出了与罚参数相关的解的误差估计,在适当的条件下,当罚参数大于某一阈值时,算法产生的点列收敛到KKT点。数值算例也说明了算法的可行性和有效性。第三章将标准形式的半定规划进行转化,给出了求解较大规模半定规划问题的解析中心割平面算法,证明了算法的收敛性定理,并用实际算例验证了算法的有效性。算法的执行或者有限步终止,或者产生一个收敛到解的点列。

关键词：半定规划最优性条件非线性Lagrange算法解析中心割平面

带时间窗车辆路径问题的分支—切割—定价算法研究

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

带时间窗车辆路径问题的分支—切割—定价算法研究

作者：王维杰武汉理工大学

学位级别：硕士

带时间窗的车辆路径问题（Vehicle Routing Problem with Time Windows,VRPTW）作为物流行业中最常见的组合优化问题之一,其模型结构及算法都具有普遍性和拓展性。通过特定的转化与变形,VRPTW的模型及算法同样也适用于其他大多数的组合... 详细信息

带时间窗的车辆路径问题（Vehicle Routing Problem with Time Windows,VRPTW）作为物流行业中最常见的组合优化问题之一,其模型结构及算法都具有普遍性和拓展性。通过特定的转化与变形,VRPTW的模型及算法同样也适用于其他大多数的组合优化场景,公交线路规划、港口设备协同调度等资源分配问题都与其有着相似的数学结构。因此,对车辆路径问题的研究同样有助于推动其他相关领域的发展,如何有效提升该问题的求解效率对物流行业的发展有直接且重大的影响。本文将以精确算法作为研究方向,对VRPTW进行较为全面的理论探究。目前针对VRPTW精确算法的研究主要分为两个方向:整数规划以及动态规划。因VRPTW的求解属于强NP-hard问题,大多数学者更倾向于选择可在伪多项式时间内完成求解的动态规划来进行探究。而动态规划所求得的最优解的理论下界质量较差。且在时间窗约束较宽的情况下,其求解性能并不优于整数规划。相比之下,整数规划则更加灵活,它可以通过合并分支决策或加入有效不等式来实现高效求解。因此,本文将以整数规划为理论基础,对VRPTW进行算法优化。主要提出并实现的创新点及研究成果如下:（1）完成了结合列生成以及割平面的分支-切割-定价的算法框架搭建,并对原始二维车流模型中的子回路约束加以改进,使其适用于VRPTW。在算法后期引入改进后的二维车流模型来代替原有的分支过程。在其基础上猜测了最小车辆数量K的上界,目前本文完成的所有实验均证实了该猜想。（2）创新性地提出了两点及三点加强广义割集不等式,并证明其均为满足小平面定义（facet-defining）的不等式。虽然VRPTW作为经典的组合优化问题拥有很长的研究历史,但其子问题:带资源约束的最短路径问题（Elementary Shortest Path Problem with Resource Constraints,ESPPRC）方面的探究则少之又少。仅有的以整数线性规划为基础的理论研究也都是将旅行商问题的经典不等式加以变形后应用于ESPPRC。本文正面探究了ESPPRC的多胞形结构,并提出了两组适用于ESPPRC的有效不等式。（3）针对有效不等式加入策略的问题,本文以排列组合的形式尝试了所有两点及三点加强割集不等式的组合实验。最终确定以割平面回调的形式将三点割集不等式加入到子问题分支定界树的根节点上,完成了ESPPRC以及VRPTW的实验测试,并验证了割集不等式的有效性,改进后的模型性能得到显著提升。

关键词：车辆路径问题时间窗分支-切割-定价算法割平面多面体

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

基于集合划分的车辆路径优化精确算法研究

物流技术 2019年第3期38卷 43-48页

作者：王维杰武汉理工大学物流工程学院湖北武汉430063

将VRPTW(Vehicle Routing Problem with Time Window)通过D-W分解划分为主问题为集合划分以及子问题为带资源约束的基本最短路径问题,对子问题以割平面回调形式加入两点加强割集不等式来消除网络流中的子回路,并通过二维车流模型代替分... 详细信息

将VRPTW(Vehicle Routing Problem with Time Window)通过D-W分解划分为主问题为集合划分以及子问题为带资源约束的基本最短路径问题,对子问题以割平面回调形式加入两点加强割集不等式来消除网络流中的子回路,并通过二维车流模型代替分支定界过程求得精确解,对有效的提升算法求解速度提供了一种新思路。

关键词：车辆路径优化时间窗精确算法割平面整数线性规划集合划分