| 有限资源下最大可靠性网络流中断模型 |
| |
| 引用本文： | 赵 佳,于 华. 有限资源下最大可靠性网络流中断模型[J]. 中国工程科学, 2015, 17(1): 137-142 |
| |
| 作者姓名： | 赵 佳 于 华 |
| |
| 作者单位： | 中国科学院大学工程管理与信息技术学院,北京,100049 |
| |
| 基金项目： | 国家重点基础研究发展计划(973计划)(2011CB706900)；国家自然科学基金(70971128) |
| |
| 摘 要： | 提出了最大可靠性网络流中断模型。此模型是在给定的网络图中,通过在边上设置监测点来阻止给定两个顶点之间的网络流量,同时考虑所设置监测点失效的可能,在给定的资源限制下,最大化中断网络流的可能性,即给定起点和终点的网络图,在资源有限的情况下,选择一些边设置监测点使得从起点到终点的所有路都包含尽可能多的已被设置中断点的边。在给定图中,两点之间的路的条数是图的规模的指数次幂,为此将此模型转化为双层整数规划模型,鉴于双层整数规划模型在一般情况下是不可解的,通过探讨下层整数规划问题与其线性规划松弛之间的关系以及线性规划对偶理论来解此双层整数规划模型。本文不仅将该模型约束的个数从图的规模的指数次幂降到一次幂,同时也提供了一种解双层整数规划问题的方法。
|
| 关 键 词： | 中断模型 k-可靠性 对偶 线性规划松弛 互补松弛型 |
| 收稿时间： | 2014-02-24 |
| 修稿时间： | 2014-02-24 |
A maximum reliable network interdiction model with limited resources |
| |
| Zhao Jia and Yu Hua. A maximum reliable network interdiction model with limited resources[J]. Engineering Science, 2015, 17(1): 137-142 |
| |
| Authors: | Zhao Jia and Yu Hua |
| |
| Abstract: | |
| |
| Keywords: | interdiction model k-reliability duality linear programming relaxation com-plementary slackness |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
| 点击此处可从《中国工程科学》浏览原始摘要信息 |
|
点击此处可从《中国工程科学》下载全文 |
|
