当期目录

2019年 第23卷 第2期    刊出日期：2019-06-15

上一期    下一期

运筹学

具有Min(N,D,V)-策略控制的M/G/1排队系统

罗乐, 唐应辉

2019, 23(2):  1-16.  doi:10.15960/j.cnki.issn.1007-6093.2019.02.001

摘要 ( 1123 )   PDF (2405KB) ( 206 )  

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

研究服务员具有多重休假和系统采取MinMin（N,D,V）-策略控制的M/G/1排队系统，运用全概率分解技术和拉普拉斯变换工具，研究了系统队长的瞬态分布和稳态分布，得到了队长瞬态分布的拉普拉斯变换的表达式和稳态队长分布的递推表达式，同时给出了稳态队长的随机分解结果和附加队长分布的显示表达式.进一步讨论了当N→∞，或D→∞，或p{V=∞}=1，或p{V=0}=1的一些特殊情况.最后，在建立系统费用结构模型的基础上，导出了系统长期单位时间的期望费用的显示表达式，并通过数值实例不但确定了使得系统在长期单位时间内的期望费用最小的联合控制策略（N^*，D^*），而且与单一的最优N^*-控制策略和D^*-控制策略进行了比较.

求解非光滑方程组的三次正则化方法

苗小楠, 顾剑, 肖现涛

2019, 23(2):  17-30.  doi:10.15960/j.cnki.issn.1007-6093.2019.02.002

摘要 ( 1298 )   PDF (583KB) ( 245 )  

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

考虑求解非光滑方程组的三次正则化方法及其收敛性分析.利用信赖域方法的技巧，保证该方法是全局收敛的.在子问题非精确求解和BD正则性条件成立的前提下，分析了非光滑三次正则化方法的局部收敛速度.最后，数值实验结果验证了该算法的有效性.

图的区间边着色的收缩图方法

陶艳亮, 黄琼湘, 陈琳

2019, 23(2):  31-43.  doi:10.15960/j.cnki.issn.1007-6093.2019.02.003

摘要 ( 1236 )   PDF (1678KB) ( 160 )  

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

图G的一个用了颜色1，2，…，t的边着色称为区间t-着色，如果所有t种颜色都被用到，并且关联于G的同一个顶点的边上的颜色是各不相同的，且这些颜色构成了一个连续的整数区间.G称作是可区间着色的，如果对某个正整数t，G有一个区间t-着色.所有可区间着色的图构成的集合记作N.对图G∈N，使得G有一个区间t-着色的t的最小值和最大值分别记作w（G）和W（G）.现给出了图的区间着色的收缩图方法.利用此方法，我们对双圈图G∈N，证明了w（G）=△（G）或△（G）+1，并且完全确定了w（G）=△（G）及w（G）=△（G）+1的双圈图类.

基于Stein-Stein波动率和动态VaR约束下DC型养老基金的最优投资策略

孙景云, 田丽娜, 陈峥

2019, 23(2):  44-56.  doi:10.15960/j.cnki.issn.1007-6093.2019.02.004

摘要 ( 1955 )   PDF (2552KB) ( 178 )  

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

研究了确定缴费型养老基金在退休前累积阶段的最优资产配置问题.假设养老基金管理者将养老基金投资于由一个无风险资产和一个价格过程满足Stein-Stein随机波动率模型的风险资产所构成的金融市场.利用随机最优控制方法，以最大化退休时刻养老基金账户相对财富的期望效用为目标，分别获得了无约束情形和受动态VaR（Value at Risk）约束情形下该养老基金的最优投资策略，并获得相应最优值函数的解析表达形式.最后通过数值算例对相关理论结果进行数值验证并考察了最优投资策略关于相关参数的敏感性.

基于PH服务的工作休假排队的流体模型

王慧宁, 徐秀丽

2019, 23(2):  57-66.  doi:10.15960/j.cnki.issn.1007-6093.2019.02.005

摘要 ( 1345 )   PDF (939KB) ( 154 )  

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

研究了带有单重工作休假的M/PH/1排队系统驱动的流体模型.首先，通过拟生灭过程和矩阵几何解法分别得到无穷小生成元和驱动过程的稳态队长分布.其次，建立并分析流体模型，根据平衡方程给出流体模型的稳态联合分布函数满足的矩阵微分方程组，利用Laplace变换（LT）和Laplace-Stieltjes变换（LST）的方法，推导出平稳缓冲器（库）容量的空库概率表达式和稳态条件下的缓冲器（库）容量的均值表达式.最后，给出模型在移动自组织网络（Ad Hoc）中的应用，并通过数值例子讨论系统参数对系统性能指标的影响.

工件具有子工件工期的排序问题

仲维亚, 杨若瑶

2019, 23(2):  67-74.  doi:10.15960/j.cnki.issn.1007-6093.2019.02.006

摘要 ( 1219 )   PDF (500KB) ( 153 )  

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

研究了工件具有子工件工期的排序问题.需要在一台单机上加工若干个给定的工件.每个工件由若干个子工件组成，每个子工件都有各自的工期.只有当工件的每个子工件都按时完成，才能称该工件是按时完工工件，否则，称该工件产生延误.目标是最大化按时完工的工件个数.证明当每个工件都被分成两个子工件时，该问题是NP-难的，而且不存在完全多项式时间近似方案（fully polynomialtime approximation scheme，简记为FPTAS）.提出两个启发式算法，利用数值模拟比较它们的性能，并且将这两个启发式算法的解与最优解的上界进行比较.

