运筹学学报

陈宗青,孟吉翔,田应智

2013, 17(3): 1-10.

摘要 ( 2087 )

PDF (611KB) ( 926 )

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

连通图G的原子键连通性(ABC)指数定义为: ABC(G)=\sum\limits_{uv\in E(G)} \sqrt{\frac{d(u)+d(v)-2}{d(u)d(v)}} , 其中E(G)为图G的边集, d(u) 和d(v)为顶点u和v的度数. 原子键连通性指数是化学图论中比较重要的连通度指数, 最近的研究表明它可以用来研究烷烃的能量信息. 给出了线图和全图的ABC指数的上界和下界, 并且证明了这些界是可达的.

基于非单调技术的ODE型混合方法

刘媛媛, 欧宜贵

2013, 17(3): 11-22.

摘要 ( 1484 )

PDF (588KB) ( 857 )

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

基于非单调线搜索技术和IMPBOT算法，提出了一个求解无约束优化问题的ODE型混合方法.该方法的主要特点是：为了求得试验步，该方法在每次迭代时不必求解带信赖域界的子问题，仅需要求解一线性方程组系统；当试验步不被接受时，该方法就执行改进的Wolfe-型非单调线搜索来获得下一个新的迭代点，从而避免了反复求解线性方程组系统. 在一定条件下，所提算法还是整体收敛和超线性收敛的. 数值试验结果表明该方法是有效的.

油田A类物资采购决策支持系统研究

刘若阳, 崔晋川

2013, 17(3): 23-34.

摘要 ( 1758 )

PDF (774KB) ( 717 )

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

结合大庆油田物资公司在重要供应链管理环节，即采购、需求和库存中所面临的实际问题(物资需求增加、仓储压力增大、采购成本增多)及三者之间的相互作用，基于预测和优化理论，构建了针对油田A类物资的采购优化和库存管理决策支持系统原型，包括：预测模块、优化模块和方案调整评估模块，为相关部门制定合理物资采购方案提供决策支持.进一步，以银浪仓库中的4种A类物资为例，运用该原型系统进行数值模拟. 结果表明，2009年和2010年4种物资的总成本节省率分别为10.35%和8.07%，效益可观. 考虑到油田物资数据结构不完备及优化模型的复杂性，该原型系统在大庆油田大规模推广方面仍需进一步完善.

圈的中间图pebbling数和Graham猜想

叶永升, 刘芳, 翟明清

2013, 17(3): 35-44.

摘要 ( 1442 )

PDF (520KB) ( 765 )

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

图G的一个pebbling移动是从一个顶点移走2个pebble, 而把其中的1个pebble移到与其相邻的一个顶点上. 图G 的pebbling数f(G)是最小的正整数n, 使得不论n个pebble 如何放置在G的顶点上, 总可以通过一系列的pebbling移动, 把1个pebble移到图G的任意一个顶点上. 图G 的中间图M(G) 就是在G 的每一条边上插入一个新点, 再把G 上相邻边上的新点用一条边连接起来的图. 对于任意两个连通图G和H, Graham猜测f(G\times H)\leq f(G)f(H). 首先研究了圈的中间图的pebbling 数, 然后讨论了一些圈的中间图满足Graham猜想.

用最少的虚工序构建等效多阶段工序网络

苏志雄, 乞建勋, 阚芝南

2013, 17(3): 45-56.

摘要 ( 1276 )

PDF (760KB) ( 638 )

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

运用网络计划可以直观地表示项目管理中的诸多疑难问题, 便于分析和求解. 但是它也存在明显的缺点, 如, (1) 工序网络的有向无回路性表明很多时候适合运用动态规划法, 但它在通常情况下的无阶段性使得该方法无法直接应用; (2) 任意构建的工序网络容易表现得错综复杂, 不利于研究; (3) 用最少的虚工序表示双代号网络是NP-难问题, 因此对一个工序系统可能构建出多个差别迥异的工序网络, 有碍于进度计划管理研究, 等等. 如果能将工序网络构建成等效的多阶段网络, 各工序分别表示在相应的阶段中, 无疑有助于上述问题的解决. 构建等效多阶段工序网络需要添加虚工序. 通过添加最少的虚工序将工序网络构建成等效多阶段网络, 从而有助于建立更合理的工序网络表示法.

