首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到19条相似文献,搜索用时 113 毫秒
1.
哈明距离下的网络逆问题研究综述   总被引:6,自引:0,他引:6  
逆优化问题研究的是如何改变原问题中的权参数,使得某些给定的解是问题在新的权参数下的最优解,且使总的改造费用尽可能少.作为逆优化问题中相对较新的一个分支,哈明距离下的网络逆问题具有较大的理论研究及实际应用价值.此文首先介绍了逆优化问题和哈明距离下的网络逆问题以及它们的应用,然后详细介绍了哈明距离下的网络逆问题的研究动态及使用的研究方法.最后给出了该领域中的一些值得研究的问题.  相似文献   

2.
贺琳  陈燕 《运筹与管理》2014,23(3):176-182
交通阻断成因复杂,与气象环境、道路线形、车辆状态以及交通环境等多因素相关。由于缺乏对造成交通阻断相关因素间潜在关联的研究,交通阻断管控一直是公路管理,特别是高速公路管理的难点。本文提出了一种基于多维模糊关联规则的道路交通阻断分析方法,发掘交通阻断的潜在规律和各因素间的关联关系。首先在国家现有相关划分体系和大量交通阻断(事件)案例的基础上,根据道路管理实际需求,建立了交通阻断多维属性模型,然后利用基于FCM的模糊关联规则,挖掘阻断因素的多维属性的依存关系,得到面向道路交通阻断分析的多维模糊关联规则。通过研究成果的实践应用,证明关联规则可以为道路交通阻断预防和管理提供有效支持,在道路交通阻断分析领域有着良好的应用前景。  相似文献   

3.
在大数据爆炸的时代,网络舆情、尤其是负面网络舆情管理,已成为管理层面临的难题和亟需解决的决策问题.基于目前涉警网络舆情事件研究更多偏向于定性研究,应用大数据和动态优化理论,从历史事件中寻找舆情演变规律,创新性的提出从负面评论占比的角度量化系统状态和干预效果,创造性的在涉警网络舆情这一社会管理领域首次应用马氏决策过程展开研究,通过转移概率矩阵给出涉警网络舆情在不同状态下、不同干预行动下的动态发展转移规律.同时,以马氏决策过程计算结果作为系统的初始状态,应用向后递归值迭代算法进行干预行动选择策略动态寻优,分别给出了有限阶段、无限阶段各状态下的最优干预行动选择策略.案例对比研究表明,结论可为舆情管理部门提供量化决策支持,对不同状态下的干预行动选择策略提供辅助参考.  相似文献   

4.
过去数十年间,现代运筹学,特别是优化理论、方法和应用有了长足的发展.本文就运筹与优化多个领域的一些背景知识、前沿进展和相关技术做了尽可能详尽的概述,涵盖了线性规划、非线性规划、在线优化、机器学习、组合优化、整数优化、机制设计、库存管理和收益管理等领域.本文的主要目标并非百科全书式的综述,而是着重介绍运筹学某些领域的主流方法、研究框架和前沿进展,特别强调了近期一些比较重要和有趣的发现,从而激发科研工作者在这些领域进行新的研究.  相似文献   

5.
社团结构研究是复杂网络这一前沿领域中的重要问题,同运筹学有着密切的关联。本文介绍了传统社团结构问题的基本定义,以及最近十年通过应用运筹学理论对该问题的研究进展。这些进展包括启发式模型,到随后的概率优化模型,以及组合优化模型。通过这些介绍,说明了运筹学方法论和基本工具在复杂系统研究中所起到的重要作用。  相似文献   

6.
网络舆情传播速度快、波及范围广,同时具有很强的突发性、不确定性、难以控制等特点,对相关部门进行涉警网络舆情干预和引导带来巨大挑战。目前有关网络舆情引导、管控机制、应对策略研究等成果丰富、但是对网络舆情危机的演变和干预多停留在定性分析之上、定量分析研究相对欠缺。现有网络舆情研究多针对舆情发展某一阶段进行研究,未结合网络舆情发展的多阶段属性展开全生命周期研究,为数不多的网络舆情多阶段干预决策机制研究也比较粗略,缺乏一套科学、规范的干预决策机制作为支撑。因此,结合网络舆情的多阶段属性、应用定量分析方法,是未来网络舆情干预决策机制研究的方向之一。本文通过对网络舆情发展过程的描述,给出一定量的状态表述和行动刻画,构建一个分类多阶段决策模型框架。  相似文献   

7.
施工网络计划优化的极值种群遗传算法   总被引:3,自引:0,他引:3  
针对普通遗传算法用于施工网络计划优化的缺点,通过种群划分与极值搜索,建立了网络计划优化的极值种群改进遗传算法模型,有效地避免了陷入局部极值点,应用证明,该算法与普通遗传算法相比,具有优化速度快、求解精度高,全局寻优能力强等优点,尤其适合于大型复杂工程网络的优化计算。  相似文献   

