运筹学学报

王星，徐大川

2013, 17(2): 1-9.

摘要 ( 2057 )

PDF (633KB) ( 1332 )

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

考虑带次模惩罚和随机需求的设施选址问题，目的是开设设施集合的一个子集，把客户连接到开设的设施上并对没有连接的客户进行惩罚，使得开设费用、连接费用、库存费用、管理费用和惩罚费用之和达到最小. 根据该问题的特殊结构，给出原始对偶3-近似算法. 在算法的第一步，构造了一组对偶可行解；在第二步中构造了对应的一组原始整数可行解，这组原始整数可行解给出了最后开设的设施集合和被惩罚的客户集合. 最后，证明了算法在多项式时间内可以完成，并且算法所给的整数解不会超过最优解的3倍.

W₆*S_n的交叉数

周志东，王晶

2013, 17(2): 10-18.

摘要 ( 1667 )

PDF (912KB) ( 894 )

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

早在20世纪50年代，Zarankiewicz 猜想完全2-部图K_{m,n}(m\leq n)的交叉数为\lfloor\frac{m}{2}\rfloor\times \lfloor\frac{m-1}{2}\rfloor\times\lfloor\frac{n}{2}\rfloor\times\lfloor\frac{n-1}{2}\rfloor (对任意实数x，\lfloor x\rfloor表示不超过x的最大整数). 目前这一猜想的正确性只证明了当m\leq6时成立. 假定著名的Zarankiewicz的猜想对m=7的情形成立，确定了6-轮W_{6}与星S_{n}的笛卡尔积图的交叉是 cr(W_{6}\times S_{n})=9\lfloor\frac{n}{2}\rfloor\times\lfloor\frac{n-1}{2}\rfloor+2n+5\lfloor\frac{n}{2}\rfloor.

求解图着色问题的量子蚁群算法

何小锋，马良

2013, 17(2): 19-26.

摘要 ( 2041 )

PDF (611KB) ( 1080 )

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

针对经典的图着色问题，在蚁群算法的基础上结合量子计算提出一种求解图着色问题的量子蚁群算法. 将量子比特和量子逻辑门引入到蚁群算法中，较好地避免了蚁群算法搜索易陷入局部极小的缺陷，并显著加快了算法的运算速度. 通过图着色实例的大量仿真实验，表明算法对图着色问题的求解是可行的、有效的，且具有通用性.

实时系统中单处理器调度算法的优化设计研究

段渊

2013, 17(2): 27-34.

摘要 ( 1559 )

PDF (608KB) ( 693 )

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

研究实时系统的建模与调度问题是运筹与控制领域研究的热点问题, 对实时系统中的单处理器的调度算法进行了分析与研究, 特别是对其中的单调速率算法和最早时间限优先算法进行了深入的研究, 指出单调速率算法是一种典型的静态调度算法, 并且证明了单调速率算法是单处理器最优的静态优先级调度算法, 同时还指出最早时间限优先算法是一种典型的动态优先级调度算法,证明了最早时间限优先算法是单处理器的最优的动态优先级调度算法. 最后, 为了更好地进行实时系统的建模与调度, 引入了一种新的对任务执行行为进行抽象的方法--T-LET平面方法, 利用这种方法建立了单处理器流调度模型和BLREF调度算法, 并指出这种模型和算法都具有很强的几何背景.

无爪图上团横贯数的界

梁作松，单而芳，管梅

2013, 17(2): 35-40.

摘要 ( 1630 )

PDF (546KB) ( 731 )

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

设 G=(V,E) 为简单图，图 G 的每个至少有两个顶点的极大完全子图称为 G 的一个团. 一个顶点子集 S\subseteq V 称为图 G 的团横贯集, 如果 S 与 G 的所有团都相交，即对于 G 的任意的团 C 有 S\cap{V(C)}\neq\emptyset. 图 G 的团横贯数是图 G 的最小团横贯集所含顶点的数目，记为~${\large\tau}_{C}(G)$. 证明了棱柱图的补图(除5-圈外)、非奇圈的圆弧区间图和 Hex-连接图这三类无爪图的团横贯数不超过其阶数的一半.

一种求解延迟工件数最小的混合流水车间调度问题的模拟退火算法

帅天平，余金果，孙玲

2013, 17(2): 41-47.

摘要 ( 1506 )

PDF (532KB) ( 1336 )

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