中国高考招生匹配市场中的算法设计及公平激励机制

李建荣

2019, 23(2):  75-85.  doi:10.15960/j.cnki.issn.1007-6093.2019.02.007

摘要 ( 1327 )   PDF (575KB) ( 2082 )  

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

用匹配博弈的方法，研究中国高考招生市场的算法设计及公平激励机制.基于高考招生程序，构建高考招生匹配算法，证明该算法的可行性.证明一个稳定匹配，可以由一个纳什均衡策略经高考招生算法生成，但反之不一定成立.证明一个稳定匹配一定是公平的，反之不一定成立.构建拒绝-接受算法，证明该算法是一个稳定的、策略防御的匹配机制，因而是一个公平的激励机制.

求解稀疏逻辑回归问题的嵌套BB算法的分裂增广拉格朗日算法

梁仁莉, 白延琴

2019, 23(2):  86-94.  doi:10.15960/j.cnki.issn.1007-6093.2019.02.008

摘要 ( 863 )   PDF (873KB) ( 191 )  

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

逻辑回归是经典的分类方法，广泛应用于数据挖掘、机器学习和计算机视觉.现研究带有l₀模约束的逻辑回归问题.这类问题广泛用于分类问题中的特征提取，且一般是NP-难的.为了求解这类问题，提出了嵌套BB（Barzilai and Borwein）算法的分裂增广拉格朗日算法（SALM-BB）.该算法在迭代中交替地求解一个无约束凸优化问题和一个带l₀模约束的二次优化问题.然后借助BB算法求解无约束凸优化问题.通过简单的等价变形直接得到带l₀模约束二次优化问题的精确解，并且给出了算法的收敛性定理.最后通过数值实验来测试SALM-BB算法对稀疏逻辑回归问题的计算精确性.数据来源包括真实的UCI数据和模拟数据.数值实验表明，相对于一阶算法SLEP，SALM-BB能够得到更低的平均逻辑损失和错分率.

均衡约束数学规划问题的一类广义Mond-Weir型对偶理论

高雷阜, 闫婷婷

2019, 23(2):  95-103.  doi:10.15960/j.cnki.issn.1007-6093.2019.02.009

摘要 ( 1007 )   PDF (483KB) ( 172 )  

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

针对均衡约束数学规划模型难以满足约束规范及难于求解的问题，基于Mond和Weir提出的标准非线性规划的对偶形式，利用其S稳定性，建立了均衡约束数学规划问题的一类广义Mond-Weir型对偶，从而为求解均衡约束优化问题提供了一种新的方法.在Hanson-Mond广义凸性条件下，利用次线性函数，分别提出了弱对偶性、强对偶性和严格逆对偶性定理，并给出了相应证明.该对偶化方法的推广为研究均衡约束数学规划问题的解提供了理论依据.

最大匹配的路变换图

刘岩, 雷梦霞, 黄晓娴

2019, 23(2):  104-112.  doi:10.15960/j.cnki.issn.1007-6093.2019.02.010

摘要 ( 589 )   PDF (860KB) ( 208 )  

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

图G的最大匹配的路变换图NM（G）是这样一个图，它以G的最大匹配为顶点，如果两个最大匹配M₁与M₂的对称差导出的图是一条路（长度没有限制），那么M₁和M₂在NM（G）中相邻.研究了这个变换图的连通性，分别得到了这个变换图是一个完全图或一棵树或一个圈的充要条件.

6-圈至多含一弦平面图的线性荫度

罗朝阳, 孙林

2019, 23(2):  113-119.  doi:10.15960/j.cnki.issn.1007-6093.2019.02.011

摘要 ( 604 )   PDF (599KB) ( 129 )  

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

线性森林是指每个连通分支都是路的图.图G的线性荫度la（G）等于将其边分解为k个边不交的线性森林的最小整数k.文中利用权转移方法证明了，若G是一个最大度大于等于7且每个6-圈至多含一条弦的平面图，则la（G）=「△（G）/2」.

极大限制边连通超图的两个充分条件

裴建峰, 林上为

2019, 23(2):  120-126.  doi:10.15960/j.cnki.issn.1007-6093.2019.02.012

摘要 ( 1991 )   PDF (622KB) ( 165 )  

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

图的限制边连通度是经典边连通度的推广，可用于精确度量网络的容错性.极大限制边连通图是使限制边连通度达到最优的一类图.首先将图的限制边连通度和最小边度的概念推广到r一致线性超图H，证明当H的最小度δ（H）≥r+1时，H的最小边度ξ（H）是它的限制边连通度，λ'（H）的一个上界，并将满足ξ（H）=λ'（H）的H称为极大限制边连通超图，然后证明n个顶点的r一致线性超图H如果满足δ（H）≥n-1/2（r-1）+（r-1），则它是极大限制边连通的，最后证明直径为2，围长至少为4的一致线性超图是极大限制边连通的.所得结论是图中相关结果的推广.