当期目录

2020年 第24卷 第4期    刊出日期：2020-12-15

上一期    下一期

稀疏优化理论与算法若干新进展

赵晨, 罗自炎, 修乃华

2020, 24(4):  1-24.  doi:10.15960/j.cnki.issn.1007-6093.2020.04.001

摘要 ( 6352 )   PDF (949KB) ( 1486 )  

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

稀疏优化是指带有ℓ₀范数正则或稀疏约束的一类重要的非凸非连续优化问题，并被广泛应用于信号和图像处理、机器学习、经济学、统计学等众多领域。经过十多年的发展，稀疏优化已经成为当下热门的研究方向，并已获得丰富的研究成果。为进一步拓展稀疏优化研究，将重点关注最近五年该领域的最新研究成果，并从理论与算法两个方面进行总结与评述，同时列出相关的重要文献以供读者参考。

广义凸区间值优化问题的最优性条件

黎君, 陈加伟, 邓光菊

2020, 24(4):  25-38.  doi:10.15960/j.cnki.issn.1007-6093.2020.04.002

摘要 ( 874 )   PDF (663KB) ( 217 )  

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

引入一种区间CW-序关系，借助CW-序关系引入了区间值预不变凸，伪不变凸和拟不变凸函数，并建立了几类区间值广义不变凸函数之间的关系。最后，在区间值不变凸性条件下，利用标量化方法建立了不变凸区间值优化问题的最优性条件。

复杂多层次指标合成技术及效率分析

曹莉, 马占新, 马生昀

2020, 24(4):  39-50.  doi:10.15960/j.cnki.issn.1007-6093.2020.04.003

摘要 ( 876 )   PDF (1133KB) ( 199 )  

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

数据包络分析（data envelopment analysis，DEA）方法在评价复杂系统效率问题时，由于评价指标过多，常常导致多个单元有效，使评价结果失去意义，而把指标合成为几个主要指标，又很难找到针对原始指标的投影。为解决上述问题，给出了一种用于面向输出的复杂系统效率评价的DEA模型，探讨了相应的DEA有效性含义、模型性质以及模型的求解方法。最后，利用该方法对内蒙古自治区14所三甲医院综合运营效率进行了分析。

地铁网络关键节点二次规划模型与求解算法研究

郭晓玲, 庄远鑫, 刘轶凡

2020, 24(4):  51-62.  doi:10.15960/j.cnki.issn.1007-6093.2020.04.004

摘要 ( 817 )   PDF (4630KB) ( 278 )  

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

地铁网络中的关键节点对其连通性有着重要的影响。在有限的资源以及人力物力下，找出其中的关键节点进行强化管理以减小随机故障对整个网络造成的损失是非常重要的。应用二次约束二次规划模型，针对赋权网络，综合考虑节点移除后对网络的整体结构和功能的影响，给出了计算网络连通性的一个新测度——一步连接和两步连接；并基于模型特点设计了遗传算法。最后，以北京市地铁网络为例进行求解，表明了该方法的有效性和优越性。

非线性整数规划问题的无参数填充函数算法

赵丹, 高岳林

2020, 24(4):  63-73.  doi:10.15960/j.cnki.issn.1007-6093.2020.04.005

摘要 ( 759 )   PDF (665KB) ( 212 )  

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

为解决无约束非线性整数规划问题，提出了一个新的无参数填充函数算法。构造的填充函数与原函数有相同的局部极小点，因此可以通过不断极小化填充函数从而找到全局最优解，极大地减少计算量，提高计算效率。通过对六个测试函数进行数值实验，结果表明这个算法是有效可行的。

加权Solidarity值的公理化及其程序实现

杨慧, 徐根玖, 王文娜

2020, 24(4):  74-82.  doi:10.15960/j.cnki.issn.1007-6093.2020.04.006

摘要 ( 733 )   PDF (675KB) ( 175 )  

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

在合作对策中引入归一化权重系统，给出加权Solidarity值的递归定义，在收益分配过程中照顾到联盟中的弱势参与者，并运用权重参数度量参与者之间的差异、调整对弱势参与者的保护程度。通过定义解的期望变异加权对称性，从代数角度给出公理化加权Solidarity值的新方法。设计加权Solidarity值的递归实现算法，并通过案例将加权Solidarity值与其他经典解进行比较，分析加权Solidarity值的合理性。

集值优化中扰动映射的二阶S导数的灵敏度分析

汤卫, 杨赟

2020, 24(4):  83-92.  doi:10.15960/j.cnki.issn.1007-6093.2020.04.007

摘要 ( 782 )   PDF (571KB) ( 98 )  

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

引进一种新的二阶切导数，称为二阶S导数，并讨论它的性质以及它与二阶切导数的关系。借助二阶S导数，建立集值映射切导数的极小值与扰动映射切导数之间的关系。

安装时间具有退化效应的MapReduce模型下的平行机调度

黄基诞, 郑斐峰, 徐寅峰, 刘明

2020, 24(4):  93-106.  doi:10.15960/j.cnki.issn.1007-6093.2020.04.008

摘要 ( 727 )   PDF (3069KB) ( 153 )  

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