针对延迟工件数最小的混合流水车间调度问题，给出了一种改进的模拟退火求解算法. 该算法首先给出一个启发式算法来获得初始解，然后用模拟退火算法对初始解改进. 通过交换工件在第一阶段的排序来获得一个新的解，采用最先空闲设备分配规则和先到先被加工规则，对工件在剩余各级的工序进行调度. 实验仿真表明算法是可行有效的.

多面体集下多目标优化问题近似解的若干性质

高英

2013, 17(2): 48-52.

摘要 ( 1594 )

PDF (493KB) ( 962 )

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

研究了多目标优化问题的近似解. 首先证明了多面体集是 co-radiant集，并证明了一些性质. 随后研究了多面体集下多目标优化问题近似解的特殊性质.

不完全市场定价与对冲方法

任凤英，李兴斯

2013, 17(2): 53-69. doi:O225

摘要 ( 2297 )

PDF (640KB) ( 1036 )

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

在经典的完全市场中, 根据无套利原理, 能够为期权提供唯一的价格同时可以完全对冲风险. 在这样的理论假设下, 没有理由管理不好相关衍生产品的风险. 但是在现实的金融市场中, 有关衍生产品风险管理失败的案例时有发生, 特别是最近的金融危机使人们认识到, 现实的金融市场是非常复杂而不完全的. 在这样的市场中, 风险不能完全对冲, 定价与对冲问题也变得不易处理, 至今还没有一致接受的理论. 为了促进更深入的研究, 综述了各种在不完全市场中的定价与对冲方法, 侧重于基本思想和基本模型. 同时也探讨了各种方法的优缺点, 以及它们之间的联系, 突出了优化理论和方法在解决这类问题中的关键作用, 同时也分析了一些需要进一步研究的问题及方法上的空白点.

非线性约束优化的光滑化平方根罚函数

孟志青，高嵩

2013, 17(2): 70-80.

摘要 ( 1613 )

PDF (477KB) ( 1485 )

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

介绍一种非线性约束优化的不可微平方根罚函数，为这种非光滑罚函数提出了一个新的光滑化函数和对应的罚优化问题，获得了原问题与光滑化罚优化问题目标之间的误差估计. 基于这种罚函数，提出了一个算法和收敛性证明，数值例子表明算法对解决非线性约束优化具有有效性.

补图为2-点或2-边连通的图的最小特征值

余桂东，范益政

2013, 17(2): 81-88.

摘要 ( 1912 )

PDF (439KB) ( 1161 )

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

图的最小特征值定义为图的邻接矩阵的最小特征值，是刻画图结构性质的一个重要代数参数. 在所有给定阶数的补图为2-点或2-边连通的图中, 刻画了最小特征值达到极小的唯一图, 并给出了这类图最小特征值的下界.

仿射变换内点Levenberg-Marquardt法解KKT系统

王云娟，朱德通

2013, 17(2): 89-106.

摘要 ( 1830 )

PDF (492KB) ( 1130 )

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

提供了一类新的结合非单调内点回代线搜索技术的仿射变换Levenberg-Marquardt法解Karush-Kuhn-Tucker（KKT）系统. 基于由KKT系统转化得到的等价的部分变量具有非负约束的最小化问题，建立了Levenberg-Marquardt方程. 证明了算法不仅具有整体收敛性，而且在合理的假设条件下，算法具有超线性收敛速率. 数值结果验证了算法的实际有效性.

向量均衡问题的超有效性的对偶形式

龚舒，龚循华

2013, 17(2): 107-123.

摘要 ( 1496 )

PDF (467KB) ( 964 )

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

在局部凸空间中引进了向量均衡问题的强超有效解、C-强超有效解、弱超有效解, C-弱超有效解、齐次超有效解、 C-齐次超有效解的概念，并在局部凸空间中用极理论为工具讨论了向量均衡问题的 C-弱超有效解， C-超有效解， C-齐次超有效解，以及C-强超有效解的对偶形式. 又在赋范线性空间中讨论了向量均衡问题的以上各种超有效解之间的等价性，并且在赋范线性空间具正规锥的条件下讨论了向量均衡问题的以上各种超有效解的对偶形式. 作为它的应用，给出了向量优化问题各种超有效解的对偶形式.

任意初始点下的广义梯度投影滤子算法

高晶，王薇

2013, 17(2): 124-130.

摘要 ( 1553 )

PDF (413KB) ( 1001 )

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

提出了一个任意初始点的广义梯度滤子方法. 该方法不使用罚函数以避免由此带来的缺陷并可以减少计算量. 方法的另一个特点是不因使用了滤子技术而使算法早熟或陷入循环. 算法对初始点没有要求并在比较合理的条件下具有全局收敛性.

当期目录