运筹学学报

甄孟可, 高红伟, 刘树清, 纪海强

2016, 20(3): 1-10. doi:10.15960/j.cnki.issn.1007-6093.2016.03.001

摘要 ( 907 )

PDF (1717KB) ( 643 )

相关文章 | 多维度评价

通过建立JW(Jackson-Wolinsky)规则之下二元稳定网络的等价条件, 给出其完整算法. 引入边支付后, 证明了增连接情形具有边支付的二元稳定网络集合是二元稳定网络集合与具有边支付的二元稳定网络集合的交集. 考察两个特定的网络模型, 系统分析了它们的二元稳定性.

对一类等待空间有限的抢占优先权排队的分析

张宏波, 周高军, 封平华

2016, 20(3): 11-20. doi:10.15960/j.cnki.issn.1007-6093.2016.03.002

摘要 ( 670 )

PDF (791KB) ( 383 )

相关文章 | 多维度评价

讨论M/M/1抢占优先权排队模型, 且假设低优先权顾客的等待空间有限. 该模型可以用有限位相拟生灭过程来描述. 由矩阵解析方法, 对该拟生灭过程进行了分析, 并得到排队模型平稳队长的计算公式, 最后还用数值结果说明了方法的有效性.

最大割问题和最大平分割问题基于半定规划松弛的近似算法

孙婷, 李改弟, 徐文青

2016, 20(3): 21-32. doi:10.15960/j.cnki.issn.1007-6093.2016.03.003

摘要 ( 1262 )

PDF (765KB) ( 479 )

相关文章 | 多维度评价

考虑每条边具有非负权重的无向图, 最大割问题要求将顶点集划分为两个集合使得它们之间的边的权重之和最大. 当最大割问题半定规划松弛的最优解落到二维空间时, Goemans将近似比从0.87856...改进为0.88456. 依赖于半定规划松弛的目标值与总权和的比值的曲线, 此曲线的最低点为0.88456, 当半定规划松弛的目标值与总权和的比值在0.5到0.9044之间时, 利用Gegenbauer多项式舍入技巧, 改进了Zwick的近似比曲线. 进一步, 考虑最大割问题的重要变形------最大平分割问题, 在此问题中增加了划分的两部分的点数相等的要求. 同样考虑了最大平分割问题半定规划松弛的最优解落到二维空间的情形, 并利用前述的Gegenbauer多项式舍入技巧得到0.7091-近似算法.

具有时间与位置相关及维修限制的单机排序问题

苟燕, 张新功

2016, 20(3): 33-44. doi:10.15960/j.cnki.issn.1007-6093.2016.03.004

摘要 ( 812 )

PDF (541KB) ( 472 )

相关文章 | 多维度评价

考虑时间和位置相关的单机排序问题, 且机器具有退化的维修限制. 工件的实际加工时间是工件加工位置相关的函数, 目标函数为最大完工时间和总完工时间两个函数, 并利用匹配算法给出这两个问题的多项式时间算法. 最后得出工件满足一定条件时最大完工时间满足组平衡规则.

基于梯度的自适应快速布谷鸟搜索算法

李荣雨, 刘洋

2016, 20(3): 45-56. doi:10.15960/j.cnki.issn.1007-6093.2016.03.005

摘要 ( 977 )

PDF (1145KB) ( 497 )

相关文章 | 多维度评价

针对标准布谷鸟搜索(CS)算法存在全局搜索和局部搜索能力不平衡的缺点, 提出一种基于梯度的自适应快速布谷鸟搜索(GBAQCS)算法. 在改进的算法中, 针对偏好随机游动的步长, 在利用目标函数的梯度决定步长方向的基础上, 首先提出自适应搜索机制平衡了算法的全局搜索和局部搜索能力; 其次提出快速搜索策略, 充分利用当前鸟巢信息进行精细化搜索, 从而提高算法的搜索精度和收敛速度. 实验结果表明, 相比其他算法, 所提出的改进策略使算法的全局搜索和局部搜索能力保持了相对的平衡, 并提高了算法的收敛性能.

求解带箱式约束全局优化问题的滤子填充函数方法

胡铨, 王薇

2016, 20(3): 57-67. doi:10.15960/j.cnki.issn.1007-6093.2016.03.006

摘要 ( 1060 )

PDF (554KB) ( 518 )

相关文章 | 多维度评价

提出一个基于滤子技术的填充函数算法, 用于求解带箱式约束的非凸全局优化问题. 填充函数算法是求解全局优化问题的有效方法之一, 而滤子技术以其良好的数值效果广泛应用于局部优化算法中. 为优化填充函数方法, 应用滤子来监控迭代过程. 首先给出一个新的填充函数并讨论了其特性, 在此基础上提出了理论算法及算法性质. 最后列出数值实验结果以说明算法的有效性.

多目标半定规划的最优性条件及对偶理论

李永玲, 杨洋, 罗洪林

2016, 20(3): 68-78. doi:10.15960/j.cnki.issn.1007-6093.2016.03.007

摘要 ( 1133 )

PDF (569KB) ( 466 )

相关文章 | 多维度评价

