运筹学学报

安邦, 程朋

2015, 19(4): 1-13. doi:10.15960/j.cnki.issn.1007-6093.2015.04.001

摘要 ( 845 )

PDF (1591KB) ( 846 )

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

无容量限制设施选址问题是经典的组合优化问题, 具有广泛的应用价值,然而该问题已被证明是NP难问题, 并且传统的分支定界方法求解速度较慢.研究以最大化总收益费用与总投建费用之差为目标的无容量限制设施选址问题,将其转化为节点包装问题,并根据模型的图形特点提出了新的合法不等式族------轴不等式族,经过严格的数学证明后得出轴不等式要强于原有的奇洞不等式. 同时,设计出切割不等式快速搜索算法嵌入到分支割平面方法中. 最后,通过实验验证了轴不等式族的强有效性,
以及分支割平面方法比分支定界方法求解速度快、节点数量少的优点.

关于可靠性设施布局问题的近似算法

闫林成, 肖汉, 赵红娟, 孙小淇

2015, 19(4): 14-24. doi:10.15960/j.cnki.issn.1007-6093.2015.04.002

摘要 ( 746 )

PDF (569KB) ( 552 )

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

设施布局问题的研究始于20世纪60年代,主要研究选择修建设施的位置和数量,以及与需要得到服务的城市之间的分配关系,使得设施的修建费用和设施与城市之间的连接费用之和达到最小.现实生活中, 受自然灾害、工人罢工、恐怖袭击等因素的影响,修建的设施可能会出现故障, 故连接到它的城市无法得到供应,这就直接影响到了整个系统的可靠性.针对如何以相对较小的代价换取设施布局可靠性的提升,研究人员提出了可靠性设施布局问题.参考经典设施布局问题的贪婪算法、原始对偶算法和容错性问题中分阶段分层次处理的思想,设计了可靠性设施布局问题的一个组合算法.该算法不仅在理论上具有很好的常数近似度,而且还具有运算复杂性低的优点.这对于之前的可靠性设施布局问题只有数值实验算法, 是一个很大的进步.

基于数据包络分析的并行生产系统效率评价方法

王有森, 许皓

2015, 19(4): 25-36. doi:10.15960/j.cnki.issn.1007-6093.2015.04.003

摘要 ( 631 )

PDF (694KB) ( 426 )

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

数据包络分析是一种评价具有多投入、多产出决策单元的相对效率的线性规划方法.在现实世界中,决策单元有时呈现出由多个独立子系统构成的复杂并联网络系统,各子系统的投入/产出之和构成了系统的总投入/产出. 目前,用于评价这种具有并联网络生产系统相对效率的模型主要有三种:网络 DEA 模型、多部门 DEA 模型和关联 DEA 模型.现有这些模型的基本特性和相互关系存在着不足,即子系统的效率分解和优化指数不唯一. 为解决这一问题,提出了改进的并联 DEA 模型,并采用加拿大银行系统实例来说明所提出模型的合理性和有效性.

求解无容量设施选址问题的半拉格朗日松弛新方法

张惠珍, 魏欣, 马良

2015, 19(4): 37-47. doi:10.15960/j.cnki.issn.1007-6093.2015.04.004

摘要 ( 1173 )

PDF (649KB) ( 533 )

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

无容量设施选址问题Un-capacitated Facility Location, UFL是应用于诸多领域的经典组合优化难题, 半拉格朗日松弛方法是求解UFL问题的一种精确方法. 分析了半拉格朗日松弛方法在求解UFL问题时所具有的性质, 在此基础上, 对求解UFL问题的半拉格朗日松弛方法进行了一定的理论完善, 并探讨了提高半拉格朗日松弛方法求解性能的有效途径.数值计算结果表明：改进方法具有明显的可行性和有效性.

不等式约束优化一个可行序列线性方程组算法

马国栋, 简金宝

2015, 19(4): 48-58. doi:10.15960/j.cnki.issn.1007-6093.2015.04.005

摘要 ( 930 )

PDF (571KB) ( 490 )

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

提出了求解非线性不等式约束优化问题的一个可行序列线性方程组算法. 在每次迭代中, 可行下降方向通过求解两个线性方程组产生, 系数矩阵具有较好的稀疏性. 在较为温和的条件下, 算法具有全局收敛性和强收敛性, 数值试验表明算法是有效的.

基于部分三角函数变换矩阵的块压缩感知测量方法

陈建, 苏凯雄, 彭拯, 苏立超

2015, 19(4): 59-71. doi:10.15960/j.cnki.issn.1007-6093.2015.04.006

摘要 ( 982 )

PDF (4593KB) ( 391 )

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

为了提高块压缩感知的测量效率和重构性能,根据离散余弦变换和离散正弦变换具有汇聚信号能量的特性,提出了基于重复块对角结构的部分离散余弦变换partial discrete cosine transform in repeated block diagonal structure,简称PDCT-RBDS和部分离散正弦变换partial discrete sine transform in repeated block diagonal structure简称PDST-RBDS的两种压缩感知测量方法.所采用的测量矩阵是一种低复杂度的结构化确定性矩阵, 满足受限等距性质.并得到一个与采样能量有关的受限等距常数和精确重构的测量数下限.通过与采用重复块对角结构的部分随机高斯矩阵和部分贝努利矩阵的图像压缩感知对比,结果表明PDCT-RBDS和PDST-RBDS重构的PSNR大约提高1---5dBSSIM提高约0.05, 所需的重构时间和测量矩阵的存储空间大大减少.该方法特别适合大规模图像压缩及实时视频数据处理场合.

