运筹学学报

陈薪蓓, 朱明康, 陈建利

2019, 23(1): 1-14. doi:10.15960/j.cnki.issn.1007-6093.2019.01.001

摘要 ( 763 )

PDF (5439KB) ( 532 )

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

梯度硬阈值追踪算法是求解稀疏优化问题的有效算法之一.考虑到算法中投影对最优解的影响，提出一种比贪婪策略更好的投影算法是很有必要的.针对一般的稀疏约束优化问题，利用整数规划提出一种迭代投影策略，将梯度投影算法中的投影作为一个子问题求解.通过迭代求解该子问题得到投影的指标集，并以此继续求解原问题，以提高梯度硬阈值追踪算法的计算效果.证明了算法的收敛性，并通过数值实例验证了算法的有效性.

求解全局最优问题的多重点样本水平值估计的相对熵算法

周心怡, 汪可, 邬冬华, 汪晨

2019, 23(1): 15-27. doi:10.15960/j.cnki.issn.1007-6093.2019.01.002

摘要 ( 1073 )

PDF (668KB) ( 296 )

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

研究有界闭箱约束下的全局最优化问题，利用相对熵及广义方差函数方程的最大根与全局最小值之间的等价关系，设计求解全局最优值的积分型水平值估计算法.对采用重点样本采样技巧产生的函数值按一定规则进行聚类，从而在各聚类中产生的若干新重点样本，结合相对熵算法，构造出多重点样本进行全局搜索的新算法.该算法的优点在于每次迭代选用当前较好的函数值信息，以达到随机搜索到更好的函数值信息.同时多重点样本可有利挖掘出更好的全局信息.一系列的数值实验表明该算法是非常有效的.

求解带箱子集约束的非光滑全局优化问题的填充函数方法

王伟祥, 尚有林, 王朵

2019, 23(1): 28-34. doi:10.15960/j.cnki.issn.1007-6093.2019.01.003

摘要 ( 1086 )

PDF (553KB) ( 264 )

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

提出了一个求解带箱子集约束的非光滑全局优化问题的填充函数方法.构造的填充函数只包含一个参数，且此参数在迭代过程中容易调节.分析了填充函数的理论性质，在此基础上设计了填充函数算法.数值计算验证了该算法的有效性.

拟凸多目标优化问题近似解的最优性条件

陈瑞婷, 徐智会, 高英

2019, 23(1): 35-44. doi:10.15960/j.cnki.issn.1007-6093.2019.01.004

摘要 ( 865 )

PDF (626KB) ( 447 )

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

研究了拟凸多目标优化问题近似弱有效解、近似有效解的最优性条件.首先，在已有拟凸函数次微分的基础上引进4种近似次微分的概念，并给出它们之间的关系.然后，将4种近似次微分的概念应用到拟凸多目标优化问题中，给出了拟凸多目标优化问题近似弱有效解和近似有效解的充分条件和必要条件，并给出实例加以说明.

变序结构局部弱非控点的二阶刻画

徐义红, 梅芳

2019, 23(1): 45-52. doi:10.15960/j.cnki.issn.1007-6093.2019.01.005

摘要 ( 702 )

PDF (437KB) ( 1834 )

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

引进了一种二阶切导数，借助该切导数给出了变序结构集值优化问题取得局部弱非控点的二阶最优性必要条件.在某种特殊情况下，给出了一阶最优性条件.通过修正的Dubovitskij-Miljutin切锥导出的约束规格，给出了两个集值映射之和的二阶相依切导数的关系式，进一步得到目标函数与变锥函数的二阶相依切导数分开形式的最优性必要条件.

基于块循环矩阵的对称张量的最佳秩-1逼近

徐娇娇, 杨志霞, 蒋耀林

2019, 23(1): 53-60. doi:10.15960/j.cnki.issn.1007-6093.2019.01.006

摘要 ( 1049 )

PDF (517KB) ( 217 )

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

