当期目录

2022年 第26卷 第2期    刊出日期：2022-06-15

上一期    下一期

 

服务台不可靠的重试排队系统均衡分析

张钰, 王金亭

2022, 26(2):  1-15.  doi:10.15960/j.cnki.issn.1007-6093.2022.02.001

摘要 ( 2645 )   HTML ( 141)   PDF (1036KB) ( 243 )  

数据和表 | 参考文献 | 相关文章 | 多维度评价

本文研究服务台不可靠的M/M/1常数率重试排队系统中顾客的均衡进队策略, 其中服务台在正常工作和空闲状态下以不同的速率发生故障。在该系统中, 服务台前没有等待空间, 如果到达的顾客发现服务台处于空闲状态, 该顾客可占用服务台开始服务。否则, 如果服务台处于忙碌状态, 顾客可以选择留下信息, 使得服务台在空闲时可以按顺序在重试空间中寻找之前留下信息的顾客进行服务。当服务台发生故障时, 正在被服务的顾客会发生丢失, 且系统拒绝新的顾客进入系统。根据系统提供给顾客的不同程度的信息, 研究队长可见和不可见两种信息情形下系统的稳态指标, 以及顾客基于收入-支出函数的均衡进队策略, 并建立单位时间内服务商的收益和社会福利函数。比较发现, 披露队长信息不一定能提高服务商收益和社会福利。

随机Bregman ADMM及其在训练具有离散结构的支持向量机中的应用

吕袈豪, 罗洪林, 杨泽华, 彭建文

2022, 26(2):  16-30.  doi:10.15960/j.cnki.issn.1007-6093.2022.02.002

摘要 ( 2707 )   HTML ( 59)   PDF (895KB) ( 335 )  

数据和表 | 参考文献 | 相关文章 | 多维度评价

针对具有多块可分结构的非凸优化问题提出了一类新的随机Bregman交替方向乘子法，在周期更新规则下, 证明了该算法的渐进收敛性; 在随机更新的规则下, 几乎确定的渐进收敛性得以证明。数值实验结果表明, 该算法可有效训练具有离散结构的支持向量机。

随机二阶锥二次规划逆问题的SAA方法

王博, 初丽, 张立卫, 张宏伟

2022, 26(2):  31-44.  doi:10.15960/j.cnki.issn.1007-6093.2022.02.003

摘要 ( 2738 )   HTML ( 60)   PDF (829KB) ( 357 )  

数据和表 | 参考文献 | 相关文章 | 多维度评价

本文讨论一类随机的二阶锥二次规划逆问题, 该模型是一个含有二阶锥互补约束的随机二次规划模型, 对解释部分实际问题有着一定的优势。为了求解该模型, 本文引入了随机抽样技术和互补约束光滑化近似技术, 得到问题的近似子问题。本文证明, 只要子问题的解是存在且收敛的, 则该极限以概率一是原问题的C-稳定点; 若严格互补条件和二阶必要性条件成立, 则该极限以概率1是原问题的M-稳定点。一个简单的数值实验验证了该算法具有一定的可行性。

双边配给问题的Shapley解及其在博物馆通票问题中的应用

宫豆豆, 徐根玖, 侯东爽

2022, 26(2):  45-54.  doi:10.15960/j.cnki.issn.1007-6093.2022.02.004

摘要 ( 2686 )   HTML ( 17)   PDF (816KB) ( 266 )  

数据和表 | 参考文献 | 相关文章 | 多维度评价

双边配给问题描述了现实生活中一类带有二部图结构的稀缺资源配置问题, 例如, 在自然灾害期间救援物资的配给; 电力和天然气等自然资源按需分配; 高校引进人才调配等。本文通过求解线性规划, 并从联盟边际贡献的角度出发定义了双边配给问题的一个Shapley解。之后, 通过合作对策模型和解的公理化方法说明新解的合理性。首先, 建立双边配给问题的合作对策模型, 论证了新解与双边配给合作对策的Shapley值一致; 其次, 证明了Shapley解是唯一满足优先一致性的有效配给方案。最后, 将Shapley解应用于博物馆通票问题的研究, 探讨了博物馆合作制定通票后所得单票和通票收益的分配方式。

工件的释放时间和加工时间具有一致性的单机在线排序问题研究

李文杰, 李钰晶, 刘海玲

2022, 26(2):  55-63.  doi:10.15960/j.cnki.issn.1007-6093.2022.02.005

摘要 ( 2638 )   HTML ( 16)   PDF (835KB) ( 143 )  

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

工件的释放时间和加工时间具有一致性, 是指释放时间大的工件其加工时间不小于释放时间小的工件的加工时间, 即若$r_{i}\geq r_{j}$, 则$p_{i}\geq p_{j}$。本文在该一致性约束下, 研究最小化最大加权完工时间单机在线排序问题, 和最小化总加权完工时间单机在线排序问题, 并分别设计出$\frac{\sqrt{5}+1}{2}$-竞争的最好可能在线算法。

修正PRP共轭梯度方法求解无约束最优化问题

张慧玲, 赛·闹尔再, 吴晓云

2022, 26(2):  64-72.  doi:10.15960/j.cnki.issn.1007-6093.2022.02.006

摘要 ( 2946 )   HTML ( 22)   PDF (823KB) ( 375 )  

数据和表 | 参考文献 | 相关文章 | 多维度评价

基于著名的PRP共轭梯度方法，利用CG_DESCENT共轭梯度方法的结构，本文提出了一种求解大规模无约束最优化问题的修正PRP共轭梯度方法。该方法在每一步迭代中均能够产生一个充分下降的搜索方向，且独立于任何线搜索条件。在标准Wolfe线搜索条件下，证明了修正PRP共轭梯度方法的全局收敛性和线性收敛速度。数值结果展示了修正PRP方法对给定的测试问题是非常有效的。

 

