运筹学学报

何炳生

2018, 22(1): 1-31. doi:10.15960/j.cnki.issn.1007-6093.2018.01.001

摘要 ( 1498 )

PDF (867KB) ( 1339 )

参考文献 | 相关文章 | 多维度评价

1997 年, 交通网络分析方面的问题把我引进乘子交替方向法(ADMM)的研究领域. 近10 年来, 原本用来求解变分不等式的ADMM在优化计算中被广泛采用, 影响越来越大. 这里总结了20 年来我们在ADMM 方面的工作, 特别是近10 年 ADMM 在凸优化分裂收缩算法方面的进展. 梳理主要结果, 说清来龙去脉. 文章利用变分不等式的形式研究凸优化的ADMM 类算法, 论及的所有方法都能纳入一个简单的预测-校正统一框架. 在统一框架下证明算法的收缩性质特别简单. 通读, 有利于了解ADMM类算法的概貌. 仔细阅读, 也许就掌握了根据实际问题需要构造分裂算法的基本技巧. 也要清醒地看到, ADMM类算法源自增广拉格朗日乘子法 (ALM) 和邻近点 (PPA)算法, 它只是便于利用问题的可分离结构, 并没有消除 ALM和PPA等一阶算法固有的缺点.

工件可自由下线最小化总完工时间的平行分批排序问题

酒明珠, 高园, 原晋江

2018, 22(1): 32-41. doi:10.15960/j.cnki.issn.1007-6093.2018.01.002

摘要 ( 1059 )

PDF (622KB) ( 291 )

相关文章 | 多维度评价

考虑工件可自由下线最小化总完工时间的有界平行分批排序问题. 在该问题中, 一台平行批机器可以同时处理 b 个工件作为一个平行批, 这里b 是批容量, 一个批的加工时间等于分配给这个批的工件的最大加工时间. 关于可自由下线工件, 每一个工件的完工时间等于包含这个工件的批的开工时间与工件的加工时间的和. 也就是, 如果一个批B 有一个开工时间S, 那么包含在批B 中的每一个工件J_j 的开工时间定义为S, 而它的完工时间定义为S+p_j, 这里p_j 是工件J_j 的加工时间. 对此问题, 首先研究最优排序的一些性质. 然后, 基于这些性质, 给出一个运行时间为O(n^{b (b-1)})的动态规划算法.

考虑非期望规模收益的创新型企业并购决策

张晓明, 王应明, 施海柳

2018, 22(1): 42-54. doi:10.15960/j.cnki.issn.1007-6093.2018.01.003

摘要 ( 876 )

PDF (1369KB) ( 282 )

相关文章 | 多维度评价

根据创新型企业持续创新发展的需要, 针对创新型企业并购决策问题, 提出一种考虑到非期望产出的规模收益的并购决策方法. 首先, 基于仅限于期望产出的企业规模收益判断方法, 建立包含非期望产出的GDEA模型与WY-DEA模型; 其次, 利用GDEA模型判断弱WY-DEA有效并购方案的规模收益不变、递增、递减或拥挤四种状态; 然后, 在剔除规模收益拥挤的并购方案基础上, 利用交叉效率模型为被收购企业选择最优的收购方; 最后, 以算例说明方法的可行性与优势.

带学习效应的两台平行机时间表长问题

朱征露, 鲁习文

2018, 22(1): 55-66. doi:10.15960/j.cnki.issn.1007-6093.2018.01.004

摘要 ( 1028 )

PDF (711KB) ( 320 )

相关文章 | 多维度评价

研究机器带学习效应, 目标函数为时间表长的两台平行机排序问题, 问题是NP-难的. 首先建立了求解该问题最优解的整数规划模型. 其次, 基于模拟退火算法给出了该问题的近似算法SA, 并证明了该算法依概率1 全局收敛到最优解. 最后, 通过数值模拟对所提出的算法进行了性能分析. 数值模拟结果表明, 近似算法SA可以达到最优值的99%, 准确度高, 算法较有效.

