Please wait a minute...

当期目录

    2017年 第21卷 第3期    刊出日期:2017-09-15
    运筹学
    半监督度量学习内蕴最速下降算法的收敛性分析
    李鑫, 白延琴
    2017, 21(3):  1-13.  doi:10.15960/j.cnki.issn.1007-6093.2017.03.001
    摘要 ( 1252 )   PDF (1389KB) ( 503 )  
    相关文章 | 多维度评价

    主要研究对称正定矩阵群上的内蕴最速下降算法的收敛性问题. 首先针对一个可转化为对称正定矩阵群上无约束优化问题的半监督度量学习模型, 提出对称正定矩阵群上一种自适应变步长的内蕴最速下降算法. 然后利用李群上的光滑函数在任意一点处带积分余项的泰勒展开式, 证明所提算法在对称正定矩阵群上是线性收敛的. 最后通过在分类问题中的数值实验说明算法的有效性.

    具有可变配送费用和固定配送时刻的单机排序问题
    王磊, 张玉忠, 邢伟, 任建峰
    2017, 21(3):  14-22.  doi:10.15960/j.cnki.issn.1007-6093.2017.03.002
    摘要 ( 1315 )   PDF (530KB) ( 358 )  
    相关文章 | 多维度评价

    研究了单机环境下生产与配送的协同排序问题. 有多个工件需要在一台机器上进行加工, 加工完的工件需要分批配送到一个客户. 每批工件只能在固定的几个配送时刻出发, 不同的配送时刻对应着不同的配送费用. 我们的目标是找到生产与配送的协同排序, 极小化排序的时间费用与配送费用的加权和. 研究了排序理论中主要的四个目标函数, 构建了单机情况下的具体模型, 分析了问题的复杂性, 对于配送费用单调非增的情况给出了它们的最优算法.

    六阶图C_6+3K_2与P_n, C_n的联图交叉数
    苏振华
    2017, 21(3):  23-34. 
    摘要 ( 849 )   PDF (656KB) ( 311 )  
    相关文章 | 多维度评价

    用P_n表示n个点的路, C_n表示长为n的圈, C_6+3K_2表示 圈C_6添加三条相邻的边3K_2=C_3得到的图. 在Kleitman给出的完全二部图的交叉数cr(K_{6,n})=Z(6,n)的基础上, 得到了特殊六阶图C_6+3K_2与路P_{n}, 圈C_{n}的联图交叉数分别为 Z(6,n)+3\lfloor \frac{n}{2} \rfloor+2 与 Z(6,n)+3\lfloor \frac{n}{2} \rfloor+4.

    基于正弦型光滑打磨函数对0-1规划问题的连续化求解方法
    隋允康, 李臻臻, 李宏, 陈国庆
    2017, 21(3):  35-44.  doi:10.15960/j.cnki.issn.1007-6093.2017.03.004
    摘要 ( 1417 )   PDF (902KB) ( 225 )  
    相关文章 | 多维度评价

    传统的求解0-1规划问题方法大多属于直接离散的解法. 现提出一个包含严格转换和近似逼近三个步骤的连续化解法: (1) 借助阶跃函数把0-1离散变量转化为[0,1]区间上的连续变量; (2) 对目标函数采用逼近折中阶跃函数近光滑打磨函数, 约束条件采用线性打磨函数逼近折中阶跃函数, 把0-1规划问题由离散问题转化为连续优化模型; (3) 利用高阶光滑的解法求解优化模型. 该方法打破了特定求解方法仅适用于特定类型0-1规划问题惯例, 使求解0-1规划问题的方法更加一般化. 在具体求解时, 采用正弦型光滑打磨函数来逼近折中阶跃函数, 计算效果很好.

    一类新的二阶组合切导数及其应用
    周丽霞, 徐义红, 吕强
    2017, 21(3):  45-54.  doi:10.15960/j.cnki.issn.1007-6093.2017.03.005
    摘要 ( 1137 )   PDF (496KB) ( 222 )  
    相关文章 | 多维度评价

    引进了一种新的切锥, 讨论它与相依切锥的关系. 借助这种新的切锥引进了一类新的二阶组合切导数, 并讨论了它与其他二阶切导数的关系. 利用这类新的二阶组合切导数, 建立了集值优化分别取得Henig有效元和全局有效元的最优性必要条件.

    串联双路图的亏格分布
    张湘林, 黄元秋, 郭婷
    2017, 21(3):  55-64.  doi:10.15960/j.cnki.issn.1007-6093.2017.03.006
    摘要 ( 1110 )   PDF (1111KB) ( 243 )  
    相关文章 | 多维度评价

    计算双路图的亏格分布是拓扑图论关注的一个问题, 利用传递矩阵与向量积矩阵, 给出了两类由双路图串联构建而成的两类闭链图的亏格分布.

    带负顾客和N-策略的Geo^{lambda_1, lambda_2/Geo/1(MWV)排队系统分析及最优控制策略N*
    潘取玉, 唐应辉, 兰绍军
    2017, 21(3):  65-76.  doi:10.15960/j.cnki.issn.1007-6093.2017.03.007
    摘要 ( 1140 )   PDF (1191KB) ( 276 )  
    相关文章 | 多维度评价

    分析了一个带有负顾客、N-策略控制的Geo/Geo/1多重工作休假排队系统, 其中正顾客在工作休假及正规忙期以不同的到达率进入系统. 利用拟生灭过程和矩阵几何解方法, 给出了该模型的稳态队长分布及平均队长, 以及系统分别处于假期和忙期的概率. 同时, 对该系统的忙期进行了分析, 并讨论了稳态队长分布在系统容量的优化设计中的应用. 最后, 在给定的费用结构下, 用数值计算例子确定了使系统长期单位时间内期望费用最小的最优控制策 N*.

    可行策略对应的图像拓扑下广义博弈Nash平衡的稳定性
    陈拼博, 王能发, 丘小玲, 王春
    2017, 21(3):  77-85.  doi:10.15960/j.cnki.issn.1007-6093.2017.03.008
    摘要 ( 1096 )   PDF (570KB) ( 249 )  
    相关文章 | 多维度评价

    以往关于广义博弈Nash平衡的稳定性的研究, 均利用可行策略映射之间的一致度量. 现考虑在更弱的度量下, 利用可行策略映射图像之间的Hausdorff距离定义度量.
    在此弱图像拓扑下, 证明了广义博弈空间的完备性, 以及Nash平衡映射的上半连续性和紧性, 进而得到广义博弈Nash平衡的通有稳定性. 即在Baire分类的意义下,
    大多数的广义博弈都是本质的.

    求解弱线性双层规划问题的一种全局优化方法
    郑跃, 庄道元, 万仲平
    2017, 21(3):  86-94.  doi:10.15960/j.cnki.issn.1007-6093.2017.03.009
    摘要 ( 1352 )   PDF (525KB) ( 323 )  
    相关文章 | 多维度评价

    双层规划在经济、交通、生态、工程等领域有着广泛而重要的应用. 目前对双层规划的研究主要是基于强双层规划和弱双层规划. 然而, 针对弱双层规划的求解方法却鲜有研究. 研究求解弱线性双层规划问题的一种全局优化方法, 首先给出弱线性双层规划问题与其松弛问题在最优解上的关系, 然后利用线性规划的对偶理论和罚函数方法, 讨论该松弛问题和它的罚问题之间的关系. 进一步设计了一种求解弱线性双层规划问题的全局优化方法, 该方法的优势在于它仅仅需要求解若干个线性规划问题就可以获得原问题的全局最优解. 最后, 用一个简单算例说明了所提出的方法是可行的.

    求解对称张量绝对值方程问题的非光滑牛顿法
    梁娜, 杜守强
    2017, 21(3):  95-102.  doi:10.15960/j.cnki.issn.1007-6093.2017.03.010
    摘要 ( 1191 )   PDF (541KB) ( 288 )  
    相关文章 | 多维度评价

    提出一类对称张量绝对值方程问题, 给出了求解此类问题的一类非光滑牛顿法, 并且在一般的假设条件下, 给出了算法的局部收敛性. 最后给出相关的数值实验表明了算法的有效性.

    图的广义Randi\'{c} Estrada 指标的界
    高楠, 李美丽, 折延宏
    2017, 21(3):  103-110.  doi:10.15960/j.cnki.issn.1007-6093.2017.03.011
    摘要 ( 1079 )   PDF (494KB) ( 266 )  
    相关文章 | 多维度评价

    受图的Randi\'{c} Estrada 指标和广义 Randi\'{c} 能量的启发,  定义了图的广义 Randi\'{c} Estrada 指标. 利用代数方法和初等分析方法给出了n 阶简 单连通图和 r-正则图的广义Randi\'{c} Estrada指标的上下界, 推广了Bozkurt等人有关Randi\'{c} Estrada指标的结论.

    一个新的非线性整数规划问题的单参数填充函数算法
    吴佩佩, 高岳林
    2017, 21(3):  111-118.  doi:10.15960/j.cnki.issn.1007-6093.2017.03.012
    摘要 ( 1173 )   PDF (518KB) ( 272 )  
    相关文章 | 多维度评价

    非线性整数规划问题是一类复杂的优化问题,填充函数算法是求解整数规划问题的一类有效方法. 构造一个新的单参数填充函数,分析并证明了其填充性质; 然后,基于该填充函数并结合离散 最速下降法提出了一种新的填充函数算法; 最后,采用新算法对6个测试函数进行数值实验,结果表明该算法具有良好的计算效果,是有效可行的.

    图的半强积的邻点可区别染色
    田双亮, 董新芳, 刘睿琳
    2017, 21(3):  119-125.  doi:10.15960/j.cnki.issn.1007-6093.2017.03.013
    摘要 ( 1145 )   PDF (554KB) ( 253 )  
    相关文章 | 多维度评价

    两个简单图G与H的半强积G\bullet H是具有顶点集V(G)\times V(H)的简单图, 其中两个顶点(u,v)与(u',v')相邻当且仅当u=u'且vv'\in E(H), 或 uu'\in E(G)且 vv'\in E(H). 图的邻点可区别边(全)染色是指相邻点具有不同色集的正常边(全)染色. 统称图的邻点可区别边染色与邻点可区别全染色为图的 邻点可区别染色. 图G的邻点可区别染色所需的最少的颜色数称为邻点可区别染色数, 并记为\chi^{(\tau)}_{a}(G), 其中\tau=1,2, 且\chi^{(1)}_{a}(G)与\chi^{(2)}_{a}(G)分别表示G的 邻点可区别的边色数与全色数. 给出了两个简单图的半强积的邻点可区别染色数的一个上界, 并证明了该上界是可达的. 然后, 讨论了两个树的不同半强积具有相同邻点可区别染色数的充分必要条件. 另外, 确定了一类图与完全图的半强积的邻点可区别染色数的精确值.