8.
《大学数学》2016,(4):1-11
复杂网络有自身的动力学性质,这可以通过定义相应的拓扑统计量来刻画;另一方面,网络的拓扑结构对其上的动力学过程,尤其是疾病传播过程,具有重要影响.本文简要回顾了复杂网络理论发展的几个重要标志及一些经典的疾病传播动力学模型,重点介绍了退火网络、淬火网络、自适应网络和耦合网络上疾病传播的相关研究成果以及网络疾病建模思想在其它一些社会传播中的应用.最后,根据作者本人的工作和理解,提出了一些值得进一步思考和研究的问题.  相似文献   

9.
本文对近年来国内外系统控制领域中的热点研究问题之一—分布式优化算法及其应用进行了简明的介绍,分别从优化问题提法、信息分享模型、优化算法设计和优化应用研究四个角度对分布式优化的理论研究结果进行了梳理.通过这种系统化整理和多角度介绍,本文在以上四个维度上基本呈现了国内外分布式优化理论研究的现状,并给出了对该领域发展的一些浅见.特别地,为了强调国内学者的贡献,本文虽无法全面但仍着重地介绍了国内有关学者在该领域的研究成果.  相似文献   

10.
针对网络推手参与社交媒体的舆情炒作和操纵行为,探讨如何实现对社交媒体平台的舆情传播进行有效管控.构建基于网络推手、社交媒体平台、政府监管部门和网民等四方利益主体的演化博弈模型,分析各博弈主体的稳定策略,并通过实验仿真探讨关键要素对博弈模型的影响.研究得到如下结论:1)权威媒体及时辟谣能够有效阻断社交媒体平台上虚假舆情信息传播:2)政府监管部门加强对网络推手和社交媒体平台的有效监管,加大违规惩罚力度,可对网络推手起到有力警醒,督促社交媒体规范舆情信息推送流程;3)主流媒体平台发布的舆情信息较为可靠,网民对小道消息应及时查证.据此,提出政府有效监管社交媒体平台舆情传播的相关建议,为净化网络信息空间,保障网民权益,维护社会安定团结,提供决策参考.  相似文献   

11.
Heuristics for Multi-Stage Interdiction of Stochastic Networks   总被引:1,自引:0,他引:1  
We describe and compare heuristic solution methods for a multi-stage stochastic network interdiction problem. The problem is to maximize the probability of sufficient disruption of the flow of information or goods in a network whose characteristics are not certain. In this formulation, interdiction subject to a budget constraint is followed by operation of the network, which is then followed by a second interdiction subject to a second budget constraint. Computational results demonstrate and compare the effectiveness of heuristic algorithms. This problem is interesting in that computing an objective function value requires tremendous effort. We exhibit classes of instances in our computational experiments where local search based on a transformation neighborhood is dominated by a constructive neighborhood.  相似文献   

12.
The maximum flow interdiction is a class of leader–follower optimization problems that seek to identify the set of edges in a network whose interruption minimizes the maximum flow across the network. Particularly, maximum flow interdiction is important in assessing the vulnerability of networks to disruptions. In this paper, the problem is formulated as a bi-level mixed-integer program and an iterative cutting plane algorithm is proposed as a solution methodology. The cutting planes are implemented in a branch-and-cut approach that is computationally effective. Extensive computational results are presented on 336 different instances with varying parameters and with networks of sizes up to 50 nodes, 1200 edge, and 800 commodities. The computational results show that the proposed cutting plane approach has significant computational advantage over the direct solution of the monolithic formulation of the maximum flow interdiction problem for the majority of the tested instances.  相似文献   

13.
The network flow interdiction problem asks to reduce the value of a maximum flow in a given network as much as possible by removing arcs and vertices of the network constrained to a fixed budget. Although the network flow interdiction problem is strongly NP-complete on general networks, pseudo-polynomial algorithms were found for planar networks with a single source and a single sink and without the possibility to remove vertices. In this work, we introduce pseudo-polynomial algorithms that overcome various restrictions of previous methods. In particular, we propose a planarity-preserving transformation that enables incorporation of vertex removals and vertex capacities in pseudo-polynomial interdiction algorithms for planar graphs. Additionally, a new approach is introduced that allows us to determine in pseudo-polynomial time the minimum interdiction budget needed to remove arcs and vertices of a given network such that the demands of the sink node cannot be completely satisfied anymore. The algorithm works on planar networks with multiple sources and sinks satisfying that the sum of the supplies at the sources equals the sum of the demands at the sinks. A simple extension of the proposed method allows us to broaden its applicability to solve network flow interdiction problems on planar networks with a single source and sink having no restrictions on the demand and supply. The proposed method can therefore solve a wider class of flow interdiction problems in pseudo-polynomial time than previous pseudo-polynomial algorithms and is the first pseudo-polynomial algorithm that can solve non-trivial planar flow interdiction problems with multiple sources and sinks. Furthermore, we show that the k-densest subgraph problem on planar graphs can be reduced to a network flow interdiction problem on a planar graph with multiple sources and sinks and polynomially bounded input numbers.  相似文献   