关联聚类问题的半定规划舍入算法

王一水, 徐大川, 吴晨晨

2018, 22(1): 67-76. doi:10.15960/j.cnki.issn.1007-6093.2018.01.005

摘要 ( 1121 )

PDF (1304KB) ( 307 )

相关文章 | 多维度评价

主要研究带有两类权重的一般图下的关联聚类问题. 问题的定义是, 给定图G=(V,E), 每条边有两类权重, 我们需要将点集V进行聚类, 目标是最大相同性, 即最大化属于某个类的边的第一类权重之和加上在两个不同类之间的边的第二类权重之和. 该问题是NP-难的, 我们利用外部旋转技术将现有的半定规划舍入0.75-近似算法改进. 算法的分析指出, 改进的算法虽然不能将近似比0.75提高, 但是对于大多数实例, 可以获得更好的运行效果.

无限阶段网络博弈中合作解的策略稳定性

王磊, 林崇, 谷岩, 刘翠, 高红伟

2018, 22(1): 77-86. doi:10.15960/j.cnki.issn.1007-6093.2018.01.006

摘要 ( 1093 )

PDF (591KB) ( 364 )

相关文章 | 多维度评价

合作博弈的经典合作解不满足时间一致性, 并缺乏策略稳定性. 本文研究无限阶段网络博弈合作解的策略稳定性理论. 首先建立时间一致的分配补偿程序实现合作解的动态分配, 然后建立针对联盟的惩罚策略, 给出合作解能够被强Nash均衡策略支撑的充分性条件, 最后证明了博弈中的惩罚策略局势是强Nash均衡, 从而保证了合作解的策略稳定性. 作为应用, 考察了重复囚徒困境网络博弈中Shapley值的策略稳定性.

一类博弈排序问题的纳什均衡存在性证明

张龙, 张玉忠, 柏庆国

2018, 22(1): 87-96. doi:10.15960/j.cnki.issn.1007-6093.2018.01.007

摘要 ( 1225 )

PDF (532KB) ( 401 )

相关文章 | 多维度评价

研究机器带有激活费用的博弈排序问题. 机器集由两类组成: 一类是速度为1、激活费用为B的k_1台同型机; 另一类是速度为a(>1)、激活费用为aB的k_2台同型机,
其中k_1与k_2是任意正整数. 工件作为``局中人", 其目的是极小化自身的费用, 工件的费用是由其所在机器的负载和其所承担的激活费用组成, 其中工件承担的激活费用与工件的加工时间成正比. 针对不同的情况, 设计不同的算法, 并证明各算法得到的排序都是纳什均衡.

基于特征根方法的M/G_N/1个性化服务排队顾客逗留时间分布函数的数值计算

邹雪华, 余玅妙, 唐应辉, 周杰

2018, 22(1): 97-108. doi:10.15960/j.cnki.issn.1007-6093.2018.01.008

摘要 ( 964 )

PDF (1294KB) ( 283 )

相关文章 | 多维度评价

以多语种便民服务热线为实际应用背景, 研究个性化服务M/G_N/1排队系统中顾客逗留时间分布函数的数值计算方法. 首先, 利用嵌入Markov链技术和Pollaczek-Khintchine变换公式给出顾客逗留时间的Laplace-Stieltjes(LS)变换. 其次, 根据个性化服务时间分布函数的具体类型, 给出上述LS变换的有理函数表达形式. 通过求解有理函数分母之具有负实部的零点, 即所谓的特征根, 最终使用部分分式分解方法和复分析中的留数理论给出顾客逗留时间的概率分布函数.

基于带约束的隐表示非线性形状配准

郑杨, 胡娟, 王永波, 彭亚新

2018, 22(1): 109-118. doi:10.15960/j.cnki.issn.1007-6093.2018.01.009

摘要 ( 979 )

PDF (5658KB) ( 291 )