对称张量的最佳秩-1问题是张量研究中非常重要的部分.首先，基于三阶张量的块循环矩阵，提出了求解对称张量最佳秩-1逼近问题的一个新方法.其次，针对求解对称张量的最佳秩-1逼近方法，给出了对称张量的最佳秩-1逼近不变性的一个充要条件，以及逼近误差上界的估计.最后，数值算例表明了上述方法的可行性和误差上界的正确性.

带有固定区间的单机双代理可中断总误工问题

陈秋宏, 张新功

2019, 23(1): 61-71. doi:10.15960/j.cnki.issn.1007-6093.2019.01.007

摘要 ( 732 )

PDF (550KB) ( 243 )

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

研究带有固定区间的两个代理单机排序问题.第一个代理工件可中断，且工件到达时间与工期满足一致关系，目标函数为最小化总误工.第二个代理工件被安排在固定时间窗口.目标是寻找一个排序，使得满足第二个代理目标可行情况下，第一个代理目标函数值最小.在固定区间等于加工时间的情况下，利用分块原则，提出了一个伪多项式时间动态规划算法，并给出了固定区间大于加工时间情况下的时间复杂度分析.

新单圈图H(p,tK_1,m)的拉普拉斯谱刻画

孙秋实, 杨筱韵, 王力工, 李希赫, 王朋超

2019, 23(1): 72-80. doi:10.15960/j.cnki.issn.1007-6093.2019.01.008

摘要 ( 1011 )

PDF (559KB) ( 1249 )

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

设图H（p，tK_1，m）是一个顶点数为p+mt的连通单圈图，它是由圈C_p的依次相邻的t（1 ≤ t ≤ p）个顶点的每一个顶点分别与星K_1，m的中心重合而得到的单圈图.现证明单圈图H（p，p K_1，5），H（p，（p-1）K_1，4）是由它们的拉普拉斯谱确定的，并证明了当p为偶数时，单圈图H（p，2K_1，4），H（p，（p-2）K_1，4），H（p，（p-3）K_1，4）也是由它们的拉普拉斯谱确定的.

三圈图的无符号拉普拉斯谱半径

陈媛媛, 王国平

2019, 23(1): 81-89. doi:10.15960/j.cnki.issn.1007-6093.2019.01.009

摘要 ( 1267 )

PDF (867KB) ( 298 )

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

假设图G的点集是V（G）={v₁，v₂，…，v_n}，用d_{v_i}（G）表示图G中点v_i的度，令A（G）表示G的邻接矩阵，D（G）是对角线上元素等于d_{v_i}（G）的n×n对角矩阵，Q（G）=D（G）+A（G）是G的无符号拉普拉斯矩阵，Q（G）的最大特征值是G的无符号拉普拉斯谱半径.现确定了所有点数为n的三圈图中无符号拉普拉斯谱半径最大的图的结构.

补图具有悬挂点且连通的图的最小特征值

余桂东, 孙威, 芦兴庭

2019, 23(1): 90-96. doi:10.15960/j.cnki.issn.1007-6093.2019.01.010

摘要 ( 691 )

PDF (1051KB) ( 233 )

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

图的最小特征值定义为图的邻接矩阵的最小特征值，它是刻画图的结构性质的重要参数.在给定阶数且补图为具有悬挂点的连通图的图类中，刻画了最小特征值达极小的唯一图，并给出了这类图最小特征值的下界.

单圈图生成的凯莱图UG_n在PMC模型和MM^*模型下的1好邻诊断度

任佳敏, 冯伟, 赵凌琪, 王世英, 吉日木图

2019, 23(1): 97-103. doi:10.15960/j.cnki.issn.1007-6093.2019.01.011

摘要 ( 839 )

PDF (628KB) ( 259 )

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

多处理系统的诊断度是一个重要的研究课题.一种新的系统故障诊断方法称为g好邻诊断度，它是限制每个无故障点至少包含g个无故障的邻点.单圈图生成的凯莱图UG_n作为一种极好的互联网络拓扑结构有许多好的性质.现证明了当n ≥ 4时，单圈图生成的凯莱图UG_n在PMC模型下的1好邻诊断度是2n-1；当n ≥ 5时，UG_n在MM^*模型下的1好邻诊断度是2n-1.