14.
In this paper, we concentrate on computing several critical budgets for interdiction of the multicommodity network flows, and studying the interdiction effects of the changes on budget. More specifically, we first propose general interdiction models of the multicommodity flow problem, with consideration of both node and arc removals and decrease of their capacities. Then, to perform the vulnerability analysis of networks, we define the function F(R) as the minimum amount of unsatisfied demands in the resulted network after worst-case interdiction with budget R. Specifically, we study the properties of function F(R), and find the critical budget values, such as \(R_a\), the largest value under which all demands can still be satisfied in the resulted network even under the worst-case interdiction, and \(R_b\), the least value under which the worst-case interdiction can make none of the demands be satisfied. We prove that the critical budget \(R_b\) for completely destroying the network is not related to arc or node capacities, and supply or demand amounts, but it is related to the network topology, the sets of source and destination nodes, and interdiction costs on each node and arc. We also observe that the critical budget \(R_a\) is related to all of these parameters of the network. Additionally, we present formulations to estimate both \(R_a\) and \(R_b\). For the effects of budget increasing, we present the conditions under which there would be extra capabilities to interdict more arcs or nodes with increased budget, and also under which the increased budget has no effects for the interdictor. To verify these results and conclusions, numerical experiments on 12 networks with different numbers of commodities are performed.  相似文献   

15.
项寅 《运筹与管理》2020,29(10):1-10
“一带一路”战略加深了我国与邻国的合作交流,也为境外恐怖分子的潜入提供可乘之机。为防止恐怖分子潜入,提出一类新的恐怖分子入侵阻止网络设计问题,充分考虑恐怖分子的计算能力,通过决策有限安检资源在边境交通网络中的最优分配来降低袭击风险。首先,将该问题构造为双层规划模型,上层规划是政府的阻止网络设计问题,下层规划是恐怖分子的袭击节点选择和入侵路径优化问题;其次,设计一类用禁忌搜索处理上层规划,并结合下层规划直接求解的混合算法;最后,结合南疆实例进行仿真分析,结果发现:恐怖分子计算能力越强,网络城市节点受袭风险越大;政府最优阻断方案随恐怖分子计算能力强弱变化而变化,但存在一定共性原则;增加阻断资源投入可降低袭击风险,但两者存在“边际效用递减”关系。  相似文献   

16.
This paper considers a novel formulation of the multi-period network interdiction problem. In this model, delivery of the maximum flow as well as the act of interdiction happens over several periods, while the budget of resource for interdiction is limit. It is assumed that when an edge is interdicted in a period, the evader considers a rate of risk of detection at consequent periods. Application of the generalized Benders decomposition algorithm considers solving the resulting mixed-integer nonlinear programming problem. Computational experiences denote reasonable consistency with expectations.  相似文献   

17.
In this work, we introduce multi-interdictor games, which model interactions among multiple interdictors with differing objectives operating on a common network. As a starting point, we focus on shortest path multi-interdictor (SPMI) games, where multiple interdictors try to increase the shortest path lengths of their own adversaries attempting to traverse a common network. We first establish results regarding the existence of equilibria for SPMI games under both discrete and continuous interdiction strategies. To compute such an equilibrium, we present a reformulation of the SPMI game, which leads to a generalized Nash equilibrium problem (GNEP) with non-shared constraints. While such a problem is computationally challenging in general, we show that under continuous interdiction actions, an SPMI game can be formulated as a linear complementarity problem and solved by Lemke’s algorithm. In addition, we present decentralized heuristic algorithms based on best response dynamics for games under both continuous and discrete interdiction strategies. Finally, we establish theoretical lower bounds on the worst-case efficiency loss of equilibria in SPMI games, with such loss caused by the lack of coordination among noncooperative interdictors, and use the decentralized algorithms to numerically study the average-case efficiency loss.  相似文献   

18.
Hao  Tianyu  Pang  Jong-Shi 《Mathematical Programming》2020,180(1-2):33-73
Mathematical Programming - Generalizing certain network interdiction games communicated to us by Andrew Liu and his collaborators, this paper studies a bilevel, non-cooperative game wherein the...  相似文献   

19.
In this paper, we model and solve the network interdiction problem of minimizing the maximum flow through a network from a given source node to a terminus node, while incorporating different forms of superadditive synergy effects of the resources applied to the arcs in the network. Within this context, we examine linear, concave, and convex–concave synergy relationships, illustrate their relative effect on optimal solution characteristics, and accordingly develop and test effective solution procedures for the underlying problems. For a concave synergy relationship, which yields a convex programme, we propose an inner-linearization procedure that significantly outperforms the competitive commercial solver SBB by improving the quality of solutions found by the latter by 6.2% (within a time limit of 1800 CPU?s), while saving 84.5% of the required computational effort. For general non-concave synergy relationships, we develop an outer-approximation-based heuristic that achieves solutions of objective value 0.20% better than the commercial global optimization software BARON, with a 99.3% reduction in computational effort for the subset of test problems for which BARON could identify a feasible solution within the set time limit.  相似文献   

设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号