相关文章 | 多维度评价

主要通过对形状进行带约束的隐表示来研究非线性形状配准. 首先, 采用隐函数的零水平集来表示形状, 并结合从整体到局部的策略, 对形状配准问题进行了建模. 其次, 为提高模型精度, 对全局尺度形变和局部非线性形变引入了尺度约束和带状约束. 进一步, 给出了一阶变分, 并应用负梯度流进行数值求解. 最后，多个数据集上与现有经典算法的对比实验表明, 给出的算法具有更优的精度.

一般均衡下基于产品市场和资本市场的单名CDS定价

陈艳声, 邹辉文, 蔡立雄, 祝群

2018, 22(1): 119-128. doi:10.15960/j.cnki.issn.1007-6093.2018.01.010

摘要 ( 886 )

PDF (1321KB) ( 227 )

相关文章 | 多维度评价

次贷危机呼吁新的信用衍生品定价模型, 因此为存在产品市场和资本市场的经济结构建立一般均衡的单名CDS定价模型, 使用最优化求解一般均衡下的商品价格和CDS价格. 可以发现一般均衡的CDS定价具有资本市场和产品市场的因素, 这表示CDS的价格不再是由单纯的资本市场因素决定的, 而是由无风险利率、资本产出弹性、违约率、回收率同时决定的. 通过数量约束用模拟的方式研究多个均衡的动态变化, 发现违约风险的增加使得价格剧烈波动且市场交易萎缩. 在为以中国工商银行为参考资产的CDS定价过程中, 发现各种因素在不同的时期都可能成为定价的主要影响因素. 可以发现, 次贷危机的定价体系存在着信用调整问题和定价与实体经济脱节的问题. 可以认为, 一般均衡下基于产品市场和资本市场的单名CDS定价可以囊括多个市场的交叉影响, 为衍生品定价提供一个新的方向.

含不动产项目的保险公司再保险-投资策略

陈树敏, 郝志峰

2018, 22(1): 129-141. doi:10.15960/j.cnki.issn.1007-6093.2018.01.011

摘要 ( 875 )

PDF (2524KB) ( 322 )

相关文章 | 多维度评价

站在保险公司管理者的角度, 考虑存在不动产项目投资机会时保险公司的再保险--投资策略问题. 假定保险公司可以投资于不动产项目、风险证券和无风险证券, 并通过比例再保险控制风险, 目标是最小化保险公司破产概率并求得相应最佳策略, 包括: 不动产项目投资时机、再保险比例以及投资于风险证券的金额. 运用混合随机控制-最优停时方法, 得到最优值函数及最佳策略的显式解. 结果表明, 当且仅当其盈余资金多于某一水平(称为投资阈值)时保险公司投资于不动产项目. 进一步的数值算例分析表明: (a)~不动产项目投资的阈值主要受项目收益率影响而与投资金额无明显关系, 收益率越高则投资阈值越低; (b)~市场环境较好(牛市)时项目的投资阈值降低; 反之, 当市场环境较差(熊市)时投资阈值提高.

三圈图的极小广义和连通指数

秦倩楠, 邵燕灵

2018, 22(1): 142-150. doi:10.15960/j.cnki.issn.1007-6093.2018.01.012

摘要 ( 734 )

PDF (4192KB) ( 303 )

相关文章 | 多维度评价

图的广义和连通指数作为新提出的一类分子拓扑指数, 在QSPR/QSAR 中有很大的应用价值. 树图、单圈图和双圈图的极值问题已取得很多结果, 而三圈图相关问题的研究较为复杂. 限制 - 1 \leqslant \alpha < 0, 对三圈图的广义和连通指数进行了研究. 通过对三圈图的分析, 构造了一种图的变换, 指出在三圈图中广义和连通指
数的极小值必由其中的七种类型图取得. 然后通过悬挂边的变换, 最终得到三圈图广义和连通指数的极小值并刻画了唯一的极图.

当期目录