考虑了平行机环境下安装时间具有退化效应且加工时间具有分步恶化效应的MapReduce模型调度优化问题。在MapReduce模型中，每个工件包含Map和Reduce两道工序。其中，Map工序可以分割成若干个子任务并在多台平行机上同时加工，而Reduce工序只有在该工件Map工序的所有子任务完成后才能启动加工，而且只能在一台机器上连续加工。研究Reduce工序的启动安装时间具有线性恶化效应、两个工序的加工时间具有分步恶化效应的平行机调度问题，构建了以最小化最大完成时间为优化目标的混合整数规划模型。给出了问题解的一个下界；同时，设计了采用单纯形差分扰动机制的改进灰狼算法以及贪婪算法进行模型求解。最后，利用数值仿真实验，将灰狼优化算法、贪婪算法、遗传算法的解与问题的下界进行对比，验证了模型与所设计算法的有效性。

带树层次加工集约束的调度问题

张玉忠, 李曙光

2020, 24(4):  107-112.  doi:10.15960/j.cnki.issn.1007-6093.2020.04.009

摘要 ( 642 )   PDF (606KB) ( 141 )  

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

研究工件带释放时间、送货时间和树层次加工集约束的调度问题。工件的加工开始时间不能早于它的释放时间，送货开始时间等于它的加工完成时间。所有机器形成一个树层次结构：若某机器能加工某工件，则该机器在树上的所有祖先均能加工该工件，这些机器构成该工件的加工集。目标是极小化最大送货完成时间。对于工件释放时间和送货时间任意的一般情形，给出了一个多项式时间近似方案（PTAS）。

基于T-联盟Shapley值的分配策略

于晓辉, 杜志平, 张强, 逄金辉

2020, 24(4):  113-127.  doi:10.15960/j.cnki.issn.1007-6093.2020.04.010

摘要 ( 716 )   PDF (701KB) ( 256 )  

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

考虑合作博弈中子联盟整体参与合作的情形，提出了T-联盟相关概念，对Shapley提出的公理进行拓广，并构造了T-联盟Shapley值。针对局中人在合作完成后需要分配收益的情况，利用构造的T-联盟Shapley值给出了子联盟在博弈中的利益分配方案，并分析了该分配方法的相关性质。给出了局中人接受子联盟作为整体参与合作博弈的条件。T-联盟Shapley值是经典Shapley值的扩展，该分配方法允许子联盟中的局中人作为整体参与合作，从而为局中人选择联盟的合作形式提供了理论依据。最后，通过实例分析了局中人依据T-联盟Shapley值选择合作联盟的过程。

单圈图的次大(拉普拉斯)分离度

余桂东, 阮征, 舒阿秀, 于涛

2020, 24(4):  128-134.  doi:10.15960/j.cnki.issn.1007-6093.2020.04.011

摘要 ( 689 )   PDF (896KB) ( 171 )  

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

设G是一个n阶单圈图，λ₁（G）、λ₂（G）分别为图G的邻接矩阵的最大特征值与次大特征值，μ₁（G）、μ₂（G）分别为图G的拉普拉斯矩阵的最大特征值与次大特征值。图G的分离度定义为S_A（G）=λ₁（G）-λ₂（G），拉普拉斯分离度定义为S_L（G）=μ₁（G）-μ₂（G）。研究单圈图的（拉普拉斯）分离度，并分别给出了取得次大分离度和次大拉普拉斯分离度的极图。

具有较大Randić指数的仙人掌图

王娅静, 高玉斌

2020, 24(4):  135-144.  doi:10.15960/j.cnki.issn.1007-6093.2020.04.012

摘要 ( 569 )   PDF (2450KB) ( 250 )  

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

Randić指数是一类重要的分子拓扑指数，在数学及化学研究中有重要作用。树图、单圈图以及双圈图的Randić指数的上下界及其极图已有相关的结论。仙人掌图Randić指数的下界及极图已被刻画，而极大图的研究较为复杂。通过对仙人掌图中边的顶点度的分析，定义了对称边和非对称边，并且刻画了图的一些变换。在此基础上，根据仙人掌图中顶点的最大度分情况讨论，得到了给定圈数r的n阶仙人掌图中具有前五大Randić指数的极图中的非对称边结构。

超图的限制边连通度与最优限制边连通

童林肯, 单而芳

2020, 24(4):  145-152.  doi:10.15960/j.cnki.issn.1007-6093.2020.04.013

摘要 ( 1137 )   PDF (1203KB) ( 179 )  

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

设H=（V，E）是顶点集为V，超边集为E的连通超图。对H的边子集S，若H\S不连通而且不含孤立点，则称S是H的一个限制边割。把H中最小限制边割的基数称为H的限制边连通度，记为λ'（H）。对边e，其边度是指在H中与e相交的超边的数目，H中最小边度记为ξ（H）。如果λ'（H）=ξ（H），那么称超图H是最优限制边连通的，简记为λ'-最优。研究超图H的限制边连通度和λ'-最优，推广了图上关于限制边连通度和λ'-最优的一些结论。

区间图最小伸展支撑树问题的最优性刻画

林浩, 林澜

2020, 24(4):  153-158.  doi:10.15960/j.cnki.issn.1007-6093.2020.04.014

摘要 ( 816 )   PDF (772KB) ( 125 )  

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

图G的最小伸展支撑树问题是寻求图G的支撑树T，使得相邻两顶点在T中的最大距离达到最小。这个最小值称为图G的树展，记作σ（G）。此问题已被证明为NP-困难的，对若干特殊图类亦已得到上界估计。例如对区间图已知σ（G）≤ 3，对区间图得到σ（G）=k，k=1，2，3的完整刻画。