完全对换网络的限制连通度

王国亮, 师海忠

2013, 17(3): 57-64.

摘要 ( 1383 )

PDF (668KB) ( 687 )

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

完全对换网络是基于 Cayley 图模型的一类重要互连网络. 一个图 G 的 k-限制点(边)连通度是使得 G-F 不连通且每个分支至少有 k 个顶点的最小点(边)子集 F 的基数, 记作 \kappa_{k}(\lambda_{k}). 它是衡量网络可靠性的重要参数之一, 也是图的容错性的一种精化了的度量. 一般地, 网络的 k-限制点(边)连通度越大, 它的连通性就越好. 证明了完全对换网络 CT_{n} 的 2-限制点(边)连通度和 3-限制点(边)连通度, 具体来说: 当 n\geq4 时, \kappa_{2}(CT_{n})=n(n-1)-2, \kappa_{3}(CT_{n})=\frac{3n(n-1)}{2}-6; 当 n\geq3 时, \lambda_{2}(CT_{n})=n(n-1)-2, \lambda_{3}(CT_{n})=\frac{3n(n-1)}{2}-4.

一类变结构动态系统的非光滑最优性条件

李丽花, 高岩, 王隔霞

2013, 17(3): 65-72.

摘要 ( 1150 )

PDF (557KB) ( 624 )

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

研究了一类事件驱动的变结构动态系统的非光滑最优性条件. 通过引入一个新的时间变量, 将变结构动态系统的最优性问题转化为古典动态系统的最优性问题. 基于广义微分和古典动态系统的最优性理论, 得到了该系统的Frechet上微分形式的必要性条件, 推广了已有文献的相关结论. 结果表明, 在系统的连续运行过程中, 控制变量、协态变量和状态变量满足最小值原理和协态方程. 在系统的运行模型发生改变时, 协态变量产生一定的跳跃, 哈密尔顿函数连续. 最后通过一个算例说明了该结论的有效性.

均衡约束数学规划的约束规格和最优性条件综述

黎健玲, 谢琴, 简金宝

2013, 17(3): 73-85.

摘要 ( 2222 )

PDF (632KB) ( 932 )

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

约束规格在约束优化问题的最优性条件中起着重要的作用，介绍了近几年国际上关于均衡约束数学规划(简记为MPEC)的约束规格以及最优性条件的研究成果, 包括以下主要内容: (1) MPEC常用的约束规格(如线性无关约束规格 (MPEC-LICQ)、Mangasarian-Fromovitz约束规格 (MPEC-MFCQ)等)和新的约束规格(如恒秩约束规格、常数正线性相关约束规格等), 以及它们之间的关系; (2) MPEC常用的稳定点; (3) MPEC的最优性条件. 最后还对MPEC的约束规格和最优性条件的研究前景进行了探讨.

求解位姿估计问题的对偶方法

韩颖薇, 夏勇

2013, 17(3): 86-92.

摘要 ( 1634 )

PDF (643KB) ( 783 )

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

位姿估计是计算机图形学、机器视觉、摄影测量学等研究领域中的核心问题之一，利用给定的3D-2D参考点
来估计相机与对象间的旋转和平移. 针对该问题的四元数模型，人们最近开发应用半定规划松弛(SDR) 和平方和松弛(SOS)得到了很好的计算效果.
在原始模型的基础上，通过添加冗余约束，提出了Lagrangian对偶松弛方法(Dual). 这三种方法的核心是各自求解一个常数维度的半定规划问题，调用SeDuMi求解的系数矩阵规模分别为SDR: 117\times32, SOS: 266\times70和Dual: 81\times 12，大量的数值实验表明Lagrangian对偶松弛方法在进一步缩短了计算时间的同时计算效果也十分卓越.