紧图的两个结果及其应用

斯琴巴特尔, 王井玉

2015, 19(4): 72-82. doi:10.15960/j.cnki.issn.1007-6093.2015.04.007

摘要 ( 707 )

PDF (1484KB) ( 394 )

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

双随机矩阵有许多重要的应用, 紧图族可以看作是组合矩阵论中关于双随机矩阵的著名的Birkhoff定理的拓广,具有重要的研究价值．确定一个图是否紧图是个困难的问题,目前已知的紧图族尚且不多.给出了两个重要结果：任意紧图与任意多个孤立点的不交并是紧图；任意紧图的每一个顶点上各增加一条悬挂边的图是紧图．利用这两个结果,从已知紧图可构造出无穷多个紧图族．

一个阶为2+\sqrt{6}的Newton改进算法

吕巍, 隋瑞瑞, 冯恩民

2015, 19(4): 83-96. doi:10.15960/j.cnki.issn.1007-6093.2015.04.008

摘要 ( 792 )

PDF (565KB) ( 497 )

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

针对非线性方程求单根问题,提出了一种新的Newton预测-校正格式.通过每步迭代增加计算一个函数值和一阶导数值,使得每步迭代需要估计两个函数值和两个一阶导数值.与标准的Newton算法的二阶收敛速度相比,新算法具有更高阶的收敛速度2+\sqrt{6}.通过测试函数对新算法进行测试, 与相关算法比较,表明算法在迭代次数、运算时间及最优值方面都具有较明显的优势. 最后,将这种新格式推广到多维向量值函数, 采用泰勒公式证明了其收敛性,并给出了两个二维算例来验证其收敛的有效性.

多选择NTU对策核心的一个非空条件及公理化

田海燕, 张刚

2015, 19(4): 97-106. doi:10.15960/j.cnki.issn.1007-6093.2015.04.009

摘要 ( 1089 )

PDF (550KB) ( 394 )

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

提出了\pi-均衡多选择NTU对策的概念,证明了\pi-均衡多选择NTU对策的核心非空, 定义了多选择NTU对策的非水平性质和缩减对策,给出了相容性和逆相容性等概念. 用个体合理性、单人合理性、相容性和逆相容性对非水平多选择NTU对策的核心进行了公理化.

向量优化中Free Disposal集的某些对偶性质

唐莉萍, 杨玉红

2015, 19(4): 107-113. doi:10.15960/j.cnki.issn.1007-6093.2015.04.010

摘要 ( 847 )

PDF (485KB) ( 582 )

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

在分离局部凸空间中考虑free disposal集的对偶性质, 其中free disposal集是指与凸锥的代数和仍是其本身的集合.在E_1或E_2是free disposal集的条件下,证明了(E_1\cap E_2)^+=E_1^++ E_2^+和E_1^+ \cap E_2^+=(E_1+E_2)^+等对偶结果.

Shapley值与Winter值的解析关系

胡勋锋, 李登峰

2015, 19(4): 114-120. doi:10.15960/j.cnki.issn.1007-6093.2015.04.011

摘要 ( 1021 )

PDF (484KB) ( 499 )

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

鉴于 Shapley 值和 Winter 值都是局中人边际贡献的平均值,探究了它们之间的解析关系.证明了 Shapley 值是 Winter 值在层次结构集上对称概率分布下的期望均值. 作为这一结论的一个推论, 证明了 Shapley 值是 Winter 值在层次结构集的任意相似类中的平均值. 最后,还指出了这一结论与推论的等价性.研究结果不仅扩展了 Shapley 值和 Owen 值与此对应的解析关系, 还大大简化了这些关系的已有证明.

平行机上带有前瞻区间的不相容工件组在线排序问题

李文华, 柴幸, 袁航, 杨素芳

2015, 19(4): 121-126. doi:10.15960/j.cnki.issn.1007-6093.2015.04.012

摘要 ( 876 )

PDF (509KB) ( 519 )

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

研究当不相容工件组的个数与机器数相等时,具有前瞻区间的单位工件平行机无界平行分批在线排序问题.工件按时在线到达, 目标是最小化最大完工时间. 具有前瞻区间是指在时刻t, 在线算法能预见到时间区间(t,t+\beta) 内到达的所有工件的信息.不可相容的工件组是指属于不同组的工件不能被安排在同一批中加工. \beta\geq 1 时, 提供了一个最优的在线算法; 当0\leq \beta < 1时, 提供了一个竞争比为1+\alpha 的最好可能的在线算法, 其中\alpha是方程\alpha^{2}+(1+\beta) \alpha+\beta-1=0的一个正根.最后, 给出了当\beta =0 时稠密算法竞争比的下界,并提供了达到该下界的最好可能的稠密算法.

当期目录