在不变凸的假设下来讨论多目标半定规划的最优性条件、对偶理论以及非凸半定规划的最优性条件．首先给出了非凸半定规划的一个KKT条件成立的充分必要条件, 并利用此定理证明了其最优性必要条件．其次讨论了多目标半定规划的最优性必要条件、充分条件, 并对其建立Wolfe对偶模型, 证明了弱对偶定理和强对偶定理．

离散优化问题最优值函数的连续性质

张玉忠, 杨晓光

2016, 20(3): 79-84. doi:10.15960/j.cnki.issn.1007-6093.2016.03.008

摘要 ( 1155 )

PDF (516KB) ( 443 )

相关文章 | 多维度评价

对优化问题的最优值研究是有意义的, 尽管有时并不知道怎样寻求最优值. 研究了几个重要的组合最优化问题的目标值随着输入值变化的连续化性质, 重点研究几个经典的、有代表性的离散优化问题：极小化最大完工时间的排序问题、背包问题、旅行商问题等, 以连续的数学分析思维模式审视离散问题. 最后, 研究了一些近似算法对应的目标函数的性质.

向量优化问题的一类非线性标量化定理

唐莉萍, 杨新民

2016, 20(3): 85-91. doi:10.15960/j.cnki.issn.1007-6093.2016.03.009

摘要 ( 1101 )

PDF (478KB) ( 559 )

相关文章 | 多维度评价

利用Gertewitz泛函研究向量优化问题的一类非线性标量化问题. 证明了向量优化问题的(C, \varepsilon)-弱有效解或(C, \varepsilon)-有效解与标量化问题的近似解或严格近似解间的等价关系, 并估计了标量化问题的近似解．

线图上的团染色问题

梁作松

2016, 20(3): 92-98. doi:10.15960/j.cnki.issn.1007-6093.2016.03.010

摘要 ( 940 )

PDF (546KB) ( 357 )

相关文章 | 多维度评价

设G=(V,E)为简单图, G的每个至少有两个顶点的极大完全子图称为G的一个团. 图的团染色定义为给图的点进行染色使得图中没有单一颜色的团, 也就是说每一个团具有至少2种颜色. 图的一个k-团染色是指用k 种颜色给图的点着色使得图G 的每一个团至少有2种颜色. 图G的团染色数\chi_{C}(G)是指最小的数k使得图G 存在k-团染色. 首先指出了完全图的线图的团染色数与推广的Ramsey 数之间的一个联系, 其次对于最大度不超过7的线图给出了一个最优团染色的多项式时间算法.

广义de Bruijn和Kautz有向图的双向控制集

董艳侠, 张广, 单而芳

2016, 20(3): 99-106. doi:10.15960/j.cnki.issn.1007-6093.2016.03.011

摘要 ( 998 )

PDF (704KB) ( 374 )

相关文章 | 多维度评价

设G=(V, A)是一个有向图, 其中V和A分别表示有向图G的点集和弧集. 对集合T\subseteq V(G), 如果对于任意点v\in V(G)\setminus T, 都存在点u, w\in T (u,w可能是同一点) 使得(u,v),(v,w)\in A(G), 则称T是G的一个双向控制集. 有向图G的双向控制数\gamma^{*}(G) 是G 的最小双向控制集所含点的数目. 提出了广义de Bruijn和Kautz有向图的双向控制数的新上界, 改进了以前文献中提出的相关结论. 此外, 对某些特殊的广义de Bruijn和Kautz有向图, 通过构造其双向控制集, 进一步改进了它们双向控制数的上、下界.

关于非凸的有限理性的稳定性

王春, 丘小玲, 王能发, 陈拼博

2016, 20(3): 107-120. doi:10.15960/j.cnki.issn.1007-6093.2016.03.012

摘要 ( 756 )

PDF (616KB) ( 371 )

相关文章 | 多维度评价

关于有限理性方面的文献, 大多数都是在满足凸性条件下研究有限理性的相关性质, 在一定程度上限制了其应用范围. 应用Ekeland变分原理, 减弱了有限理性模型的假设条件, 考虑在不满足凸性条件下的有限理性模型的稳定性问题. 具体给出了非凸的Ky Fan点问题解的稳定性, 非凸非紧的Ky Fan点问题解的稳定性, 非凸向量值函数Ky Fan点解的稳定性和非凸非紧向量值函数Ky Fan点解的稳定性. 作为应用, 还给出了非凸的n人非合作博弈有限理性模型解的稳定性和非凸的多目标博弈有限理性模型解的稳定性.

求解物流运输网络SUM-MIN双目标路径问题的扩展标号法

韩世莲

2016, 20(3): 121-128. doi:10.15960/j.cnki.issn.1007-6093.2016.03.013

摘要 ( 681 )

PDF (616KB) ( 390 )

相关文章 | 多维度评价

研究了物流运输网络SUM-MIN双目标路径问题. 基于模糊规划方法提出了一种求解SUM-MIN双目标路径问题的目标函数集成方法，以及集成后目标函数的扩展标号法. 在将双目标转化为单目标时，综合考虑了每个目标的边缘评价和两个目标的整体评价因素，通过对每个目标分配的权重将决策者的偏好充分体现到决策过程中，采用广义的模糊目标集成算子形成了相应的折衷规划模型. 最后，通过实例对所提方法进行了说明.

当期目录