工件有到达时间及可拒绝下的同类平行机排序问题的近似算法

毕春燕, 万龙, 罗文昌

2022, 26(2):  73-82.  doi:10.15960/j.cnki.issn.1007-6093.2022.02.007

摘要 ( 2597 )   HTML ( 12)   PDF (861KB) ( 211 )  

数据和表 | 参考文献 | 相关文章 | 多维度评价

本文研究工件有到达时间且可拒绝下的同类平行机排序问题。在该问题中, 给定一个待加工工件集, 每个工件在到达之后, 可以被选择安排到$m$台同类平行机器中的某一台机器上进行加工, 也可以被选择拒绝加工, 但需支付一定的拒绝惩罚费用。目标函数是最小化接受工件集的最大完工时间与拒绝工件集的总拒绝费用之和。当$m$为固定常数时, 设计了一个伪多项式时间动态规划精确算法; 当$m$为任意输入时, 设计了一个近似算法, 当接受工件个数大于$(m-1)$时, 该算法近似比为3, 当接受工件个数小于$(m-1)$时, 该算法近似比为$(2+\rho)$, 其中$\rho$为机器加工速度最大值和最小值的比值。最后通过算例演示了算法的运行。

一种求解二次约束二次规划问题的自适应全局优化算法

黄小利, 高岳林, 张博, 刘霞

2022, 26(2):  83-100.  doi:10.15960/j.cnki.issn.1007-6093.2022.02.008

摘要 ( 2740 )   HTML ( 14)   PDF (871KB) ( 293 )  

数据和表 | 参考文献 | 相关文章 | 多维度评价

为了更好地解决二次约束二次规划问题(QCQP), 本文基于分支定界算法框架提出了自适应线性松弛技术, 在理论上证明了这种新的定界技术对于解决(QCQP)是可观的。文中分支操作采用条件二分法便于对矩形进行有效剖分; 通过缩减技术删除不包含全局最优解的部分区域, 以加快算法的收敛速度。最后, 通过数值结果表明提出的算法是有效可行的。

最短路博弈群体单调分配方案构造

陈泽融, 肖汉

2022, 26(2):  101-110.  doi:10.15960/j.cnki.issn.1007-6093.2022.02.009

摘要 ( 2723 )   HTML ( 21)   PDF (864KB) ( 192 )  

数据和表 | 参考文献 | 相关文章 | 多维度评价

群体单调分配方案(Population Monotonic Allocation Scheme, 后简称PMAS)是合作博弈的一类分配机制。在合作博弈中, PMAS为每一个子博弈提供一个满足群体单调性的核中的分配方案, 从而保证大联盟的动态稳定性。本文主要贡献为利用线性规划与对偶理论构造与求解一类基于最短路问题的合作博弈(最短路博弈)的PMAS。我们首先借助对偶理论, 利用组合方法为最短路博弈构造了一个基于平均分摊思想的PMAS。然后借鉴计算核仁的Maschler方案, 将PMAS的存在性问题转化为一个指数规模的线性规划的求解问题, 并通过巧妙的求解得到了与之前组合方法相同的最短路博弈的PMAS。

平面图的强边染色

卜月华, 张恒

2022, 26(2):  111-127.  doi:10.15960/j.cnki.issn.1007-6093.2022.02.010

摘要 ( 2699 )   HTML ( 14)   PDF (1349KB) ( 186 )  

数据和表 | 参考文献 | 相关文章 | 多维度评价

图$G$的强边染色是在正常边染色的基础上, 要求距离不超过$2$的任意两条边染不同的颜色, 强边染色所用颜色的最小整数称为图$G$的强边色数。本文首先给出极小反例的构型, 然后通过权转移法, 证明了$g(G)\geq5$, $\Delta(G)\geq6$且$5$-圈不相交的平面图的强边色数至多是$4\Delta(G)-1$。

求解张量随机互补问题的光滑牛顿算法

单锡泉, 李梅霞, 刘瑾瑜

2022, 26(2):  128-136.  doi:10.15960/j.cnki.issn.1007-6093.2022.02.011

摘要 ( 2675 )   HTML ( 10)   PDF (785KB) ( 167 )  

数据和表 | 参考文献 | 相关文章 | 多维度评价

近年来, 越来越多的人意识到随机互补问题在经济管理中具有十分重要的作用。有学者已将随机互补问题由矩阵推广到张量, 并提出了张量随机互补问题。本文通过引入一类光滑函数, 提出了求解张量随机互补问题的一种光滑牛顿算法, 并证明了算法的全局和局部收敛性, 最后通过数值实验验证了算法的有效性。

k圈图的最大Laplace分离度

余桂东, 阮征, 舒阿秀

2022, 26(2):  137-142.  doi:10.15960/j.cnki.issn.1007-6093.2022.02.012

摘要 ( 2607 )   HTML ( 10)   PDF (1098KB) ( 136 )  

数据和表 | 参考文献 | 相关文章 | 多维度评价

设$ G $是一个$ n $阶$ k $圈图, $ k $圈图为边数等于顶点数加$ k-1 $的简单连通图。$ \mu_{1}(G) $、$ \mu_{2}(G) $分别记为图$ G $的Laplace矩阵的最大特征值和次大特征值, 图$ G $的Laplace分离度定义为$ S_{L}(G)=\mu_{1}(G)-\mu_{2}(G) $。本文研究了给定阶数的$ k $圈图的最大Laplace分离度, 并刻画了相应的极图, 其结果推广了已有当$ k=1, 2, 3 $时的结论。