不含5-圈和相邻4-圈的平面图的线性2-荫度的一个上界

陈宏宇, 谭香

2019, 23(1): 104-110. doi:10.15960/j.cnki.issn.1007-6093.2019.01.012

摘要 ( 912 )

PDF (541KB) ( 287 )

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

图G的一个边分解是指将G分解成子图G₁，G₂，…，G_m使得E（G）=E（G₁）∪ E（G₂）∪…∪ E（G_m），且对于i≠j，E（G_i）∩E（G_j）=∅.一个线性k-森林是指每个分支都是长度最多为k的路的图.图G的线性k-荫度la_k（G）是使得G可以边分解为m个线性k-森林的最小整数m.显然，la₁（G）是G的边色数χ'（G）；la_∞（G）表示每条分支路是无限长度时的情况，即通常所说的G的线性荫度la（G）.利用权转移的方法研究平面图的线性2-荫度la₂（G）.设G是不含有5-圈和相邻4-圈的平面图，证明了若G连通且δ（G）≥ 2，则G包含一条边xy使得d（x）+d（y）≤ 8或包含一个2-交错圈.根据这一结果得到其线性2-荫度的上界为?△/2?+4.

工件满足一致性的同类机在线分批排序问题

彭南南, 张玉忠, 柏庆国, 王成飞

2019, 23(1): 111-118. doi:10.15960/j.cnki.issn.1007-6093.2019.01.013

摘要 ( 855 )

PDF (590KB) ( 309 )

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

研究了工件满足一致性，批容量无界的两台同类机在线分批排序问题，目标为极小化工件的最大完工时间和极小化工件的最大流程时间，三元素法分别表示为Q₂|r_i < r_j⇒ p_i ≤ p_j，B=∞，on-line|C_max，Q₂|r_i < r_j⇒ p_i ≥ p_j，B=∞，on-line|F_max.不失一般性，假设第一台机器速度为1，第二台机器速度为s，s ≥ 1.对于上述两类问题设计了一个在线算法，并分析了算法竞争比的上界.对第一类问题该在线算法的竞争比不超过s+α，这里α为α²+sα-1=0的正根，特别地，当s=1时，该算法的竞争比不超过1.618.对第二类排序问题，该在线算法的竞争比不超过1+1/α.

不确定性自私路由模型的理论和应用

刁卓

2019, 23(1): 119-126. doi:10.15960/j.cnki.issn.1007-6093.2019.01.014

摘要 ( 593 )

PDF (668KB) ( 273 )

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

为了更加准确地描述现实生活中的交通情况，以经典的自私路由模型为基础，在边的费用函数上引入不确定性，从而定义了具有不确定性的自私路由模型.对于不确定性自私路由模型，采用三种费用衡量标准，风险厌恶型（保守型）、风险折衷型（理智型）、风险偏好型（乐观型），分别对应着不同人群在现实中的选择.进而定义了在不同衡量标准下所形成的稳定策略，即纳什均衡策略，并且证明了在任何一种衡量标准下，纳什均衡策略总是存在并且本质是唯一的.接着对三种费用衡量标准下的纳什均衡费用进行了比较，发现了一种反直观的现象：风险厌恶型（保守型）衡量标准下的纳什均衡费用可能严格低于风险偏好型（乐观型）衡量标准下的纳什均衡费用，即有可能会出现高风险低回报，低风险高回报的情况，这与经济学中高风险高回报，低风险低回报的原则是相违背的.以此为基础，进而提出了一种自私路由风险性悖论，并证明了这种自私路由风险回报悖论本质上是传统布雷斯悖论的推广.最后，刻画出了不会发生自私路由风险回报悖论的网络结构，证明了一个单对始终点网络不会发生自私路由风险回报悖论当且仅当它是序列-平行网络.

当期目录