带有Bernoulli控制策略的M/M/1多重休假排队模型

张宏波

2013, 17(3): 93-100.

摘要 ( 1645 )

PDF (591KB) ( 833 )

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

研究具有Bernoulli控制策略的M/M/1多重休假排队模型: 当系统为空时, 服务台依一定的概率或进入闲期, 或进入普通休假状态, 或进入工作休假状态. 对该模型, 应用拟生灭(QBD)过程和矩阵几何解的方法, 得到了过程平稳队长的具体形式, 在此基础上, 还得到了平稳队长和平稳逗留时间的随机分解结果以及附加队长分布和附加延迟的LST的具体形式. 结果表明, 经典的M/M/1排队, M/M/1多重休假排队, M/M/1多重工作休假排队都是该模型的特殊情形.

不确定性下强Berge均衡的存在性

邓喜才，向淑文，左羽

2013, 17(3): 101-107.

摘要 ( 1562 )

PDF (517KB) ( 619 )

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

在已知不确定参数变化的范围下，研究了非合作博弈与广义非合作博弈的强Berge均衡的存在性，基于强Berge均衡与不确定性下非合作博弈的强Nash均衡的概念，给出了不确定参数下非合作博弈与广义非合作博弈的强Berge均衡的定义，并利用Fan-Glicksberg不动点定理证明其存在性，最后用算例验证其可行性.

关于积图点可区别边染色的若干结论

马刚, 马效敏, 冶建华, 马少仙

2013, 17(3): 108-114.

摘要 ( 1414 )

PDF (548KB) ( 1147 )

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

如果图G的一个正常边染色满足任意两个不同点的关联边色集不同, 则称为点可区别边染色(VDEC), 其所用最少颜色数称为点可区别边色数. 利用构造法给出了积图点可区别边染色的一个结论, 得到了关于积图点可区别边色数的若干结果, 并且给出25个具体积图的点可区别边色数, 验证了它们满足点可区别边染色猜想(VDECC).

可中断的多任务平行机排序问题

仲维亚，马文慧，霍志明

2013, 17(3): 115-123.

摘要 ( 1415 )

PDF (539KB) ( 700 )

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

Leung等(Preemptive multiprocessor order scheduling to minimize total weighted flowtime [J]. European Journal of Operational Research, 2008, 190: 40-51)研究了如下问题: 有 n 个订单, 其中每个订单 i 含有 n_i 个不同的工件. 所有的订单在零时刻已经到达, 并且工件的加工是可中断的. 每个订单 i有一个权重 \omega_i, 定义订单 i 的完工时间 C_i 为订单 i 最后一个完工工件的完工时间. 目标是找到一个可行排序使得加权总完工时间\sum\limits_{i=1}^n \omega_iC_i 最小. Leung等证明了这个问题是NP-难的, 给出了一个近似算法, 并且分析了该算法的最坏情况界. 但是定理2的证明存在一些错误. 证明了尽管定理2的证明过程存在错误, 但是其结论仍然正确. 另外, 对上述模型的一种特殊情形给出了更好的近似算法.

关于局部凸空间中向量Ekeland变分原理的等价性

万轩, 赵克全

2013, 17(3): 124-128.

摘要 ( 1144 )

PDF (488KB) ( 625 )

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

基于各种Ekeland变分原理的等价形式, 主要研究局部凸空间中给定有界凸子集乘以距离函数为扰动的单调半连续映射的向量Ekeand变分原理的等价性问题. 首先利用局部凸空间中的向量Ekeland变分原理证明了向量Caristi-Kirk不动点定理，向量 Takahashi非凸极小化定理和向量Oettli-Th\'{e}ra定理. 进一步研究了向量Ekeland变分原理与向量Caristi-Kirk不动点定理，向量Takahashi非凸极小化定理和向量Oettli-Th\'{e}ra定理的等价性.

当期目录